[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:
Figure 1
- 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:
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:
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’$)
- Here is the initial state distribution matrix for our toothpaste example:
- 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
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):
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:
- 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:
- Here, there are two possible state transition sequences that end in state T (highlighted in orange and green):
- 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
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’
- Notations:
- 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
- No change occurs!
- $ \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}$
- 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}$:
Questions:
- Does every Markov chain have a unique stationary matrix?
- 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