5

Context:

You and 4 other people are sitting in a circle. You are given a ball to start the game. Every second of this game, the person with the ball has three choices they can make. They can either pass the ball to the left, pass the ball to the right, or keep the ball (all with equal probability). This game goes on till someone keeps the ball. What is the probability that you are the person to end the game and keep the ball?

I am refreshing my knowledge of probability, and I am stuck on this question. For reference, it is the 'pass the Quantguide.

Working:

Consider the following diagram for clarity.

enter image description here

Let's define random variable $W(S_i)$ to be the event that player $S_i$ keeps the ball, and end the games. Well, by symmetry we have that $\mathbb{P}(W(S_1)) = \mathbb{P}(W(S_2))$, and similarly $\mathbb{P}(W(S_3)) = \mathbb{P}(W(S_4))$. For simplicity, let use denote $W(S_1)$ and $W(S_2)$ by $N$ (neighbour), and $W(S_3), W(S_4)$ by $NN$ (next neighbour).

So, we wish to find $\mathbb{P}(W(S_0))$ (presumably by also finding $\mathbb{P}(N)$ and $\mathbb{P}(NN)$).

To proceed, we may condition on the action of $S_0$. Thus,

$$ \mathbb{P}(W(S_0)) = \frac{1}{3} + \frac{1}{3} \mathbb{P}(W(S_0) | \text{left} ) + \frac{1}{3} \mathbb{P}(W(S_0) | \text{right}) = \frac{1}{3} + \frac{2}{3} \mathbb{P}(N) $$

Now, I struggle to proceed. I think that I should try to find an expression for $\mathbb{P}(N)$ in terms of $\mathbb{P}(W(S_0))$ and $\mathbb{P}(NN)$, and similarly an expression for $\mathbb{P}(NN)$ in terms of $\mathbb{P}(W(S_0))$ and $\mathbb{P}(N)$, however I am unsure of how I can do this without ending up with the exact same system of equations.

log x log log y
  • 140
  • Also, I will add that I prefer a solution that relies purely on conditioning probability, and doesn't use any heavy machinery (i.e. Markov Chains etc.). – log x log log y Feb 18 '24 at 01:55
  • 1
    Your notation is a bit confusing as I think your $\mathbb{P}(N)$ is supposed to be the conditional probability of you winning if an immediate neighbour has the ball, not the probability of the neighbour stopping or winning. You have found $\mathbb{P}(W(S_0)) = \frac{1}{3} + \frac{2}{3} \mathbb{P}(N)$. You could also find $\mathbb{P}(N) = \frac{1}{3}\mathbb{P}(W(S_0)) + \frac{1}{3} \mathbb{P}(NN)$ and $\mathbb{P}(NN) = \frac{1}{3}\mathbb{P}(N) + \frac{1}{3} \mathbb{P}(NN)$ so three linear equations with three unknowns which you can solve. – Henry Feb 18 '24 at 02:13
  • @Henry Ah, I see. I agree that my notation is confusing. I think that was the problem. – log x log log y Feb 18 '24 at 02:14
  • "Also, I will add that I prefer a solution that relies purely on conditioning probability, and doesn't use any heavy machinery (i.e. Markov Chains etc.)" << Actually, the random process you describe is a textbook Markov chain, and the answer you accepted makes that very explicit by defining three states 0,1 and 2. And yet there is nothing "heavy" about that answer. Markov chains are extremely simple :-) – Stef Feb 18 '24 at 11:34
  • It seems that if there are $n$ people in the circle, the probability of the starter winning is $\dfrac1{\sqrt{5}}\dfrac{\phi^{2n}+1}{\phi^{2n}-1}$ where $\phi$ is the golden ratio $\frac{\sqrt{5}+1}2$. So as $n$ increases, this declines towards $\frac1{\sqrt{5}}\approx 0.4472$, slightly less than the $\frac5{11}\approx 0.4545$ when $n=5$. It is not a coincidence that $5$ and $11$ are in the Fibonacci sequence. – Henry Feb 18 '24 at 14:45

2 Answers2

7

Let $p_0$ be your probability of winning when you have the ball.

Let $p_1$ be your probability of winning when one of your immediate neighbors has the ball.

Let $p_2$ be your probability of winning when one of the remaining two players has the ball.

Then

\begin{align} p_0 &= \frac 13 + \frac 23 p_1 \\ p_1 &= \frac 13 p_0 + \frac 13 p_2 \\ p_2 &= \frac 13 p_1+\frac 13 p_2 \end{align}

The third equation tells us $\frac 23 p_2= \frac 13 p_1$ so $p_1=2p_2$. Plugging this into the second equation, we find that $\frac 53 p_2=\frac 13 p_0$, so $p_0=5p_2$. Finally, we use the first equation to see:

$$5p_2=p_0=\frac 13+\frac 43 p_2 \Rightarrow \frac{11}{3} p_2 = \frac 13 \Rightarrow p_2= \frac {1}{11} \Rightarrow p_0=5p_2 = \frac {5}{11}.$$

Robert Shore
  • 23,332
2

You keep the ball after $k+1$ decisions iff the ball makes a closed walk of length $k$ among all the players (passing left or right, no keeping) and you finally keep it. Each such sequence of events happens with probability $(1/3)^{k+1}$. It follows that the probability of you ultimately keeping the ball is $\frac13$ times the value at $\frac13$ for the generating function for the number of closed walks in a pentagon of given length $$1,0,2,0,6,2,20,14,70\dots$$ This is OEIS A054877 and its generating function is $$\frac15\left(\frac1{1-2x}+\frac{2(2+x)}{1+x-x^2}\right)$$ Thus the answer is $$\frac1{15}\left(\frac1{1-2/3}+\frac{2(2+1/3)}{1+1/3-1/9}\right)=\frac5{11}$$ More generally, if the passing probabilities to the left and right are both equal to $x$, the probability of you keeping the ball simplifies to $$\frac{x^2+x-1}{x^2-x-1}$$

Parcly Taxel
  • 103,344
  • 1
    I don't follow the first two sentences. If $k=2$ you can pass it either way to start, then it has to be passed back to you and you have to keep it. I make the probability of that $\frac 2{27}$ rather than your $\frac 1{27}$ I think you mean a particular walk has that probability so you multiply this by the OEIS value. – Ross Millikan Feb 18 '24 at 03:43
  • @RossMillikan Right. – Parcly Taxel Feb 18 '24 at 04:13
  • I think there's a typo: second equation should start with 1/5, not 1/15 ? – Carl Witthoft Feb 18 '24 at 18:12
  • 1
    @CarlWitthoft It's correct. Second equation is after multiplying by $\frac13$ (and first equation is before). – Parcly Taxel Feb 19 '24 at 03:49