High-Probability Lower Bound for Sums of Conditional Probabilities in IID Sequences on the Unit Sphere
Let $(\Omega, \mathcal F, \mathbb P)$ be a filtered probability space. Let $\{u\}_{i=1}^\infty$ be a sequence of i.i.d. RV's, $u_i\sim Ber(\frac{1}{2})\,\forall i\in\mathbb N$, where we define $u_i = 0 \,\forall i \leq 0$. Let $\mathcal F_i$ be the natural filtration $\sigma(u_1, u_2, \ldots, u_i)$, with $\mathcal F_0$ the trivial $\sigma$-algebra.
Let $\mathbb S^{d-1}$ be the unit-sphere on $\mathbb R^d$ and define $u_{i: i-d+1}:= [u_i, u_{i-1},\ldots,u_{i-d+1}]$.
I'm interested in the following question: do there exist some $\alpha, \beta, c, \kappa>0$ such that the event $$ \left\{\sum_{i=1}^N\mathbb{P}\left(|u_{i:i-d+1}\,\cdot x|>\alpha\mid \mathcal F_{i-1}\right)\geq\beta N\right\} $$ happens with high probability ($\geq1-c\exp(-\kappa N)$) for all $x\in\mathbb S^{d-1}$ and all $N\geq 2d$?
Now, I think I solved the question for $d=2$, but I'm having a hard time generalizing the proof. Intuitively, I think the answer should be positive but I can't prove it.
I'll leave my attempt below.
1 answer
So for $(d=2)$ this is my solution;
First fix some $i\geq 1$ and let us investigate $$ \mathbb P \left\{|u_{i:i-1}\, x| >\alpha \mid \mathcal F_{i-1} \right\} $$ for some vector $x = [x_1, x_2]^T$ on the unit circle.
Then we have four cases.
- $u_{i-1}=1$ and $|x_2|>\alpha$: Then if $u_i=0$ we will satisfy the requirement. Hence $\mathbb P(|u_{i:i-1}\,x|>\alpha\mid\mathcal F_{i-1},u_{i-1}=1, |x_2|>\alpha)\geq 0.5$.
- $u_{i-1}=0$ and $|x_2|>\alpha$: Now we really don't know anything except that it's $\geq 0$
- (and 4) $|x_2|\leq \alpha$. Now we know that $|x_1|\geq \sqrt{1-\alpha^2}$ as $x\in\mathbb S^{d-1}$. Then let us pick an $\alpha>0$ such that $|\sqrt{1-\alpha^2}-\alpha|>\alpha$ and $\sqrt{1-\alpha^2}>\alpha$. This happens for $\alpha \in (0, \frac{1}{\sqrt{5}})$ Then, regardless of the value of $u_{i-1}$ the condition will be satisfied when $u_i=0$, and otherwise it is not. Hence $\mathbb P(|u_{i:i-1}\,x|>\alpha\mid\mathcal F_{i-1}, |x_2|\leq\alpha)= 0.5$.
Now, inspecting the overall structure, we find that for all $\alpha \in (0, \frac{1}{\sqrt{5}})$ $$ \mathbb{P}\left\{|u_{i:i-1}\, x| >\alpha \mid \mathcal F_{i-1} \right\}\geq 0.5 u_{i-1}. $$
That implies that $$ \mathbb{P}\left(\sum_{i=1}^N \mathbb{P}\left\{|u_{i:i-1}\, x| >\alpha \mid \mathcal F_{i-1} \right\}\geq \beta N\right)\geq \mathbb{P}\left(\sum_{i=1}^N 0.5 u_{i-1}\geq \beta N\right) $$ Now, we can interpret the rhs of that inequality as a tail bound on the upper tail of the cumulative distribution of a random variable distributed as a Binomial(N-1,$\frac{1}{2}$). If we then pick $\beta$ small enough (<1/4) we can use a chernoff bound to get
$$ \mathbb{P}\left(\sum_{i=1}^N 0.5 u_{i-1}\geq \beta N\right)\geq 1- \exp\left(-n\mathcal D\left(2\frac{\beta N}{N-1}\\||\frac{1}{2}\right)\right). $$Where $\mathcal{D}\left(a||b\right)$ is the Kullback-Leibler divergence. Clearly then there must exist a $\alpha, \beta, c$ and $\kappa>0$ that work for $d=2$.
For $d>2$ tracking all cases becomes very hard, so some other approach might be necessary...
0 comment threads
0 comment threads