14

Consider two random vectors $v=(v_1,\dots, v_n)$ and $w=(w_1,\dots, w_{n+1})$. Each element of $v$ is independently $\pm1$ with prob $1/2$. Each element of $w$ is independently $1$ with probability $1/4$, $-1$ with probability $1/4$ and $0$ with probability $1/2$.

Let $X$ and $Y$ denote the inner product of $v$ and $(w_1,\dots,w_n)$ and the inner product of $v$ and $(w_2,\dots,w_n, w_{n+1})$ respectively, that is, $$X=\sum_{i=1}^nv_iw_i,\qquad Y=\sum_{i=1}^nv_iw_{i+1}.$$ We know that for large $n$,

$$P(X = 0)=P(Y=0) \sim \frac1{\sqrt{\pi n}}.$$

What is $P(Y=0\mid X=0)$?

  • $v$ and $w$ have different dimensions and their inner product is not well-defined. – Julian Wergieluk Dec 09 '14 at 15:49
  • @JulianWergieluk Thank you. I just fixed that. –  Dec 09 '14 at 15:49
  • Why the restriction to $n$ even? – Did Dec 10 '14 at 09:35
  • @Did It just happens to be all I need. I am happy to get rid of it if you think it makes no difference. Thank you for the edits to the question! –  Dec 10 '14 at 09:36
  • 2
    This looks related to this question. – robjohn Dec 10 '14 at 12:47
  • @robjohn Yes thanks. I copied some of the notation from there which I hope is OK. I don't think it is a duplicate though. The zeros in my question seem to make it more difficult. Also that other question seems to do some sort of cyclic wrapping. –  Dec 10 '14 at 12:48
  • @JulianWergieluk Add zeros to complete the dimensions. – Felix Marin Dec 17 '14 at 23:45
  • @FelixMarin There is no need to do that in this case. Hopefully the edit of Dec 10 makes this clear. –  Dec 18 '14 at 10:50
  • Fine. $\mbox{}$ – Felix Marin Dec 19 '14 at 13:39
  • So far, I was able to reduce the final result to $$ {1 \over 2^{n}}\oint_{|z|\ =\ 1}\oint_{|s|\ =\ 1} {{\mathbb E}\left[,\prod_{k\ =\ 1}^{n}\left(,z^{w_{k}}s^{w_{k + 1}} + z^{-w_{k}} s^{-w_{k + 1}},\right),\right] \over zs}\quad {{\rm d}z \over 2\pi{\rm i}},{{\rm d}s \over 2\pi{\rm i}} $$ but I was unable to go any further. – Felix Marin Dec 19 '14 at 16:21
  • @FelixMarin Would you mind explaining this a little, maybe in an answer? It looks very interesting. –  Dec 19 '14 at 16:40
  • I just undelete my partial answer such that you can check it. – Felix Marin Dec 19 '14 at 17:06
  • @FelixMarin Thank you! Why did you delete it? –  Dec 19 '14 at 17:07
  • I felt it was not complete enough. Thanks. – Felix Marin Dec 19 '14 at 17:09
  • @FelixMarin I think the problem is non-trivial so maybe it will inspire someone else. Unless people just won't look at a question that already has an answer? –  Dec 19 '14 at 17:10

1 Answers1

1

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\norm}[1]{\left\vert\left\vert\, #1\,\right\vert\right\vert} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ Lets $\ds{{\cal V}_{j}\pars{m}}$ the probability of any $\ds{v_{j}}$ take the values $\ds{m = \pm 1}$ and $\ds{{\cal W}_{j}\pars{m}}$ the probability of any $\ds{w_{j}}$ take the values $\ds{m = -1,0,1}$ such that $$ {\cal V}_{j}\pars{m} = \half\,,\qquad {\cal W}_{j}\pars{m}= {1 \over 4}\,\delta_{m,-1} + \half\,\delta_{m0} + {1 \over 4}\,\delta_{m1} ={1 \over 4}\,\delta_{m^{2},1} + \half\,\delta_{m0} $$

The result is given by: \begin{align}&\color{#66f}{\large{\rm P}\pars{Y=0\mid X=0}} \\[5mm]&=\sum_{v_{1}\ =\ \pm 1}{\cal V}_{1}\pars{v_{1}}\ldots \sum_{v_{n}\ =\ \pm 1}{\cal V}_{1}\pars{v_{n}} \sum_{w_{1}\ =\ -1}^{1}{\cal W}_{1}\pars{w_{1}}\ldots \sum_{w_{n + 1}\ =\ -1}^{1}{\cal W}_{1}\pars{w_{n}}\times \\&\phantom{===} \delta_{\sum_{j\ =\ 1}^{n}v_{j}w_{j},0}\ \delta_{\sum_{k\ =\ 1}^{n}v_{k}w_{k + 1},0} \\[5mm]&={1 \over 2^{n}}\sum_{v_{1}\ =\ \pm 1}\ldots\sum_{v_{n}\ =\ \pm 1} \sum_{w_{1}\ =\ -1}^{1}{\cal W}_{1}\pars{w_{1}}\ldots \sum_{w_{n + 1}\ =\ -1}^{1}{\cal W}_{1}\pars{w_{n}}\times \\&\phantom{===--} \delta_{\sum_{j\ =\ 1}^{n}v_{j}w_{j},0}\ \delta_{\sum_{k\ =\ 1}^{n}v_{k}w_{k + 1},0} \end{align}

With the identity $\delta_{a0}=\ds{\oint_{\verts{z}\ =\ 1}{1 \over z^{1 - a}} \,{\dd z \over 2\pi\ic}}$: \begin{align}&\color{#66f}{\large{\rm P}\pars{Y=0\mid X=0}} ={1 \over 2^{n}}\sum_{v_{1}\ =\ \pm 1}\ldots\sum_{v_{n}\ =\ \pm 1} \sum_{w_{1}\ =\ -1}^{1}{\cal W}_{1}\pars{w_{1}}\ldots \sum_{w_{n + 1}\ =\ -1}^{1}{\cal W}_{1}\pars{w_{n}}\times \\&\oint_{\verts{z}\ =\ 1}{1 \over z^{1 - \sum_{j\ =\ 1}^{n}v_{j}w_{j}}} \,{\dd z \over 2\pi\ic} \oint_{\verts{s}\ =\ 1}{1 \over s^{1 - \sum_{k\ =\ 1}^{n}v_{k}w_{k + 1}}} \,{\dd s \over 2\pi\ic} \\[5mm]&={1 \over 2^{n}}\oint_{\verts{z}\ =\ 1}\oint_{\verts{s}\ =\ 1} {1 \over zs}\sum_{v_{1}\ =\ \pm 1}\ldots\sum_{v_{n}\ =\ \pm 1} \sum_{w_{1}\ =\ -1}^{1}{\cal W}_{1}\pars{w_{1}}\ldots \sum_{w_{n + 1}\ =\ -1}^{1}{\cal W}_{1}\pars{w_{n}}\times \\& z^{\sum_{j\ =\ 1}^{n}v_{j}w_{j}}s^{\sum_{k\ =\ 1}^{n}v_{k}w_{k + 1}} \,{\dd z \over 2\pi\ic}\,{\dd s \over 2\pi\ic} \\[5mm]&={1 \over 2^{n}}\oint_{\verts{z}\ =\ 1}\oint_{\verts{s}\ =\ 1} {1 \over zs}\sum_{v_{1}\ =\ \pm 1}\ldots\sum_{v_{n}\ =\ \pm 1} \sum_{w_{1}\ =\ -1}^{1}{\cal W}_{1}\pars{w_{1}}\ldots \sum_{w_{n + 1}\ =\ -1}^{1}{\cal W}_{1}\pars{w_{n}}\times \\&\pars{z^{w_{1}}s^{w_{2}}}^{v_{1}}\ldots\pars{z^{w_{n}}s^{w_{n + 1}}}^{v_{n}} \,{\dd z \over 2\pi\ic}\,{\dd s \over 2\pi\ic} \\[5mm]&={1 \over 2^{n}}\oint_{\verts{z}\ =\ 1}\oint_{\verts{s}\ =\ 1} {1 \over zs}\sum_{w_{1}\ =\ -1}^{1}{\cal W}_{1}\pars{w_{1}}\ldots \sum_{w_{n + 1}\ =\ -1}^{1}{\cal W}_{1}\pars{w_{n}}\times \\&\pars{z^{w_{1}}s^{w_{2}} + z^{-w_{1}}s^{-w_{2}}}\ldots \pars{z^{w_{n}}s^{w_{n + 1}} + z^{-w_{n}}s^{-w_{n + 1}}} \,{\dd z \over 2\pi\ic}\,{\dd s \over 2\pi\ic} \\[1cm]&={1 \over 2^{n}}\oint_{\verts{z}\ =\ 1}\oint_{\verts{s}\ =\ 1} \\[2mm]&{{\mathbb E}\bracks{% \pars{z^{w_{1}}s^{w_{2}} + z^{-w_{1}}s^{-w_{2}}}\ldots \pars{z^{w_{n}}s^{w_{n + 1}} + z^{-w_{n}}s^{-w_{n + 1}}}} \over zs} \,{\dd z \over 2\pi\ic}\,{\dd s \over 2\pi\ic} \end{align}

$\ds{\tt\mbox{So far, I couldn't go any further}}$.

Felix Marin
  • 89,464