# Electoral vote distributions are polynomials

Published on

In his article Electoral vote distributions are Monoids, Gabriel Gonzalez poses and answers the following question based on 538’s data:

what would be Hillary’s chance of winning if each state’s probability of winning was truly independent of one another?

To answer the question, Gabriel devises a divide-and-conquer algorithm. He computes probability distributions over vote counts in subsets of all states and then combines them. He also observes that vote distributions form a monoid.

Here I want to share an algebraic perspective on vote counting and show why distributions form a monoid.

Let $p_i$ be the probability of Hillary’s victory in state $i$, and $n_i$ be the number of electoral college votes for that state, where $i=1,\ldots,N$, and $N$ is the total number of states (and districts; see Gabriel’s post for details).

Then a vote distribution is a collection of probabilities $q_k$ that Hillary will get exactly $k$ votes:

$\newcommand{\p}[1]{\mathrm{Pr}\{#1\}} $$q_k = \p{\text{number of votes for H.Clinton} = k},\;k=1,\ldots,\sum_{i=1}^N n_i.$$$

Consider the following polynomial:

$Q(x)=\prod_{i=1}^N\left(p_i x^{n_i}+(1-p_i)\right).$

This is a product of $N$ brackets, one for each state. If we expanded it, we would get $2^N$ terms. Every such term takes either $p_i x^{n_i}$ or $1-p_i$ from each bracket and multiplies them. Every such term corresponds to a particular election outcome: if Hillary won in a particular state, take $p_i x^{n_i}$ from the corresponding bracket; otherwise, take $1-p_i$.

For example, if an election outcome means that Hillary won in states $1,4,\ldots$ and lost in states $2,3,\ldots$, then the corresponding term is

$p_1 x^{n_1}(1-p_2)(1-p_3)p_4 x^{n_4}\ldots=p_1(1-p_2)(1-p_3)p_4\ldots x^{n_1+n_4+\ldots}.$

Notice that $p_1(1-p_2)(1-p_3)p_4\ldots$ is exactly the probability of the outcome (under the independence assumption) and $n_1+n_4+\ldots$ is the number of votes for Hillary under that outcome.

Since the power of $x$ in each term is the number of votes for Hillary, outcomes that result in the same number of votes, say $k$, correspond to like terms. If we combine them, their probabilities (terms’ coefficients) will add up. To what? To $q_k$, the total probability of Hillary getting $k$ votes.

Therefore,

$Q(x) = \sum_{k}q_kx^k.$

Deriving the final vote distribution $q_k$ from $p_i$ and $n_i$ is just expanding and reducing $Q(x)$ from $\prod_{i=1}^N\left(p_i x^{n_i}+(1-p_i)\right)$ to $\sum_{k}q_kx^k$.

As Gabriel notes, doing this in the direct way would be inefficient. His divide-and-conquer approach directly translates to expanding $Q(x)$: divide all brackets into two groups, recursively expand the groups, combine the results.

Under this formulation, it becomes obvious that vote distributions form a proper monoid: it is just a monoid of polynomials under multiplication.