Thoughts on Talks: Polya’s Theorem and Fourier Transforms

Polya’s theorem states, colloquially speaking, that “a drunk man will eventually return home, but a drunk bird might not.” Though an interesting theorem, the novelty of today’s talk by resident probabilist Aaron Montgomery was that by using Fourier transforms (and copious applications of Fubini’s theorem) the theorem is proved with relative ease and without any messy combinatorics. This explains the latter half of his title: “Local Central Limit Theorem for Z^d or: How I Learned to Stop Worrying and Love the Fourier Transform,” though as Aaron himself stated the first part of the title did not actually make an appearance.

During the talk, I began to remember the rich connection one has between integrals and our respective fields. In functional analysis, we associate integrals with algebraic functions: linear functionals and inner products. In probability, the association is with expected values. But more than a surface level association, this gives a depth to the subjects involved and the seemingly straightforward yet stubbornly difficult integral becomes something alluring yet austere.

As a contribution, I wanted to talk about how functional analysis fit into this talk, but first I have to retell the beginning.

The basic setup is that one has a sequence $\{X_i\}$ of independent, identically distributed random vectors in $\mathbb{Z}^d$. These vectors correspond to the steps that our random walker (or flyer as the case may be) are taking. The example of interest to us is where we take the standard basis vectors and vectors obtained by multiplying them by -1 and give them uniform probability of being chosen. We will call this the simple random walk. So in the case of $d=2$, we have a $1/4$ chance of going up, down, left or right. To keep track of the walker’s position, we just need to add up the vectors: $S_n=\sum_{i=1}^{n}X_i$.

We consider the characteristic functions $\Phi_{X}(t)=\mathbb{E}(e^{it\cdot X})$, and by independence we have $\Phi_{S_n}=\Phi_{X_1}^n$. This follows quickly from the fact that $X_i$ are independent and identically distributed. But we pause here briefly, to mention the fact that rare numerical equality of the integral of a product with the product of integrals is the very condition of independence, about which we usually rely on our intuitive notion. This quickly reminded me about Mark Kac’s monograph about the subject, but maybe more on that later this month.

The latter is computable, at least in the simple case, we have that $\Phi_{X_1}(t)=\frac{1}{d}\sum_{k=1}e^{it_k}+e^{-it_k}=\frac{1}{d}\sum_{k=1}^{d}\cos(t_k)$.

It is at this point in the talk that we see functional analysis taking a peek, bidding us to invite it in. We notice that by taking the proper scaling of our usual Lebesgue measure on $[-\pi,\pi]^d$, we have that the functions $f_x(t)=e^{it\cdot x}$ form an orthonormal basis for $x\in\mathbb{Z}^d$, and that by definition of expected value, one has $\Phi_{S_n}(t)=\sum_{x\in\mathbb{Z}^d}\mathbb{P}(S_n=x)e^{it\cdot x}$. So we have that our characteristic function can be written as a linear combination of our orthonormal basis, but more to the point, we have numerical values for the coefficients of that sum by taking inner products!

So with a generalization of Parseval’s identity, we have that $\langle \Phi_{X_1}^n(t), e^{it\cdot x} \rangle = \mathbb{P}(S_n=x)$, or to put this in integral terms: $\int_{[-\pi,\pi]^d}\!\Phi_{X_1}^n(t)e^{-it\cdot x}\,dm=\mathbb{P}(S_n=x)$.

The characteristic function lines up the information we need and sorts them out, and then the Fourier transform allows us to take them out.

Of course, we still have some computations to do and it is not easy, but with this association between the probabilities of $S_n$ and the characteristic function, we have something that we can estimate and prove the theorem.