14
$\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$
4
  • $\begingroup$ What does it mean, to wrap a vector on to a circle? $\endgroup$ Jun 15, 2015 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$
    – Simd
    Jun 15, 2015 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, 2015 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$
    – Simd
    Jun 19, 2015 at 15:53

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.