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.
2 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| Alex de Ruijter | (no comment) | Dec 29, 2024 at 16:09 |
I've found a way to generalize the proof.
So we know $x\in \mathbb S^{d-1}$. Now that implies that there exists a threshold $\alpha>0$ such that $\sum_{i=1}^d \mathbf{1}\{|x_i|>\alpha\}\geq 1$ where $\mathbf{1}\{A\}$ is an indicator-function.
We know that this $\alpha$ exists. It's upper-bound is purely a function of $d$; clearly the smallest unit-vector we need to take into account is the evenly divided one (signs do not matter), which implies $\alpha < \sqrt{1/d}$. We could for instance pick $\alpha=\sqrt{1/2d}$.
Anyway, back to track. Fix some $x\in\mathbb S^{d-1}$ and some $\alpha \in (0, \sqrt{1/d})$. We know then that $\{|u_{i:i-d+1}x|>\alpha\}$ definitely happens for a fixed sequence of $u_{i:i-d+1}$. We can construct that sequence as follows;
- Pick some $0\leq j \leq d$ such that $|x_j|>\alpha$. We know there must be at least one such $j$ for our choice of $\alpha$.
- Define a vector $L(x) \in \{0,1\}^d, L(x)_i = 1$ if $i=j$ and 0 else. Clearly $|L(x)x|= |x_j| > \alpha$.
- Clearly, $u_{i:i-d+1} = L(x)$ implies $|u_{i:i-d+1}x|>\alpha$.
Then we know that $\mathbb P(|u_{i:i-d+1}x|>\alpha\mid \mathcal F_{i-1}) \geq \mathbb P(u_{i:i-d+1}= L(x)\mid \mathcal F_{i-1})$ as we can introduce a partitioning with $\{u_{i:i-d+1} = L(x)\}^{\{1, c\}}$. Furthermore, we know that $\mathbb P(u_{i:i-d+1}= L(x)\mid \mathcal F_{i-1}) = 0.5\, \mathbf{1}\{u_{i-1:i-d+1} = L(x)_{2:d}\}$ as $\mathbb P (u_i = L(x)_1) = 0.5$ and $u_{i-1:i-d+1} \in \mathcal F_{i-1}$. Hence we find that
\begin{align*} &\mathbb{P}\left(\sum_{i=1}^N\mathbb{P}(|u_{i:i-d+1}x|>\alpha\mid \mathcal F_{i-1}) \geq \beta N\right)\\ &\geq\mathbb{P}\left(\sum_{i=1}^N \mathbb P(u_{i:i-d+1}= L(x)\mid \mathcal F_{i-1}) \geq \beta N\right)\\ &=\mathbb{P}\left(\sum_{i=1}^N 0.5\, \mathbf{1}\{u_{i-1:i-d+1} = L(x)_{2:d}\} \geq \beta N\right)\\ &\geq\mathbb{P}\left(\sum_{i=1}^{\frac{N}{d-1}}\mathbf{1}\{u_{i\cdot(d-1):i\cdot(d-1)-d+2} = L(x)_{2:d}\geq \beta N\}\right) \end{align*}Clearly, that last line is again some sort of binomial sum. Hence although the chance is low of each individual succes ($=2^{-d+1}$) there will exist at least some $\beta>0$ such that this holds with exponential probability in the same way as the $d=2 case.
Hence I conclude that there must exist some $\alpha, \beta, c, \kappa >0$ such that it holds with high probability over increasing $N$.
0 comment threads
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