Computation of the mean of a random variable to estimate algorithm complexity

Question

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:

$E\left[d\right]=\sum_{k=1...n}kP\left(d=k\right)$

and

$\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 !

Answer 1

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.