Expected Tries to Find the Maximum from $n$ normally distributed numbers

35 Views Asked by At

Consider a scenario where you write on $n$ pieces of paper a value obtained from a normal distribution $N(0,1)$. They're flipped over and arranged randomly. One-by-one you begin flipping over the pieces of paper. What is the probability that the $i$-th piece of paper you turn over is the maximum value? What is the expected number of flips until you flip over the maximum value?

My initial thought was that any piece of paper has a $1/n$ chance of being the largest value, and by inverting that to obtain expectation, one should expect to flip all $n$ pieces of paper to find the maximum value, but, this can obviously not be the correct answer.

1

There are 1 best solutions below

0
On

My initial thought was that any piece of paper has a $1/n$ chance of being the largest value

That's right.

and by inverting that to obtain expectation

Why would you do that? That applies only to the experiment where each try is independent of the others (geometric distribution), which is not the case here.

In this case, if $X$ is the number of tries, then $X$ follows a uniform distribution over the values $1, 2, 3 \cdots n$. Hence the expected value is $E[X]=\frac{n+1}{2}$