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