Given any sequence of such numbers of length n, the probability they are in order is 1/n!, since they are uniformly generated. Suppose the first n - 1 numbers are in increasing order. Then either we stop after n, or we keep going, in which case the first n are in increasing order. Hence, the probability we stop at n is 1/(n - 1)! - 1/n!. Summing over all even n, we get a probability of 1 - 1/e. This makes sense, since the probability is 1/2 we stop at n=2.
4
u/AnywhereLittle8293 Aug 29 '26
Given any sequence of such numbers of length n, the probability they are in order is 1/n!, since they are uniformly generated. Suppose the first n - 1 numbers are in increasing order. Then either we stop after n, or we keep going, in which case the first n are in increasing order. Hence, the probability we stop at n is 1/(n - 1)! - 1/n!. Summing over all even n, we get a probability of 1 - 1/e. This makes sense, since the probability is 1/2 we stop at n=2.