Mathematics

Combinatorics

Combinatorics, the branch of mathematics concerned with counting, arrangement, and combination of objects, plays a crucial role in quantitative finance. It provides the mathematical foundation for analyzing various financial models, optimizing portfolios, pricing complex derivatives, and managing risks. This introduction aims to shed light on the key aspects of combinatorics, ending with an introduction on a foundational distribution in the finance space: the binomial distribution.

Random Variables I Random Variables II The Covariance Matrix Multiple Random Variables Moments Combinatorics Conditional Probability Markov Chains Random Processes Stochastic Calculus

Combinatorics is the branch of mathematics concerned with counting, arranging and selecting objects. Combinatorics is used in quantitative finance, as we will see when we cover the binomial pricing model, and combinatorics questions come up frequently in technical interviews. The first concept we will outline is combinations. Combinations are a way to choose a subset of items from a larger set, where the order of selection does not matter. Suppose we have $n$ objects. The total number of possible ways of having $k$ distinct combinations of objects from the starting pool of $n$, disregarding order of objects is $$ {n \choose k} = \frac{n!}{(n-k)!k!} $$ $n!$ denotes the factorial of n - the product of all integers from one to $n$ inclusive $$ n! = \prod_{k=1}^{n} k. $$

The size of the sample space is the total number of combinations of 5 cards from a 52 card deck. $${52 \choose 5} = 2598960$$ To calculate the number of possible of combinations of 5 cards that contain two pairs, we have to restrict 4 cards to be such that they make up two pairs. The total number of combinations of 2 pairs from 13 card ranks is ${13 \choose 2}$. We have 4 cards to create each pair, so there are ${4 \choose 2}$ ways of constructing each pair. We restrict the final card to be one that is a different rank from these pairs, and there are 44 possible cards left which fit this category. Therefore the answer is ${13 \choose 2} \cdot {4 \choose 2} \cdot {4 \choose 2} \cdot 44 = 123552$. The probability of the hand containing two pairs is therefore $$ P(\text{hand has 2 pairs}) = \frac{N_{2pairs}}{N_{total}} = \frac{123552}{2598960} = 4.75\%. $$
Example: the Binomial Distribution

Consider an experiment which can either succeed with probability $p$ or fail with probability $1-p$. The binomial distribution is a discrete probability distribution which gives the probability of $k$ successes in $n$ independent experiments. The probability mass function is $$ f(k,n,p) = P(X=k) = {n \choose k} p^k (1-p)^{n-k}. $$ Notice that the probability mass function includes ${n \choose k}$, that is, the number of ways to distribute $k$ successes in a set of $n$ trials. The expected value of the binomial distribution is $$ \text{E}[X] = np $$ and the variance is $$ \text{Var}(X) = np(1-p). $$

Probability mass function of the binomial distribution for $p=0.5$ (top) and $p=0.8$ (bottom). A normal distribution is fitted to each binomial distribution (gray).

Probability mass function of the binomial distribution

An important property of the binomial distribution is that if $n$ is large and $p$ is not too close to zero or one, then the binomial distribution can be reasonably approximated by a normal distribution with equal mean and variance, that is $$ f(k,n,p) \sim N(np, np(1-p)). $$ We see the figure above that for $n=20, p=0.5$ that the distribution is well approximated by a normal distribution. However, for $p=0.8$ the approximation is less accurate. This approximation enables us to do some remarkable calculations with very little working.

Initially, this problem looks intractable. However, a normal distribution will accurately approximate the distribution. Since the exponential term, $e^{-\frac{(x-\mu)^2}{2\sigma^2}}$, is equal to $1$ at the mean, the value of the normal distribution at the mean is $$ f(x = \mu) = \frac{1}{\sigma \sqrt{2 \pi}}. $$ Now, since the normal distribution is continuous and the binomial is discrete, we need the area under the curve in the range $499.5$ to $500.5$. So, the answer is simply the area of a rectangle with sides $1$ and $\frac{1}{\sigma \sqrt{2\pi}}$. We insert the standard deviation of the binomial distribution to get $$ P(X = 500) = \frac{1}{\sqrt{2 \pi n p (1-p) }} = \frac{1}{\sqrt{500\pi}} \approx \frac{1}{\sqrt{1600}} = \frac{1}{40} = 2.5\%. $$ The real answer is $2.522\%$, so our quick approximation got us to within 5% of the real answer. This question is quite popular in technical interviews but is on the more difficult side, so understanding this technique is sure to impress your interviewer.