What proportion of my friend's calzones were the best he had made so far?

Question

(True story:) A friend of mine was making a calzone and said it wasn't the best he had ever made. It got me wondering, what fraction of the calzones he has made were the best he had made at the time?

Assume he makes $n$ calzones, each with a quality chosen i.i.d. from a normal distribution (he never improves at all). Asymptotically, what proportion of the calzones he makes are the best he had made so far?

My intuition says it should be something like $1/\sqrt{n}$?

Answer 1

We make a calculation that answers your question, at least in the sense of expectation. Suppose that we make $n$ calzones in a row. Assume that for any two calzones $C_1$ and $C_2$, either $C_1$ is better than $C_2$ or the other way around (no ties).

For any $i$ from $1$ to $n$, let random variable $X_i$ be equal to $1$ if the $i$-th calzone is the best so far, and be equal to $0$ otherwise.

Let $Y=X_1+X_2+\cdots+X_n$. We find the expectation of $Y$, which by the linearity of expectation is $E(X_1)+E(X_2)+\cdots+E(X_n)$.

The probability that $X_i=1$ is $\dfrac{1}{i}$. This requires the assumption that one does not learn from experience, so all orders of quality among the first $i$ calzones are equally likely. Under that assumption, it follows that $$E(Y)=1+\frac{1}{2}+\cdots+\frac{1}{n}.$$

So $E(Y)$ is the $n$-th harmonic number $H_n$. It is well-approximated by $\ln n$.

The expected proportion of calzones that are "the best so far" is therefore $\dfrac{H_n}{n}$, which is approximately $\dfrac{\ln n}{n}$.

Answer 2

We may assume without loss of generality that there is never a time where he makes a calzone exactly the same.

We can then make the simplification to the problem that of the $n$ calzones, they are each labeled $1,2,3,\dots,n$ in terms of value.

Rewording the question, we could ask instead "In a permutation $\sigma\in S_n$, how many $i$ satisfy $\sigma(i)>\sigma(j)$ for all $j<i$?"

Let $X_i$ be an indicator random variable $X_i=\begin{cases}1&\text{if}~\sigma(i)>\sigma(j)~\text{for all}~ j<i\\ 0&\text{otherwise}\end{cases}$

We have then $X=\sum\limits_{i=1}^n X_i$ is the random variable counting how many "best so far" occur.

$\mathbb{E}[X]=\mathbb{E}[\sum\limits_{i=1}^n X_i]=\sum\limits_{i=1}^n \mathbb{E}[X_i]$ by linearity of expectation.

In calculating each of these, note that given whatever $i$ numbers appear, each permutation of said $i$ numbers are equally likely. If $X_i=1$, that implies that the largest of which will be at the end.

We have then $\mathbb{E}[X_i]=\frac{(i-1)!}{i!}=\frac{1}{i}$

So, $\mathbb{E}[X]=\sum\limits_{i=1}^n \frac{1}{i}=H(n)$ is the $n^{th}$ harmonic number.