Mathematics, Neuroscience

Markov Chains

[latexpage]

Introduction – Toothpaste Brand Example

Consider the following scenerio:

  • Brand T is a toothpaste company that controls 20% of the toothpaste market
  • A market researcher predicts the following effects of an ad campaign:
    • A consumer using brand T will continue using brand T with a 90% probability
    • A consumer not using brand T will switch to brand T with a 70% probability
  • For any given customer in the toothpaste market, let…
    • $T$ denote a state of using brand T
    • $T’$ denote the state of using a toothpaste brand other than T

Definitions:

  • transition diagram is wieghted directed graph whose nodes denote various states a system can exist in and edges denote the probability of the system transitioning from one state to another after some time step $\Delta t$
    • Transition diagram describing our toothpaste brand example:

      Transition Diagram - Copy
      Figure 1
  • transition probability matrix $\mathrm{P}$ is a $n \times n$ matrix whose $(i,j)$ entries give the probabiliy a “sample” in the $i$th state of a $n$-state system will transition to its $j$th state
    • Importantly, the elemental sum of all rows in any $\mathrm{P}$ must equal 1
    • Here is transition probability matrix describing our toothpaste brand example:

      Transition Probability Matrix - copy
      Figure 2
  • An initial state distribution matrix $\mathrm{S_0}$ for a $n$-state system is a $n$-dimensional column vector whose $i$th entries denote the percentage of “samples” that are in state $i$ at time $t=0$
    • Here is the initial state distribution matrix for our toothpaste example:

      initial state distribution matrix
      Figure 3
    • The $i=1$st entry indicates that 20% of customers in the toothpaste market use brand T (state $T$) and the $i=2$nd entry indicates that 80% of customers in the toothpaste market use brand T’ (state $T’$)
  • probability tree gives the probability a “sample” will transition to some state after some time
    • For our toothpaste example, let’s construct  a probability tree that tells us the probability a person will use brand T vs. T’ after one month

      Probability Tree 1
      Figure 4:
    • In order to determine the probability a customer is using brand T after one week, we need to take the sum of all the possible products of the probability transitions that end in state T (Fig 5)
      • Here, there are two possible state transition sequences that end in state T (highlighted in orange and green):
        Probability Tree 2
        Figure 5
        • The orange path gives the probability of a customer will use toothpaste brand T for the entire month ⇒ $P(T \rightarrow T) = (0.2)(0.9) = 0.18$
        • The green path gives the probability of a customer using brand T’ at the beginning of the month, then switching to band T at the end of the month ⇒ \[P(T’ \rightarrow T) = (0.8)(0.7) = 0.56\]
      • Now, we can sum the probabilities of each possible transition sequence ending in state $T$ in order to determine the total probability a custormer will be using brand T by the end of the month: $P(T) = P(T \rightarrow T) + P(T’ \rightarrow T) = (0.18)(0.56) = 0.74$
        • There is a 74% chance a random customer in the toothpaste market will be using brand T by the end of the month
      • Since we only have two possible states in our system, subtracting $P(T)$ from 1 will give us the probability a random customer will be using brand T’ by the end of the month: $P(T’) = 1 – P(T) = 1 – 0.74 = 0.26$
        • Importantly, we can construct a state distribution matrix giving the the probabilities for the toothpaste brand a randomly sampled customer will be using after one month: state distribution matrix 1

Theorem: $\mathrm{S_i} \cdot \mathrm{P} = \mathrm{S_{i+1}}$

  • Specifically, this is saying that the dot product between a state distribution matrix for time $i$th time step and a corresponding transition probability matrix will return the state distribution matrix for the $i+1$th time step
  • Let’s check and make sure this hold true for our example:

$\mathrm{S_0} \cdot \mathrm{P} = \begin{bmatrix} 0.2 & 0.8 \end{bmatrix} \cdot \begin{bmatrix} 0.9 & 0.1 \\ 0.7 & 0.3 \end{bmatrix} = \begin{bmatrix} (0.2)(0.9) + (0.8)(0.7) & (0.2)(0.1) + (0.8)(0.3) \end{bmatrix} = \begin{bmatrix} 0.74 & 0.26 \end{bmatrix} =  \mathrm{S_{1}}$

  • Results agree with our probability tree!

Assuming $\mathrm{P}$ remains valid, we can determine the expected state distribution matrix for any time step (i.e., month)

  • State distribution matrix for second time step:

$\mathrm{S_1} \cdot \mathrm{P} = \begin{bmatrix} 0.74 & 0.26 \end{bmatrix} \cdot \begin{bmatrix} 0.9 & 0.1 \\ 0.7 & 0.3 \end{bmatrix}$

$= \begin{bmatrix} (0.74)(0.9) + (0.26)(0.7) & (0.74)(0.1) + (0.26)(0.3) \end{bmatrix}$

$= \begin{bmatrix} 0.848 & 0.152 \end{bmatrix} =  \mathrm{S_{2}}$

  • State distribution matrix for third time step

$\mathrm{S_2} \cdot \mathrm{P} = \begin{bmatrix} 0.848 & 0.152 \end{bmatrix} \cdot \begin{bmatrix} 0.9 & 0.1 \\ 0.7 & 0.3 \end{bmatrix}$

$= \begin{bmatrix} (0.848)(0.9) + (0.152)(0.7) & (0.848)(0.1) + (0.152)(0.3) \end{bmatrix}$

$= \begin{bmatrix} 0.8698 & 0.1304 \end{bmatrix} =  \mathrm{S_{3}}$

Regular Markov Chains: Stationary Matrices and Steady State Markov Chains

Example: assume a company initially has 10% of the market share

  • Using an advertising campaign, the transition probability matrix is given by Transition Probability Matrix Example 2
    • Notations:
      • $A = $ state where a customer is using brand A
      • $A’ =$ state where a customer is using brand A’
  • Question: what happens to the company’s market shar over a long period of time (assuming $\mathrm{P}$ continues to be valid)
    • Solution:

$ \mathrm{S_0} = \begin{bmatrix} 0.1 & 0.9 \end{bmatrix}$

$ \mathrm{S_1} = \mathrm{S_0} \cdot \mathrm{P} = \begin{bmatrix} 0.1 & 0.9 \end{bmatrix} \cdot \begin{bmatrix} 0.8 & 0.2 \\ 0.6 & 0.4 \end{bmatrix} = \begin{bmatrix} 0.62 & 0.38 \end{bmatrix}$

$ \mathrm{S_2} = \mathrm{S_1} \cdot \mathrm{P} = \begin{bmatrix} 0.62 & 0.38 \end{bmatrix} \cdot \begin{bmatrix} 0.8 & 0.2 \\ 0.6 & 0.4 \end{bmatrix} = \begin{bmatrix} 0.724 & 0.276 \end{bmatrix}$

$ \mathrm{S_3} = \mathrm{S_2} \cdot \mathrm{P} = \begin{bmatrix} 0.7448 & 0.2552 \end{bmatrix}$

$ \mathrm{S_4} = \mathrm{S_3} \cdot \mathrm{P} = \begin{bmatrix} 0.74896 & 0.25104 \end{bmatrix}$

$ \mathrm{S_5} = \mathrm{S_4} \cdot \mathrm{P} = \begin{bmatrix} 0.749792 & 0.250208\end{bmatrix}$

$ \mathrm{S_6} = \mathrm{S_5} \cdot \mathrm{P} = \begin{bmatrix} 0.7499584 & 0.2500416\end{bmatrix}$

  • Here, the state distribution matrices $\mathrm{S_i}$ get closer and closer to $\begin{bmatrix} 0.75 & 0.25 \end{bmatrix}$ as $i \rightarrow \infty$
    • Moreover, if we take the dot product between $\mathrm{S} = \begin{bmatrix} 0.75 & 0.25 \end{bmatrix}$ and $\mathrm{P}$, we get $\mathrm{S}$:
      • $ \mathrm{S} = \mathrm{S} \cdot \mathrm{P} = \begin{bmatrix} 0.75 & 0.25 \end{bmatrix} \cdot \begin{bmatrix} 0.8 & 0.2 \\ 0.6 & 0.4 \end{bmatrix} = \begin{bmatrix} 0.75 & 0.25 \end{bmatrix}$
        • No change occurs!
          • The matrix $\mathrm{S}$ is called a stationary matrix and the system is said to be at steady state

Questions:

  1. Does every Markov chain have a unique stationary matrix?
  2. If a Markov chain does have a unique stationary matrix, will the successive state matrices always approach this stationary matrix?

Answers:

  • Generally, the answer to both questions is no
  • However, if a Markov chain is a regular Markov chain, then the answer to both questions is yes

Sources:

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.