My Math Forum Markov chain probability

 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 $1-p$ 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 $1-q$ 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 & 1-p \\ 1-q & 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,121
Thanks: 1101

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,~1-p_y)$

such that

$Tv = v$

You'll find that $p_y = \dfrac{q-1}{p+q-2}$

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 \\ 1-p_y\end{pmatrix} =\lim \limits_{n\to \infty}~T^n \begin{pmatrix}x \\ 1-x\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 \\ 1-p_y\end{pmatrix}=S D_\infty S^{-1}\begin{pmatrix}x \\ 1-x\end{pmatrix},~\forall 0 \leq x \leq 1$

Attached Images
 Clipboard01.jpg (47.4 KB, 20 views)

Last edited by romsek; August 11th, 2018 at 10:11 AM.

August 11th, 2018, 04:31 PM   #3
Member

Joined: Feb 2018

Posts: 34
Thanks: 2

Quote:
 Originally Posted by romsek 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,~1-p_y)$ such that $Tv = v$ You'll find that $p_y = \dfrac{q-1}{p+q-2}$ 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 \\ 1-p_y\end{pmatrix} =\lim \limits_{n\to \infty}~T^n \begin{pmatrix}x \\ 1-x\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 \\ 1-p_y\end{pmatrix}=S D_\infty S^{-1}\begin{pmatrix}x \\ 1-x\end{pmatrix},~\forall 0 \leq x \leq 1$
Thank you for your help. I am so sorry for a repeated reply above but I cannot delete it by now.
So I have the transition matrix $T$ which is:
\begin{bmatrix}
p & 1-q \\
1-p & 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 \\ 1-p_y\end{pmatrix} =\lim \limits_{n\to \infty}~T^n \begin{pmatrix}x \\ 1-x\end{pmatrix}$
$\begin{pmatrix}p_y \\ 1-p_y\end{pmatrix}=S D_\infty S^{-1}\begin{pmatrix}x \\ 1-x\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,121 Thanks: 1101 $p_y$ is the overall probability that you receive a yes message. the state vector $(p_y, 1-p_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 Thanks from Shanonhaliwell
August 12th, 2018, 01:08 AM   #5
Global Moderator

Joined: Dec 2006

Posts: 19,702
Thanks: 1804

Quote:
 Originally Posted by romsek The transition matrix should be the transpose . . . $Tv = v$
Shanonhaliwell's post implied using $vT = v$, which wouldn't need $T$ to be transposed.

 Tags chain, markov, markov chain, probability

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post helpneeded123 Advanced Statistics 1 January 27th, 2015 12:07 AM Hemantha Probability and Statistics 1 July 7th, 2014 12:57 PM dr_romix Advanced Statistics 2 October 16th, 2012 06:36 PM legendoulis Advanced Statistics 4 April 4th, 2012 11:28 AM butabi Advanced Statistics 1 February 12th, 2012 03:20 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top