# Expectation values, induction and conditioning

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)].$$

Proof
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?

-
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

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.
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
(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