I have sequence of random variables defined by the following recursion:

$$X_{n+1} = X_n+\begin{cases} \alpha(S_n - X_n), \text{ if } S_n > X_n \\ \beta(S_n - X_n), \text{ if } S_n < X_n, \end{cases}$$ where $0<\beta < \alpha <1$ are constants, $(S_n)$ are i.i.d with known distributions. Also, $S_n$ independent of $\sigma(X_1, X_2,\dots, X_n)$ and $X_ 0 = 0.$

Initially, I asked about the convergence/limiting distribution of $X_n,$ but after doing some research, I realize that it is generally considered a very difficult problem - to obtain explicit distribution/asymptotics.

Therefore, I want to ask following questions with increasing orders of difficulties (according to my very limited probability theory knowledge.)

1) Can we at least prove that it has a limiting distribution? It looks like one can formulate this as a general state space Markov Chain but there do not seem to be an abundance of sources on this topic. Probability by Durrett has a brief chapter on it and he mentions that discrete Orstein- Uhlehnbeck process: $$V_{n+1} = \theta V_n+\xi_n$$ is an example of a discrete time, general state space Markov Chain. However, most of the resources I could find on the internet refers to the continuous one and as such my hope of modifying proofs for OU did not pan out.

2) If there is a limiting distribution, what kind of qualitative results can I hope to achieve? For example, one has the following for the expected value: $$\mathbb{E}[X_{n+1}] = \mathbb{E}[X_n](1 - \beta ) + \beta\mu + ( \alpha - \beta)\mathbb{E}[\delta_n\mathbb{1}_{\delta_n >0}],$$ where $\delta_n = S_n - X_n,$ and $\mu = \mathbb{E}[S_n].$ But then, the issue I am having is manipulating: $$P(S_n - X_n > t|S_n > X_n)$$, which will come from the last term.

I will greatly appreciate if anyone has some ideas or point me to a helpful source.

Simulation: I attach some simulations that seem to suggest that there is a bounded, limiting distribution.

R ~ Skew normal

  • $\begingroup$ I think it's a Markov Chain. Why wouldn't it be? It is certainly true that $X_{n+1}$ is dependent on $X_{n-1}$ ("implicitly" as you said), but the Markov property is that such a dependence disappears when we also condition on $X_n$. I.e., if you know $X_n$, then also knowing $X_{n-1}$ gives you no additional info w.r.t. distribution of $X_{n+1}$, which is the case here. $\endgroup$
    – antkam
    Nov 7, 2019 at 3:53
  • $\begingroup$ @antkam I see that makes sense. $\endgroup$
    – dezdichado
    Nov 7, 2019 at 4:47
  • $\begingroup$ @antkam OP said "$S_n$ is independent of $X_n$", so it may very well be that $S_n$ is not independent of $X_{n-1}$. $\endgroup$ Nov 16, 2019 at 23:26
  • $\begingroup$ @mathworker21 - oh you are right! I had assumed $S_n$ is independent of all $X_j$'s. But if $S_n$ depends on $X_{n-1}$ then this is indeed not a Markov Chain. Maybe the OP can clarify? $\endgroup$
    – antkam
    Nov 17, 2019 at 1:03
  • 1
    $\begingroup$ @NapD.Lover, you are right the upper bound is for positive means. There is similar lower bound for negative means etc. $\endgroup$
    – dezdichado
    Nov 24, 2019 at 3:07

2 Answers 2


1. Here is a mild condition on the distribution of $S_n$'s that guarantee the existsence of limiting distribution.

Proposition. Assume that $\sum_{n=0}^{\infty} (1-\beta)^n |S_n| < \infty$ holds almost surely. Then $(X_n)_{n\geq 0}$ has a limiting distribution.

Proof. For each $s \in \mathbb{R}$, define $f_s : \mathbb{R} \to \mathbb{R}$ by

$$ f_s(x) = \begin{cases} \alpha s + (1-\alpha) x, & \text{if $s \geq x$}, \\ \beta s + (1-\beta) x, & \text{if $s \leq x$}. \end{cases} $$

This function allows to rewrite the recursive formula as $ X_{n+1} = f_{S_n}(X_n) $, and so,

$$X_n = (f_{S_{n-1}} \circ \cdots \circ f_{S_0} )(0).$$

But since $S_n$'s are i.i.d., this implies

$$X_n \stackrel{\text{law}}{=} X'_n := (f_{S_{0}} \circ \cdots \circ f_{S_{n-1}} )(0).$$

In light of this, it suffices to prove that $(X'_n)_{n\geq 0}$ converges in distribution. Given the assumption, we actually prove that $(X'_n)_{n\geq 0}$ converges almost surely. Indeed, note that

$$|f_s(y) - f_s(x)| \leq (1-\beta)|y - x|$$

uniformly in $s, x, y \in \mathbb{R}$. Applying this to

$$ X'_{n+1} - X'_n = (f_{S_{0}} \circ \cdots \circ f_{S_{n-1}} )(f_{S_n}(0)) - (f_{S_{0}} \circ \cdots \circ f_{S_{n-1}} )(0), $$

we get

$$ \sum_{n=0}^{\infty} \left| X'_{n+1} - X'_n \right| \leq \sum_{n=0}^{\infty} (1-\beta)^n \left|f_{S_n}(0) - 0\right| \leq \sum_{n=0}^{\infty} (1-\beta)^n \alpha \left|S_n\right|. $$

Together with the assumption, the desired conclusion follows. $\square$


  1. The assumption of the proposition is rather arbitrary but still moderately general. For instance, it is satisfied whenever $S_0$ is integrable.

  2. Although the original problem is formulated with the initial condition $X_0 = 0$, this is not important. Indeed, the recurrence relation teaches us that $(X_n)$ forgets its initial condition at least exponentially fast, hence the question on the existence of limiting distribution does not depend on $X_0$.

    To see this, let $X_n(\xi) = (f_{S_{n-1}} \circ \cdots \circ f_{S_0})(\xi)$ denote the sequence given by OP's recurrence relation with the (possibly random) initial condition $X_0 = \xi$. Then

    $$ |X_n(\xi_2) - X_n(\xi_1)| \leq (1-\beta)^n|\xi_2 - \xi_1|. $$

2. Assume that $(X_n)$ converges in distribution to a random variable $X$. Let $S$ be identically distributed as $S_0$ and independent of $X$. Then the followings are easy consequences.

  • If $S$ is supported on an interval $I$, then so is $X$.
  • If $S$ is integrable, then so is $X$. More precisely, we have $\mathbb{E}[|X|] \leq \frac{\alpha}{\beta}\mathbb{E}[|S|]$. Also,

    $$ \mathbb{E}[X] = \mathbb{E}[S] + \frac{\alpha-\beta}{\alpha+\beta}\mathbb{E}[|X-S|] $$

    In particular, if $S$ is non-degenerate, then we have $\mathbb{E}[X] > \mathbb{E}[S]$.

  • $\begingroup$ Were you applying inequality for $\vert f_s(y) - f_s(x) \vert$ on $\left\vert f_{S_{n+1}}(X_{n+1}) - f_{S_n}(X_n) \right\vert$? $\endgroup$ Nov 24, 2019 at 17:32
  • $\begingroup$ @XiaohaiZhang, I updated my answer to clarify that step. $\endgroup$ Nov 24, 2019 at 20:15
  • $\begingroup$ I am not sure about your reversing order of $X_n$s. But I don't think $\sum \vert X_{n+1} - X_{n} \vert$ would be finite. Take for example, a simple random walk for $S_n$. Then the sequence values of $X_n$ will be pulled to walk between +1 and -1. If $X_n$s go to -1 for an extended period of time/steps, and then comes $S_n=+1$, you will have a sizable up move in the value of $X_n$ much larger than the previous steps. The increments never diminish and that is why I don't think it converges a.s. or in probability. $\endgroup$ Nov 24, 2019 at 21:11
  • 1
    $\begingroup$ @XiaohaiZhang, Reversing the order only gives the 'distributional identity', i.e., $$ X_n=(f_{S_{n-1}} \circ \cdots \circ f_{S_{0}} )(0) \stackrel{\text{law}}= (f_{S_{0}} \circ \cdots \circ f_{S_{n-1}} )(0)=X'_n. $$ Although this reversal changes the joint distribution, i.e., $(X_n)$ has not the same joint distribution as $(X'_n)$, this does not affect the convergence in distribution which only cares marginal distributions of $X_n$'s. $\endgroup$ Nov 24, 2019 at 21:47
  • 1
    $\begingroup$ @XiaohaiZhang, Also, this is not the same as simple random walk. Working with the case $\alpha=\beta$, we have $$X_n = \alpha \sum_{k=0}^{n-1} (1-\alpha)^{k} S_{n-1-k}. $$ Note the geometric weights. And although $(X_n)_{n\geq 0}$ converges neither a.s. nor in probability, the reversals $(X'_n)_{n\geq 0}$ given by $$X'_n = \alpha \sum_{k=0}^{n-1} (1-\alpha)^{k} S_{k} $$ (which has the same distribution as $X_n$ for each given $n$) converges a.s. under quite mild conditions on $S_n$'s. $\endgroup$ Nov 24, 2019 at 21:58

I will take my shot here. However, the post won't fully answer the question, and it lacks rigor in later parts.

Let's first examine a simpler claim that will be a basis for later discussion.

Claim: Let $S_n$ be i.i.d. and has symmetric distribution with non-negative characteristic function values. $Z_{n+1}=Z_n + \gamma (S_n - Z_n)$ be a sequence of random variable with $Z_0 = 0, 0 < \gamma < 1$. Then $Z_n$ converges in distribution.

Proof: Let the characteristic function of $S_n$ be $\psi(t)$. Since $S_n$ is symmetric, $\psi(t)$ takes real values and $\vert \psi(t) \vert \le 1$. The characteristic function of $Z_n$ is denoted by $\phi_n(t)$. Then $\phi_0(t) = 1 $, and $$ \phi_{n+1}(t)=\phi_n((1-\gamma)t)\cdot\psi(\gamma t). $$ Recursively applying the last equation leads to $$ \phi_n(t) = \prod_{k=0}^{n}\psi\left( \gamma{(1-\gamma)}^kt \right). \quad (1) $$ Note the value of $\phi_n(t)$ is always non-increasing and lower bounded by zero for any $t \in \mathcal{R}$. Hence $\phi_n(t)$ converges to a characteristic function $\phi(t)$ pointwise, and $Z_n$ converges in distribution.

Note: I think it is possible to weaken the requirements on the characteristic function values of $S_n$. But it will require more work.

Coming back to the original problem, let's first reformulate it into an equivalent format.

Reformulation: The original recursion is equivalent to $$ X_{n+1} = \max\{(1-\alpha)X_n + \alpha S_n, (1-\beta)X_n + \beta S_n\}. $$

Proof: Recall $0 < \beta < \alpha < 1$. The above is true because if $S_n > X_n$, then $\alpha(S_n - X_n) > \beta(S_n - X_n)$, and if $S_n \le X_n$, then $\alpha(S_n - X_n) \le \beta(S_n - X_n)$. The original recursion always takes the maximum of the two branches.

Unfortunately things from here below become a bit fuzzy.

Conjecture 1: $X_n$ does NOT converge a.s. or in probability.

Justification: Both $(1-\alpha)X_n + \alpha S_n$ and $(1-\beta)X_n + \beta S_n$ can be viewed as moving average between $X_n$ and $S_n$ with two different coefficients. Assuming $S_n$ is non-degenerate, the sequence $X_n$ can never settle at a converging point, since the next averaging will make a non-diminishing move proportional to $\alpha$ or $\beta$. This is most likely true since most Markov process do not converge in probability.

Conjecture 2: $X_n$ does NOT converge in distribution.

Justification: Equation (1) shows the limiting characteristic function, hence the distribution as well, is affected by the parameter $\gamma$. So recursion patterns $(1-\alpha)X_n + \alpha S_n$ and $(1-\beta)X_n + \beta S_n$ converge to two different distributions since $\alpha \ne \beta$. Given that $S_n$ is non-degenerate, we always have non-zero probability in following one limiting path and suddenly switching the recursion patterns, hence the limiting distribution will oscillate between different distributions. I am less confident in this conclusion.

Finding the stationary distribution if there is one:

I actually think this might be tractable computationally and analytically for simple cases.

  • Determine the domain of the distribution. Domain is limited by the minimum value and maximum value of $S_n$ (because $X_n$ are moving averages of $S_n$ starting from zero with switching). This helps in computation. Even if range of $S_n$ is not bounded, one can still truncate it to use a reasonable approximation.
  • Establish a functional equation based on the simple fact that the distributions of post and pre Markov transition are the same. Once the equation is established, analytical solutions can be sort for $S_n$ with simple distributions. An iterative algorithm can be used to compute the stationary distribution for $S_n$ with more complicated distributions.
  • $\begingroup$ I can't get through second sentence. are you saying proof won't lack rigor in later parts? $\endgroup$ Nov 23, 2019 at 22:10
  • $\begingroup$ @mathworker21 Clarified. Thanks $\endgroup$ Nov 23, 2019 at 22:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .