Consider a circular arrangement of 8 people as shown below:
Let's say person 1 has a candy which is passed around with equal probability either to the left or right. All the other people do the same.
a) Find the probability that the person 3 gets the candy before person 6.
b) Find the expected number of times the candy will be passed before the person 5 gets it for the first time.
For a) I could just break the circle between 3 and 4 and consider them siting in a straight line as,
$3\hspace{10pt}2\hspace{10pt}1\hspace{10pt}8\hspace{10pt}7\hspace{10pt}6$
Now how do I go about calculating the probability? Do I take different cases? I think using conditional probability I could get some recurrence relation. Not sure how to go about b). Any help is appreciated. Thanks!
We can solve this using the theory of absorbing markov chains. It may be over-complicating the question a little but I think it's a useful and general tool worth using. For question a, the absorbing states will be 3 & 6 while state 4 & 5 have been removed. Our transition matrix will then be $$ P = \begin{pmatrix} 0 & 1/2 & 1/2 & 0 & 0 & 0 \\ 1/2 & 0 & 0 & 0 & 1/2 & 0 \\ 1/2 & 0 & 0 & 1/2 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 0 & 1/2 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} Q & R \\ 0 & I_2 \end{pmatrix} $$
where our indices are in the order $(1,2,8,7,3,6)$.
We then find the fundamental matrix (using some CAS) which is $$ N = (I_4 - Q)^{-1} = \frac25 \begin{pmatrix} 6 & 3 & 4 & 2\\ 3 & 4 & 2 & 1\\ 4 & 2 & 6 & 3\\ 2 & 1 & 3 & 4\\ \end{pmatrix} $$
Finding the probability of being absorbed can be done just by examing the (1,1) entry in $$ B = NR = \frac15 \begin{pmatrix} 3 & 2 \\ 4 & 1 \\ 2 & 3 \\ 1 & 4 \\ \end{pmatrix} $$
So the probability of 3 getting the candy before 6 is $3/5$.
For question b, the method is similar but with a larger transition matrix and 5 as the only absorbing state. We are looking for the number of states visited before being absorbed when starting from position 1, which is just the sum of the first row of N. If we order the states $(1,2,3,4,6,7,8,5)$ in $P$ then we will get $$Q= \frac12 \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix} $$ And then $$ N = (I_7 - Q)^{-1} = \frac14 \begin{pmatrix} 16 & 12 & 8 & 4 & 4 & 8 & 12 \\ 12 & 15 & 10 & 5 & 3 & 6 & 9 \\ 8 & 10 & 12 & 6 & 2 & 4 & 6 \\ 4 & 5 & 6 & 7 & 1 & 2 & 3 \\ 4 & 3 & 2 & 1 & 7 & 6 & 5 \\ 8 & 6 & 4 & 2 & 6 & 12 & 10 \\ 12 & 9 & 6 & 3 & 5 & 10 & 15 \end{pmatrix} $$
If we sum all values on the first row, because we are starting from position 1, we find that the expected number of times the candle is passed is 16.