To prove that this procedure is a Markov chain, we need to show that it possesses the Markov property: The probability of future states depends only on the current state, not on the past states.
Let's denote the state of the ordered list at time \(t\) by \(X_t\). To show that this is a Markov chain, we need to prove that \(P(X_{t+1} = j | X_t = i, X_{t-1} = i_{t-1}, ..., X_0 = i_0) = P(X_{t+1} = j | X_t = i)\).
First, we know that \(P(X_{t+1} = j | X_t = i)\) is the probability of the element on the list changing from state \(i\) to state \(j\). This will happen if the element requested at time \(t+1\) is the first element in the list \(j\), which is obtained from list of elements in state \(i\) by placing requested element on the front. The probability of this is given by the probability of the requested element, i.e. \(P(X_{t+1} = j | X_t = i) = P_{i_1}\), where \(i_1\) is the first element in list \(j\).
Now let's consider \(P(X_{t+1} = j | X_t = i, X_{t-1} = i_{t-1}, ..., X_0 = i_0)\). Since the list changes its order depending on the requested element, and given that the states are the ordering of the list, the future state \(X_{t+1}\) depends only on the current state \(X_t\) and the requested element at time \(t+1\). The past states \(X_{t-1}, ..., X_0\) do not have an impact on the future state, so \(P(X_{t+1} = j | X_t = i, X_{t-1} = i_{t-1}, ..., X_0 = i_0) = P(X_{t+1} = j | X_t = i)\).
Since both probabilities are equal, the Markov property holds, and thus, the given procedure is a Markov chain.
#b) Verify limiting probabilities for n = 3#
To verify that the given limiting probabilities are correct for n = 3, we'll use the intuitive formula provided: \(\pi(i_1, i_2, i_3) = P_{i_1}\frac{P_{i_2}}{1 - P_{i_1}}\frac{P_{i_3}}{1 - P_{i_1} - P_{i_2}}\).
There are 3! = 6 possible permutations for list elements (1, 2, 3):
1. \((1, 2, 3)\)
2. \((1, 3, 2)\)
3. \((2, 1, 3)\)
4. \((2, 3, 1)\)
5. \((3, 1, 2)\)
6. \((3, 2, 1)\)
Compute the limiting probabilities for these permutations:
1. \(\pi(1, 2, 3) = P_1 \frac{P_2}{1 - P_1} \frac{P_3}{P_3}\)
2. \(\pi(1, 3, 2) = P_1 \frac{P_3}{1 - P_1} \frac{P_2}{P_2}\)
3. \(\pi(2, 1, 3) = P_2 \frac{P_1}{1 - P_2} \frac{P_3}{P_3}\)
4. \(\pi(2, 3, 1) = P_2 \frac{P_3}{1 - P_2} \frac{P_1}{P_1}\)
5. \(\pi(3, 1, 2) = P_3 \frac{P_1}{1 - P_3} \frac{P_2}{P_2}\)
6. \(\pi(3, 2, 1) = P_3 \frac{P_2}{1 - P_3} \frac{P_1}{P_1}\)
For the probabilities to be limiting probabilities, the sum of these probabilities must be equal to 1. Let's check this:
$$\pi(1, 2, 3) + \pi(1, 3, 2) + \pi(2, 1, 3) + \pi(2, 3, 1) + \pi(3, 1, 2) + \pi(3, 2, 1) = 1$$
Cancel out the terms in the numerators and denominators, and see if they add up to 1:
$$P_1 + P_1 + P_2 + P_2 + P_3 + P_3 = P_1 + P_2 + P_3 = 1$$
Since the sum of the limiting probabilities equals 1, and we have been given that \(\sum_{1}^{3} P_{i}=1\), the intuitive formula provided for limiting probabilities is indeed correct when \(n = 3\).
