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 !



Computation of the mean of a random variable to estimate algorithm complexity
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.


