0
$\begingroup$

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?

  • 0
    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.2011-05-03
  • 0
    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]$2011-05-04
  • 0
    @GWu, you might reconsider your comment.2011-05-04
  • 0
    @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$X^t\le x_c$" is "for all $t$\omega$ such that $X^t(\omega)>x_c$". Unless I didn't understand your proven result, this is not enough for your purpose. – 2011-05-04
  • 0
    @Lagerbaer: When you write $X^T$, is that a power, or just a superscript? And when you write $\alpha^T$?2011-05-04
  • 0
    $X^T$ is a superscript and $\alpha^T$ is a power. I changed the sup- to subscripts to avoid this. That is the typical effect of "I have used that notation all the time so I intuitively now what it means, but know that someone points it out to me it really is ambigous" :)2011-05-05

1 Answers 1

1

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.

  • 0
    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.2011-05-05
  • 0
    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.2011-05-05
  • 0
    I have restated the problem and realized that my situation is a bit different2011-05-05
  • 0
    (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})]$.2011-05-05
  • 0
    You still have not written the result you want to prove (precise hypothesis, conclusion). Believe me, you should try to.2011-05-05
  • 0
    (1) Not exactly! The conditioning is on $X_t = x$, not on $f(X_t) = x. (2) Why? That is the Lemma I have proven elsewhere.2011-05-05
  • 0
    The new version has the same problem than the old one, which is the meaning of lemma 2. Call $B$ the event that there exists $t$f(X_t)\le f_c$ and (P) the property that $E(f(X_T))\le\alpha^Tf(X_0)$. You say that either $B$ or (P), what does that mean? To prove (P) you need to assume that $B$ is empty or rather, since stochasticity is involved, that $P(B)=0$. Nothing gives you this. To put it more directly: who is $x$ in the step I recalled in my (2)? – 2011-05-05
  • 0
    Ah. Your last question gave me the clue. By applying Lemma 1, I clandestinely assumed that the $x$ in the double expectation value was restricted to those states $x$ that satisfy $f(x) > f_c$, but of course this is not given...2011-05-05
  • 0
    Aaaahh... :-) $ $2011-05-05
  • 0
    Okay. I have an idea of how to fix my problem, but I will open this as a new question as changing it in this question would make your answer look unrelated.2011-05-05
  • 0
    Or maybe real quick in the comments: If my condition in Lemma 2 would not read "Either there is a $t < T$ such that $f(X_t) \leq f_c$", but rather it would read "Either there is a $t < T$ such that $E[f(X_t)] \leq f_c$", could I then just prove this via induction on t?2011-05-05