Skip to content

Polya's Criterion

Polya’s criterion, in the context of probability theory, is a condition used to determine whether a function is a characteristic function. Combined with the property that characteristic functions are non-negative definite, Pólya's criterion ensures that the function is non-negative definite.
POLYA'S CRITERION
Let φ(t)\varphi(t) be real nonnegative and have φ(0)=\varphi(0)= 1,φ(t)=φ(−t)1, \varphi(t)=\varphi(-t), and φ\varphi is decreasing and convex on (0,∞)(0, \infty) with
lim⁡t↓0φ(t)=1,lim⁡t↑∞φ(t)=0\begin{equation*}\lim _{t \downarrow 0} \varphi(t)=1, \quad \lim _{t \uparrow \infty} \varphi(t)=0\end{equation*}
Then there is a probability measure ν\nu on (0,∞)(0, \infty), so that
φ(t)=∫0∞(1−∣ts∣)+ν(ds)\begin{equation}\varphi(t)=\int_0^{\infty}\left(1-\left|\frac{t}{s}\right|\right)^{+} \nu(d s)\end{equation}
and hence φ\varphi is a characteristic function.

Proof of Polya's criterion

The following proof is due to Durrett [Durrett2019], p. 119.
The assumption that lim⁡t→0φ(t)=1\lim _{t \rightarrow 0} \varphi(t)=1 is necessary because the function φ(t)=\varphi(t)= 1{0}(t)1_{\{0\}}(t) which is 1 at 0 and 0 otherwise satisfies all the other hypotheses.

Radon-Nikodym measure

\quad Proof. Let φ′\varphi^{\prime} be the right derivative of ϕ\phi, i.e.,
φ′(t)=lim⁡h\0φ(t+h)−φ(t)h\begin{equation*}\varphi^{\prime}(t)=\lim _{h \backslash 0} \frac{\varphi(t+h)-\varphi(t)}{h}\end{equation*}
Since φ\varphi is convex this exists and is right continuous and increasing. So we can let μ\mu be the measure on (0,∞)(0, \infty) with
μ(a,b]=φ′(b)−φ′(a)for all 0≤a<b<∞,\begin{equation*}\mu(a, b]=\varphi^{\prime}(b)-\varphi^{\prime}(a) \quad \text{for all } 0 \leq a<b<\infty,\end{equation*}
and let ν\nu be the measure on (0,∞)(0, \infty) with
dν/dμ=s.\begin{equation*}d \nu / d \mu=s.\end{equation*}

Integrating over new measure

Since φ\varphi is decreasing, we have φ′(t)≤0\varphi'(t)\le 0 for all t>0t>0. Also, because φ\varphi is convex, the function φ′\varphi' is increasing, so the limit
ℓ:=lim⁡t→∞φ′(t)\begin{equation*}\ell:=\lim_{t\to\infty}\varphi'(t)\end{equation*}
exists and satisfies ℓ≤0\ell\le 0. In fact ℓ=0\ell=0. Indeed, if ℓ<0\ell<0, then for some ϵ>0\epsilon>0 we would have φ′(t)≤−ϵ\varphi'(t)\le -\epsilon for all sufficiently large tt, and hence φ(t)\varphi(t) would eventually decrease at least linearly, which would force φ(t)<0\varphi(t)<0 for large tt. This contradicts the assumption that φ\varphi is nonnegative. Therefore
lim⁡t→∞φ′(t)=0.\begin{equation*}\lim_{t\to\infty}\varphi'(t)=0.\end{equation*}
Now, by the definition of μ\mu, for every s>0s>0 we have
μ((s,∞))=lim⁡b→∞μ((s,b])=lim⁡b→∞(φ′(b)−φ′(s))=−φ′(s).\begin{equation*}\mu((s,\infty))=\lim_{b\to\infty}\mu((s,b])=\lim_{b\to\infty}\bigl(\varphi'(b)-\varphi'(s)\bigr)=-\varphi'(s).\end{equation*}
Since dν/dμ=rd\nu/d\mu=r, we have ν(dr)=r μ(dr)\nu(dr)=r\,\mu(dr), and therefore r−1ν(dr)=μ(dr)r^{-1}\nu(dr)=\mu(dr). Hence
−φ′(s)=μ((s,∞))=∫(s,∞)μ(dr)=∫(s,∞)r−1ν(dr).\begin{equation*}-\varphi^{\prime}(s)=\mu((s,\infty))=\int_{(s,\infty)} \mu(dr)=\int_{(s,\infty)} r^{-1} \nu(d r).\end{equation*}
Since lim⁡u→∞φ(u)=0\lim_{u\to\infty}\varphi(u)=0, we also have for every t≥0t\ge 0
φ(t)=−∫t∞φ′(s) ds.\begin{equation*}\varphi(t)=-\int_t^\infty \varphi'(s)\,ds.\end{equation*}
Substituting the previous formula for −φ′(s)-\varphi'(s) and using Fubini's theorem, we get for t≥0t \geq 0
φ(t)=∫t∞∫s∞r−1ν(dr)ds=∫t∞r−1∫trdsν(dr)=∫t∞(1−tr)ν(dr)=∫0∞(1−tr)+ν(dr)\begin{equation*}\varphi(t) =\int_t^{\infty} \int_s^{\infty} r^{-1} \nu(d r) d s=\int_t^{\infty} r^{-1} \int_t^r d s \nu(d r) =\int_t^{\infty}\left(1-\frac{t}{r}\right) \nu(d r)=\int_0^{\infty}\left(1-\frac{t}{r}\right)^{+} \nu(d r)\end{equation*}
Using φ(−t)=φ(t)\varphi(-t)=\varphi(t) to extend the formula to t≤0t \leq 0 we have (1)(1). Setting t=0t=0 in (1)(1) shows ν\nu has total mass 1.

Approximating by atomic measures

If φ\varphi is piece-wise linear, ν\nu has a finite number of atoms and the result follows from fact that weighted average of characteristic function is again characteristic function. To prove the general result, let νn\nu_n be a sequence of measures on (0,∞)(0, \infty) with a finite number of atoms that converges weakly to ν\nu and let
φn(t)=∫0∞(1−∣ts∣)+νn(ds)\begin{equation*}\varphi_n(t)=\int_0^{\infty}\left(1-\left|\frac{t}{s}\right|\right)^{+} \nu_n(d s)\end{equation*}
Since s→(1−∣t/s∣)+s \rightarrow(1-|t / s|)^{+}is bounded and continuous, φn(t)→φ(t)\varphi_n(t) \rightarrow \varphi(t) and the desired result follows from Levy's Continuity Theorem. □\Box

Applications of Polya's criterion

Examples of φ1(t)\varphi_1(t) and φ2(t)\varphi_2(t)
We can apply Polya's criterion to verify whether certain functions are characteristic. Simple examples which can be deduced to characteristic from the plot are
φ1(t)=exp⁡(−∣t∣)φ2(t)={1−∣t∣,∣t∣≤1,0,∣t∣>1.\begin{align*}\varphi_1(t) &= \exp(-|t|) \\\varphi_2(t) &= \begin{cases} 1 - |t|, & |t| \leq 1 , \\ 0, & |t|>1 .\end{cases}\end{align*}

Exponent with power less two

We can see that in the case 1<α<21 < \alpha < 2 the function exp⁡(−∣t∣α)\exp(-|t|^\alpha) is not convex and Polya's criterion can be applied directly
THEOREM
exp⁡(−∣t∣α)\exp(-|t|^\alpha) is a characteristic function for 0<α<20 < \alpha < 2
The case α=1\alpha = 1 corresponds to the Cauchy distribution and the case α=2\alpha = 2 corresponds to the standard normal distribution.
\quad Proof. The key idea is to approximate the function exp⁡(−∣t∣α)\exp(-|t|^\alpha) by a sequence of characteristic functions and then apply Lévy's Continuity Theorem at the end.
The function which help us to make approximation is
ψ(t)=1−(1−cos⁡t)α/2.\begin{equation*}\psi(t) = 1 - (1 - \cos t)^{\alpha/2}.\end{equation*}
Then for any for any β\beta and ∣x∣<1|x| < 1 we have the formula
(1−x)β=∑n=0∞(βn)(−x)n,(βn)=β(β−1)⋯(β−n+1)1⋅2⋅…⋅n.\begin{equation*}(1 - x)^\beta = \sum_{n=0}^{\infty} \binom{\beta}{n} (-x)^n,\qquad\binom{\beta}{n} = \frac{\beta (\beta - 1) \cdots (\beta - n + 1)}{1 \cdot 2 \cdot \ldots \cdot n}.\end{equation*}
Now we can represent ψ(t)\psi(t) as a infinite series
ψ(t)=1−(1−cos⁡t)α/2=∑n=1∞cn(cos⁡t)n,cn=(α/2n)(−1)n+1.\begin{equation*}\psi(t) = 1 - (1 - \cos t)^{\alpha/2} = \sum_{n=1}^{\infty} c_n (\cos t)^n, \qquad c_n = \binom{\alpha/2}{n} (-1)^{n+1}.\end{equation*}
cn≥0c_n \geq 0(we used α<2\alpha < 2), and ∑ncn=1\sum_n c_n = 1 (take t=0t=0 in the definition of ψ(t)\psi(t)). To confirm that ψ(t)\psi(t) is a characteristic function, first note that
P(X=1)=P(X=−1)=1/2⟹EeitX=eit+e−it2=cos⁡t.\begin{equation*}\mathbb{P}(X = 1) = \mathbb{P}(X = -1) = 1/2 \quad \Longrightarrow \quad \mathbb{E}e^{itX} = \frac{e^{it} + e^{-it}}{2} = \cos t.\end{equation*}
So cos⁡t\cos t is a characteristic function. Moreover, if X1,…,XnX_1,\dots,X_n are independent random variables with
P(Xk=1)=P(Xk=−1)=12⟹Eeit(X1+⋯+Xn)=∏k=1nEeitXk=(cos⁡t)n.\begin{equation*}\mathbb{P}(X_k=1)=\mathbb{P}(X_k=-1)=\tfrac12 \quad \Longrightarrow \quad \mathbb{E}e^{it(X_1+\cdots+X_n)} = \prod_{k=1}^n \mathbb{E}e^{itX_k} = (\cos t)^n.\end{equation*}
Hence (cos⁡t)n(\cos t)^n is also a characteristic function. Since a weighted average of characteristic functions remains a characteristic function, it follows that ψ(t)\psi(t) is indeed a characteristic function. From analysis 1−cos⁡t∼t2/21 - \cos t \sim t^2/2 as t→0t \to 0, so
1−cos⁡(2tn1/α)∼t2n2/α.\begin{equation}1 - \cos( \frac{\sqrt{2} t}{n^{1/\alpha}}) \sim \frac{t^2}{n^{2/\alpha}}.\end{equation}
Using the above-mentioned lemma, we get the pointwise limit
lim⁡n→∞{ψ(2tn1/α)}n=lim⁡n→∞{1−(1−cos⁡(2tn1/α))α/2}n=exp⁡(−∣t∣α).\begin{equation*}\lim_{n \to \infty} \{\psi(\frac{\sqrt{2} t}{n^{1/\alpha}})\}^n = \lim_{n \to \infty} \left\{ 1 - (1 - \cos( \frac{\sqrt{2} t}{n^{1/\alpha}}))^{\alpha/2} \right\}^n = \exp(-|t|^\alpha).\end{equation*}
Since each function {ψ(2tn1/α)}n\{\psi(\frac{\sqrt{2} t}{n^{1/\alpha}})\}^n is a characteristic function, Lévy's Continuity Theorem implies that exp⁡(−∣t∣α)\exp(-|t|^\alpha) is also a characteristic function. □\Box

References

  • [Durrett2019]Durrett, Rick. Probability: Theory and Examples. Fifth edition. Cambridge University Press, 2019. PDF.