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

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()

• I don't know about your question, but it should not be too difficult to show that, on average over $O$, your question has a positive answer. Your question then boils down to concentration inequalities for the $\ell_1$ norm of a random uniform point on the unit sphere if $\mathbf{R}^d$, which are certainly well-known. This at least explains your numerical evidence. Apr 16 at 16:05
• Thanks for the reply! Indeed, on average over $O$ it should work out. :) But in this case I'm specifically looking for an argument that works for all $O$ (or find an $O$ for which the statement doesn't hold, of course :p) Apr 16 at 16:49
• Is the $\frac 1 4$ in your question important, or are you happy with another constant, say $\frac 1 {10}$? Apr 16 at 16:53
• I would also be fine with changing d/4 to d/10 or d/10000. If this is still too hard, then even though d/log(d) would be somewhat weaker, it would still be interesting. What interests me most is the method behind the proof, not the precise constants. :) Apr 16 at 16:56
• Maybe one can use the Sauer-Shelah lemma and argue that if the probability is too large, then there is a subcube $\{0,1\}^{cn}$ "inside" the $\ell_1$ unit ball, which is not possible because e.g. of mean width estimates? Apr 16 at 17:26

## 3 Answers

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.

• Can you expand a bit the second point? I do not see directly how the corollary in Handel's notes gives the result. Apr 16 at 19:43
• BTW, another way to see that $E\|OX\|_1 \geq cd$ is by symmetrization and Khintchine's inequality. Apr 16 at 19:44
• @MikaeldelaSalle: I may be goofing off, but it seems by letting $f(x) := \|Ox\|_1$, van Handel's corollary should give that $f(X)$ is $d$-subgaussian (it is stated in terms of gradients but we can replace by subgradients, and the subgradients of $f$ should have $\ell_2$ norm at most $\sqrt{d}$). But $d$-subgaussian RVs have concentration $Pr(f(X) \le E f(X) - \epsilon d) \le e^{-\frac{(\epsilon d)^2}{2 d}}$, and we should get the result. Apr 16 at 19:57
• Thanks, I got it. Apr 16 at 20:11
• Thanks a lot for the response! :) This certainly looks like an interesting approach. I will have a more careful look at the details after the weekend, and then award the bounty accordingly. Apr 17 at 11:24

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.

• Thanks a lot for the response! :) This certainly looks like an interesting approach. I will have a more careful look at the details after the weekend, and then award the bounty accordingly. Apr 17 at 11:24
• Since Marco's answer provided a better scaling, I decided to award the bounty to them. Still, thanks for the solution you proposed! :) Apr 20 at 0:16

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

1. Taking a union bound over the two steps above seems to give the desired result.
• Thanks a lot for your idea! :) Do I understand correctly that this only works whenever $O$ is chosen randomly too? Ideally, I would like to find an argument in which $O$ is fixed (or find a single $O$ for which the claim doesn't hold, naturally :p). Apr 16 at 16:45
• Sorry, I should have read the question more carefully :). I'll edit the answer to make it clear that it does not address the actual question. Apr 16 at 16:52