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.



Fourier transform of a simple random walk
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).
$$


