Difficulty understanding step in Kac's proof of Feynman-Kac Theorem

I am trying to understand a proof of the Feynman-Kac Theorem, as set out in Mark Kac's 1949 paper 'On Distributions of Certain Wiener Functionals'.

Kac defines a series of independent and identically distributed, discrete random variables $\left( X_i\right)_{i\in\mathbb N}$, each of which has value either 1 or $-1$ with equal probability.

On page 6 he makes the following statement, without providing any justification:

$$\mathbb{P}\left\{\sum_{i=1}^k X_i=m\right\}=\frac{1}{2\pi}\int_0^{2\pi}e^{-im\xi}\cos^k\xi\ d\xi$$

for any $m\in\mathbb Z$.

I am totally stumped as to how this formula is justified. The left-hand side should be fairly simple as, if my calculations are correct, it is equal to $$\mathbb{P}\left\{2M_k^{0.5}-k=m\right\}$$ where $M_k^p$ is a binomial random variable that is the result of $k$ trials with probability of success $p$.

The integral on the right looks like it will have a complex result, and hence not be equal to that on the left. Complex numbers and integrals have played no part in the paper up to that point, so their sudden introduction is a complete surprise.

Also, while I could not integrate the expression, Wolfram Alpha says the indefinite integral is (replacing $\xi$ by $x$):

$$i\frac{2^{-k}(e^{-ix}+e^{ix})(1+e^{2ix})^{-k}e^{-imx}{}_2F_1(-k,-\frac k2-\frac m2;-\frac k2-\frac m2+1;-e^{-2ix})}{k+m}$$

where the ${}_2F_1$ item is the hypergeometric function.

For $x=0$ this is

$$i\frac{2^{-k}\cdot 2^k\cdot2^{-k}\cdot 1\cdot {}_2F_1(-k,-\frac k2-\frac m2;-\frac k2-\frac m2+1;-1)}{k+m}$$which is $$i\frac{2^{-k}\cdot {}_2F_1(-k,-\frac k2-\frac m2;-\frac k2-\frac m2+1;-1)}{k+m}$$which is $$i\cdot\frac{2^{-k}}b\cdot {}_2F_1(-k,-b;1-b;-1)$$where $b\equiv (k+m)/2$.

The same value should be obtained for $x=2\pi$, so it seems to me that, based on that, the definite integral should be zero.

I am stuck in a situation where, not only can I see neither motivation nor justification for Kac's introduction of the formula on the RHS, but on my (quite possibly faulty) calculations, that step seems to lead to an impossible result.

I would be very grateful to anybody that can help me understand this.

Thank you very much.

• For the record, I don't know the answer, but it looks like something to do with Fourier transforms/coefficients (the imaginary exponential, the limits of the integral being 0 and two pi, the cosine term). My guess is that it has something to do with the characteristic function of the sum of independent Bernoulli random variables -- for n=2 this is the triangular distribution: en.wikipedia.org/wiki/Triangular_distribution -- for general $n$ the density function should be some convex polygonal path. Jun 26 '16 at 2:08

Note that the characteristic function of the sum of the random variables being described is:

$$(\frac{1}{2}e^{-it}+\frac{1}{2}e^{it})^k=\cosh^k(it)=\cos^k(t)$$

since it is the sum of $k$ independent random variables, each of which has the characteristic function $\frac{1}{2}e^{-it}+\frac{1}{2}e^{it}$ (use the convolution formula).

Then he just uses one of the characteristic function inversion formulas (see for example: https://en.wikipedia.org/wiki/Characteristic_function_(probability_theory)#Inversion_formulas) to get the probability mass function back from the characteristic function.

EDIT: This question seems to give a better account of using the inversion formula for this specific case (discrete random variables): Recovering pmf from characteristic function

EDIT: An explanation of why the bounds are $[0, 2\pi]$ can be found here, Theorem 3.8 (take d=1 and then note that integrating over $[-\pi, \pi]$ should give the same result as $[0,2\pi]$ due to the periodicity of the cosine and imaginary exponential). http://www.math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/Hill.pdf

Also search anywhere for "characteristic function random walk". I believe there are discussions of using characteristic functions to calculate and estimate probabilities in both Durrett and Feller's probability theory textbooks. Spitzer's classic treatise on random walks almost certainly discusses it. Characteristics functions give us an easier way to show that the random walk in any dimension greater than or equal to 3 is not recurrent, in addition to allowing us to calculate probabilities associated with random walks, as is being done in Kac's paper.

• Thank you very much. I had not come across characteristic fns before. They are really interesting! I now get that the pdf of a discrete RV is a sum of Dirac deltas. A remaining obstacle seems to be that Kac integrates only over $[0,2\pi]$ rather than over the whole real line. So his formula differs from the inversion formula in that respect. That may be related to the fact that he needs his formula to give a proper function of $m$, not a distribution as a sum of Dirac deltas would be (because the LHS is a proper function). I'll ponder this some more. Jun 27 '16 at 1:09
• We used a similar technique to study the probability distributions of random walks in my class (which is essentially what those random variables are). An explanation of why the bounds are $[0, 2\pi]$ can be found here, Theorem 3.8 (take d=1 and then note that integrating over $[-\pi, \pi]$ should give the same result as $[0,2\pi]$ due to the periodicity of the cosine and imaginary exponential. We did a very similar procedure in my probability course, but I don't have my notes nearby and I forgot the motivation. Jun 27 '16 at 1:16
• Sorry here's the link math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/Hill.pdf @AndrewKirk Jun 27 '16 at 1:16
• Thank you very much William. That proof you posted was exactly what I needed. The problem is now solved, I can go on with deciphering the paper, and I have learned about characteristic functions into the bargain! Jun 27 '16 at 9:01