9

Consider a random $n+1$-dimensional vector $v$. Each $v_1,\dots,v_n$ equals $1$ with probability $1/2$ and $-1$ with probability $1/2$ independently. We also set $v_{n+1} = v_1$.

Now consider a random $n$-dimensional vector $w$. Each $w_i$ equals $1$ with probability $1/4$ and $-1$ with probability $1/4$ and equals $0$ with probability $1/2$, all sampled independently.

We know$$P\left(\sum_{i=1}^n v_i w_i = 0\right) = \sum_{k=0}^{\lfloor \frac n2 \rfloor}\frac{n!}{k!(n-2k)!k!}\left(\frac14\right)^k\left(\frac12\right)^{n-2k}\left(\frac14\right)^k \sim \frac{1}{\sqrt{\pi n}}.$$

I wrote computer code to compute probabilities exactly for smallish $n$. It seems numerically that $$P\left(\sum_{i=1}^n v_{i+1} w_i = 0 \; \land \sum_{i=1}^n v_{i} w_i = 0\right) = \frac{\sum _{i=0}^{\lfloor n/2 \rfloor} {2(n-2i) \choose n-2i} {n \choose 2i} {4i \choose 2i}}{ 2^{3n - 1}}.$$

Is this equality true and how could one prove it?

Community
  • 1
  • Could the technique from http://math.stackexchange.com/questions/1021933/conditional-probability-that-a-rotated-inner-product-is-zero?rq=1 be applied to your problem maybe? –  Jun 04 '15 at 06:52
  • @eleanora That would be lovely but I don't see how to do that yet. –  Jun 06 '15 at 15:31

1 Answers1

1

I havn't found the time to state and simplify a formula, but one would have to do the following. First exclude the possibility that $w_i = 0$. If one or more of the $w_i$'s are Zero, you can just reduce $n$ by that amount. So let's assume $w_i$ are distributed like $v_i$. Now you construct $w_i = u_i v_i$ with $u_i$ being independently sampled like $v_i$. This way $w_i$ will still be Independent of $v_i$ but the two constraints simplify to $\sum_{i=1}^n w_i = 0 \wedge \sum_{i = 1}^n v_i v_{i+1} w_i = 0$. Now the first constraint has only a solution if $n$ is even. In this case there are $\binom{n}{n/2}$ possibilities each of it contains $n/2$ ones and $n/2$ minus ones. Now for fixed $w$ it is possible to calculate the number of Solutions of the equation $\sum_{i = 0}^n x_i w_i$. If $x$ has an even number of $-1$'s it is easy to calculate the probability of $v_i v_{i+1} = x_i$ for all $i$. If $x$ has an odd number of $-1$, the probability is Zero. In this way you might come up with a formula, that could be Close to the one you stated there.

SebastianZ
  • 86