MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I made an incremental algorithm which I would like to evaluate the complexity. The algorithm works with a sliding window of size n.

To study the complexity, the window is considered full and the data present are ${x_{1},...,x_{n}}$ . They are assumed to be random, i.i.d, but with no assumption regarding their distribution. In particular, they are not necessarily bounded. Finally, the most recent data is $x_{n+1}$.

The complexity of the algorithm depends on the distance from $x_{n+1}$ to its “nearest lower value” $x_{l}$ whose index is $l=\max\left\{ k\in\{1...n\}\;st\;x_{k}<x_{n+1}\right\}$. The distance $d$ is then $d=n+1-l$.

$d$ is obviously a random variable, and I would like to determine its mean, which would give the algorithm complexity.

I first thought $d$ was a geometric variable with argument 1/2 since $P\left(x_{n+1}\geq x_{n}\right)=1/2$ (which I cannot prove either), so $E\left[d\right]=2$ but it is not the case. Indeed, $x_{n+1}$ and $x_{n}$ are not independent so $d$ does not follow a geometric law. Moreover, I did some experiments on Excel to compute $E\left[d\right]$ using different distributions and it seems it does not depend on the distribution of the $x_{i}$ but on $n$ (I can not post the image).

Below is a track I have tried to follow to determine $E\left[d\right]$ which proved unsuccessful:



$\begin{eqnarray*} P\left(d=k\right) & = & P\left(x_{n-k}<x_{n+1}\cap x_{n-k+1}\geq x_{n+1}\cap...\cap x_{n}\geq x_{n+1}\right)\\ & = & \forall\lambda_{1},\lambda_{2}\in\mathbb{R}\int_{\lambda_{1}<\lambda_{2}}P\left(x_{n-k}<\lambda_{1}\cap x_{n+1}\in\left[\lambda_{1};\lambda_{2}\right]\cap\bigcup_{j=n-k+1...n}x_{j}\geq\lambda_{2}\right)d\lambda_{2}d\lambda_{2}\\ & = & \int_{\lambda_{1}<\lambda_{2}}P\left(x_{n-k}<\lambda_{1}\right)P\left(x_{n+1}\in\left[\lambda_{1};\lambda_{2}\right]\right)\sum_{j=n-k+1...n}P\left(x_{j}\geq\lambda_{2}\right)d\lambda_{2}d\lambda_{2}\\ & = & \int_{\lambda_{1}<\lambda_{2}}F_{X}\left(\lambda_{1}\right)\left(F_{X}\left(\lambda_{2}\right)-F_{X}\left(\lambda_{1}\right)\right)\sum_{j=n-k+1...n}\left(1-F_{X}\left(\lambda_{2}\right)\right)d\lambda_{2}d\lambda_{2} \end{eqnarray*}$

But I can not go any further ? Do you have any idea ? Thanks in advance !

share|cite|improve this question
Is this the same question?… – kyticka Aug 18 '13 at 11:06
Yes it is. Sorry I'm quite new in using these sites, I just wanted to improve my question's visibility. Should I remove one version ? – Gim Aug 18 '13 at 12:46
I think it is fine to ask at both (if the question is on topic...). Just let everybody know the link to the repost, we do not want to answer it twice or check if there is repost elsewhere. – kyticka Aug 18 '13 at 15:59
up vote 1 down vote accepted

It seems to me that $P(d>k)=\tfrac1{k+1}$ for $k\in[0,n]$, so that $$E[d]=\sum_{k\ge 0}P(d>k)=H_{n+1}\simeq \ln n.$$ The reason is that the last $k+1$ terms of the sequence are in random order, so that the last one is the smallest among the last $k+1$ terms of the sequence with probability $P(d>k)=\tfrac1{k+1}$. When the last is the smallest of all I assume that $d$ is set equal to $n+1$. Does it make sense ?

For this to be valid, you need to assume that the probability distribution has no atoms, which is true for instance if it has a density of probability.

share|cite|improve this answer
Thanks a lot for your answer ! As this question is a duplicate with this one on math.stackexchange, I've also put a comment on the other one. – Gim Aug 19 '13 at 8:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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