Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I try to adopt Wald's equation to a slightly more complex problem. In fact, after a full day, I found some solution now, but it has a confusing argument in the middle. Perhaps somebody can help me at that point? Perhaps I am even wrong with my conjecture? If the conjecture holds, it is a quite helpful tool.

Let $(X_n)_{n\in\mathbb{N}}$ be a series of real-valued random variables from within $[-c, c]$ for some constant $c$. They are neither independent nor identically distributed. However, there are only two different types of distributions: $A$ and $B$. Whether $X_i$ belongs to $A$ or $B$ depends on the realization of $X_i$ and all other $X_j$'s, thus, there is no fixed assignment to these classes, i.e., each realization also defines some random labeling $\ell: \{X_1, X_2, \ldots, ...\} \rightarrow \{A, B\}$, where I write $X_i \in A$ for $\ell(X_i) = A$. For example, it might be that $X_1, X_4, X_5, ... \in A$ and $X_2, X_3, X_6, ... \in B$, while for another realization the $X_i$'s might be mapped totally different. Further, let $T$ be a stopping time for $(X_n)_{n\in\mathbb{N}}$. Thus, the event $\{T \geq j\}$ does only depend on $X_1, \ldots, X_j$, but is independent of $X_{j+1}, \ldots$.

I am interested in an upper bound on $\mathbb{E}\left(\sum_{i=1}^T X_i\right)$. Since the $X_i$'s are not i.d., it is not possible to apply Wald's equation to get something like $\ldots = \mathbb{E}(T)\mathbb{E}(X)$.

For deriving a similar result, I already have that $\mathbb{E}\left(X|X \in A\right) < -2$ and $\mathbb{E}\left(X|X \in B\right) < 1$. Further, I have that $|B_T| \leq |A_T|$, with $A_T := \{X_i \in A | i=1,\ldots,T\}$, and $B_T$ analogous. Thus, it is intuitively clear, that an upper bound should be given by $\mathbb{E}\left(\sum_{i=1}^T X_i\right) < -\mathbb{E}\left(T\right)/2$, since any positive contribution ($<1$) of some random variable in $B_T$ is overcompensated ($<-2$) by some other in $A_T$, and we have that $|A_T|=|B_T|=T/2$ in the worst case. In fact, I suppose that it holds that

conjecture: $\mathbb{E}\left(\sum_{i=1}^T X_i\right) < \mathbb{E}\left(|A|\right) \cdot \mathbb{E}\left(X|X \in A\right) + \mathbb{E}\left(|B|\right) \cdot \mathbb{E}\left(X|X \in B\right)$.

It is easy to show a similar result for fixed $T$, but things get very complicated for $T$ being a stopping time.

So, perhaps you already know a solution to this? Then please share your knowledge!

Here is my approach incl. the confusing detail: With $N_a = |A_T|$ and $N_b = |B_T|$ the random variables with $N_a + N_b = T$, and from above $N_b \leq N_a$, we have that:

$\mathbb{E}\left(\sum_{i=1}^T X_i\right) = \mathbb{E}\left(\sum_{i=1}^{N_a} X_{a(i)} + \sum_{i=1}^{N_b} X_{b(i)}\right) = \mathbb{E}\left(\sum_{i=1}^{N_a} X_{a(i)}\right) + \mathbb{E}\left(\sum_{i=1}^{N_b} X_{b(i)}\right)$, where the indices $a(i)$ and $b(i)$ partition the indicies $1, 2, \ldots$ in order corresponding to $A$ and $B$, especially, $\{X_1, \ldots, X_T\} = \{X_{a(1)}, \ldots, X_{a(N_a)}\} \dot\cup \{X_{b(1)}, \ldots, X_{b(N_b)}\}$.

Now I think that the following argument is correct, but I have some doubts about it (and not the deep understanding or a formal method to prove it):

claim: $N_a$ is independent of $(X_{a(N_a)+i})_{i\in\mathbb{N}}$.

(same for $N_b$).

If this argument is correct, then we can just apply Wald's equation for the both sums independently, and get the final result.

But: I somehow get lost in accepting that this independency holds, since it might be that for example $T \gg a(N_a)$. Thus, $N_a$ somehow also depends on the fact that $X_i \in B$ for $i \in \{ a(N_a)+1, \ldots, T\}$. But, on the other hand side, this dependency is totally transparent due to seperating all these random variables into two separate 'streams'. Further, there 'should' be no dependency on $X_{a(N_a+1)}$ and later, since $a(N_a+1) > T$.

Do you see the reason for my confusion? Perhaps can you help me with that? Further, I read something about filterings in this context (although this concept is totally new to me), perhaps something like that can be applied here?

share|improve this question
add comment

1 Answer

After carefully reviewing this question, I was able to work out the details and answer it by myself: The above claim is ill-formulated.

For applying Wald's equation to each summand, one would need that the event $\{N_a = j\}$ is independent of $(X_{a(j + 1)}, X_{a(j + 2)}, ...)$, not just independency of indices above $a(N_a)$.

Well, and unfortunately this is not satisfied, since indeed $\{N_a = j\}$ also depends on $X_{a(j + 1)}, ..., X_{T-1}$, thus, on the remaining part up to the stopping time $T$.

Thus, without additional assumptions, especially on $\ell$, it is more than doubtful whether just grouping the random variables by their distribution $A$ or $B$ and counting the number of each type leads to the above conjecture.

share|improve this answer
add comment

Your Answer

 
discard

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.