Sums of powers of roots

It is known since Newton's time that sums of the form \(\sigma_k:=\sum x_i^k\) are polynomial expressions in the coefficients of \(f=\prod(z-x_i)\). What follows is my best understanding of this. We use a formal power series approach, and therefore define \(N_f:=\sum\sigma_kz^k\). I want to prove that \[z^nf(\frac1z)N_f(z) = z^{n-1}f'(\frac1z).\label{th1}\tag{1}\] (It is written this way since \(z^nf(\frac1z)\) and \(z^{n-1}f'(\frac1z)\) are polynomials.)

The proof uses logarithmic differentiation and geometric series expansion only. \begin{align*} \frac{z^{n-1}f'(\frac1z)}{z^nf(\frac1z)} &= \frac1z(\log f)'\left(\frac1z\right) &&= \frac1z\sum\frac1{\frac1z-x_i} \\ &= \sum\frac1{1-x_iz} &&= \sum x_i^kz^k \\ &= \sum\sigma_kz^k &&= N_f(z) \end{align*} For example suppose \(f=(z-x_0)(z-x_1)=(z-2)(z-3)=z^2-5z+6\). The first few sums are \[\sigma_0 = 2,\quad\sigma_1=5,\quad\sigma_2=13,\quad\sigma_3=35,\quad\sigma_4=97\] so \(N_f\approx2+5z+13z^2+35z^3+97z^4\). Furthermore \(z^nf(\frac1z)=1-5z+6z^2\) and \(z^{n-1}f'(\frac1z)=2-5z\). We may test \((\ref{th1})\) by computing its left- and right-hand sides up to fourth order: \[(2+5z+13z^2+35z^3+97z^4)(1-5z+6z^2) = (2-5z) \mod z^5.\] Conversely, we can compute more terms \(\sigma_k\) by polynomial division: \[N_f = \frac{2-5z}{1-5z+6z^2} = \sum_{0\leq k\lt m}\sigma_kz^k + z^m\frac{\textrm{remainder polynomial}}{1-5z+6z^2}\] In python:

>>> z = sympy.var('z')
>>> Nf = sympy.fps((2-5*z)/(1-5*z+6*z*z))
>>> Nf.truncate(10)
2 + 5*z + 13*z**2 + 35*z**3 + 97*z**4 + 275*z**5
+ 793*z**6 + 2315*z**7 + 6817*z**8 + 20195*z**9 + O(z**10)

Demuxing a random variable

Suppose \(f = ag + (1-a)h\), a convex combination of pdfs. Then \(f\) is a pdf.

Suppose \(X\) has \(f\) as pdf. For any evaluation \(x\) of \(X\), produce a random variable with conditional distribution, \[Y\sim\text{Bernoulli}\left(\frac{(1-a)h(x)}{(ag(x)+(1-a)h(x)}\right).\] Then \(X|(Y=0)\sim g\) and \(X|(Y=1)\sim h\) since \begin{align} p(x|0) &= \frac{p(0|x)p(x)}{\sum_{x'}p(0|x')p(x')} = \frac{\frac{ag(x)}{f(x)}f(x)}{\sum_{x'}\frac{ag(x)}{f(x)}f(x)}\\ &= \frac{ag(x)}{\sum_{x'}ag(x')} = \frac{a\cdot g(x)}{a\cdot1} = g(x)\\ p(x|1) &= \frac{p(1|x)p(x)}{\sum_{x'}p(1|x')p(x')} = \frac{\frac{(1-a)h(x)}{f(x)}f(x)}{\sum_{x'}\frac{(1-a)h(x)}{f(x)}f(x)}\\ &= \frac{(1-a)h(x)}{\sum_{x'}(1-a)h(x')} = \frac{(1-a)\cdot h(x)}{(1-a)\cdot1} = h(x). \end{align}

The utility of this construction is as follows: It lets you turn a probabilistic experiment with definite outcomes (say the probabilities are \([0.2,\,0.6,\,0.2]\)) into an experiment with outcomes which are again probability distributions, such as \([0.4,\,0.6,\,0]\) and \([0,\,0.6,\,0.4]\), each with probability \(\frac12\). This blurs the distinction between deterministic variables (or often equivalently zero variance, zero entropy) and nondeterministic variables (positive variance, positive entropy).

In fact, it suggests that entropy can be calculated from the coefficients of an arbitrary convex combination. In the example just given, the entropy of \([0.2,\,0.6,\,0.2]\)) with respect to \([0.4,\,0.6,\,0]\) and \([0,\,0.6,\,0.4]\) is the entropy of \([0.5,\,0.5]\) with respect to \([1,\,0]\) and \([0,\,1]\), i.e. \(\frac12\log2+\frac12\log2=1\).

And why not try affine combinations! \[[0.2,\,0.6,\,0.2] = 2\cdot[\frac13,\,\frac13,\,\frac13]-1\cdot[\frac7{15},\,\frac1{15},\,\frac7{15}].\] The associated entropy in base 2 is \[-2\log2+1\log(-1) = -2+\pi i\log e = -2 + 4.53236i.\]