Matthew N. Bernstein

Matthew N. Bernstein

Machine learning scientist at Stellaromics

The binomial theorem

4 minute read

Published:

The binomial theorem appears in many proofs across mathematics and mathematical statistics. In this post, I will walk through a proof of this theorem.

Introduction

The Binomial Theorem is a basic theorem in mathematics that states that a binomial expression of the form $(x+y)^n$ can be represented as a summation involving the binomial coefficient:

\[(x+y)^n = \sum_{k=0}^n {n \choose k} x^ky^{n-k}\]

This statement always appeared mysterious to me. What is the intuition for the summation? Moreover, why does the binomial coefficient, “$n$ choose $k$”, appear? In this post I will provide a proof that helped me better intuit this theorem.

Proof

Let’s start with a polynomial of the form

\[(a + b)(c + d)(e + f)\]

We can apply the distributive property as follows:

\[(a + b)(c + d)(e + f) = a(c+d)(e+f) + b(c+d)(e+f)\]

Notice that the first and second terms are two separate polynomials involving $a$ and $b$ where the first only involves $a$, but not $b$, whereas the second polynomial only involves $b$, but not $a$. In fact, for each binomial factor (i.e. for each of $(a + b)$, $(c + d)$, and $(e + f)$), only one of the terms of the binomial will appear in a given term of the fully expanded polynomial.

\[\begin{align*}(a + b)(c + d)(e + f) &= a(c+d)(e+f) + b(c+d)(e+f) \\ &= a(c(e+f) + d(e+f)) + b(c(e+f) + d(e+f)) \\ &= ace + acf + ade + adf + bce + bcf + bde + bdf\end{align*}\]

To form a term in the fully expanded polynomial, we imagine the process of iterating over each binomial factor and choosing one of the two terms to include. For example, from $(a+b)$, we choose either $a$ or $b$ to include in the term, but never both. This is because of how the distributive property works: as we expanded the expression, we separated the two terms in each binomial factor so that they never could appear in the same term of the expansion. This process is depicted in the following diagram:

drawing

We also see that every combination of terms from each binomial factor will be used to form a term in the expanded polynomial. Again, this occurs from the process of carrying out the distributive property repeatedly when carrying out the expansion: everytime we perform the distributive property, we create two batches of terms in the expansion that will include either the first or second term from that binomial factor. Each batch is created in a split in the tree diagram above.

With this insight, let’s look at the following polynomial:

\[\begin{align*}(x + y)^3 &= (x + y)(x + y)(x + y) \\ &= x(x+y)(x+y) + y(x+y)(x+y) \\ &= x(x(x+y) + y(x+y)) + y(x(x+y) + y(x+y)) \\ &= xxx + xyx + yxx + yyx + xxy + xyy + yxy + yyy \\ &= x^3 + 3x^2y + 3y^2x + y^3\end{align*}\]

Let’s say we’re interested in all terms in the expanded polynomial that have $k$ of the $x$ terms. By the previous observation, any term that has $k$ of the $x$ terms must have $n − k$ of the $y$ terms because we only pick a single term from each of the original binomial factors. Now, how many of the terms in the expanded polynomial will have $k$ of the $x$ terms and $n-k$ of the $y$ terms? Recall that every combination of ways of picking $k$ of the $x$ terms from the binomial factors will result in a term in the expansion of the form $x^ky^{n-k}$. We can think of this as computing all possible ways of choosing $k$ $x$ terms from the $n$ binomial factors. Thus, there will be ${n \choose k}$ such terms.

Finally, there are terms in the polynomial with $k$ $x$ terms for every value of $k$ between $0$ and $n$. Again, this follows from from the fact that every combination of terms from each of the binomial factor will be used to form a term in the expanded polynomial, and thus, there must be at least one term with $k$ of the $x$ terms and $n-k$ of the $y$ terms. This final observation leads to the Binomial Theorem:

\[(x+y)^n = \sum_{k=0}^n {n \choose k} x^ky^{n-k}\]

$\square$

You May Also Enjoy

Notes on The Art of War by Sun Tzu (Books 1 and 2)

27 minute read

Published:

I am currently reading Sun Tzu’s Art of War and, as cliche as it sounds, am finding much wisdom in it. I have been taking notes during my reading and I thought I’d share them in this post. Here I cover Books 1 and 2.

Denoising diffusion probabilistic models (Part 2: Theoretical justification)

11 minute read

Published:

In Part 1 of this series, we introduced the denoising diffusion probabilistic model for modeling and sampling from complex distributions. We described the diffusion model as a model that can generate new samples by learning how to reverse a diffusion process. In this post, we provide more theoretical justification for the objective function used to fit diffusion models and make connections between the diffusion model and other concepts in statistical inference and probabilistic modeling.

Denoising diffusion probabilistic models (Part 1: Definition and derivation)

56 minute read

Published:

Diffusion models are a family of state-of-the-art probabilistic generative models that have achieved ground breaking results in a number of fields ranging from image generation to protein structure design. In Part 1 of this two-part series, I will walk through the denoising diffusion probabilistic model (DDPM) as presented by Ho, Jain, and Abbeel (2020). Specifically, we will walk through the model definition, the derivation of the objective function, and the training and sampling algorithms. We will conclude by walking through an implementation of a simple diffusion model in PyTorch and apply it to the MNIST dataset of hand-written digits.

Assessing the utility of data visualizations based on dimensionality reduction

14 minute read

Published:

We human beings use our vision as our chief sense for understanding the world, and thus when we are confronted with data, we try to understand that data through visualization. Dimensionality reduction methods, such as PCA, t-SNE, and UMAP, are approaches designed to enable the visualization of high-dimensional data. Unfortunately, because these methods inevitably distort aspects of the data, these methods are receiving new scrutiny. In this post, I propose that dimensionality reduction requires a “probabilistic” framework of interpretation rather than a “deterministic” one wherein conclusions one draws from a dimensionality reduction plot have some probability of not actually being true of the data. I will propose that this does not mean these plots are not useful. Rather, to evaluate their utility, I will argue that empirical user studies of these methods will shed light on whether these methods provide more benefit or more harm in practice.