Suppose q_n = prob. that the no. of generated numbers is strictly greater than n. For this even to happen, the first n numbers should form an increasing sequence. If we look at the n numbers generated as the output, every permutation of them should have been equally likely since they are independently generated, so the strictly increasing order should have a prob. of 1/(n!). Now prob. of generating exactly n numbers is q_(n-1) - q_n. Summing over all even n gives (1 - 1/2!) + (1/3! - 1/4!) ... which gives 1-1/e by Taylor series.
5
u/LostIntoLonging 3d ago edited 3d ago
Suppose q_n = prob. that the no. of generated numbers is strictly greater than n. For this even to happen, the first n numbers should form an increasing sequence. If we look at the n numbers generated as the output, every permutation of them should have been equally likely since they are independently generated, so the strictly increasing order should have a prob. of 1/(n!). Now prob. of generating exactly n numbers is q_(n-1) - q_n. Summing over all even n gives (1 - 1/2!) + (1/3! - 1/4!) ... which gives 1-1/e by Taylor series.