Randomly picking increasing numbers in $\{ 1, \dots, n\}$

Consider the following procedure (whose input is $N$) that picks increasing numbers from the set $\{ 1, \dots, N \}$ until it picks $N$:

i := 0
K_i := 1
while K_i < N
pick a number K_{i+1} from the set { K_i, ..., N } uniformly at random
i = i + 1


How many times do we expect the loop to be executed?

I expect $O(\log N)$ times myself: every round, we expect about half of the remaining numbers to be removed, which should result in $O(\log N)$ rounds. Unfortunately, I have no idea how to prove this. Markov's inequality trivially gives you that you will only throw away a constant fraction with constant probability, but if you wish this to happen $O(\log N)$ times in a row, your probability estimate goes to 0 as $N$ goes to infinity.

Apparently (while I was randomly looking through books for help) the above problem is quite suited to a Markov chain formulation, except I am not familiar with them and have no idea how to use that to get the expected value I want. When the book told me I was supposed to evaluate determinants through Cramer's rule and provided an example which was not at all clear to me, I gave up.

The above problem came up when analyzing a probable counterexample for an algorithm I have been working on. The actual probabilities involved are not uniformly random, but I think the above problem captures the essence of my problems, so an answer would probably help me enough to solve my own problem. If the number of rounds indeed increases as $N$ increases, then my (counter)example would indeed be a counterexample.

-

As you suspect, this problem is amenable to standard Markov chain theory.

Define $e(i)$ to be the expected number of steps until you hit $N$, starting at position $i=1,2,\dots ,N$. Then $e(N)=0$, and a first step analysis shows that $$e(i)=1+{1\over N-i+1}\sum_{j=i}^{N}e(j),\quad 1\leq i<N.\tag1$$ Solving this equation gives $$e(i)=1+1+{1\over 2}+\cdots+{1\over N-i}\approx \log(N-i).\tag2$$ Setting $i=1$, we see that the average number of steps required is roughly $\log(N)$.

Added: For a general Markov chain, it is not easy to find an explicit formula for $e(i)$, we are lucky that your Markov chain is simple enough. So now you may wonder how to get from (1) to (2).

One way is to calculate a few values of $e(i)$, and hope to spot a pattern that can be proven. Starting with large $i$ values, we have $$\begin{eqnarray*} e(N)&=&0\\ e(N-1)&=&1+{1\over 2}(e(N-1)+e(N))\implies e(N-1)=2\\ e(N-2)&=&1+{1\over 3}(e(N-2)+e(N-1)+e(N))\implies e(N-2)=2+{1\over 2}\\ &\dots&\mbox{etc.} \end{eqnarray*}$$ From this I guessed (2) and then checked that it actually solves (1). As I show below, I had seen similar problems before, so it's not like I had very deep insight.

References:

1. There is a very similar process in section 4.5.2. in the 10th edition of Introduction to Probability Models by Sheldon Ross. The difference is that he jumps backwards from $N$ to 1, and that he always jumps to a smaller state; there is no "staying put" as there can be in your model. Ross analyzed the expected time to hit state 1, and in his model gets $e(i)=\sum_{j=1}^{i-1}{1\over j}$ and hence finds that the expected time until absorption is about $\log(N)$, starting at state $N$.

2. Just for fun, and further practice, here is a similar question from the Problems section of the American Mathematical Monthly (#10788 (March 2000) and solution (November 2002)).

Imagine a random walk on the nonnegative integers that begins at 1 and that takes steps according to the following rules: When located at $n$, the next location is chosen uniformly from $\{0,1,\dots,n,n+1\}$. The walk ends when it first arrives at 0. What is the expected number of steps in the walk?

-
+1. Very nice. You might want to expand how one deduces the explicit formula for e_n from the first step analysis identity. – Did Sep 10 '12 at 19:26
This, or generating functions. – Did Sep 10 '12 at 20:48