(no subject)

[impossiblewizardry]

Let X be a random variable which can be 0, 1, 2, etc. (that is, with support on the non-negative integers.)

Consider a constant number n. The probability that n divides X is

(1/n) ∑ Ψ(2π k / n) from k=0 to n-1

where Ψ(t) is the characteristic function of X, that is, the expected value of exp(i t X).

Deriving this formula was a good exercise in using the fact that the discrete Fourier transform is unitary. The basic idea is: expectations are dot products, dot products are preserved under unitary transformations. So instead of taking a dot product between a function and a probability distribution, you can take it between the Fourier transform of that function, and the Fourier transform of the probability distribution, which is given by values of the characteristic function.

The formula itself is also cool, since I didn’t really expect it to be this easy, since it’s related to divisibility, which I think of as a stubborn discrete math concept. For most of the distributions I think about, the characteristic function is easily obtained. In fact, I have the characteristic function more often than I have the probabilities themselves. So I can evaluate this probability pretty easily for small n.

Although for large n this formula is not so easy. Although the sum is finite, its size scales with n, and for no distribution that I’ve tried have I been able to simplify it to a constant-size formula. (although for the geometric distribution, I can get a constant-size formula more directly.)