My Math Forum  

Go Back   My Math Forum > College Math Forum > Advanced Statistics

Advanced Statistics Advanced Probability and Statistics Math Forum


Thanks Tree2Thanks
  • 1 Post By romsek
  • 1 Post By romsek
Reply
 
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 $ 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.
Shanonhaliwell is offline  
 
August 11th, 2018, 09:53 AM   #2
Senior Member
 
romsek's Avatar
 
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,~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
File Type: jpg Clipboard01.jpg (47.4 KB, 19 views)
Thanks from Shanonhaliwell

Last edited by romsek; August 11th, 2018 at 10:11 AM.
romsek is offline  
August 11th, 2018, 04:31 PM   #3
Member
 
Joined: Feb 2018
From: Canada

Posts: 34
Thanks: 2

Quote:
Originally Posted by romsek View Post
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.
Shanonhaliwell is offline  
August 11th, 2018, 06:37 PM   #4
Senior Member
 
romsek's Avatar
 
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, 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
romsek is offline  
August 12th, 2018, 01:08 AM   #5
Global Moderator
 
Joined: Dec 2006

Posts: 19,285
Thanks: 1681

Quote:
Originally Posted by romsek View Post
The transition matrix should be the transpose . . .

$Tv = v$
Shanonhaliwell's post implied using $vT = v$, which wouldn't need $T$ to be transposed.
skipjack is offline  
Reply

  My Math Forum > College Math Forum > Advanced Statistics

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





Copyright © 2018 My Math Forum. All rights reserved.