5
$\begingroup$

Consider a circular arrangement of 8 people as shown below:

enter image description here

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!

$\endgroup$
8
  • $\begingroup$ Doesn’t the question mention about in how many passing moves ? Cause like candy can be passed 1-2-3 and also 1-8-7-8-1-2–3 and 1-8-1-8-1-2-3 and we can go on like this forever .which is uncountable if we don’t know how many moves are allowed $\endgroup$
    – Negar
    Dec 21 '20 at 9:45
  • $\begingroup$ @Negar No. No number of moves are given. But I think the question still makes sense since it is probability. $\endgroup$
    – MakVish
    Dec 21 '20 at 9:47
  • 1
    $\begingroup$ For the first question, consider the probability of going first to the place $n$ to your left before than to the one $m$ to your right, denoted like $P(n,m)$. You can find two good recurrence relation like $P(n,m) = P(n-1,m+1)/2 + P(n+1,m-1)/2$ and also $P(n,m) = 1-P(m,n)$. Try to reason why. You also know $P(0,m) = 1$ if $m>0$ and $P(n,0) = 0$ if $n>0$. Do you think you can find the probability with that? $\endgroup$
    – AnilCh
    Dec 21 '20 at 10:10
  • $\begingroup$ For the second try to come up with a similar expression for the expected number of times the candy will get passed before arriving to the person $n$ to your left, $m$ to your right. Do you think you can find the recurrence relation yourself? It's quite similar $\endgroup$
    – AnilCh
    Dec 21 '20 at 10:21
  • 1
    $\begingroup$ The probability of going $n$ to your left before going $0$ to your right is $0$ because you're already $0$ to your right. That's why $P(n,0) = 0$. The first recurrence relation is considering one step of the random walk and applying that the probability will be the sum of probabilities in each of the two alternatives in that step. The probability starting in $1$ will be half the probability of starting in $2$ + half the probability of starting in $8$. $\endgroup$
    – AnilCh
    Dec 21 '20 at 10:48
2
$\begingroup$

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.

$\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.