<p>I am interested in the volume of the intersection of two Hamming balls of radius say m/6 in m-dimensional space, the distance between whose centers is about \sqrt{m}. I would ideally like this to be a constant or 1/poly(m) fraction of the volume of the Ball itself and wondering if this is true.  </p>

<p>This should be an elementary question and I imagine the answer must be well-known, but I am not able to find this on the interweb. Thanks!</p>

CC BY-SA 3.0
2015-05-06T19:58:22.920Z
Is this hwk? There are $n\choose i$ points at distance $i$ from the origin.  When $i\approx m/6$, there are about 5 times as many points at distance $i$ as there are at distance $i-1$.  So almost all points in the Hamming ball of radius $m/6$ around the origin are at distance $m/6 \pm \Theta(\log m)$ from the origin.  Similarly, almost all points in the Hamming ball of radius $m/6$ around, say, a given point $p$ with $\sqrt m$ ones and $m-\sqrt m$ zeros, are at distance $m/6 \pm \Theta(\log m)$ from $p$.  But no point has distance $m/6 \pm \Theta(\log m)$ from both the origin and $p$. Right?
Neal Young
CC BY-SA 3.0
2015-05-06T20:29:53.497Z
@Neal: don't lots of points have distance $m/6$ both from the origin and $p$?
Peter Shor 
CC BY-SA 3.0
2015-05-06T21:06:13.857Z
Hi @PeterShor!  Yes, you are right.  I should not say "no point".  But very few.  Any point $q$ at distance $m/6$ from the origin has $m/6$ ones.  To also have Hamming distance $m/6$ from $p$, in the $\sqrt m$ coordinates in which $p$ is 1, $q$ has to have exactly $\sqrt m/2$ 1's and $\sqrt m/2$ 0's...  Right?  This is still not a complete argument, but I think it gives the right intuition.
Neal Young
CC BY-SA 3.0
2015-05-06T21:09:50.467Z
@Neal: Right. You expect $\sqrt{m}/6$ 1's in those $p$ coordinates. The probability of getting $\sqrt{m}/2$ will be something like $2^{-c \sqrt{m}}$.
Peter Shor 
CC BY-SA 3.0
2015-05-06T21:21:25.753Z
Yes, just what I was going to say.
Neal Young
CC BY-SA 3.0
2015-05-13T21:26:47.537Z
I feel like this question might be a better fit for math.SE. If you want then I can migrate it for you (please don't cross-post, ping me in the comments or flag the question).
Artem Kaznatcheev
<convex-geometry>
Intersection of Hamming Balls
Vinod
# Intersection of Hamming Balls

(Asked by: username_0 on 2015-05-06)

I am interested in the volume of the intersection of two Hamming balls of radius say m/6 in m-dimensional space, the distance between whose centers is about \sqrt{m}. I would ideally like this to be a constant or 1/poly(m) fraction of the volume of the Ball itself and wondering if this is true.

This should be an elementary question and I imagine the answer must be well-known, but I am not able to find this on the interweb. Thanks!

**Tags:** convex-geometry

> **Comments:**
> **username_1**: Is this hwk? There are $n\choose i$ points at distance $i$ from the origin.  When $i\approx m/6$, there are about 5 times as many points at distance $i$ as there are at distance $i-1$.  So almost all points in the Hamming ball of radius $m/6$ around the origin are at distance $m/6 \pm \Theta(\log m)$ from the origin.  Similarly, almost all points in the Hamming ball of radius $m/6$ around, say, a given point $p$ with $\sqrt m$ ones and $m-\sqrt m$ zeros, are at distance $m/6 \pm \Theta(\log m)$ from $p$.  But no point has distance $m/6 \pm \Theta(\log m)$ from both the origin and $p$. Right?  
> **username_2**: @Neal: don't lots of points have distance $m/6$ both from the origin and $p$?  
> **username_1**: Hi @PeterShor!  Yes, you are right.  I should not say "no point".  But very few.  Any point $q$ at distance $m/6$ from the origin has $m/6$ ones.  To also have Hamming distance $m/6$ from $p$, in the $\sqrt m$ coordinates in which $p$ is 1, $q$ has to have exactly $\sqrt m/2$ 1's and $\sqrt m/2$ 0's...  Right?  This is still not a complete argument, but I think it gives the right intuition.  
> **username_2**: @Neal: Right. You expect $\sqrt{m}/6$ 1's in those $p$ coordinates. The probability of getting $\sqrt{m}/2$ will be something like $2^{-c \sqrt{m}}$.  
> **username_1**: Yes, just what I was going to say.  
> **username_3**: I feel like this question might be a better fit for math.SE. If you want then I can migrate it for you (please don't cross-post, ping me in the comments or flag the question).  

---

## 0 answers

