Combinatorics and Asymptotics

TL;DR

1. $n!=1\cdot 2\cdots n$; $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$ = number of ways to choose $k$ of $n$. A set of $n$ elements has $2^n$ subsets; $n$ points have $2^n$ binary labelings.
2. Growth hierarchy: $\log n\ll n^a\ll e^{cn}$ (any power beats a log, any exponential beats any power).
3. $a_n=O(b_n)$: at most a constant times $b_n$. $a_n=o(b_n)$: $a_n/b_n\to 0$ (strictly smaller order).
4. Is it going to 0? Divide out, keep the dominant terms, compare powers: $\frac{\log n}{\sqrt{n}}\to 0$, $\sqrt{n}\cdot \frac{1}{\sqrt{n}}=1\nrightarrow 0$, $\sqrt{n}\cdot n^{-0.4}=n^{0.1}\to \infty$.

Counting

Factorials and binomial coefficients

$n!=1\cdot 2\cdots n$, $0!=1$. $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$, $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\left(\genfrac{}{}{0ex}{}{n}{n}\right)=1$, $\left(\genfrac{}{}{0ex}{}{n}{1}\right)=n$, $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$, $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$. ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$.

Pascal’s triangle for quick values:

$n$	$\left(\genfrac{}{}{0ex}{}{n}{0}\right),\left(\genfrac{}{}{0ex}{}{n}{1}\right),\dots$	${\sum }_{i\le 1}$	${\sum }_{i\le 2}$	${\sum }_{i\le 3}$	$2^n$
3	1, 3, 3, 1	4	7	8	8
4	1, 4, 6, 4, 1	5	11	15	16
5	1, 5, 10, 10, 5, 1	6	16	26	32
6	1, 6, 15, 20, 15, 6, 1	7	22	42	64
10	1, 10, 45, 120, 210, …	11	56	176	1024

The columns ${\sum }_{i\le d}\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ are exactly the Sauer-Shelah bound for VC dimension $d$ (L3): a class of VC dimension 2 realizes at most 11 of the 16 labelings of 4 points.

Memory aid

Labelings of $n$ points: $2^n$ (each point + or −). While a class shatters, its growth function doubles with every new point; after the VC dimension $d$ it can only grow like $n^d$. Read a growth table as “doubling, doubling, …, then slower”.

Where else counting appears:

• SHAP weights $\frac{|S|!(|F|-|S|-1)!}{|F|!}$: among all $|F|!$ orderings of the features, the fraction in which exactly the features of $S$ come before $i$ (L9.2). With 3 features: $\frac{1}{3},\frac{1}{6},\frac{1}{6},\frac{1}{3}$.
• No Free Lunch: on $m$ points there are $2^m$ possible target functions (L1.2).
• Bootstrap: a point is missed by one draw with probability $1-\frac{1}{n}$, by all $n$ draws with $(1-\frac{1}{n}{)}^n\approx e^{-1}\approx 0.37$, so a bootstrap sample contains about 63% of the distinct points (L6).

Growth rates

The hierarchy

$$1\ll \log n\ll \sqrt{n}\ll n\ll n\log n\ll n^2\ll \dots \ll 2^n\ll n!$$

$a_n\ll b_n$ means $a_n/b_n\to 0$. The base of the log does not matter for the order (${\log }_{2}n=\ln n/\ln 2$).

O and o

• $a_n=O(b_n)$: $|a_n|\le C{b}_n$ for some constant $C$ and large $n$ (“at most of the order”).
• $a_n=o(b_n)$: $a_n/b_n\to 0$ (“of strictly smaller order”).
• $a_n=\Omega (b_n)$: at least of the order; $\Theta$: both.

Example: $\frac{1}{n}=o\left(\frac{1}{\sqrt{n}}\right)$, but $\frac{1}{\sqrt{n}}$ is not $o\left(\frac{1}{\sqrt{n}}\right)$.

Deciding whether a rate goes to 0

Recipe: (1) write everything as powers of $n$ and logs, (2) keep only the dominant factor, (3) compare exponents: negative power → 0, logs lose against any power.

The stability condition ${\beta }_n=o(1/\sqrt{n})$ (L4)

Test $\sqrt{n}{\beta }_n\to 0$:

${\beta }_n$	$\sqrt{n}{\beta }_n$	$\to 0$?
$1/n$	$n^{-1/2}$	yes
$\log n/n$	$\log n/\sqrt{n}$	yes (power beats log)
$1/(\sqrt{n}\log n)$	$1/\log n$	yes, slowly
$1/\sqrt{n}$	$1$	no
$n^{-0.4}$	$n^{0.1}$	no, grows
$1/\log n$	$\sqrt{n}/\log n$	no, grows

Bound terms of Lecture 3

$\sqrt{\frac{d\log n}{n}}\to 0$ for fixed $d$ (the log loses against $n$). $\sqrt{\frac{n\log 2}{n}}$ is constant, so a class with $\mathcal{N}(n)=2^n$ gives no bound. With a growing VC dimension $d_n$: fine as long as $d_n\log n/n\to 0$, e.g. $d_n=\sqrt{n}$, but not $d_n=n/10$.

Memory aid

Logs are slow, powers are fast, exponentials are faster. When in doubt, plug in $n=10^6$: $\log n\approx 14$, $\sqrt{n}=1000$, $n^{0.1}\approx 4$, and see which way it moves as $n$ grows further.

Self-check

Question cards (4)

Compute $\left(\genfrac{}{}{0ex}{}{7}{3}\right)$ and the Sauer-Shelah bound for $d=2$, $n=7$.

Answer

$\left(\genfrac{}{}{0ex}{}{7}{3}\right)=35$. $\left(\genfrac{}{}{0ex}{}{7}{0}\right)+\left(\genfrac{}{}{0ex}{}{7}{1}\right)+\left(\genfrac{}{}{0ex}{}{7}{2}\right)=1+7+21=29$.

Is $\frac{\log n}{n^{0.1}}\to 0$?

Answer

Yes: any positive power beats the logarithm, even $n^{0.1}$ (it only takes very large $n$).

Is ${\beta }_n=n^{-0.6}$ good enough for the stability bound?

Answer

$\sqrt{n}{n}^{-0.6}=n^{-0.1}\to 0$: yes, ${\beta }_n=o(1/\sqrt{n})$.

How many SHAP subset terms does one feature have with $|F|=4$?

Answer

All subsets of the other 3 features: $2^3=8$.

Related

• Math overview · Inequalities and Convergence · Calculus and Optimization