Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Suppose I have a series $X_t$ of random variables, $t \in \mathbb{N}_0$. I am not sure if the following reasoning is sound:

Let $f(x)$ be a function of the random variables.

Let $E[f(X_t)]$ denote the expectation value of $f$ for variable $t$, and let $E[f(X_t) | X_{t-1} = x]$ be the expectation value of $f(X_t)$ when we already know that $X_{t-1}$ had value $x$. Think of the $X_t$ as states of a system and $f(x)$ some function of these states.

I have proven the following result:

Lemma 1

If $f(x) > f_c$ for a certain critical value $f_c$, then $$E[f(X_t) | X_{t-1} = x] \leq \alpha \cdot f(x)$$ for $0 < \alpha < 1$.

I now want to prove the following:

Lemma 2

Let $T \ge 0$. Then either there is a $t < T$ so that $f(X_t) \leq f_c$, or it holds $$E[f(X_T)] \leq \alpha^T \cdot E[f(X_0)].$$

Either there is a $t < T$ so that $f(X_t) \leq f_c$. Then we are done. Or there is no such $t$ and we can use the previous bound: $$E[f(X_T)] = E[E[f(X_T)|X_{T-1}=x]] \leq \alpha \cdot E[f(X_{T-1})]$$ I can apply the induction hypothesis to that and obtain the claim.

Problem Now, I feel a bit queasy: In the expectation value, would I also have to define some event $\xi_T$ as the event that there is no $t < T$ such that $X_t \leq f_c$, and condition on that or is that, via the induction, already taken care of?

share|cite|improve this question
The step $E[X^T] = E[E[X^T|X^{T-1}=x]] \leq \alpha \cdot E[X^{T-1}]$ does not make sense to me. $E[X^T|X^{T-1}=x]$ is already some deterministic function of $x$. Taking expectation doesn't get rid of $x$. This is not the tower property of conditional expectation. – GWu May 3 '11 at 23:38
Maybe it is just sloppy writing on my part? What I mean is this: $E[X^T] = \sum_k k \cdot P[X^T = k] = \sum_k k \cdot \sum_x P[X^T | X^{T-1} = x] = \sum_x E[X^T | X^{T-1} = x] = E[E[X^T|X^{T-1}=x]$ – Lagerbaer May 4 '11 at 0:11
@GWu, you might reconsider your comment. – cardinal May 4 '11 at 0:25
@Lagerbaer I see what you mean. So $E[X^T]=\sum_x E[X^T|X^{T-1}=x]P[X^{T-1}=x]$. If you want to use your previous result to conclude $E[X^T]\le \alpha E[X^{T-1}]$, you would need $X(\omega)>x_c$ for a.e. $\omega$. But the opposite of "there exists a $t<T$ so that $X^t\le x_c$" is "for all $t<T$, there's an $\omega$ such that $X^t(\omega)>x_c$". Unless I didn't understand your proven result, this is not enough for your purpose. – GWu May 4 '11 at 1:06
@Lagerbaer: When you write $X^T$, is that a power, or just a superscript? And when you write $\alpha^T$? – Henry May 4 '11 at 7:18
up vote 1 down vote accepted

The conclusion that $E(X_T)\le\alpha^TE(X_0)$ for $T$ large enough cannot hold. Forget about probability for a minute and consider a deterministic sequence $(x_t)$ whose dynamics is $x_{t+1}=x_t+1$ if $x_t< x_c$ and $x_{t+1}=\alpha x_t$ if $x_t\ge x_c$. After a while, the sequence $(x_t)$ wil oscillate between $\alpha x_c$ and $x_c+1$ hence it cannot converge to zero.

Coming back to the probabilistic setting, the typical behaviour that your condition implies is that $(X_t)$ is positive recurrent and that the sequence $(E(X_t))$ converges to a positive and finite limit.

share|cite|improve this answer
I don't claim that it holds "for $T$ large enough". I claim that it holds as long as the $X_t, t < T$ satisfy a certain condition. The purpose of this is to prove that this cannot go on for ever so I can prove a bound on the expected time $T$ for which that condition is violated. – Lagerbaer May 5 '11 at 18:13
The problem is that you mix deterministic statements (such as $E(X_t)\ge x_c$ or not, but for each $t$ this is either one or the other) and probabilistic ones (the event $[X_t\ge x_c]$ happens in general with a probability strictly between $0$ and $1$). To go further, you might want to state rigorously the result you want to prove. – Did May 5 '11 at 18:41
I have restated the problem and realized that my situation is a bit different – Lagerbaer May 5 '11 at 19:32
(1) Sorry but the new version is equivalent to the old one (replace $X_t$ by $f(X_t)$ everywhere). (2) In your proof, a faulty step is to write $E[f(X_T)] = E[E[f(X_T)|X_{T-1}=x]] \leq \alpha \cdot E[f(X_{T-1})]$. – Did May 5 '11 at 20:01
You still have not written the result you want to prove (precise hypothesis, conclusion). Believe me, you should try to. – Did May 5 '11 at 20:03

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.