# How to show Martingale property for sum of $S_k-E(S_k)$-summands where $S_k$ is a function of two RV's

EDIT: new formulation of the question (old version below).

In a paper I found the statement that a certain sum $M_n =Y_1+\dotsb Y_n$ is a martingale, $Y_i=f (X_k, Z_k) - E ( f(X_k, Z_k) | X_k)$. (The new $S_k$ would be $:=f(X_k, Z_k)$ but I won't use this in the new formulkation of the question). We have $E(f(X_k, Z_k) | X_k) = E(f(X_k, Z_k) | \mathcal{F}^X_k)$ with $\mathcal{F}^X_k=\{X_1, \dots, X_k\}$. $Z_k$ is iid, and ($X_k$, $Z_k$) are independent for each $k$, f is differentiable.

How can I assert that this is a martingale?

Let me explain what I know so far about the filtrations: In the original question (see bottom) I thought I would have to use the natural filtration, which doesn't seem to fulfill the martingale property. Then @Gortaur suggested to use the filtration $\mathcal{F}^X_k$. I wondered why this is measurable with respect to the filtration (question) - it isn't. So to achieve $M_n$ being a martingale, we have to choose at least the filtration $D_k:=\mathcal{F}^{(X, Z)}_k$, but with this filtration the martingale property doesn't seem to hold (instead of $E(M_{k+1} | F_k)=M_k$, $E(Y_{k+1}|F_k)=0$ is sufficient):

$$E(Y_{k+1}|D_k)=E(f(X_k, Z_k) | D_k) - E(E( f(X_k, Z_k ) | \mathcal{F}^X_k ) | D_k) = f(X_k, Z_k) - E(f(X_k, Z_k)|\mathcal{F}^X_k)$$

And if the subtrahend would be $=f(X_k, Z_k)$ then it would have to be $\mathcal{F}^X_k$-measurable as a version of this conditional expectation which it would not be in general (consider Doob's Lemma for example in this answer to my other question)

Link to the paper: here . In the notation there, $X_k:=\hat{\theta_k}$, $Z_k:= \Delta_k$ and $f=\hat{g}_{ki} (\hat{\theta_k})=\frac{L(\hat{\theta_k} + c_k \Delta_k)-L(\hat{\theta_k} - c_k \Delta_k)}{2c_k \Delta_{ki}}$ (I assume that I can deal with the cancelation of noise terms via the paper's assumption $E(\epsilon_k^+ - \epsilon_k^- | F_k, \Delta_k) =0$ and put the noise-less $L$ directly for $f$)

The original question:

I want to show that a sum is a martingale sequence, $M_n=Y_1+\dots+Y_n$. I know that it is sufficient to show that $E(Y_{n+1} | M_n) =0$ a.s. Unfortunately, the sum is rather complicated, $Y_k=S_k - E(S_k|X_k)$, where $S_k=\frac{f(X_k, Z_k)}{Z_k}$. That means for $k=1$: $$E[Y_2 | Y_1] = E \left[ \tfrac{f(X_2, Z_2)}{Z_2} - E \left(\tfrac{f(X_2, Z_2)}{Z_2} \right | X_2) | \tfrac{f(X_1, Z_1)}{Z_1} - E \left(\tfrac{f(X_1, Z_1)}{Z_1} \right | X_1) \right] =0$$

I think I will have to use that $E(Y_k)=0$, and I could if I knew, that $Y_k$ independent from $Y_1+\dots +Y_{k-1}$. $Z_k$ is an independent sequence and $X_2$ is more or less $X_1+f(X_1,Z_1)$ but still, the intuition would be that how far $Y_1$ is away from it's expectation is independent from how far $Y_2$ is Q: How can I show that $M_n$ is a martingal sequence? Are my preliminary considerations right? Would you think with this way one can show martingale property? Do I have to impose additional conditions on $f$ ?

I am thankful vor every hint

Note: $f:R^m \times R \to R$, $(X_k (\omega) , Z_k(\omega) ) \mapsto f(X_k (\omega) , Z_k(\omega) )$

EDIT: I had forgotten, that in $Y_k$ we have the conditional expectation on $X_k$ instead of expectation per se.

-
@Gortaur: with $\stackrel{!}{=}0$ I wanted to say that the expression should be 0 –  Johannes L Sep 22 '11 at 11:05
Sorry, never seen this notation. –  Ilya Sep 22 '11 at 11:08
$X_{k+1}=X_k+f(X_k,Z_k)$ so $X_k$ is a Markov chain. The $Z_k$ are iid. $Z_k$ and $X_k$ are independent. Maybe there are general results when Markov chains are Martingale sequences? –  Johannes L Sep 22 '11 at 11:17
There are, like $g(X)$ is a martingale iff $\mathcal P g(x) = g(x)$ for all $x$, where $\mathcal P g(x) = \mathsf E_x[f(X_1)]$. In your question $S$ is already not necessary Markov. –  Ilya Sep 22 '11 at 11:27
@Gortaur What do you mean with $E_x$ in $E_x [g(X)]$? (You wanted to define $Pg(x):= E_x [g(X)]$, right? –  Johannes L Sep 22 '11 at 11:49

The statement of this question has witnessed so many patches and modifications that I find difficult to spot the exact hypotheses. Hence I will formulate a question which might or might not be the one that interests you, and I will answer it. The idea is that if this is not the question you wanted to ask, at least you will be able to set things straight starting from this answer.

Here we go. You are given two independent sequences $(X_n)$ and $(Z_n)$, which you further assume to be independent from each other. You consider some sigma-algebras $F_n$, such that, for every $n$, $(X_{n+1},Z_{n+1})$ is independent on $F_n$, and, for some given (sufficiently integrable) functions $f_n$, the random variables $Y_n=f_n(X_n,Z_n)-\mathrm E(f_n(X_n,Z_n)\mid X_n)$.

Note that $F_n$ might be the sigma-algebra generated by the random variables $X_k$ and $Z_k$ for every $k\leqslant n$, or the sigma-algebra generated by the random variables $X_k$ for every $k\leqslant n$, or any other sigma-algebra which fits the bill that $(X_{n+1},Z_{n+1})$ is independent on $F_n$.

The question is whether $\mathrm E(Y_{n+1}\mid F_n)=0$, almost surely.

The answer is yes and the proof is direct. Since $Y_{n+1}$ is measurable with respect to $(X_{n+1},Z_{n+1})$ which is independent from $F_n$, one knows that $\mathrm E(Y_{n+1}\mid F_n)=\mathrm E(Y_{n+1})$, almost surely. By the tower property, the expectations of the random variables $f_{n+1}(X_{n+1},Z_{n+1})$ and $\mathrm E(f_{n+1}(X_{n+1},Z_{n+1})\mid X_{n+1})$ are both $\mathrm E(f_{n+1}(X_{n+1},Z_{n+1}))$. Hence $\mathrm E(Y_{n+1}\mid F_n)=0$, almost surely.

Now, it is up to you: shoot...

Edit Allright, so you shot (see the comments)... As a result, the setting is still not entirely clear but seems to be closer to the following than to what I wrote above.

Consider independent random variables $X_0$ and $Z_n$ for $n\geqslant0$. Assume that $(Z_n)_{n\geqslant0}$ is i.i.d. For every $n\geqslant0$, define the random variables $$X_{n+1}=h(X_n,Z_n),\quad U_n=f(X_n,Z_n),\quad Y_n=U_n-\mathrm E(U_n\mid X_n).$$ Let us fix $n\geqslant0$, let $G_n$ denote any sigma-algebra such that $(X_n,Z_n)$ is $G_n$-measurable and $Z_{n+1}$ is independent on $G_n$, and let us prove that $\mathrm E(Y_{n+1}\mid G_n)=0$, almost surely.

Consider the function $g$ defined on the state space of every $X_n$ by $g(x)=\mathrm E(f(x,Z_1))$.

Then, on the one hand, $X_{n+1}=h(X_n,Z_n)$ is $G_n$-measurable, $Z_{n+1}$ is independent on $G_n$ and $U_{n+1}=f(X_{n+1},Z_{n+1})$, hence $\mathrm E(U_{n+1}\mid G_n)=g(X_{n+1})$. Now, $\mathrm E(U_{n+1}\mid G_n)$ is $X_{n+1}$-measurable hence $\mathrm E(U_{n+1}\mid X_{n+1})=\mathrm E(\mathrm E(U_{n+1}\mid G_n)\mid X_{n+1})=g(X_{n+1})$ and $\mathrm E(Y_{n+1}\mid G_n)=0$.

This proves that $(M_n)_{n\geqslant0}$ is an $(F_n)_{n\geqslant0}$ martingale, where $M_0=0$ and $M_n=Y_1+\cdots+Y_n$ for every $n\geqslant1$, as soon as $(F_n)_{n\geqslant0}$ denotes a filtration (hence $F_n\subseteq F_{n+1}$ for every $n\geqslant0$) such that each $F_n$ satisfies the conditions we put on $G_n$ above. This means that for every $n\geqslant0$, $F_n$ is independent on $\sigma(Z_{n+1})$ and $H_n\subseteq F_n$, where $$H_n=\sigma(X_0)\vee\sigma(Z_k;0\leqslant k\leqslant n).$$ An example of such a filtration is $F_n=H_n$ for every $n\geqslant0$, but each $F_n$ may contain some extraneous information.

-
$X_n$ is not an independent sequence, only $Z_k$ –  Johannes L Oct 5 '11 at 14:47
I guessed so. Question: what are exactly and precisely the independence assumptions you want to make? –  Did Oct 5 '11 at 14:49
$Z_n$ iid sequence, $X_k$ and $Z_k$ independent for all k. (The dependence of $X_k$ on its predecessor is of the kind $X_{k+1} = X_k + h(X_k, Z_k, \omega)$, $h$ evaluates $f$ at $X_k \pm Z_k$ with some extra noise (therefore $\omega$), in the notation of the paper $\hat{\theta}_{k+1}$ $= \hat{\theta_k} - a_k \hat{g_k} (\hat{\theta_k})$) And thank you a lot for your effort! –  Johannes L Oct 5 '11 at 15:08
Is $Z_n$ independent on $\{X_k;k\leqslant n\}$? –  Did Oct 5 '11 at 15:12
Indeed the exact dependence structure IS important. But in the situation you describe, it seems one can simply use the whole package $(r_k,Z_k)$ as $Z_k$ in my answer, modify the function $h$ accordingly, and apply my answer. As long as $X_{n+1}$ is a given function of $X_n$ and of plenty of other stuff and as long as this other stuff is independent of the whole past, you are done. Call me optimistic if you like but, where you see a confusing question, I see a solved one. –  Did Oct 7 '11 at 8:04

Some information about the processes $X,Z$ will be extremely useful. E.g. if $X,Z$ are iid and mutually independent then $Y$ is iid process with the zero mean, hence $M$ is a martingale random walk.

Edited: After a discussion with OP in the chat we clarified that $Y_k = S_k - \mathsf E[S_k|\mathcal F_k]$ for the filtration $\mathcal F_k = \mathcal F^X_k$. This result simply implies the martingale property of $(M,\mathcal F)$.

-
I don't have direct conditions on $X$. $X_{k+1}=X_k+f(X_k, Z_k)$. X_k and Z_k are independent and Z_k is iid. –  Johannes L Sep 22 '11 at 11:07

Also this is not a full answer, but just a try to expand Gotaurs comments, it would be too long for a comment.

I take $E_x(g(X))$ as conditional expectation $E(g(X)|x)$, did you mean this? And after your comment I have to show that $Pg(x)=g(x)$ for all x

Now if I assume that $S_k$ is Markov then use $g(S_k)=S_k -E(S_k|X_k)$ $$E_{s_k} [ g(S_k)] = g(s_k) \quad \forall s_k$$ $$E[S_k - E(S_k|X_k) | S_k=s_k] = s_k - E(s_k)$$ which is always true and I guess something of what I wrote doesn't make any sense at all

-