Post History

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