Expected number of days for books to return to their original position 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?
 A: 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:


*

*$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$.

*$B:=$ We draw the same number

*$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:


*

*How can you make this a martingale process?

*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?

