1
$\begingroup$

This is a cross-post from math.stackexchange.com. There has been no response there.

Given a Markov chain of finite states with constant transition probabilities, what is the method to compute the probability of a path finally landing in a particular state for the first time having traversed all other states? Are there any references? The following is a puzzle as an example.

$12$ people sit on a round table to play a variation of the telephone game. They are numbered from $1$ to $12$ in clockwise order, i.e. the people with adjacent numbers (including $1$ and $12$) sit next to each other. Person #1 chooses a secret word and starts the game by randomly selecting one of the two neighbors and whispering the word to that person. Upon hearing the word, each person continues the game by randomly selecting one of the neighbors and whispering the word. The game ends when everyone knows the secret word.

What is the probability that the last person whispering the word is numbered $6$?

$\endgroup$
  • $\begingroup$ For this specific case if you denote by $p_k$ the probability that the person sitting k seats in clockwise order from the current whisperer then because the word goes left or right with probability 1/2 we have $p_k=(p_{k-1}+p_{k+1})/2$ for $k>1$. In the case $k=1$ consider persons A,B,C in that order and we want the probability that the word starting in B is last at A. For that to happen we must first go from B to C. Then A is last if starting from C that B or A is last, hence $p_1=(p_1+p_2)/2$ therefore $p_1=p_2$. Inductively it follows that all probabilities are equal. $\endgroup$ – user100927 Jul 24 at 15:45
  • $\begingroup$ @user100927: It seems your first sentence missed a word indicating what probability $p_k$ is. I supposed you meant $p_k$ to be the probability of the person $k$ seats clockwise away hearing the message. More importantly, $p_k$ is the probability of the equilibrium or stationary state (at time infinity) which is indeed $\frac1n$ where $n$ is the total number of seats. However, this is not what the question is asking for. $\endgroup$ – Hans Jul 24 at 19:56
  • $\begingroup$ no I meant the probability that the person sitting k seats clockwise away hears the message last. $\endgroup$ – user100927 Jul 26 at 7:41
  • $\begingroup$ You want the word always emanates from $k=0$, right? Then I do not think your recursion equation is right. For $k>1$, each path reckoned by $p_{k-1}$ traverses through $k$ before it hits $k-1$ which excludes itself from being accounted for by $p_k$. The same goes for $p_{k+1}$. $\endgroup$ – Hans Jul 26 at 18:33
  • 1
    $\begingroup$ $p(i,j)$ only depends on the difference $i-j$, i.e. $p(i,j)=q(j-i)$ so either both statements are true or both are wrong. $\endgroup$ – user100927 Aug 5 at 8:32
4
$\begingroup$

For the example, the considered event $E$ is the intersection of two events $A$ and $B$, namely that both 5 and 7 are reached before 6. The union of the two events has probability $1$. So the probability of $E$ is $P(A)+P(B)-1$. By this answer:

https://math.stackexchange.com/questions/725996/reaching-a-level-before-another-for-a-random-walk

$P(A)=7/11$ and $P(B)=5/11$ so the sought probability is $1/11$. The argument can be adapted to any position on the circle : they all have the same probability to be reached last.

$\endgroup$
  • $\begingroup$ sorry, I made the mistake of thinking 6 was opposite to 1. The final answer was correct though. Fixed the text. Circular topology doesn't really make it more complicated I think. $\endgroup$ – alesia Jul 31 at 21:44
  • $\begingroup$ +1 and accepted. Bravo! $\endgroup$ – Hans Aug 1 at 0:24
1
$\begingroup$

You could expand the state space by including the subset of people visited so far. Also introduce two absorbing states, win and lose, and then use the usual approach to find the absorption probabilities.

For the example with 12 people, the only subsets you need to track are the four subsets of {5,7}, rather than all subsets of $\{1,\dots,12\}\setminus \{6\}$.

Let $w(i,S)$ denote the win probability starting with person $i$ and $S \subseteq \{5,7\}$ visited so far. Then $w(6,\{5,7\})=1$, $w(6,S)=0$ for $S\not=\{5,7\}$, and $$w(i,S) = \sum\limits_{j,T} p_{i,S,j,T}\ w(j,T),$$ where the transition probabilities $p_{i,S,j,T}$ are as follows (with 0, 5, 7, and 57 as shorthand for the corresponding subsets):

i S j T p(i,S,j,T)
1 0 2 0 0.5 
1 0 12 0 0.5 
1 5 2 5 0.5 
1 5 12 5 0.5 
1 7 2 7 0.5 
1 7 12 7 0.5 
1 57 2 57 0.5 
1 57 12 57 0.5 
2 0 1 0 0.5 
2 0 3 0 0.5 
2 5 1 5 0.5 
2 5 3 5 0.5 
2 7 1 7 0.5 
2 7 3 7 0.5 
2 57 1 57 0.5 
2 57 3 57 0.5 
3 0 2 0 0.5 
3 0 4 0 0.5 
3 5 2 5 0.5 
3 5 4 5 0.5 
3 7 2 7 0.5 
3 7 4 7 0.5 
3 57 2 57 0.5 
3 57 4 57 0.5 
4 0 3 0 0.5 
4 0 5 5 0.5 
4 5 3 5 0.5 
4 5 5 5 0.5 
4 7 3 7 0.5 
4 7 5 57 0.5 
4 57 3 57 0.5 
4 57 5 57 0.5 
5 5 4 5 0.5 
5 5 6 5 0.5 
5 57 4 57 0.5 
5 57 6 57 0.5 
6 5 6 5 1.0 
6 7 6 7 1.0 
6 57 6 57 1.0 
7 7 6 7 0.5 
7 7 8 7 0.5 
7 57 6 57 0.5 
7 57 8 57 0.5 
8 0 7 7 0.5 
8 0 9 0 0.5 
8 5 7 57 0.5 
8 5 9 5 0.5 
8 7 7 7 0.5 
8 7 9 7 0.5 
8 57 7 57 0.5 
8 57 9 57 0.5 
9 0 8 0 0.5 
9 0 10 0 0.5 
9 5 8 5 0.5 
9 5 10 5 0.5 
9 7 8 7 0.5 
9 7 10 7 0.5 
9 57 8 57 0.5 
9 57 10 57 0.5 
10 0 9 0 0.5 
10 0 11 0 0.5 
10 5 9 5 0.5 
10 5 11 5 0.5 
10 7 9 7 0.5 
10 7 11 7 0.5 
10 57 9 57 0.5 
10 57 11 57 0.5 
11 0 10 0 0.5 
11 0 12 0 0.5 
11 5 10 5 0.5 
11 5 12 5 0.5 
11 7 10 7 0.5 
11 7 12 7 0.5 
11 57 10 57 0.5 
11 57 12 57 0.5 
12 0 1 0 0.5 
12 0 11 0 0.5 
12 5 1 5 0.5 
12 5 11 5 0.5 
12 7 1 7 0.5 
12 7 11 7 0.5 
12 57 1 57 0.5 
12 57 11 57 0.5 

Here are the resulting win probabilities $w(i,S)$ for the various states: \begin{align} i\backslash S &&\{\} &&\{5\} &&\{7\} &&\{5,7\} \\ 1 &&1/11 &&5/11 &&7/11 &&1 \\ 2 &&1/11 &&4/11 &&8/11 &&1 \\ 3 &&1/11 &&3/11 &&9/11 &&1 \\ 4 &&1/11 &&2/11 &&10/11 &&1 \\ 5 && &&1/11 &&&&1 \\ 6 && &&0 &&0 &&1 \\ 7 && && &&1/11 &&1 \\ 8 &&1/11 &&10/11 &&2/11 &&1 \\ 9 &&1/11 &&9/11 &&3/11 &&1 \\ 10 &&1/11 &&8/11 &&4/11 &&1 \\ 11 &&1/11 &&7/11 &&5/11 &&1 \\ 12 &&1/11 &&6/11 &&6/11 &&1 \end{align} In particular, the desired win probability is $w(1,\{\}) = 1/11$.

$\endgroup$
  • $\begingroup$ Sounds promising. But I do not fully understand your solution. Could you please write out all the details of your derivation? Are you trying to compute the transition probability, say, from the set $\{11,12,1,2\}$ of all points having visited to the set $\{11,12,1,2,3\}$? $\endgroup$ – Hans Jul 24 at 20:21
  • $\begingroup$ Let $w(i,S)$ denote the win probability, starting at person $i$, with $S \subseteq \{5,7\}$ already visited. Then $w(6,\{5,7\}) = 1$ and $w(6,S) = 0$ if $S \not= \{5,7\}$. For all other $i$ and $S$, we have linear equations $w(i,S) = \sum\limits_{j,T} p_{i,S,j,T}\ w(j,S)$, where $p_{i,S,j,T}$ is the transition probability from state $(i,S)$ to state $(j,T)$. Because we start with person 1, want to compute $w(1,\{\})$, which turns out to be $1/11$. $\endgroup$ – Rob Pratt Jul 24 at 20:24
  • $\begingroup$ Please excuse my obtuseness. I still do not understand. Do you want $𝑤(𝑖,𝑆)$ to denote the win probability, starting at person 𝑖, with 𝑆⊆{5,7} already visited by a fixed finite time $t$ or $t=\infty$ (meaning eventually)? I suppose you want the latter. Am I correct? Is there any typo in the indices in your linear equation? How do you compute $p_{i,S,j,T}$? It would really help if you could be so kind as to write out all the details in your answer. $\endgroup$ – Hans Jul 24 at 21:01
  • $\begingroup$ Eventual win probability, given that you are currently at person $i$ and have so far visited $S$. Yes, sorry, the $w(j,S)$ on the right hand side is a typo for $w(j,T)$. $\endgroup$ – Rob Pratt Jul 24 at 21:09
  • $\begingroup$ Thank you for your edit. However, I do not understand how to interpret $p_{i,S,j,T}$ and how it is computed. $\endgroup$ – Hans Jul 24 at 21:26
0
$\begingroup$

Here I am exploring an approach that may be slightly different from Rob Pratt. I will use a less complex example. a Instead of $12$ people, we seat $4$ labeled clockwise as $(0,1,2,-1)$. Let $A:=\{0,1,2,-1\}$. Define $p(i,S),\,i\in A,\,S\subset\{-1,1\}$ as the probability of paths starting from $i$ and satisfying the following property. The subset of $\{-1,1\}$ each of these path passes before for the first time landing on $2$ is $S$.

By the Markov property, we have \begin{align} p(0,\{-1,1\}) &= \frac12\big(p(-1,\{-1,1\})+p(1,\{-1,1\})\big) \\ p(-1,\{-1,1\}) &= \frac12\big(p(0,\{-1,1\})+p(0,\{1\})\big) \\ p(1,\{1,-1\}) &= \frac12\big(p(0,\{1,-1\})+p(0,\{-1\})\big) \\ p(-1,\{-1,1\}) &= p(1,\{1,-1\}) \\ p(0,\{1\}) &= p(0,\{-1\})) \end{align} All these $p(i,S)$ are equal. But then I can not proceed further.


Rob Pratt, please feel free to add your comment here.

$\endgroup$
0
$\begingroup$

Here is the insightful solution of user100927 in the top comment section. I transcribe his answer.

Let us define $𝑝(𝑖,𝑗)$ to be the probability of the word starting from 𝑖 and traversing all other persons before landing on $𝑗$. $𝑝(𝑖,𝑗)=\frac12(𝑝(𝑖−1,𝑗)+𝑝(𝑖+1,𝑗)),\forall |𝑗−𝑖|>1$. For, say, $j=i+1$, $p(i,i+1)=\frac12\big(p(i-1,i)+p(i-1,i)\big)$. The second term in the parenthesis comes from the equivalence of the following two events. A path starts from $i-1$ and hits $i+1$ before $i$ and one starts from $i-1$ and hits $i$ last. The equivalence of the two is implied by the fact that the starting point $i-1$ is the neighbor of $i$ opposite of $i+1$. Moreover, obviously $\sum\limits_jp(i,j)=1$.

Now the symmetry in the problem implies that $p(i,j)$ depends only on $|j-i|$. Without the risk of notational confusion, we denote $p(|j-i|):=p(i,j)$. We have $p(i)=\frac12\big(p(i-1)+p(i+1)\big),\,\forall i>1;\ p(1)=\frac12\big(p(2)+p(1)\big);\,\sum\limits_{i\ne0}p(i)=1$. With $n$ nodes, we obtain $\displaystyle p(i)=\frac1{n-1}$.

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