Tallest Person Average Memory Updating?

We ran into a problem that was mentioned in an interview 2 days ago. Can you help us with any idea or hint?

A sequence of $n$ people, $\langle\,p_1,p_2,\dotsc p_n\,\rangle$ enter a room. We want to find the index, $i$, of the tallest person in the room. We have one variable for saving that index, which is updated when we see a person who
is taller than the maximum height so far. We want to calculate the average number of times our variable is updated. For simplicity, assume that $p$ is a permutation of $\{1, 2, \dotsc, n\}$

Short answer: it is close to $\ln n$. (i.e: natural logarithm)

How can one solve such a question?

Let $T(n)$ denote the total number of updates to the variable when $n$ people have entered the room. For example, with $n=3$ there will be $3!=6$ possible orders where the heights are $1, 2, 3$. Notice that once the height 3 person enters, no further updates will occur, so let's group the six possible arrangements by when the height 3 person enters:
$$\begin{array}{ccc}
\mathbf{3}21 & \mathbf{3}12 \\
1\mathbf{3}2 & 2\mathbf{3}1 \\
12\mathbf{3} & 21\mathbf{3} \\
\end{array}$$
For each of these arrangements, let's count the number of updates we have to make before we see the tallest person. In the two arrangements where the height-3 person arrives first, there are 0 earlier updates. In the second row above, there will be 1 update we have to make before the tallest person arrives and in the third row there will be either 1 or two updates before the tallest person arrives: arrangement $12\mathbf{3}$ will require 2 updates (one for the height-1 person and another for the height-2 person and the arrangement $21\mathbf{3}$ will require 1 update, for the height-2 person. In this $n=3$ case, then, we'll have $0+2+3$ total prior updates (0 in row 1, 2 in row 2, and 3 in row 3). To this add the $3!=6$ updates for the tallest person, giving us a total $T(3)=5+6=11$.

Now let's look at the general case for $n$ people. As we did above, let's group the $n!$ possible arrangements by when the height-$n$ person arrived. Denote this tallest person by $X$ and the rest of the people by dots. As we did above, we'll defer counting the last update until later.

We'll have these possibilities, each of which can happen in $(n-1)!$ ways:
$$\begin{array}{cc}
\text{arrival of }X & \text{arrangement}\\
1 & X\circ\dotsc\circ \\
2 & \circ X\circ\dotsc\circ \\
3 & \circ\circ X\circ\dotsc\circ\\
\dotsm & \dotsm \\
n & \circ\dotsc\circ X
\end{array}$$

For each row above we'll count the total updates before the tallest person arrives: Obviously if the tallest person arrives first, we'll have no prior updates, so the first row above will give a total count of 0. Each of the following rows will look like this:
$$
\underbrace{\circ\dotsc\circ}_k\ X\ \underbrace{\circ\dotsc\circ}_{n-1-k}
$$
The first set of $k$ dots can be filled with the heights $\{1, 2, \dotsc, n-1\}$ and there are $\binom{n-1}{k}$ ways to choose these sets, each of which will contribute $T(k)$ updates. The last set of $n-1-k$ dots can be filled with the remaining numbers in $(n-1-k)!$ ways. Thus each row in the table will contribute
$$
\binom{n-1}{k}T(k)(n-1-k)!
$$
to the total of prior updates. Adding these and including the $n!$ updates for the tallest person we have the recurrence relation
$$\begin{align}
T(n) &= n! + \sum_{k=1}^{n-1}\binom{n-1}{k}T(k)(n-1-k)!\\
&= n!+ \sum_{k=1}^{n-1}\frac{(n-1)!}{k!(n-1-k)!}T(k)(n-1-k)!\\
&= n!+ \sum_{k=1}^{n-1}\frac{(n-1)!}{k!}T(k)\\
&= n!+ (n-1)!\sum_{k=1}^{n-1}\frac{T(k)}{k!}\\
\end{align}$$
Divide both sides by $n!$ to get
$$
\frac{T(n)}{n!} = 1 + \frac{1}{n}\sum_{k=1}^{n-1}\frac{T(k)}{k!}
$$
and remember that the average number of updates, $U(n)=T(n)/n!$ which gives us.
$$
U(n) = 1 + \frac{1}{n}\sum_{k=1}^{n-1}U(k)
$$
Now we'll find a simple closed form for this:
$$\begin{align}
U(n) &= 1+\frac{1}{n}\sum_{k=1}^{n-1}U(k)\\
&= 1+\frac{1}{n}\left(\sum_{k=1}^{n-2}U(k)\right)+\frac{1}{n}U(n-1) &\text{pulling out the last term}\\
&= 1+\frac{n-1}{n}\left(\frac{1}{n-1}\sum_{k=1}^{n-2}U(k)\right)+\frac{1}{n}U(n-1)\\
&= 1+\frac{n-1}{n}(U(n-1)-1)+\frac{1}{n}U(n-1) & \text{definition of }U(n-1)\\
&= U(n-1)\left(\frac{n-1}{n}+\frac{1}{n}\right)+\left(1-\frac{n-1}{n}\right)\\
&= U(n-1) + \frac{1}{n}
\end{align}$$
Whaddya know? With $U(0)=0$ we just have
$$
U(n) = 1 + \frac{1}{2}+\frac{1}{3}+\dotsm+\frac{1}{n} = H(n)
$$
the $n$-th harmonic number, as it's known and it's also known that $H(n)$ is asymptotic to $\ln n$.

StackExchange Computer Science Q#40811, answer score: 4