# Puzzle - People in a line.

$n$ people labeled from $1$ to $n$ stand in line in increasing order. Starting from the first person, each of them flip a (possibly biased) coin.

If getting a head, the person goes to the end of the line, otherwise, he stays unchanged at his position. For the $i^{th}$ person, his possibility of getting a head is $\frac{i}{n}$. For example, the possibility of getting a head for the last person is $\frac{n}{n}$.

After everyone of them has flipped a coin, what is the probability that the $i^{th}$ person stands at the $i^{th}$ position?

Here's my model:

If the $i^{th}$ person get a tail (he stays unchanged), it must be the case that $1^{st}$ to $(i-1)^{th}$ persons also get a tail. If the $i^{th}$ person get a head (he goes to end of line), then if $k$ people in $1$ ~ $(i-1)$ also get a head, it must be the case that exactly $k$ people in $(i+1)$ ~ $n$ get a head. Yet, the probability of $\frac{i}{n}$ makes it pretty hard to carry out this model.

Any good ideas?

• If he gets a head, the $i-1$ people originally in front of him will still be in front of him. Even the ones ahead of him who flipped head will end up ahead of him, because they will go to the back of the line before, and then he will go to the back when he flips head, sending him further behind. So it's [(he flips tails AND everyone ahead flips tails) OR (he flips heads AND everyone after flips HEADS)]. – Amit Kumar Gupta Mar 14 '15 at 9:57
• I think your argument is based on a special case of this problem. Let's say there are 5 persons and we're observing the $4^{th}$ person. These operations: HTTHH will turn the $4^{th}$ person back to the $4^{th}$ position. Observe that there is one H in 1~3 and one H in 5~5, which correspond to my second case. – Yun-Chih Chen Mar 14 '15 at 10:21
• @AmitKumarGupta: Turn your comment into an answer! – Christian Blatter Mar 14 '15 at 10:59

If he flips heads, the $i−1$ people originally in front of him will still be in front of him. Even the ones ahead of him who flipped heads will end up ahead of him, because they will go to the back of the line before, and then he will go to the back when he flips heads, sending him further behind. So you just need to compute the probability that [(he flips tails AND everyone ahead flips tails) OR (he flips heads AND everyone after flips heads)].