Suppose I have a uniform random number generator producing a sequence of random numbers in the range $0…100$. I am trying to work out what the probability is that the $n^{th}$ number in this sequence is the greatest of any numbers seen so far.
My initial thoughts were that the probability of the first number being the greatest so far is obviously $1$. Since the expected value for any generated number is $50$, the probability of the second number being greater than this would be $0.5$. I could not see a way to apply this logic to the third number, but after performing a simple trial, it doesn't look like the answer is $1/2^n$, in fact, it looks more like the answer is simply $1/n$.
Can anybody explain this?
I also thought of two extensions to this question:
- What is the expected value for the number of times that the newly generated value was the largest seen so far in a sequence of length $n$? This part is in fact the real point of interest. For example, in the sequence 28, 26, 60, 93, 67, 71, 16, 49, 94, 91, the number of times a new value was the greatest is 4.
- How would all this be affected by a non-uniformly distributed number generator, for example if the numbers were normally distributed about $50$, with some defined variance?
Best Answer
Assuming no ties, the order statistics for the first $n$ numbers can take $n!$ equally probable patterns. $(n-1)!$ of these have the last as the largest number.
So the probability the $n$th number seen is the largest of the first $n$ is $\dfrac{(n-1)!}{n!}=\dfrac1n$