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:

• A 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:

    

• A 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:

    

• 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:

    

  • 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’$)
• A 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

    

  • 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):

      

      • 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: 

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 
  • 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:

• Markov Chains – Part 1
• Markov Chains – Part 2
• Markov Chains – Part 3
• Markov Chains – Part 4
• Markov Chains – Part 5
• Markov Chains – Part 6
• Markov Chains – Part 7
• Markov Chains – Part 8
• Markov Chains – Part 9