DRMacIver's Notebook
Levy’s theorem
Levy’s theorem
I have this theorem from “Combinatorics of Permutations” by Miklós Bóna, where it’s frustratingly referred to as Levy’s theorem and neither proved nor referenced. Fortunately despite its incredibly odd looking nature it’s not actually that hard to prove.
Theorem: Let \(a_0, \ldots, a_n\) be a sequence of non-negative real numbers and let \(A(z) = \sum a_k z^k\). If \(A(z) > 1\) then the following two statements are equiovalent:
- The polynomial \(A(z)\) is either constant or has real zeros only.
- There are probabilities \(p_i\) such that if \(X_i\) are independent Bernoulli random variables with \(P(X_i = 1) = p_i\) then \(P(\sum X_i = k) = \frac{a_k}{A(1)}\). The roots of \(A(z)\) are \(-\frac{1 - p_i}{p_i}\) for the \(p_i\) with \(p_i > 0\).
This theorem took me completely aback when I saw it but once you see the proof it’s quite natural.
Let \(p_i\) be arbitrary probabilities. Without loss of generality assume that \(p_i > 0\) (if some of the \(p_i\) are non-zero this will just result in some of the high coefficients being 0$. Let \(X_i\) be independent bernoulli variables as above, and let \(d_k = P(\sum X_i = k)\).
Construct the generating function \(f(z) = \sum d_k z^k\). This can be written as \(f(z) = \sum\limits_{A \subseteq [n]} \prod\limits_{i \in A} z p_i \prod\limits_{i \not\in A} (1 - p_i)\), but this is \(\prod\limits_{i} (z_i p_i + 1 - p_i)\). This is a polynomial with roots at \(z = -\frac{1 - p_i}{p_i}\) as desired.
This gives us our implication from the second to the first. By construction and the fact that \(f(1) = P(0 \leq \sum X_i \leq n) = 1\), \(A(z) = A(1) f(z)\), so the roots of \(A(z)\) are the roots of \(f\) and \(d_k = \frac{a_k}{A(1)}\).
To get the other implication we just need to show every possible \(A(z)\) arises this way. i.e. we can always find \(p_i\) such that \(A(z) = A(1) f(z)\).
Let \(A(z)\) be non-constant and have real roots. Note that these roots must be negative, because for any \(z > 0\) we have \(A(z) \geq a_0 + \min(z, z^n) \min\limits_{i \geq 1} a_i > 0\). So suppose these roots are \(r_1, \ldots r_n\).
Because the formula for the roots of \(f\) takes the value \(0\) when \(p_i = 1\) and tends to \(-\infty\) as \(p_i \to 0\), we can choose our \(p_i\) so that \(r_i = -\frac{1 - p_i}{p_i}\). This ensures that \(A\) is proportional to \(f\), and again because \(f(z) = 1\) this means that \(A(z) = A(1) f(z)\) as desired.
QED
A rather surprising (to me) implication of this theorem is that unless there are \(j, k\) such that \(a_i > 0\) if and only if \(j \leq i \leq k\), \(A(z)\) has at least one non-real root. There’s presumably some elementary way of proving that, but it’s direct from Levy’s theorem because the probabilities of getting \(k\) successes have this property.
In general this seems to put strong constraints on the coefficients of polynomials with non-negative coefficients and real zeroes, but I haven’t fully understood what they are yet (something to do with log concativity of their coefficients?).