7

You have a deck of numbered cards from $1$ to $n$. After shuffling the cards randomly, you put them in numbered boxes, from $1$ to $n$, i.e. $1$ card per box. So box $1$ can contain any one card from $1$ to $n$, etc.

You now go to box $1$ and look at the card inside. If the card is, for example, a $4$, you go to box number $4$ and look at the card inside. That card tells you where to go next. You continue, until you reach card $1$ (which would tell you to go to box $1$, which is empty). The number of cards (or steps) is the number of a cycle you just discovered. You then go to the first box with a card inside, and repeat the process. You end up with $1$ to $n$ cycles of $1$ to $n$ cards.

For example, you could have one very big cycle with all the cards, or one big cycle with half of the cards and lots of smaller cycles. If you look into box number $7$ and you find the card with a $7$, that is a $1$-cycle.

What is the probability that no cycle is longer than ${n \over 2}$?

Thank you!

Ludolila
  • 3,034
Demian Schkolnik
  • 71

1 Answers1

4

If $n=2m$, there are $$\binom{2m}{m+1}m!(m-1)!=\frac{(2m)!}{m+1} $$ permutations with a cycle of length $m+1$, $$\binom{2m}{m+2}(m+1)!(m-2)!=\frac{(2m)!}{m+2} $$ permutations with a cycle of length $m+2$ and so on, so the probability is: $$ 1-\sum_{k=m+1}^{2m}\frac{1}{k} = 1-(H_{2m}-H_m).$$ When $n=2m+1$ the probability is: $$ 1-\sum_{k=m+1}^{2m+1}\frac{1}{k}=1-(H_{2m+1}-H_m).$$ In both cases we have that the probability is: $$ (1-\log 2)+\frac{1}{2n}+O\left(\frac{1}{n^2}\right)\geq\color{red}{30,68\%}. $$

Jack D'Aurizio
  • 353,855