Suppose you have a list of non negative numbers of size N. Now you calculate the maximum element in the list by scanning the list linearly and constantly updating a variable which has initial value of -1. We update the variable whenever we find a value greater than the variable. At the end of the scan the variable contains the maximum value in the list. Now if the array contains numbers which are distributed randomly, what are the expected number of times the variable is updated?



Expected value of swaps
Here is the answer when your numbers are independent and uniformly distributed in $[0,1]$.


Let $Y\_{i}$ be the i-th number in the list. Let $X\_{i}=\text{max}\_{j\leq i} Y\_{j}$. Let $Z\_{j}=1$ if $Y\_{i+1}\geq X\_{i}$ and $0$ otherwise. We can compute the expected value of $Z\_{n}$ (i.e., the probability that $Y\_{n+1}\geq X\_{n}$) by integrating the probability that $Y\_{n}\geq t$ against the probability density for $X\_{n}=t$, which is $nt^{n-1}dt$:


$E[Z\_{n}]=\int\_{0}^{1}(1-t)nt^{n-1}dt=1-\frac{n}{n+1}=\frac{1}{n+1}$


Now linearity of expectation tells us that the expected number of swaps is


$E[Z\_{1}+\ldots+Z\_{N}]=E[Z\_{1}]+\ldots+E[Z\_{N}]\approx \log(N)$


One imagines that other distributions can be done similarly.


