# Probability an inner product is $0$

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.

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