Timeline for Growth of inner products between two random vectors on the sparse hypercube
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2016 at 6:50 | comment | added | Steve | Thanks. I am interested in the case where $s = o(\sqrt{d}$, that is $s^2 / d$ goes to zero. | |
| Apr 11, 2016 at 8:43 | comment | added | Ben Barber | What ranges of $s$ and $d$ are of interest? If say $s$ is some constant fraction of $d$ then the inner products are tightly concentrated in an interval of length $O(\sqrt d)$ around $0$. More generally, the inner products look like taking some number of steps of the symmetric random walk on $\mathbb Z$, with varying degrees of laziness. | |
| Apr 8, 2016 at 8:10 | comment | added | kodlu | @FedorPetrov, thanks, that $d-s$ helps. | |
| Apr 8, 2016 at 6:57 | comment | added | Fedor Petrov | Definitely $M_k$ does not depend on $\bf{v}$. | |
| Apr 8, 2016 at 6:56 | comment | added | Fedor Petrov | Ah, $n-s$ should be of course $d-s$. | |
| Apr 8, 2016 at 6:54 | comment | added | Fedor Petrov | @kodlu each other coordinate is 0, +1 or -1, this is what $1+2x$ is about: 1 is for 0, $x$ for +1, $x$ for -1. | |
| S Apr 8, 2016 at 5:59 | history | suggested | Minkov | CC BY-SA 3.0 |
spelling edit
|
| Apr 8, 2016 at 4:54 | review | Suggested edits | |||
| S Apr 8, 2016 at 5:59 | |||||
| Apr 7, 2016 at 22:15 | comment | added | kodlu | It would be wonderful to have this explained in a full answer. I can see the $t$ and $t^{-1}$ account for +1 and -1, in up to $s$ positions (thus raise to power $s$) but how does the $(1+2x)$ term work? | |
| Apr 7, 2016 at 21:23 | comment | added | Fedor Petrov | $M_k/2$ is a coefficient of $x^st^k$ in $(1+tx+x/t)^s (1+2x)^{n-s}$. | |
| Apr 7, 2016 at 20:14 | history | asked | Steve | CC BY-SA 3.0 |