I stumbled upon a simple card game that I found interesting from a probability point of view.
The rules are as follows:
There is only one player who has n cards facing down in a deck in random order (1,2,3,…, n; we can consider the ace as 1). Cards are drawn from the top until the number on the card matches its order. The drawn cards are then put at the bottom of the deck and the game continues until there are no cards to draw anymore.
An example:
There are 5 cards initially in this order: [5, 3, 1, 2, 4]
The first card is drawn: 4, but it's not equal to 1 so the next card is drawn which is 2 and it is a match so the deck is now: [2,4,5,3,1]
1 is then drawn as the first card so it will be put at the back and the deck will be: [1,2,4,5,3]
Then cards are drawn as follows:
1st: 3
2nd: 5
3rd: 4
4th: 2
5th: 1
None of them match so the game ends.
Initially, I wanted to calculate the probability of a game to finish in just n moves. I thought it is equal to $(n-1/n)^n$ which is $(4/5)^5=0.327$ when $n=5$. But after running some simulations in Python I found that it is closer to $0.36$. Where is this difference coming from?
I also thought about calculating the average length of a hand( where a hand is defined as the cards drawn before a match ), but I just don't know where to start. Can anyone point me in the right direction?
Best Answer
Your first problem is the probability of having a permutation of $\{1,\dots,n\}$ without a fixed point https://en.wikipedia.org/wiki/Derangement. The limit of the probability goes to $\frac{1}{e}\approx0.37.$
For the second problem think of the permutation $\phi$ such that $\phi(k)=k, \, \, \forall k\leq n-2$ and $\phi(n-1)=n,\phi(n)=n-1$. The corresponding sequence is $[n-1,n,n-2,n-3\dots,2, 1]$. After one step you will have the sequence $[1,n-1,n,n-2,\dots, 2],$ that is you will have a permutation $\psi$ such that $\psi(k)=k+1, \, \, \, \forall k\leq n-3$ and $\psi(n-2)=n,\psi(n-1)=n-1,$ $\psi(n)=1.$ The only fixed of this permutation is $n-1$ thus the game will get to step $n-1$ and then return the sequence $[n-1,n,n-2,\dots,2,1].$ Therefore, the sequence is the same as the initial one and the game will go infinitely often. So for each $n\geq 3$ the game can will run infintely often with probability at least $\frac{1}{n!}$.