General Statement

Suppose we have a sequence of identically distributed but dependent random variables $(X_n)_{n\in \mathbb{N}}$ which take values on $\{0,\dots,m\}$ for some $m \in \mathbb{N}$ (suppose for all $n$, $X_n \sim X$). Assume further that the $(X_n)_n$ are such that the correlation between $X_{n}$ and $X_{n+m}$ is independent on $n$ for all fixed $m$. We define the sequence $(Y_n)_n$ by: $$ Y_n := \sum_{k=0}^{m-1} \delta\{X_{n+k} > k\}, $$ where we use the notation $$\delta\{X_n > n\} := \begin{cases} 1 & \mbox{ if } X_n > n \\ 0 & \mbox{ otherwise} \end{cases}.$$ Note that the sequence $(Y_n)_n$ are also identically distributed and dependent (use the notation $Y$ with for all $n$: $Y_n \sim Y$). I have reason to believe that: $$ \mbox{Var}(Y) \leq \mbox{Var}(X) $$

My special case

In the case I'm interested in, $(X_n)_n$ is a Markov Process.


In case we only have $2$ possible values for $X$, say that it takes values in $\{0,m\}$, we have $\delta\{X_n > n\} = X_n/m$ and thus we find: $$ Y = \sum_{k=0}^{m-1} \frac{X_k}{m} $$ which incurrs: \begin{align*} \mbox{Var}(Y) &= \frac{1}{m^2}\sum_{k,l=0}^{m-1} \mbox{Cov}(X_k,X_l)\\ &= \frac{1}{m^2}\sum_{k,l=0}^{m-1} \mbox{Var}(X)\mbox{Corr}(X_k,X_l)\\ &\leq \mbox{Var}(X). \end{align*} we see that the statement indeed holds, moreover we didn't use that $(X_n)_n$ is a Markov Chain. In the more dimensional case I have done simulations which all seem to be indicating that this inequality seems to hold in general but I haven't been able to prove it.

  • $\begingroup$ why are $Y$'s identically distributed? $\endgroup$ Commented Jan 24, 2017 at 14:30
  • $\begingroup$ I added a condition on $(X_n)_n$, namely that the correlation between $X_n$ and $X_{n+m}$ doesn't depend on $n$. $\endgroup$
    – HolyMonk
    Commented Jan 24, 2017 at 14:33
  • $\begingroup$ It still seems to be not enough. Assume That $m=3$, $X,T,Z$ are independent i.i.d and your sequence is $ZTT\,TZX\,ZXT\,TZX\, ZXT\,...$. Then $X_n$ and $X_{n+3}$ are always independent, but $Y_1$ and $Y_3$ may have different distribution. $\endgroup$ Commented Jan 24, 2017 at 14:41
  • $\begingroup$ I don't want to have that $X_{n+m}$ and $X_n$ are independent, but I want to have that for every $m$, the map $n \mapsto \mbox{Corr}(X_{n+m}, X_n)$ is constant $\endgroup$
    – HolyMonk
    Commented Jan 24, 2017 at 15:05
  • $\begingroup$ The idea is to work with an ergodic process and view this far enough in time that we can assume that convergence to the stationary distribution has already occurred. $\endgroup$
    – HolyMonk
    Commented Jan 24, 2017 at 15:06

1 Answer 1


$\newcommand{\E}{\mathbb{E}}$ You practically answered your own question.

Denote by $A_k$ the event "$X_0 > k$". Then $X_0=\sum_{k=0}^{m-1} \delta(A_k)$.

Denote by $B_k$ the event "$X_k > k$". Then $Y_0=\sum_{k=0}^{m-1} \delta(B_k)$.

$A_k$ and $B_k$ have the same probabilities, hence $\E[X_0]=\E[Y_0]$. We need to show that $\E[X^2_0]\ge \E[Y^2_0]$.

But $\E[\delta(A_k)\delta(A_l)]\ge \E[\delta(B_k)\delta(B_l)]$ simply because $A_k \subset A_l$ (for $k<l$). In other words the correlation is maximized when the sequence of sets is monotone.

The only requirement is that the $X_n$'s are identically distributed, they sequence doesn't have to be shift invariant. In the case of Markov chain, you need to start from the stationary distribution.

  • $\begingroup$ Nice, didn't think of that trick with $X_0$ $\endgroup$
    – HolyMonk
    Commented Jan 24, 2017 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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