Expected value of swaps 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?
 A: 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.
A: David Cohen's answer of $log(N)$ holds for all continuous distributions.  By contrast, consider a discrete distribution with probability $p$ of 2, and probability $1-p$ of 1.  Then there is probability $p + (1-p)^n$ of only one swap (if the first element is 2 or if all the elements are 1), and $1 - p - (1-p)^n$ of two swaps (otherwise).  This gives an expected value of $2 - p - (1-p)^n$, which approaches $2-p$.
A: If all the $N$ values in the list are distinct (unlike Matt F.'s answer) and any order of them is equally likely, then the probability that the $n$th is higher than all the previous values, necessitating a swap, is $\frac1n$.  You do not need a continuous distribution of values or even independence.
So the expected number of swaps after considering $n$ values is $$\frac11+\frac12+\frac13+\cdots+\frac1n = H_n$$ i.e. the $n$th harmonic number with $H_n\approx \log_e(n) + \gamma+\frac1{2n}.$
The probability of having made $k$ swaps after considering $n$ values is $$P_n(k) = \frac1n P_{n-1}(k-1) + \frac{n-1}n P_{n-1}(k) = \frac{s(n,k)}{n!}$$ with the recurrence starting at $P_{0}(0) = P_{1}(1) = 1$ and where $s(n,k)$ is an unsigned Stirling number of the first kind. 
