2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Other continuous distributions need not be done similarly; they can be done the same! The log(N) result is the same for any continuous distribution, since any Z can be transformed to a uniform distribution via its cdf, and this preserves its ordering. $\endgroup$ – Matt F. Feb 12 '14 at 2:06
  • $\begingroup$ Thanks for your reply. I have a question regarding your answer - Could you explain how the probability density of $X_n$ = t is $nt^{n-1}dt$ ? Also should it by $Y_{n+1} \geq t$ in line 3? $\endgroup$ – Piyush Feb 12 '14 at 3:28
  • $\begingroup$ Yes, it should be $Y_{n+1}\geq t$. You can find the probability density by just taking the derivative of the cumulative density function $P(X_{n}\leq t)$ (because this function is smooth). $\endgroup$ – David Cohen Feb 12 '14 at 4:24
  • $\begingroup$ Could you explain how do I find the cumulative density function $P(X_n \leq t)$ ? $\endgroup$ – Piyush Feb 12 '14 at 19:16
  • $\begingroup$ I understood the CDF part but how does the linearity of expectation calculation give logn ? Shouldn't it give n/(n+1) ? $\endgroup$ – Piyush Aug 19 '15 at 22:32
2
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you explain your formula for $P_n(k)$ ? $\endgroup$ – Piyush Feb 18 '14 at 22:54
  • $\begingroup$ @elixir24: The probability of having made $k$ swaps after considering $n$ values is the sum of the probability of having to make a swap of the $n$th value times the probability of having already made $k-1$ swaps plus the probability of not having to make a swap of the $n$th value times the probability of having already made $k$ swaps. (I seem to have $k$ where I should have $n$, so I shall edit my answer) $\endgroup$ – Henry Feb 18 '14 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.