Probability of $\ell_1$-norms of vertices of the rotated Hamming cube

Question

Let $O$ be a $d$-dimensional rotation matrix (i.e., it has real entries and $OO^T = O^TO = I$). Let $\mathbf{x}$ be a uniformly random bitstring of length $d$, i.e., $\mathbf{x} \sim U(\{0,1\}^d)$. In other words, $\mathbf{x}$ is a vertex of the Hamming cube, selected uniformly at random. I would like to show that there exists a $C > 0$ such that $$\mathbb{P}\left[\|O\mathbf{x}\|_1 \leq \frac{d}{4}\right] \leq 2^{-Cd}.$$ I am horribly stuck, any ideas on how to approach this problem would be very much appreciated. Below are some of my own attempts. This question is cross-posted at math stack exchange here.

---

Observation 1: If $O = I$, then the statement holds.

If $O = I$, then $\|O\mathbf{x}\|_1 = \|\mathbf{x}\|_1$ is simply the number of ones in the bitstring. Among the $2^d$ choices for $\mathbf{x}$, the number of choices that satisfies $\|\mathbf{x}\|_1 \leq d/4$ is

$$1 + \binom{d}{1} + \binom{d}{2} + \cdots + \binom{d}{\lfloor d/4\rfloor} \leq 2^{dH(\lfloor d/4\rfloor/d)} \leq 2^{dH(1/4)},$$ hence the probability is upper bounded by $2^{-d(1-H(1/4))}$. Here, $H(\cdot)$ is the binary entropy function, i.e., $H(p) = -p\log_2(p) - (1-p)\log_2(1-p)$.

Observation 2: Numerical experiments support this result. Below is a plot of the probability versus the dimension, where $O$ is selected at random:

The blue line is the probability. The orange line is the bound derived in the case where $O = I$.

For comparison, here is the same numerical experiment, but with $O = I$:

Thus, it appears that the introduction of $O$ decreases the probability.

Both plots are obtained by sampling $100000$ $\mathbf{x}$'s at random. The code is here:

import numpy as np
import matplotlib.pyplot as plt
import random
from scipy.stats import ortho_group

H = lambda p : -p * np.log2(p) - (1-p) * np.log2(1-p)
C = 1 - H(1/4)
print(C)

N = 100000
ds,Ps = [],[]
for d in range(2,40):
    O = ortho_group.rvs(dim = d)
    # O = np.eye(d)
    P = 0
    for _ in range(N):
        x = random.choices(range(2), k = d)
        if np.linalg.norm(O @ x, ord = 1) <= d/4: P += 1/N
    print(d,P)
    ds.append(d)
    Ps.append(P)

fig = plt.figure()
ax = fig.gca()
ax.plot(ds, Ps)
ax.plot(ds, [2**(-C*d) for d in ds])
ax.set_yscale('log')
ax.set_xlabel('d')
ax.set_ylabel('P')
plt.show()

Answer 1

Here is an attempt to the problem for a worst-case $O$, with worse constants. So fix $O$, letting $o_i$ denote its $i$th row, and take $X$ random in $\{0,1\}^d$.

1. We claim that $E |\langle o_i, X\rangle| \ge cst$. To see this, write $$\langle o_i, X\rangle = \langle o_i, \frac{{\bf 1}}{2}\rangle + \langle o_i, (X - \frac{{\bf 1}}{2})\rangle$$ and assume WLOG the first term on the RHS is non-negative. The second term on the RHS is a weighted sum of Rademacher random variables, and so with probability at least $\frac{1}{20}$ it is above its standard deviation, which is $\Omega(1)$ (see for example this paper of Oleszkiewicz)

2. Adding over all $i$'s, the result holds in expectation: $E \|OX\|_1 \ge cst\cdot d$. But since the function $x \mapsto \|Ox\|_1$ is $\sqrt{d}$-Lipschitz wrt $\ell_2$ (and convex), we should be able to use concentration to say that the probability that we get below this mean minus $\frac{cst \cdot d}{2}$ is at most $e^{-cst' \cdot d}$ (see for example Corollary 4.23 of van Handel's notes). This gives the result.

Answer 2

We prove the weaker bound $$ \mathbf{P} \left[ \|O \mathbb{x}\|_1 \leq \frac{cd}{\sqrt{\log d}} \right] \leq 2^{-Cd} $$ for some constants $C, c$.

Define the Gaussian mean width of a compact subset $A \subset \mathbf{R}^d$ as $$ w(A) = \mathbf{E} \sup_{x \in A} \langle G,x \rangle $$ where $G$ is a standard Gaussian vector in $\mathbf{R}^d$. We use the following properties

1. If $\pi$ is an orthogonal projection, then $w(\pi(A))\leq w(A)$.
2. If $A = \{0,1\}^k \subset \{0,1\}^n$, then $w(A)=k/\sqrt{2\pi}$.
3. If $A=B_1^d$ (the unit $\ell_1$ ball), then $w(A) \leq \sqrt{2\log d}$.
4. $w$ is rotation invariant

Let $A$ be the set of $x \in \{0,1\}^d$ such that $\|Ox\|_1 \leq cd/\sqrt{\log d}$. We have $w(A) \leq w(cd/\sqrt{\log d} \cdot B_1^d) \leq c\sqrt{2}d$.

If $\mathrm{card}(A) \geq 2^{dH(1/4)}$, then the Sauer--Shelah lemma implies that there is a coordinate projection $\pi$ of rank $k=d/4$ such that $\pi(A)$ identifies with $\{0,1\}^k$. Therefore, $w(A) \geq w(\pi(A))=d/4\sqrt{2\pi}$. If we choose $c=1/8\pi$, combining both estimates gives the bound $\mathrm{card}(A) < 2^{dH(1/4)}$, as needed.

Answer 3

Adding more detail to Mikael's point, the result seems to hold on average over $O$ because of the following:

1. Using a Chernoff bound, we can see that the probability that for any constant $\epsilon$, with probability at least $1- e^{-C d}$ the random vector $x$ has at least $\frac{(1-\epsilon)d}{2}$ 1's.

2. Consider a fixed vector $x \in \{0,1\}^d$. For a uniformly distributed $O$, $O x$ is uniformly distributed on the sphere of size $\sqrt{\|x\|_1}$. This has distribution essentially the same as the vector $\sqrt{\|x\|_1} (G_1,\ldots,G_d)$, where the $G_i$'s are independent Gaussians $N(0,\frac{1}{d})$ (in fact $\sqrt{\|x\|_1}$ has the same distribution as $\sqrt{\|x\|_1} (G_1,\ldots,G_d)/\|G\|_2$, or alternatively one can bypass using Gaussians and work with concentration on the sphere, as Mikael suggested).

Then in expectation (over $O$) $$E \|Ox\|_1 \approx \sqrt{\|x\|_1} \cdot \|G\|_1 = \sqrt{\|x\|_1} \cdot \sqrt{d} \sqrt{\frac{2}{\pi}},$$ where the last inequality uses the fact that the expected value of a folded Gaussian of standard deviation $\sigma$ is $\sigma \sqrt{\frac{2}{\pi}}$.

Moreover, the function $\|\cdot\|_1$ is $\sqrt{d}$ Lipschitz wrt $\ell_2$ we can use concentration of such functions over Gaussian space to get that with probability at least $1 - e^{- Cd}$ we have $$\|Ox\|_1 \ge (1-\epsilon) \sqrt{\|x\|_1} \cdot \sqrt{d} \sqrt{\frac{2}{\pi}},$$ see for example Example 4.2 in van Handel excellent notes or inequality (1.6) of Ledoux-Talagrand "Probability in Banach Spaces".

3. Taking a union bound over the two steps above seems to give the desired result.