On top to random shuffles, no feedback card guessing, and fixed points of permutations
by Pehlivan, Lerna, Ph.D., UNIVERSITY OF SOUTHERN CALIFORNIA, 2009, 141 pages; 3389534

Abstract:

We study two problems related to top to random shuffling. First, we show that for an O(n ln( n)) top to random shuffled deck, there exists a best no feedback card guessing strategy, i.e., a strategy maximizing the expected number of correct guesses without revealing information to the guesser. Moreover, using the best no feedback guessing strategy, the difference between the expected number of correct guesses for a deck that is O(n ln(n)) top to random shuffled and a deck that is uniformly distributed can be made arbitrarily small.

Second, we study the expected value and the variance of the number of fixed points of a permutation that is obtained after an arbitrary number of top to random shuffles and provide closed formulas for both. Two different methods of proofs are provided, one combinatorial and another one using the distribution of the eigenvalues among the irreducible representations of Sn. Since the number of fixed points is a feature of a permutation, it is natural to expect that with O( n ln(n)) shuffles it will converge to Poisson(1). However, we show that O(cn) top to random shuffles (contrary to riffle shuffles) are not enough to achieve convergence to a Poisson(1).

 
AdviserJason Fulman
SchoolUNIVERSITY OF SOUTHERN CALIFORNIA
SourceDAI/B 71-01, p. , Feb 2010
Source TypeDissertation
SubjectsMathematics
Publication Number3389534
Adobe PDF Access the complete dissertation:
 

» Find an electronic copy at your library.
  Use the link below to access a full citation record of this graduate work:
  http://gateway.proquest.com/openurl%3furl_ver=Z39.88-2004%26res_dat=xri:pqdiss%26rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation%26rft_dat=xri:pqdiss:3389534
  If your library subscribes to the ProQuest Dissertations & Theses (PQDT) database, you may be entitled to a free electronic version of this graduate work. If not, you will have the option to purchase one, and access a 24 page preview for free (if available).

About ProQuest Dissertations & Theses
With over 2.3 million records, the ProQuest Dissertations & Theses (PQDT) database is the most comprehensive collection of dissertations and theses in the world. It is the database of record for graduate research.

The database includes citations of graduate works ranging from the first U.S. dissertation, accepted in 1861, to those accepted as recently as last semester. Of the 2.3 million graduate works included in the database, ProQuest offers more than 1.9 million in full text formats. Of those, over 860,000 are available in PDF format. More than 60,000 dissertations and theses are added to the database each year.

If you have questions, please feel free to visit the ProQuest Web site - http://www.proquest.com - or call ProQuest Hotline Customer Support at 1-800-521-3042.