
Advanced Statistics Advanced Probability and Statistics Math Forum 
 LinkBack  Thread Tools  Display Modes 
August 10th, 2018, 11:29 AM  #1 
Member Joined: Feb 2018 From: Canada Posts: 34 Thanks: 2  Markov chain probability
Today I am starting to learn Markov chain and this is a question I've got. A simple message  either "yes" or "no"  is passed from one person to the next in a large group. Each person who receives the message "yes" has probability $ p $ of passing on the message "yes", and probability $ 1p $ of passing on the message "no". Each person who receives the message "no" has probability of $ q $ of passing on the message "no", and probability $ 1q $ of passing on the message "yes". Assume that $ 0 < p,q < 1 $. After many iterations, what is the probability that the final person in the group receives the message "yes"? So I think we can have this following transition matrix: \begin{bmatrix} p & 1p \\ 1q & q \end{bmatrix} And I think the calculations can be done by the following matrix multiplication: $ Current State * Transition Matrix = Final State $ How can I apply this to solve this question or there is another simple way to do it. Thank you. 
August 11th, 2018, 09:53 AM  #2 
Senior Member Joined: Sep 2015 From: USA Posts: 2,038 Thanks: 1063 
The transition matrix should be the transpose of what you have written. Let that matrix be $T$ you want to solve for $v=(p_y,~1p_y)$ such that $Tv = v$ You'll find that $p_y = \dfrac{q1}{p+q2}$ but of course you need to show this. It's just a bit of algebra. There is another method for solving this. Basically you are after $\begin{pmatrix}p_y \\ 1p_y\end{pmatrix} =\lim \limits_{n\to \infty}~T^n \begin{pmatrix}x \\ 1x\end{pmatrix}$ where $x$ is any initial probabilities you care to assign to the system. Diagonalize $T$ using the eigensystem so that $T = S D S^{1}$ Then $T^n = S D^n S^{1}$ find $D_{\infty}=\lim \limits_{n\to \infty}~D^n$ then $\begin{pmatrix}p_y \\ 1p_y\end{pmatrix}=S D_\infty S^{1}\begin{pmatrix}x \\ 1x\end{pmatrix},~\forall 0 \leq x \leq 1$ Last edited by romsek; August 11th, 2018 at 10:11 AM. 
August 11th, 2018, 04:31 PM  #3  
Member Joined: Feb 2018 From: Canada Posts: 34 Thanks: 2  Quote:
So I have the transition matrix $T$ which is: \begin{bmatrix} p & 1q \\ 1p & q \end{bmatrix} Since $T$ is primitive then there exist a matrix $V$ such that $T^n \to V $ as $n \to \infty $. Each row of $V$ is the same row vector $ v = (p_y, 1  p_y) $. This is what I've got from a theorem in my class and your answer. But what is this value $p_y$? Is it the probability of the final person in the group receives the message "yes" after n iterations? I would be very grateful if you could explain a bit more regarding the second method and how you come up with both of these $\begin{pmatrix}p_y \\ 1p_y\end{pmatrix} =\lim \limits_{n\to \infty}~T^n \begin{pmatrix}x \\ 1x\end{pmatrix}$ $\begin{pmatrix}p_y \\ 1p_y\end{pmatrix}=S D_\infty S^{1}\begin{pmatrix}x \\ 1x\end{pmatrix},~\forall 0 \leq x \leq 1$ Or could you please give me some references where I can learn to come up with these? I am sort of new to Markov chain. Thank you. Last edited by Shanonhaliwell; August 11th, 2018 at 04:46 PM.  
August 11th, 2018, 06:37 PM  #4 
Senior Member Joined: Sep 2015 From: USA Posts: 2,038 Thanks: 1063 
$p_y$ is the overall probability that you receive a yes message. the state vector $(p_y, 1p_y)$ is equivalent to $\left(P[\text{receive yes}],~P[\text{receive no}]\right)$ and of course $P[\text{receive no}] = 1  P[\text{receive yes}]$ You start the system in some initial probabilistic state. For example dictating that the first message received was "yes" corresponds to the state $(1,0)$ The initial state doesn't matter in the limit but it will affect the final probabilities of finite trials. A typical initial state is uniform and in this case corresponds to $s_0 = (1/2, ~1/2)$ $P[\text{receiving yes after } n \text{ trials}] = \{T^n s_0\}_1$ i.e. the first element of the vector $T^n s_0$ So the kicker is calculating $T^n$ Have you done any work on eigenvalues and eigenvectors yet? There is a method of diagonalizing a matrix which allows relatively simple computation of $T^n$ https://en.wikipedia.org/wiki/Diagonalizable_matrix scan that and write back w/further questions 
August 12th, 2018, 01:08 AM  #5 
Global Moderator Joined: Dec 2006 Posts: 19,285 Thanks: 1681  

Tags 
chain, markov, markov chain, probability 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Absorbing Markov chain help  helpneeded123  Advanced Statistics  1  January 27th, 2015 12:07 AM 
Do you know Markov chain?  Hemantha  Probability and Statistics  1  July 7th, 2014 12:57 PM 
Help with Hidden Markov chain  dr_romix  Advanced Statistics  2  October 16th, 2012 06:36 PM 
help in markov chain  legendoulis  Advanced Statistics  4  April 4th, 2012 11:28 AM 
Markov chain  butabi  Advanced Statistics  1  February 12th, 2012 03:20 PM 