August 10th, 2018, 12:29 PM #1 Member   Joined: Feb 2018 From: Canada Posts: 46 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, 10:53 AM   #2
Senior Member

Joined: Sep 2015
From: USA

Posts: 2,647
Thanks: 1476

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, 24 views)

Last edited by romsek; August 11th, 2018 at 11:11 AM. August 11th, 2018, 05:31 PM   #3
Member

Joined: Feb 2018

Posts: 46
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 05:46 PM. August 11th, 2018, 07:37 PM #4 Senior Member   Joined: Sep 2015 From: USA Posts: 2,647 Thanks: 1476 $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, 02:08 AM   #5
Global Moderator

Joined: Dec 2006

Posts: 21,124
Thanks: 2332

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 ### hilbert cube is compact proof

Click on a term to search for related topics.
 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post helpneeded123 Advanced Statistics 1 January 27th, 2015 01:07 AM Hemantha Probability and Statistics 1 July 7th, 2014 01:57 PM dr_romix Advanced Statistics 2 October 16th, 2012 07:36 PM legendoulis Advanced Statistics 4 April 4th, 2012 12:28 PM butabi Advanced Statistics 1 February 12th, 2012 04:20 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      