We first suppose that $X$ is the random variable equal to the number of MIN updates made by this algorithm to find the minimum element of a list $a_{1}, a_{2}, ..., a_{n}$ of n distinct numbers. Then $E(X)$ is the average number of updates made. We let $X_{i}$ be a random variable such that $X_{i}$ = $\begin{cases} & 1 \text{ if } a_{i} < min\\ & 0 \text{ otherwise} \end{cases}$

That is, $X_{i}$ has value 1 if and only if it is the smallest element seen so far, in which case there will be an update. Then it is clear that $ X = X_{1} + X_{2} + ... + X_{n}$. We can use the linearity of expectations to conclude that,

$E(X) = E(X_{1} + X_{2} + ... + X_{n}) = E(X_{1}) + E(X_{2}) + ... + E(X_{n}). $

Now, notice that the position of elements in the list is completely random, so for any given set of positions in the list, it is equally likely for any of them to be holding the smallest element. Hence,

$P(a_{1} < min) = 1$, because $min = \infty$

$P(a_{2} = min(a_{1}, a_{2})) = 1/2$

$P(a_{3} = min(a_{1}, a_{2}, a_{3})) = 1/3$

$.\\.\\.$

$P(a_{n} = min(a_{1}, a_{2}, ..., a_{n})) = 1/n$.

Expectation for a single $X_{i}$ can be calculated as: $E(X_{i}) = 1.P(X_{i} = 1) + 0.P(X_{i} = 0)$.

Then, their sum is: $E(X) = 1.(1) + 1. (1/2) + 1.(1/3) + ... + 1.(1/n)$ = $\sum_{i=1}^{n} 1/i$