Volume of Hamming ball w.r.t power-law distribution on hypercube

53 Views Asked by At

Let $n$ be a large positive integer and let $X$ be a random element of hypercube $\{0,1\}^n$ such that $\mathbb P(|X|= \ell) \propto (\ell + 1)^{-\beta}$ for all $\ell \in \{0,1,\ldots,n\}$. Here $\beta \ge 0$ is a constant. Fix $x \in \{0,1\}^n$, $r \in (0,1)$, and let $B_n(x;rn)$ be the Hamming ball of radius $rn$ around $x$.

Question. What is a good asymptotic estimate for $\mathbb P(X \in B_n(x;rn))$ ?

Edit

As point outed by user @Mike Earnest, the distribution of $X$ is underspecified. What I really had in mind for the distribution of $X$ was the following:

$$ \mathbb P(X=x) \propto (|x| + 1)^{-\beta},\,\forall x. $$

With this modification, not that $\beta=0$ to the uniform distribution on $X$, and in this case it is standard knowledge (coding theory, etc.) that $$ \mathbb P(X \in B_n(x;rn)) \asymp 2^{-(1-H_2(r))n}, $$ where $H_2$ is binary entropy.

1

There are 1 best solutions below

0
On

Let's first count the number of $z \in \{0,1\}^n$ such that $d_H(z,x) = t$ and $|z| = \ell$. For such a $z$ to even exist, a necessary and sufficient condition is that $$ \ell = t + w,\quad 0 \le t \le n-w. $$

Now, WLOG let $x=1^w0^{n-w}$, as a string of $0$'s and $1$'s. Here, $w = |x|$. We can always write $z=uv$, where $u \in \{0,1\}^w$, $v \in \{0,1\}^{n-w}$. Let $w_1 = d(u,1^w) = w-|u|$ and $w_0 = d(v,0^{n-w}) = |v|$. Then, the only constraint on $z$ is that $$ t = w_0+w_1 = w-|u| + |v|,\quad \ell = |u| + |v|. $$ Solving this gives $|v| = (\ell + t-w)/2 = t$ and $|u| = \ell - t = w$.

In particular, this means that $u=1^w$ and so $z$ is of the form $z=1^w v^{n-w}$, where $|v| = t$. There are ${n-w\choose t}$ choices for $v$, and therefore, for $z$. We conclude that \begin{equation} \mathrm{card}(\{z \in \{0,1\}^n \mid d_H(z,x) = t,\, |z| = \ell\}) = \begin{cases} {n-w\choose t},&\mbox{ if }0 \le t \le n-w,\, \ell = t + w,\\ 0,&\mbox{ otherwise } \end{cases} \end{equation} We deduce that \begin{equation} \mathbb P(X \in B_n(x;R)) \propto \sum_{t=0}^{\min(n-w,R)}{n-w \choose t} (t+w+1)^{-\beta}, \end{equation} where $w := |x|$.