How long until a draw is smaller than the last?

Question

Draw U1, U2, \dots independently from U(0,1). Stop at the first draw that is smaller than the one before it. Let N be the number of draws made when you stop. What is E[N]?

Accepted Answer

Step 1: the tail. You are still going after n draws exactly when the first n came out in strictly increasing order: P(N n) = P(U1 < U2 < \cdots < Un). For n i.i.d. continuous draws, all n! orderings are equally likely (ties have probability 0), and exactly one of them is increasing, so P(N n) = \frac{1}{n!}. Step 2: sum the tail. With P(N 0) = P(N 1) = 1 (a single draw cannot yet decrease), E[N] = \sum{n=0}^{\infty} P(N n) = \sum{n=0}^{\infty} \frac{1}{n!} = e \approx 2.718. So on average you make e draws before the sequence first goes down. Intuitively you almost always get at least two draw…

How long until a draw is smaller than the last?

Your answer

More Probability questions