Timeline for Fourier transform of a simple random walk
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 18, 2019 at 8:35 | comment | added | Kostya_I | as for citation, you can cite the MO entry, just click the "cite" button below the post. | |
| Mar 18, 2019 at 8:34 | comment | added | Kostya_I | I don't have a reference ready (Spitzer, maybe?) but the computation is not hard. If you denote by $\phi(x,t)=\mathbb{P}^x(\tau>t)$ the probability for the random walk started from $x$, then it satisfies the obvious finite difference equation $\phi(x,t)=\frac12(\phi(x+1,t-1)+\phi(x-1,t-1))$, a discrete heat equation. Now you solve it just as the usual one: write a general solution as a linear combination of $e^{i \alpha x}e^{-\beta(\alpha) t}$ and figure out the coefficients from the boundary data $\phi(x,0)\equiv 1$, $\phi(a,i)\equiv\phi(-b,i)\equiv 0$. | |
| Feb 22, 2019 at 13:44 | comment | added | Vilhelm Agdur | Also, if I use this computation for an example in my master's, do you want to be cited and if so how? | |
| Feb 22, 2019 at 12:46 | comment | added | Vilhelm Agdur | Sorry to be following up on this so late (and accepting your answer so late), but could you point to where that probability can be found? I am apparently looking in the wrong books, because I can't find it. | |
| Feb 22, 2019 at 12:44 | vote | accept | Vilhelm Agdur | ||
| Jan 4, 2019 at 14:15 | comment | added | Vilhelm Agdur | That was indeed easier when computed using the actual definition. That it is an even function is correct. Even more useful is the observation that the function is monotone in the $\omega_i$s. For example, this monotonicity should imply (or at least it does in the finite-bit case) that the first-level Fourier coefficients are exactly the influences of the function. That is, they should be the probability that flipping bit $i$ changes the value of the function. That is what I was trying to compute, which was harder. | |
| Jan 4, 2019 at 13:15 | history | answered | Kostya_I | CC BY-SA 4.0 |