Expected number of days for books to return to their original position

Question

An ordered vertical stack of n books is on my desk. Every day, I pick one book uniformly at random from the stack and put the book on the top of the stack. What is the expected number of days before the books are back to the original order?

I don't even an idea how to start. Any hints?

Answer 1

Modelling the situation

Let us model this as having the sorted list of numbers $$ 1,2,...,n $$ and in the first step/the first day, we pick some number $i\in\{1,2,...,n\}$, find that number in the list and place it in front to have $$ i,1,2,...,n $$ except if $i=1$ which would give us back the original sorted list. After repeating the process we end up with some permutation of the numbers $1,2,...,n$. Given such a permuted list one may ask: "What is the fewest number of steps needed to sort the list?". The answer is as follows:

Let $(i,i+1)$ be the largest pair appearing in reverse order in the list. The only way we can reverse its order is if we bring $i$ to the front. Having done that, the pair $(i-1,i)$ must then be the largest pair appearing in reverse order in the list - unless $i=1$. So the shortest way to sort the list is by bringing $i,i-1,...,1$ to the front in that order. This takes $i$ steps.

So in this sense it is reasonable to define the minimal solution time for the list $\pi_t$ that is obtained after $t$ steps of the algorithm as $$\min(\pi_t)=\max\{i\ \mid\ (i,i+1)\text{ is reversed in }\pi_t\}$$

Note now, that the only way $\min(\pi_t)=i$ can be increased, is if we bring some $j>i+1$ to the front leading to $\min(\pi_{t+1})=j-1$. Whenever we bring $i+1$ or some $j<i$ to the front $\min(\pi_t)=\min(\pi_{t+1})=i$ remains unchanged. If we bring $i=\min(\pi_t)$ to the front we obtain $\min(\pi_{t+1})=i-1$. For brevity, let us say that we are in state $i$ if $\min(\pi_t)=i$. Then let $p(i,j)$ denote the probability going from state $i$ to state $j$ in the next step. Then we have for $i\geq 1$ that $$ p(i,j)= \begin{cases} \frac{1}{n}&\quad i+1\leq j\leq n-1\\ \frac{i}{n}&\quad j=i\\ \frac{1}{n}&\quad j=i-1\\ 0&\quad \text{otherwise} \end{cases} $$ Suppose we are considering the situation after the first book has been picked. So one day has already passed and we are in state $0,1,2,...,n-1$ with equal probability. Then let $E(i)$ denote the expected number of days remaining from now on, given that we are in state $i$. Then we can form the system of equations $$ \begin{align} E(0)&=0\\ E(1)&=p(1,0)(E(0)+1)+p(1,1)(E(1)+1)+...+p(1,n-1)(E(n-1)+1)\\ E(2)&=p(2,1)(E(1)+1)+p(2,2)(E(2)+1)+...+p(2,n-1)(E(n-1)+1)\\ E(3)&=p(3,2)(E(2)+1)+ṕ(3,3)(E(3)+1)+...+p(3,n-1)(E(n-1)+1)\\ &\vdots\\ E(n-1)&=p(n-1,n-2)(E(n-2)+1)+p(n-1,n-1)(E(n-1)+1) \end{align} $$ using the formula for $p(i,j)$ given above one may transform this into the matrix equation $$ \begin{pmatrix} \frac{1-n}{n}&\frac1n&\frac1n&...&...&\frac1n\\ \frac1n&\frac{2-n}n&\frac1n&...&...&\frac1n\\ 0&\frac1n&\frac{3-n}n&...&...&\frac1n\\ &\vdots&&\vdots\\ 0&0&0&...&\frac1n&-\frac1n \end{pmatrix} \cdot \begin{pmatrix} E(1)\\ E(2)\\ E(3)\\ \vdots\\ E(n-1) \end{pmatrix} = \begin{pmatrix} -1\\ -1\\ -1\\ \vdots\\ -1 \end{pmatrix} $$ Since we assumed that already one day had gone by, we should add $1$ to all the expectations, multiply them by the probability of entering the respective states on day one, and then add them together to have the expected stopping time as $$ E_n=\sum_{i=0}^{n-1}\frac1n(E(i)+1) $$

---

Here are a few numeric examples based on this: $$ \begin{align} E_3&=\frac13(0+1)+\frac13(6+1)+\frac13(9+1)\\ &=6\\ E_4&=\frac14(0+1)+\frac14(24+1)+\frac14(32+1)+\frac14(36+1)\\ &=24\\ E_5&=120\\ E_6&=720 \end{align} $$ And I feel like conjecturing that the expected stopping time for $n$ books is $n!$. It is not hard to show that $E_1=1!$ and $E_2=2!$.

---

UPDATE: I whipped up a quick and dirty Monte Carlo trial program to test if those figures are reasonable. Repeating the experiment about $1000$ times shows results that seem quite consistent with $n!$ for $n$ up to $8$, but since $n!$ grows so rapidly it quickly becomes infeasable to perform $1000$ trials of average size $n!$. For $n=9,10$ I was able to perform only a few trials within reasonable time, but those were also (roughly) consistent with the overall expectation of $9!=362880$ and $10!=3628800$ on average respectively. For lower values of $n$ like $n=5$ my program easily performed $100000$ trials with a bound of $20\cdot 5!$ days per trial to avoid the risk of unpleasently long running time, and this came out as $119.9655\approx 5!=120$ days on average. So indeed very consistent!

Answer 2

HINT:

We can think of this as drawing numbered balls from an urn (with replacement). Let $X_t=\text { Number of balls drawn in correct order at step $t$ }$, then $X_0=0$.

Now, each time we draw a ball, one of three events can happen:

1. $A:=$We draw the next ball in the sequence. E.g., if we've drawn $1,2,3$ then $A$ means we've drawn a $4$.
2. $B:=$ We draw the same number
3. $C$: We draw anything else.

Lets say $X_t=x$, then $X_{t+1}|A = x+1$, $X_{t+1}|B=x$ , and $X_{t+1}|C=0$

Since we are sampling with replacement $P(A)=\frac{1}{10},P(B)=\frac{1}{10},P(C)=\frac{8}{10}$ Thus, we've defined a discrete time stochastic process that either goes up by 1 wp 0.1 stays the same w.p. 0.1, or goes to to 0 w.p. 0.8.

Note that $E[X_t|X_{t-1}]=0.1(X_{t-1}+1)+0.1(X_{t+1})=0.1+0.2X_{t+1}\leq X_{t+1}$, so this is a supermartingale process.

Here's some next steps:

1. How can you make this a martingale process?
2. Can you think of a recursive way to find the expected value of the stopping time $\tau:=\{\inf t: X_t=10\}$, using properties of martingales and conditional expected values?