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

2more comments