# Using a Markov Chain to find the limiting probability?

Let's say a website makes available only one of three online quizzes A, B and C, daily.

If the majority of visitors pass the quiz then the next day the website will randomly publish either quiz A, B, or C with equal probability $\frac{1}{3}$.

If the majority of visitors fail the quiz then the next day the website will publish only quiz A (with probability one).

The probability of passing a quiz is:

$P(A) = \frac{3}{10}$, $P(B) = \frac{6}{10}$, $P(C) = \frac{9}{10}$

QUESTION: suppose that the testing procedure has been running for a large number of days without interruption. Let $\xi_A$ be the proportions of the total number of days in which quiz A was used. (This can be thought of as being the "limiting probability" that quiz A is used).

HINT: Use the stationary distribution (G, B) = ($\frac{3}{7}$, $\frac{4}{7}$) and use this stationary distribution to work out $\xi_A$ (apply appropriate conditioning and limiting operations).

My thoughts thus far: The bit where it says "limiting operations" is confusing me slightly on what it means? Is the following approach correct? I feel it is but I'm new to stochastic modelling..

I can model this as a Markov Chain with transition matrix (where rows sum to one):

$\left[\begin{array}{ccc} 0.6 & 0.4 \\ 0.3 & 0.7 \\ \end{array}\right]$

i.e. A good day (G) follow by another G day = $(\frac{1}{3})(\frac{3}{10})+(\frac{1}{3})(\frac{6}{10})+(\frac{1}{3})(\frac{9}{10}) = \frac{6}{10}$

and a bad day (B) followed by a G day = $(\frac{1}{1})(\frac{3}{10})+ 0 + 0 = \frac{3}{10}$.

Step 1: I worked out that the stationary distribution is $P(G)=\frac{3}{7}$ and $P(B)=\frac{4}{7}$.

Step 2: using a bit of conditional probability, then the probability of quiz $A$ being used on day $n$ is:

P(quiz A on day n) = P(quiz A and day n-1 is G) + P(quiz A and day n-1 is B)

$= P(A|G)*P(G) + P(A|B)*P(B)$

$= (\frac{1}{3})(\frac{3}{7}) + (\frac{1}{1})(\frac{4}{7})$

$= \frac{5}{7}$

Step 3: Apply limiting operations? What does that mean?

• It seems to me that using only two states doesn't fully capture what's going on, because (since quiz A has a special treatment and quizzes B and C have different passing probabilities) in order to determine the transition probabilities you need to know what quiz was offered. – whuber Mar 20 '13 at 17:27
• @whuber The quiz offered is dependent on whether the results from the previous day were (G)ood or (B)ad. The transition matrix is what is given in my notes (it took me quite some time to confirm the probabilities). This is all the information I have. Steps 2 and especially 3 are my main worry. – Clair Crossupton Mar 21 '13 at 10:14
• The problem with the $(G,B)$ representation is that it only indirectly models what is of interest. Because the question asks about the proportion of days on which quiz $A$ is given, a direct (and quite the easiest) attack on the problem would include the state "$A$ was given," for then you just read off the answer directly without having to take that time to compute the probabilities. – whuber Mar 21 '13 at 14:47

This problem describes five situations, or states. Although it can be solved (somewhat painfully, in my view) using just two of them, as a good principle of modeling we should start out by contemplating all five.

The states, and the transitions among them, are:

1. $A$: Quiz $A$ is given. This transitions to $G$ ("Good") when a majority passes it. Presumably the chance that a majority passes is the same as the chance that one person passes it, $3/10$. (I say "presumably" because this "obvious" deduction depends on implicit assumptions, such as that the chances of passing are independent among people, and without those assumptions the deduction can be false.) Otherwise this transitions to $Z$ ("Bad") with probability $1-3/10 = 7/10$.

2. $B$: Quiz $B$ is given. This transitions to $G$ with probability $6/10$ and $Z$ with probability $1-6/10=4/10$.

3. $C$" Quiz $C$ is given. This transitions to $G$ with probability $9/10$ and $Z$ with probability $1-9/10=1/10$.

4. $G$ (a "good" day): This transitions to $A$, $B$, and $C$ with equal probabilities of $1/3$ each.

5. $Z$ (a "bad" day): This transitions to $A$ with probability $1$.

The transition matrix $\mathbb{P}$ for $(A,B,C,G,Z)$ therefore is

$$\left( \begin{array}{ccccc} 0 & 0 & 0 & \frac{3}{10} & \frac{7}{10} \\ 0 & 0 & 0 & \frac{3}{5} & \frac{2}{5} \\ 0 & 0 & 0 & \frac{9}{10} & \frac{1}{10} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{array} \right).$$

This is bipartite: the transitions alternate between states in $\{A,B,C\}$ and states in $\{G,Z\}$. By taking two transitions at once--which models what happens in the course of a single day--we can study the evolution of the distribution in states $\{A,B,C\}$ and, separately, the evolution in states $\{G,Z\}$. As expected, $\mathbb{P}^2$ decomposes into a direct sum. One block is for the $\{A,B,C\}$ transitions,

$$\mathbb{P}_{ABC} = \left( \begin{array}{ccc} \frac{4}{5} & \frac{1}{10} & \frac{1}{10} \\ \frac{3}{5} & \frac{1}{5} & \frac{1}{5} \\ \frac{2}{5} & \frac{3}{10} & \frac{3}{10} \end{array} \right)$$

and the other is for the $\{G,Z\}$ transitions,

$$\mathbb{P}_{GZ} = \left( \begin{array}{cc} \frac{3}{5} & \frac{2}{5} \\ \frac{3}{10} & \frac{7}{10} \end{array} \right).$$

From these matrices (in the usual purely mechanical ways) we deduce the stationary distributions $(5/7,1/7,1/7)$ for $(A,B,C)$ and $(3/7, 4/7)$ for $(G,Z)$: these are the (normalized-to-sum-to-unity) left eigenvectors with eigenvalues $1$. From them we immediately read off the answers to question 1 ($5/7$, the $A$ component of the first eigenvector) and question 2 ($3/7$, the $G$ component of the second eigenvector).

These are stationary distributions. Let's track what actually happens when we start, say, in state $A$ (initially, quiz $A$ is given). In this simulation, which used only the transition matrix $\mathbb{P}_{ABC}$, the majority failed $A$, so $A$ was given again; the majority failed again; finally the majority passed, and $B$ was randomly assigned; and so on. I have plotted the results for the first $100$ days:

After 100 days, quiz $A$ had been given $72$ times ($0.72$ of the total), quiz $B$ $17$ times ($0.17$), and quiz $C$ $12$ times ($0.12$). Clearly these realized frequencies do not equal the limiting probabilities of $5/7 \approx 0.714$, $1/7 \approx 0.143$, and $1/7$, respectively, but they are approximately the same.

After running a simulation for a million days(!), though, the counts happened to be $713446$, $143495$, and $143060$: each, as a fraction of the total, is considerably closer to the limiting probabilities.

Were we to re-run these simulations, the results would likely differ from the results I have obtained, and they would still differ from the limiting probabilities. However, the differences in proportions for the million-day simulation would be relatively small. It is only in this limiting, approximate sense that the stationary distributions of the Markov chain describe what really might happen as the chain evolves in the real world.