3
$\begingroup$

Consider the following game played by $N>1$ players in a circle: player $1$ starts the game. He then passes the turn to either of his neighbors (player $N$ and player $2$), with equal probability. The game continues like this until each player has had a turn. The last player to get a turn wins the game.

Clearly player $1$ can never win the game, but the others can. We wish to determine the probability that player $k$ wins the game.

I have simulated some games of this type using a C++ program. The results suggest that the winning probabilities (except for player $1$'s) are uniform. For $N = 7$ I simulated 500 million games. The relative winning probabilities I found are displayed in the following figure:

enter image description here

Although I didn't bother to calculate error bars, this suggests uniform probabilities.

Can we prove that the probabilities are (or are not) uniform?

$\endgroup$
  • 1
    $\begingroup$ Your distribution seems to suggest that C++'s random function is skewed towards going left. $\endgroup$ – Irvan Nov 5 '14 at 15:46
  • 1
    $\begingroup$ I used a better random function (Mersenne prime twister) than the standard rand(), which gave abysmal results. $\endgroup$ – user111187 Nov 5 '14 at 15:49
  • 1
    $\begingroup$ Btw the exact probabilities can be calculated using Dynamic Programming (but it's cyclic, so kind of painful to implement). $\endgroup$ – Irvan Nov 5 '14 at 15:52
  • $\begingroup$ You seem to be assuming players choose a direction at random. $\endgroup$ – Henry Nov 5 '14 at 16:04
  • 1
    $\begingroup$ To reinforce Irvan's point: the probabilities are clearly symmetric about whoever goes first (to each path that ends the game in one direction, there's exactly one 'mirror path' that ends the game the other direction) so that player 2's win probability must be equal to player 7's win probability. $\endgroup$ – Steven Stadnicki Nov 7 '14 at 2:33
3
$\begingroup$

Let imagine the players numbered $\cdots,-2,-1,0,1,2\cdots$, and let the "time" $t=1,2\cdots$ be incremented each time a new player has been tagged. Let $x_t$ be the player tagged at time $t$.

Then, $x_1=0$. And $x_2=\pm 1$ with equal probability. Further, $$Q_{t,k}=p(x_t=k)=\frac{k}{t(t-1)} \hspace{1cm}(0\le k<t, \,t>1) \tag{1}$$

Then, the probability that, having $n$ positions, the last free one is position $m$ (suppose $0<m\le n/2$) is given by

$$ Q_{n-1,m-1}+Q_{n-1,n-m-1} = \frac{m-1}{(n-1)(n-2)}+\frac{n-m-1}{(n-1)(n-2)}=\frac{1}{n-1}$$

This means that (perhaps surprisingly) all are equiprobable (and that perhaps this should have a simpler proof).


Proof of $(1)$ can go along this:

First, a lemma: suppose we have a row of $k$ positions, a token is placed in the leftmost position, and in each step it moves to left or right with same probability, until it leaves the row. Then, the probability that it enventually leaves the row by the left ("near") extreme is $p_k=k/(k+1)$

Then, considering the two ways that it can happen $x_t=k$, we get that $Q_{t,k}$ must follow the recursion:

$$Q_{t,k}=Q_{t-1,k-1}\frac{t-1}{t}+Q_{t-1,t-k-1}\frac{1}{t}$$ for which, along with the initial condition, $(1)$ is solution.

$\endgroup$
2
$\begingroup$

Call the string, which has all numbers of players that take turns until the end of the game, the 'main string'. Probability that $k$th player wins the game is equal to the probability that $k_{n+1},\dots,k_{n-1}$ sub-string occurs (without visiting k) in the main string.

Let probability that player $2$ wins is $p$ (Of symmetry, probability that player $N$ wins is also $p$). Therefore probability that $3,\dots,1$ occurs in the main string is $p$. Probability that $3,\dots,5$ occurs in the main string is the same as probability that $3,\dots,1$ occurs in the main string: Because both strings start at exactly same number and contains same number of players (both have $N-1$ players). So probability that $3,\dots,5$ occurs in the main string is $p$. Therefore probability that player $4$ wins is $p$.

If we continue this process until start of the cycle, we discover that all even numbers have equal probability of winning. Now there are two conditions:

  • If $N$ is odd; then from player $N$ you can repeat the same process to player $3$, proving all odd numbers have the same chance of winning which is $p$. Therefore all players have equal probability to win the game.
  • If $N$ is even; then we need a claim given below with its proof. Probability that player $N$ wins is probability that $1,\dots,N-1$ occurs in the main string. Since $1$ is certainly will appear in the main string, using the claim below, probability that $1,\dots,N-1$ occurs in the main string is $1\over N-1$. So probability that player $N$ wins is $1\over N-1$. Therefore, from the process above, probability that any even number wins is $1\over N-1$. Let probability that player $3$ wins is $q$. Carrying out above process again bringing out that probability that any odd number wins is $q$. Since there are $N\over 2$ even players which have winning probabilities $1\over N-1$ individually, and $\frac{N}{2}-1$ odd players which have winning probabilities $q$ individually, and all the probabilities sum up to $1$; then $$ 1=\frac{N}{2}\cdot\frac{1}{N-1}+\left(\frac{N}{2}-1\right)\cdot q\\ \frac{N-2}{2N-2}=\frac{N-2}{2}\cdot q\\ q=\frac{1}{N-1} $$ Therefore all players have equal probability to win the game.

Claim: On the condition that player $i$ appears in the main string, probability that $i,\dots,j$ occurs without going to $i-1$ is $1\over k$ ($k$ is the number of players in string $i,\dots,j$).

Proof: Technique is the same as proof of Kelvin Soh's answer. We use induction on $k$ on the claim:

For $k=3$: Suppose that $i$ appears in the main string. We are looking for probability that $i,\dots,i+2$ occurs without going to $i-1$. Call this probability $x$. Probability that $i,i+1$ occurs is $1\over 2$. Once this string occurs, probability that $i,i+1,i+2$ occurs is $1\over 2$ and probability that $i,i+1,i$ occurs is $1\over 2$. Once $i,i+1,i$ occurs, probability that $i,\dots,i+2$ occurs without going to $i-1$ is $x$ again. Putting all these into equation:

$$ x=\frac{1}{2}\cdot\left(\frac{1}{2}+\frac{1}{2}\cdot x\right)\\ \frac{3}{4}\cdot x=\frac{1}{4}\\ x=\frac{1}{3} $$

Suppose claim is true for $k=n-1$. And suppose that $i$ appears in the main string. We are looking for the probability that sub-string $i,\dots,j$, which has $n$ players in it, occurs without going to $i-1$. Call this probability $y$.

From $i$, probability that $i,i+1$ occurs is $1\over 2$.

  • From $i,i+1$, probability that $i,i+1,\dots,j$ occurs without going to $i$ second time is $1\over n-1$: Because once we reach $i+1$ probability that $i+1,\dots,j$ occurs without visiting $i$ is $1\over n-1$ (from hypothesis), since $i+1,\dots,j$ has $n-1$ players in it.
  • From $i,i+1$, probability that we're going to $i$ without reaching $j$ is probability that $i+1,\dots,j$ not occurs. Since probability that $i+1,\dots,j$ occurs is $1\over n-1$, probability that it is not occurs is $1-\frac{1}{n-1}$.
    • From $i,i+1,\dots,i$ probability that $i,\dots,j$ occurs without going to $i-1$ is $y$ again.

Putting all these into equation:

$$ y=\frac{1}{2}\cdot\left(\frac{1}{n-1}+\left(1-\frac{1}{n-1}\right)\cdot y\right)\\ y\cdot\left(\frac{1}{2}-\frac{1}{2(n-1)}\right)=\frac{1}{2n-2}\\ y\cdot\frac{n}{2n-2}=\frac{1}{2n-2}\\ y=\frac{1}{n} $$

Therefore claim is true for $k=n$. So it is true for all $n$. $\blacksquare$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.