Expected number of updates of Maximum

Question

Let $L$ be a list of unique elements. Consider the following standard algorithm for finding the maximum value in $L$:

1. Initialize the current maximum of the list to be $m = −\infty$.
2. For $i= 1$ up through $n$,check to see if $L[i]>m$; if so, reset $m$ to be $L[i]$.
3. Output $m$.

Suppose we randomly permuate the elements of $L$ before running the procedure. Calculated the expected number of times $m$ will be reset in Step 2.

Answer 1

Let $X_i:=L[\pi(i)]$, where $\pi$ denotes the random permutation of $[n]$, $X_0\equiv-\infty$, and $M_i:=\max_{j\le i}X_j$. Then the expected number of resets is \begin{align} &\mathsf{E}\left[\sum_{i=1}^n 1\{X_i>M_{i-1}\}\right]=\sum_{i=1}^n \mathsf{P}(X_i>M_{i-1})=\sum_{i=1}^n\frac{1}{i}\approx \ln(n+1)+\gamma, \end{align} where $\gamma$ is the Euler's constant, because (thank's to the @Solomonoff'sSecret's comment), $$ \mathsf{P}(X_i>M_{i-1})=\frac{(i-1)!}{i!}=\frac{1}{i}. $$