# Probability of many overlapping zero inner products on a circle

[Question edited and changed a little on June 14 2015]

Consider an $n$-dimensional vector $v$ with $v_i \in \{-1,1\}$. Now consider an $n$-dimensional vector $w$ with $w_i \in \{-1,0,1\}$. The elements $w_i$ are sampled independently so that $P(w_i = -1) = P(w_i = 1) = 1/4$ and $P(w_i=0) = 1/2$. The elements $v_i$ are sampled independently so that $P(v_i = -1) = P(v_i = 1) = 1/2$.

Indexing from $0$, we now define $C_i = \sum_{j=0}^{n-1} w_j v_{i+j \bmod n}$ to be the inner product between $w$ and the $i$th rotation of $v$. It may be helpful to think of both $v$ and $w$ as lying on a discrete circle of circumference $n$ so that the rotation of a vector has a natural visual interpretation. We know that $P(C_i = 0) \sim 1/\sqrt{\pi n}$.

I would like to understand the probability that $C_i = 0$ for many consecutive values of $i$.

To this end we can look at

$$z_i=P(C_i = 0 \mid \forall j < i \; C_j=0 ).$$

Let us define $z_0 = P(C_i = 0) \sim 1/\sqrt{\pi n}$ and we know that $z_{n} = 1$. With a little effort we can also see that

$$z_1 \sim \frac{2}{\sqrt{\pi n}}.$$

The value $z_i$ gives us some indication of the degree of independence of the events $(C_i=0)$. In particular, my current intuition is that the events $(C_i=0)$ are not too far from being independent for the first few values of $i$ and then once you have a lot of previous zero inner products they become highly dependent.

It appears numerically that $z_2 \sim 2/\sqrt{\pi n}$ although I don't know how to prove this. This leads to my first question:

Assuming $n$ is large, for which $i$ can we approximate $z_i$?

I am particularly interested in $i \leq n/\log_2{n}$. We know that the probability that all $n$ inner products are zero must be at least $2^{-n}$ as that is the probability that $w$ is all zeros. Therefore there cannot be many more than $n/\log_2{n}$ values of $i$ such that $z_i \approx C/\sqrt{n}$. If there were there would be a contradiction. My guess is that in fact all the first approximately $n/\log_2{n}$ values of $z_i$ are approximately of this form, This leads to my second question.

Does there exist a constant $c\geq 1$ so that for all sufficiently large $n$, $$P{\left(\forall i \leq \frac{n}{\log_2{n}}, C_i = 0\right)} \leq 2^{-\frac{n}{c}}.$$

• What does it mean, to wrap a vector on to a circle? – Gerry Myerson Jun 15 '15 at 0:04
• @GerryMyerson I just meant this to give a visualisation for the rotation of a vector so that $C_i = \sum_{j=0}^{n-1} w_j v_{i+j \bmod n}$ can then be seen as the inner product around the circle of $w$ and the $i$th rotation of $v$. I edited the text a little to hopefully make it clearer. – Raphael Jun 15 '15 at 6:10
• some basic ideas are not being defined. what is i th rotation of v ? etc. if not phrased in some std ways & not linked into any other std study (what field is this from? motivation? etc) then maybe a short intro/ writeup elsewhere would help – vzn Jun 19 '15 at 14:17
• @vzn Thank you for the question. The $i$th rotation of $v$ is a vector $y$ so $y_j = v_{i+j \bmod n}$ for $0 \leq j \leq n-1$. The $0$th rotation, for example, is $v$ itself. The motivation for a related problem is set out in mathoverflow.net/questions/207043/… . – Raphael Jun 19 '15 at 15:53