Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (10 results)

  • Article
  • Peer Reviewed
Faculty (2005)
The Thorp shuffle is defined as follows. Cut the deck into two equal piles. Drop the first card from the left pile or the right pile according to the outcome of a fair coin flip; then drop from the other pile. Continue this way until both piles are empty. We show that the mixing time for the Thorp shuffle with $2^d$ cards is polynomial in $d$.
    • Article
    • Peer Reviewed
    Faculty (2009)
    E. Thorp introduced the following card shuffling model. Suppose the number of cards $n$ is even. Cut the deck into two equal piles. Drop the first card from the left pile or from the right pile according to the outcome of a fair coin flip. Then drop from the other pile. Continue this way until both piles are empty. We show that if $n$ is a power of 2 then the mixing time of the Thorp shuffle is $O(\log^3 n)$. Previously, the best known bound was $O(\log^4 n)$.
      • Article
      • Peer Reviewed
      Faculty (2008)
      We show that the spectral gap for the interchange process (and the symmetric exclusion process) in a $d$-dimensional box of side length $L$ is asymptotic to $\pi^2/L^2$. This gives more evidence in favor of Aldous's conjecture that in any graph the spectral gap for the interchange process is the same as the spectral gap for a corresponding continuous-time random walk. Our proof uses a technique that is similar to that used by Handjani and Jungreis, who proved that Aldous's conjecture holds when the graph is a tree.
        • Article
        • Peer Reviewed
        Faculty (2008)
        We prove a theorem that reduces bounding the mixing time of a card shuffle to verifying a condition that involves only pairs of cards, then we use it to obtain improved bounds for two previously studied models. E. Thorp introduced the following card shuffling model in 1973. Suppose the number of cards n is even. Cut the deck into two equal piles. Drop the first card from the left pile or from the right pile according to the outcome of a fair coin flip. Then drop from the other pile. Continue this way until both piles are empty. We obtain a mixing time bound of O(log^4 n). Previously, the best known bound was O(log^{29} n) and previous proofs were only valid for n a power of 2. We also analyze the following model, called the L-reversal chain, introduced by Durrett. There are n cards arrayed in a circle. Each step, an interval of cards of length at most L is chosen uniformly at random and its order is reversed. Durrett has conjectured that the mixing time is O(max(n, n^3/L^3) log n). We obtain a bound that is within a factor O(log^2 n) of this,the first bound within a poly log factor of the conjecture.
          • Article
          • Peer Reviewed
          Faculty (2014)
          We prove an upper bound of $1.5324 n \log n$ for the mixing time of the random-to-random insertion shuffle, improving on the best known upper bound of $2 n \log n$. Our proof is based on the analysis of a non-Markovian coupling.
            • Article
            • Peer Reviewed
            Faculty (2013)
            We show that there are universal positive constants c and C such that the mixing time T_{mix} for the fifteen puzzle in an n by n torus satisfies cn^4 log n < T_{mix} < Cn^4 log^2 n.
              • Article
              • Peer Reviewed
              Proceedings of the Annual Meeting of the Cognitive Science Society, Volume 46 (2024)
              While people may be reluctant to explicitly state social stereotypes, their underlying beliefs may nonetheless leak out in subtler conversational cues, such as surprisal reactions that convey information about expectations. Across 3 experiments with adults and children (ages 4-9), we compare permissive responses ("Sure, you can have that one") that vary the presence of surprisal cues (interjections "oh!" and disfluencies "um"). In Experiment 1 (n = 120), children by 6-to-7 use surprisal reactions to infer that a boy more likely made a counter-stereotypical choice. In Experiment 2, we demonstrate that these cues are sufficient for children (n = 120) and adults (n = 80) to learn a novel expectation about a group of aliens. In Experiment 3, adults (n = 150) use the distribution of surprisal information to infer whether a novel behavior is gender-stereotyped. Across these experiments, we see emerging evidence that conversational feedback may provide a crucial and unappreciated avenue for the transmission of social beliefs.
                Cover page: "Oh! Um. . . Sure": Children and adults use other's linguistic surprisal to reason about expectations and learn stereotypesCreative Commons 'BY' version 4.0 license
                • Article
                Proceedings of the Annual Meeting of the Cognitive Science Society, Volume 40 (2018)
                While children must learn language from the statistical structure of the input they receive, parents play a critical role shap-ing the structure of this input. Even without an explicit pedagogical goal, parents’ desire to communicate successfully maycause them to produce language calibrated to their child’s linguistic development. We designed a Mechanical Turk studyto experimentally validate this idea, putting Turkers in the role of parents talking with children less familiar with a novellanguage. Participants could communicate in 3 ways: pointingexpensive but unambiguous, labelingcheap but knowledge-dependent, or both. They won points only for communicating successfully. Participants adapted their communicativebehavior to their own knowledge and their partners knowledge. Teaching emerged when the speaker had more linguisticknowledge than their partner. We implemented a rational planning model that fits these data and demonstrates that suchpatterns could result from maximizing expected utilities, accounting for the expected utilities of future interactions.
                  Cover page: Communicative pressure can lead to input that supports language learning
                  • Thesis
                  • Peer Reviewed
                  UC Davis Electronic Theses and Dissertations (2022)

                  We prove a theorem that reduces bounding the mixing time of a card shuffle to verifying acondition that involves only triplets of cards, based on earlier work by Morris involving pairs of cards. Then we use it to obtain a bound on the mixing time of the lazy version of a shuffle introduced by Diaconis. The Diaconis shuffle is a variation on the 15-puzzle. There are n2 tiles arranged in an n × n torus. Each step, a random tile and direction (North, South, East, West) are selected, and the chosen tile’s row or column is cycled in the chosen direction. Diaconis conjectured that the mixing time is O(n3 log n). We prove a mixing time bound of O(n3 log3 n).

                    • Thesis
                    • Peer Reviewed
                    UC Davis Electronic Theses and Dissertations (2023)

                    This dissertation analyzes two algorithms for shuffling cards: the swap-or-not shuffle and the overlapping cycles shuffle.

                    The swap-or-not shuffle was developed by Hoang, Morris, and Rogaway as a building block for quick data encryption algorithms with concrete security bounds. In Chapter 1 we introduce concepts from cryptography using the language of probability. We also reproduce an important theorem from cryptography first shown by Maurer, Pietrzak, and Renner which says that a random permutation with a total variation mixing time of t steps can be used to create an encryption algorithm with strong security against chosen ciphertext attacks after 2t rounds. We also prove a new theorem that says that a random permutation with a separation mixing time of t steps will create an algorithm with strong chosen ciphertext attack security after only t rounds.

                    In Chapter 2 we show that for the swap-or-not shuffle on n cards, the separation mixing time of square root of n of the cards is about log base 2 of n. We combine this with our theorem from Chapter 1 to tighten the best known bound on the CCA security of the n card swap-or-not shuffle in the special case of fewer than square root of n queries.

                    In Chapter 3 we consider the overlapping cycles shuffle. In each step of the overlapping cycles shuffle on n cards, a fair coin is flipped which determines whether the mth card or the nth card is moved to the top of the deck. Angel, Peres, and Wilson showed the following interesting fact: If m = cn where c is rational, then the relaxation time of a single card in the overlapping cycles shuffle is O(n^2). However if c is the inverse golden ratio, then the relaxation time is O(n^(3/2)). We show that the mixing time of the entire deck under the overlapping cycles shuffle matches these relaxation times for a single card up to a factor of log(n)^3.

                      Cover page: Mixing Times of the Swap-or-Not and Overlapping Cycles Shuffles
                      Top