# Tricky Probability question

Each morning a student takes one of the three books he owns from his shelf. The probability that he chooses book $i$ is $a_i$, where $0 < a_i < 1$ for $i=1,2,3$ and the choices on successive days are independent.

In the evening he replaces the book at the left-hand end of the shelf. If $P_n$ denotes the probability that on day $n$ the student finds the books in the order $1,2,3$, from left to right, show that, irrespective of the initial arrangement of the books, $P_n$ converges as $n\to\infty$ and find the limit.

-
is the solution for all six probabilities ie: a1a2/a2+a3 because then the probabilities don't actually sum to 1. shouldn't it be p123=a1a2/a2+a3, p213=a2a1/a1+a3,etc –  Johnny Byr Sep 4 '12 at 9:51

There are 6 different orders. For each pair of orders, you can work out the probability of transition from one to the other. For example, if today they are in order 123, then tomorrow they will be in order 123 or 213 or 312 with probability $a_1,a_2,a_3$, respectively. So this is a Markov chain with 6 states, and you can write down the $6\times6$ transition matrix.

Now, what do you know about Markov chains? What do you know about conditions on the transition matrix that guarantee the existence of a state to which the chain converges regardless of the initial conditions? And can you prove that the matrix we got in the 1st paragraph satisfies the conditions?

-

The following is not a proof of convergence, but it gives the value for all six limiting probabilities $p_{ikl}$ without solving an eigenvalue problem:

Draw a graph with six vertices $123$, $\ldots$, $321$. Each vertex gets an (unknown) probability $p_{ikl}$ assigned. There are directed edges with assigned weights $a_i$ connecting certain vertices. From this flowchart we get six equations of the form $$p_{123}=a_1(p_{123}+p_{213}+p_{231})\ ,\quad \ldots\ ,\quad p_{321}=a_3(p_{321}+p_{231}+p_{213})\ ,$$ and there is the seventh equation $p_{123}+\ldots+p_{321}=1$. Solving this system gives in particular $$p_{123}={a_1 a_2\over a_2+a_3}\ ,$$ as obtained by binn.

-
What is binn??? –  Salvattore Jan 24 '14 at 19:22
@Salvattore: "binn" is the person who has submitted an answer to this question on Sep 3 '12 at 12:40. At the moment this answer is the following next to mine. –  Christian Blatter Jan 24 '14 at 20:42

You can solve this directly using a 6x6 Markov chain with entries in $\lbrace{ 0, a_1, a_2, a_3 \rbrace}$, as I've done below using Wolfram alpha, but using the transpose of the matrix because wolfram alpha has a hatred of left (as opposed to right) eigenvectors. Here I am using x,y,z instead of a1,a2,a3 because I am lazy.

eigendecomposition of {{x, 0, x, x, 0, 0}, {0, x, 0, 0, x, x}, {y, y, y, 0, 0, 0}, {0, 0, 0, y, y, y}, {z, z, 0, 0, z, 0}, {0, 0, z, z, 0, z}}

You want the eigenvector corresponding to eigenvalue x+y+z, but Wolfram alpha also normalizes its eigenvectors in strange ways, so you need to normalize it so that its entries sum to 1 (i.e. sum to x+y+z). After doing this, I got $$\lim_{n \to \infty} P_n = \frac{a_1 a_2}{a_2 + a_3}$$

To show that this limit exists you might have to do something like showing that each state can reach each other state with positive probability; this is easy because you can reach state ijk from any state by picking book k then book j then book i, and each of these three independent events have positive probability as stated in the question.

-

You have an irreducible, aperiodic Markov chain on the set of all possible orders of books. Markov chain theory guarantees that your limit exists and equals $\pi(123)$, where $\pi$ is the unique invariant probability vector for the chain. In your notation, this turns out to be $$\pi(123)={a_1\over a_1+a_2+a_3}\,{a_2\over a_2+a_3}\,{a_3\over a_3}.$$ For an arbitrary ordering of books, we get the corresponding result $$\pi(ijk)={a_i\over a_i+a_j+a_k}\,{a_j\over a_j+a_k}\,{a_k\over a_k}.$$ A proof of this formula follows below.

More generally, let's denote the books as $A,B,C,\dots,Y,Z$ with corresponding probability of being chosen as $a,b,c,\dots,y,z$. Of course, $a+b+c+\cdots+y+z=1$.

Let's take a particular ordering, that I will label as $\beta$: $$\beta:=DJG\cdots CW.$$ The formula for the invariant probability of $\beta$ is the product $$\pi(\beta):={d\over d+j+g+\cdots+c+w}\,{j\over j+g+\cdots+c+w}\, {g\over g+\cdots+c+w} \cdots {c\over c+w}\, {w\over w}.$$

To check this, let's calculate the $\beta$th entry in the vector $\pi P$, that is, $\sum_\alpha \pi(\alpha) P(\alpha,\beta)$. The only states $\alpha$ from which it is possible to jump to state $\beta$ are those that look just like $\beta$ but with book $D$ moved. That is, $$\alpha\in\{ DJG\cdots CW, JDG\cdots CW, JGD\cdots CW, \dots, JG\cdots CWD\}.$$ For all such $\alpha$, the transition probability is simply $P(\alpha,\beta)=d$.

Therefore $$\begin{eqnarray*}(\pi P)(\beta)&=&d\sum_\alpha \pi(\alpha)\\ &=&{d\over d+j+g+\cdots+c+w} \sum_\alpha \pi(\alpha)\\ &=&{d\over d+j+g+\cdots+c+w}\, {j\over j+g+\cdots+c+w}\, {g\over g+\cdots+c+w} \cdots {c\over c+w}\, {w\over w}, \end{eqnarray*}$$ where, in the final step, we use the algebraic identity proved here.

The fact that $\sum_\gamma \pi(\gamma)=1$ can be proved by induction or using the following interpretation: $\pi(\gamma)$ is the probability that if I sample the books one at a time without replacement, they'd occur in the order $\gamma$.

-