17
$\begingroup$

[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}}.$$

$\endgroup$
  • $\begingroup$ What does it mean, to wrap a vector on to a circle? $\endgroup$ – Gerry Myerson Jun 15 '15 at 0:04
  • $\begingroup$ @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. $\endgroup$ – Raphael Jun 15 '15 at 6:10
  • $\begingroup$ 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 $\endgroup$ – vzn Jun 19 '15 at 14:17
  • $\begingroup$ @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/… . $\endgroup$ – Raphael Jun 19 '15 at 15:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.