# Fourier transform of a simple random walk

Consider the usual simple random walk on $$\mathbb{Z}$$, taking steps of +1 or -1 with equal probability. Of course, each trajectory corresponds uniquely to an element of $$\{-1,1\}^\infty$$. Now, there is an obvious way to identify this with $$\mathbb{Z}_2^\infty$$, and this is in fact a nice compact abelian group.

So, the functional of a simple random walk which, say, gives the hitting time of some $$k$$, or the indicator function of the event that we hit $$n$$ before $$-n$$, can be seen as functions from $$\mathbb{Z}_2^\infty$$ into $$\mathbb{R}$$. Thus, these functions have Fourier transforms.

Unless I am completely mistaken, the Fourier transform of these functions should look like (taking our omegas to be -1 or 1, for convenience) $$f(\omega_1,\omega_2,\ldots) = \sum_{S\subset\mathbb{N},\ |S|<\infty} \hat{f}(S)\prod_{i\in S}\omega_i$$ with $$\hat{f}(S)$$ real-valued Fourier coefficients, analogously to the Fourier analysis of functions of finitely many $$\omega$$.

Has this been studied before? Do the Fourier coefficients of these functions encode anything interesting about the simple random walk?

I tried to analyse the second example a bit, trying to compute the level one Fourier coefficients (i.e. the ones corresponding to singleton subsets of $$\mathbb{N}$$). Letting $$\tau_{x,y}$$ be the first time the random walk hits $$y$$ after it has hit $$x$$, and let $$\tau_x$$ be the hitting time of $$x$$ from $$0$$, and further letting $$\tau^i_x$$ be the first time after time $$i$$ at which the random walk hits $$x$$, I get the following formula: $$\hat{f}(\{i\}) = \mathbb{P}\left(\omega_i = 1, i \leq \tau_n, \tau^i_{-(n-1)} < \tau_{n+1}-i\ \middle|\ \tau_n < \tau_{-n}\right)$$ which I don't really immediately see how to compute.

I doubt that this is of any use but the 1-element modes are not hard to compute. Let $$X_i:=\sum^i_{k=1}\omega_k$$ be the random walk and $$\tau=\min\{i:X_i=a\text{ or }X_i=-b\}$$. We have $$\mathbb{E }(\mathbb{1}_{X_\tau=a} \omega_i)=\mathbb{E }(\mathbb{1}_{X_\tau=a} \omega_i\mathbb{1}_{\taui-1})=\mathbb{E }(\mathbb{1}_{X_\tau=a} \omega_i\mathbb{1}_{\tau>i-1}),$$ by strong Markov property. Now, you can write $$\mathbb{E }(\mathbb{1}_{X_\tau=a} \omega_i\mathbb{1}_{\tau>i-1})=\mathbb{E}(\mathbb{1}_{\tau>i-1}\mathbb{E}(\mathbb{1}_{X_\tau=a}\omega_i |\omega_1,\dots,\omega_{i-1})).$$ On the event $$\tau>i-1$$, the conditional expectation of $$\mathbb{1}_{X_\tau=a}$$ given $$\omega_1,\dots,\omega_i$$ is just $$(X_i+b)/(a+b)$$. Therefore, we have on that event $$\mathbb{E}(\mathbb{1}_{X_\tau=a}\omega_i |\omega_1,\dots,\omega_{i-1})=\frac{1}{2}\frac{X_{i-1}+1+b}{a+b}-\frac{1}{2}\frac{X_{i-1}-1+b}{a+b}=\frac{1}{a+b},$$ so that $$\mathbb{E }(\mathbb{1}_{X_\tau=a} \omega_i)=\frac{\mathbb{P}(\tau>i-1)}{a+b}.$$ The latter probability is not hard to compute using discrete Fourier transfrom, or find in any book.
The last simple observation is that if you take $$a=-b$$, then all the modes for even-size sets vanish, since $$\mathbb{E}(\mathbb{1}_{\tau_a<\tau_-a}(\omega)\omega_S)=\mathbb{E}(\mathbb{1}_{\tau_a<\tau_{-a}}(-\omega)\omega_S)=\mathbb{E}((1-\mathbb{1}_{\tau_a<\tau_{-a}}(\omega))\omega_S).$$
• 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. – Vilhelm Agdur Jan 4 '19 at 14:15
• 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$. – Kostya_I Mar 18 '19 at 8:34