Consider a uniformly sampled random vector $x \in \{0,1\}^n$ and a fixed vector $y \in \{-1,0,1\}^n$. Say $y$ has $a$ ones and $b$ minus ones.

What is the probability that the inner product of $x$ and $y$ is zero?

It seems that this is like a random walk where there are $a$ opportunities to walk right and $b$ opportunities to walk left. We are asking the probability that we end up at the origin.

  • $\begingroup$ $y$ has $a$ ones and $b$ zeros... Does that mean that it has $n-a-b$ pcs.$-1$'s? $\endgroup$ – zoli Apr 30 '15 at 10:36
  • $\begingroup$ @zoli Yes. Although I am not sure what "pcs." means. $\endgroup$ – felix Apr 30 '15 at 10:39
  • $\begingroup$ pcs.: Pieces. Three pcs. of apples :) $\endgroup$ – zoli Apr 30 '15 at 10:48
  • $\begingroup$ @zoli Edited the question to have $a$ ones and $b$ minus ones. $\endgroup$ – felix Apr 30 '15 at 10:57

Look at vectors $x$ with a fixed number of $1$'s, say $x$ has $c$ ones. Then $(x,y)=0$ iff $x$ has $d$ $1$'s in the same places as $y$ has $1$'s, $d$ $1$'s in the same places as $y$ has $-1$'s and $c-2d$ $1$'s in the same places as $y$ has $0$'s for some $d\le c/2$. For a given $d$ this can be accomplished in ${a\choose d}{b\choose d}{n-a-b\choose c-2d}$ ways, where we define ${n\choose k}=0$ if $k>n$. The probability for any given $x$ is $1/2^n$, so summing over $d$ gives a probability $$\frac{1}{2^n}\sum_{d=0}^{\lfloor c/2\rfloor} {a\choose d}{b\choose d}{n-a-b\choose c-2d}$$ of $x$ having exactly $c$ ones and $(x,y)=0$. If we also sum over $c$ we end up with the probability $$\frac{1}{2^n}\sum_{c=0}^n\sum_{d=0}^{\lfloor c/2\rfloor} {a\choose d}{b\choose d}{n-a-b\choose c-2d}$$ of $(x,y)=0$.

Edit: If we change the order of summation in the above expression we get $$\frac{1}{2^n} \sum_{d=0}^{\lfloor n/2\rfloor}{a\choose d}{b\choose d}\sum_{c=2d}^{c=n-a-b+2d} {n-a-b\choose c-2d}$$ and replacing $c$ by $c^\prime = c-2d$ gives $$\frac{1}{2^n} \sum_{d=0}^{\lfloor n/2\rfloor}{a\choose d}{b\choose d}\sum_{c^\prime=0}^{c=n-a-b} {n-a-b\choose c^\prime}=\frac{1}{2^n}\sum_{d=0}^{\min(a,b)}{a\choose d}{b\choose d}2^{n-a-b}=\\\frac{1}{2^{a+b}}\sum_{d=0}^{\min(a,b)} {a\choose d}{b\choose d}$$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.