Skip to main content
MathOverflow

Return to Question

simplified the claim
Source Link
cubic lettuce
cubic lettuce
  • 340
  • 1
  • 8

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

(same for $N_b$).

'confusing proof argument': $\{N_a \geq j\}$ is determined just by counting the number of random variables $X_{a(1)}, X_{a(2)}, \ldots, X_{a(j)}$, but it is independent of $X_{a(j+1)}, X_{a(j+2)}, \ldots$.

But: I somehow get lost in accepting that this independency holds. Fact is, that $N_a$ and $N_b$ are fully determined by $X_1, X_2, \ldots, X_T$. However, 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 is clearly'should' be no dependency on $X_{a(N_a+1)}$ and later, since $a(N_a+1) > T$.

claim: $N_a$ is a stopping time for $(X_{a(i)})_{i\in\mathbb{N}}$.

(same for $N_b$).

'confusing proof argument': $\{N_a \geq j\}$ is determined just by counting the number of random variables $X_{a(1)}, X_{a(2)}, \ldots, X_{a(j)}$, but it is independent of $X_{a(j+1)}, X_{a(j+2)}, \ldots$.

But: I somehow get lost in accepting that this independency holds. Fact is, that $N_a$ and $N_b$ are fully determined by $X_1, X_2, \ldots, X_T$. However, 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 is clearly no dependency on $X_{a(N_a+1)}$ and later, since $a(N_a+1) > T$.

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

(same for $N_b$).

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

Source Link
cubic lettuce
cubic lettuce
  • 340
  • 1
  • 8

Extending Wald's equation to two classes of i.d. random variables?

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 a stopping time for $(X_{a(i)})_{i\in\mathbb{N}}$.

(same for $N_b$).

'confusing proof argument': $\{N_a \geq j\}$ is determined just by counting the number of random variables $X_{a(1)}, X_{a(2)}, \ldots, X_{a(j)}$, but it is independent of $X_{a(j+1)}, X_{a(j+2)}, \ldots$.

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. Fact is, that $N_a$ and $N_b$ are fully determined by $X_1, X_2, \ldots, X_T$. However, 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 is clearly 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?