9
$\begingroup$

Consider a two random vectors $v=v_1,\dots, v_n$ and $w=w_1,\dots, w_n$, each of $n$ elements, each of which is independently $\pm1$ with prob $1/2$ . Let $n$ be even and let $X$ be the inner product of $v$ and $w$. We know:

$$P(X = 0) = {n \choose n/2} \frac{1}{2^n}.$$

Now let $Y$ be the inner product of $v$ and the vector $z=w_2,\dots,w_n, w_1$.

What is $P(Y=0|X=0)$?

$\endgroup$
7
$\begingroup$

First of all, for the inner product to be $0$, $n$ must be even.

We get that $u\cdot v=0$ exactly when the the element-wise product of the vectors, $v_kw_k$, has as many $+1$s as $-1$s. After a shift, the element-wise product changes every where that $w_kw_{k+1}=-1$ (with wrapping). Thus, for each $-1$ of $w_kw_{k+1}$ in the $+1$s of $v_kw_k$, there must be a $-1$ of $w_kw_{k+1}$ in the $-1$s of $v_kw_k$.

The number of transitions that leave the dot product unchanged is $$ \sum_{k=0}^{n/2}\binom{n/2}{k}\binom{n/2}{k}=\binom{n}{n/2}\tag{1} $$ The total number of transitions is $$ \sum_{k=0}^{n/2}\binom{n}{2k}=2^{n-1}\tag{2} $$ Note that $(2)$ only holds for $n\gt0$. For $n=0$, the sum is $1$, not $\frac12$.

Thus, for $n\gt0$, the probability that there is no change in the dot product is $$ \binom{n}{n/2}2^{1-n}\tag{3} $$ Which is exactly twice the probability of having a dot product of $0$ in the first place. For $n=0$, the probability is $1$.

$\endgroup$

Your Answer

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