High-Probability Lower Bound for Sums of Conditional Probabilities in IID Sequences on the Unit Sphere

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;

1. 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$.
2. 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$.
3. 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$.

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.

1. $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$.
2. $u_{i-1}=0$ and $|x_2|>\alpha$: Now we really don't know anything except that it's $\geq 0$
3. (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...