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.


1 Answer 1


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}_{\tau<i})+\mathbb{E }(\mathbb{1}_{X_\tau=a} \omega_i\mathbb{1}_{\tau>i-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). $$

  • $\begingroup$ 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. $\endgroup$ Jan 4, 2019 at 14:15
  • $\begingroup$ 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. $\endgroup$ Feb 22, 2019 at 12:46
  • $\begingroup$ Also, if I use this computation for an example in my master's, do you want to be cited and if so how? $\endgroup$ Feb 22, 2019 at 13:44
  • $\begingroup$ 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$. $\endgroup$
    – Kostya_I
    Mar 18, 2019 at 8:34
  • $\begingroup$ as for citation, you can cite the MO entry, just click the "cite" button below the post. $\endgroup$
    – Kostya_I
    Mar 18, 2019 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.