2
$\begingroup$

Let's define a "card deck" as a sequence of the first $x$ natural numbers, and a "swap" as the creation of a new sequence where the $i$th and $j$th member of the original sequence are exchanged e.g. swapping cards $2$ and $3$ so that $[1, 2, 3, 4 ] \longmapsto [1, 3, 2, 4]$.

My question is, how many swaps (where i and j are randomly chosen) must be made before a sequence is created that can be pronounced random? Is there a faster way to achieve randomness if i and j and not chosen randomly?

EDIT: I suppose I don't care how random it is, though let's say the sequence is a real deck of cards; the randomness should be close to what you would get with $7$ good riffles (see Shuffling). Even better would be a way to control the degree of randomness, i.e. estimate $z$, where your odds of predicting the location of a particular card in the deck are $\frac1x + z$.

Note: It seems that picking i and j randomly is not the best way to achieve randomness. See Fisher-Yates shuffle.

  • 4
    How exactly do we determine if an ordering is "random"?2012-04-03
  • 0
    @DavidMitra Good point.2012-04-03
  • 1
    The question can be interpreted as the question of how quickly a random walk on a certain Cayley graph of the symmetric group $S_{52}$ mixes. The answer to this question is known but I'm not familiar with it; I think Persi Diaconis has done work in this area.2012-04-03
  • 0
    a natural definition seems to be, fix $\epsilon>0$, and among all the $n!$ possible permutations, the probability of getting that permutation is within $\epsilon$ of $1/(n!)$. I don't know of that's a standard definition.2012-04-03
  • 1
    The standard definition of randomness is to compare the total variation between the uniform distribution and the distribution of cards after $n$ shuffles.2012-04-03
  • 0
    Note you should allow "no change" as a valid swap, or vary the number of rounds; otherwise the permutation will always be even or odd depending on parity of the number of swaps.2012-04-03

1 Answers 1

6

In a truly random shuffle, the probability that, say, the top card remains where it started is $1/x$. So you want to do enough swaps to make the probability of the top card moving be about $(x-1)/x$. I don't think you need to do more than that; since the swaps are random, if the top card moves, it moves somewhere random, and there's nothing special about the top card, so every card should wind up somewhere random.

So: on each swap, the probability that you don't move (say) the top card is $(x-2)/x$. After $r$ independently chosen swaps, this probability is $((x-2)/x)^r$. So we want $r$ such that $$((x-2)/x)^r=1/x$$ (roughly). If $x$ is large then $((x-2)/x)^x$ is close to $e^{-2}$ and we get an approximate solution $r=(1/2)x\log x$ for the number of swaps needed to randomize the deck.

  • 1
    This answer doesn't seem to explicitly account for the case where the top card is swapped away and swapped back again. Is there something I'm missing?2012-04-03
  • 0
    That can happen, but it's pretty unlikely. My whole answer is an approximation, and I expect the situation you bring up is swamped by the error terms.2012-04-03
  • 0
    @GerryMyerson Thanks, this is a really cool way of looking at the problem. I also appreciate that the answer is readable in layman's terms ;-)2012-04-03
  • 0
    @PeterTaylor If the deck were randomly mixed up and, amazingly, still remained in order, that's okay--that falls within the definition of random for this problem.2012-04-03