1 Probability and Computing 1.4 Chernoff and Hoeffding Bounds 1.6 The Probabilistic Method

1.5 Balls, Bins, and Random Graphs

1.5.1 A few things I should have noted about $e$

We begin with the definition of $e$ and $e^{-1}$

\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^{n}=e,\lim_{n\to\infty}\left(1-% \frac{1}{n}\right)^{n}=\frac{1}{e}.

Both $f(n)=(1+1/n)^{n}$ and $g(n)=(1-1/n)^{n}$ are monotone, proven as follows:

•

Let $\varphi_{f}(n)=n\ln\left(1+1/n\right)$ , then the first order derivative

$\varphi_{f}^{\prime}(n)=\ln\left(1+\frac{1}{n}\right)+n\cdot\frac{1}{1+1/n}% \cdot\left(-\frac{1}{n^{2}}\right)=\ln\left(1+\frac{1}{n}\right)-\frac{1}{1+n}.$

Let $t=1+1/n>1$ , then

$\varphi_{f}^{\prime}(n)=\ln\left(1+\frac{1}{n}\right)-\frac{1}{1+n}=\ln\left(1% +\frac{1}{n}\right)+\frac{n}{1+n}-1=\ln t+\frac{1}{t}-1.$

As $t>1$ and by integral,

$\ln t=\int^{t}_{1}\frac{1}{x}dx>\left(t-1\right)\cdot\frac{1}{t},$

we have $\varphi_{f}^{\prime}(n)>0$ , and thus $\varphi_{f}(n)$ is monotone increasing.
•

Similarly, let $\varphi_{g}(n)=n\ln\left(1-1/n\right)$ , then the first order derivative

$\varphi_{g}^{\prime}(n)=\ln\left(1-\frac{1}{n}\right)+n\cdot\frac{1}{1-1/n}% \cdot\left(-\frac{-1}{n^{2}}\right)=\ln\left(1-\frac{1}{n}\right)+\frac{1}{n-1}.$

Let $t=1-1/n$ that $0<t<1$ , then

$\varphi_{g}^{\prime}(n)=\ln\left(1-\frac{1}{n}\right)+\frac{1}{n-1}=\ln\left(1% -\frac{1}{n}\right)+\frac{n}{n-1}-1=\ln t+\frac{1}{t}-1.$

As $0<t<1$ and by integral again,

$\ln t=\int^{t}_{1}\frac{1}{x}dx=-\int^{1}_{t}\frac{1}{x}dx>-(1-t)\cdot\frac{1}% {t},$

we have $\varphi_{g}^{\prime}(n)>0$ , and thus $\varphi_{g}(n)$ is monotone increasing.

Moreover, by the Taylor expansion

e^{x}=\sum_{i\geq 0}\frac{x^{i}}{i!},

then $e^{x}\geq 1+x$ for all $x$ . We derive following handy inequality from the Taylor expansion.

Lemma 1.5.1.

For integer $x\geq 0$ and $n\geq 0$ , we have

\frac{1}{x!}\leq\frac{e^{n}}{n^{x}}.

Proof.

By Taylor expansion, since

\frac{n^{x}}{x!}\leq\sum_{m\geq 0}\frac{n^{m}}{m!}=e^{n},

therefore

\frac{1}{x!}\leq\frac{e^{n}}{n^{x}}.

∎

Exercise 1.5.2 (Exercise 5.7 [MU17]).

Use the Taylor expansion

\ln(1+x)=x-\frac{x^{2}}{2}+\frac{x^{3}}{3}-\frac{x^{4}}{4}+\cdots

to prove that, for any $\left|x\right|\leq 1$ , $e^{x}(1-x^{2})\leq 1+x\leq e^{x}$ .

Proof.

We prove the left side $e^{x}(1-x^{2})\leq 1+x$ first. Take $\ln$ on both sides, we have left side $x+\ln(1+x)+\ln(1-x)$ .

Now by the Taylor expansion, for $\left|x\right|\leq 1$ , we have

	$\displaystyle x+\ln(1+x)+\ln(1-x)$	$\displaystyle=x+x-\frac{x^{2}}{2}+\frac{x^{3}}{3}-\frac{x^{4}}{4}\cdots-x-% \frac{x^{2}}{2}-\frac{x^{3}}{3}-\frac{x^{4}}{4}\cdots$
		$\displaystyle=x-2\cdot\frac{x^{2}}{2}-2\cdot\frac{x^{4}}{4}\cdots$
		$\displaystyle\leq x-\frac{x^{2}}{2}+\frac{x^{3}}{3}-\frac{x^{4}}{4}+\cdots=\ln% (1+x).$

The right side holds from the Taylor expansion of $e^{x}$ , and we conclude that for $\left|x\right|\leq 1$ , $e^{x}(1-x^{2})\leq 1+x\leq e^{x}$ . ∎

Lemma 1.5.3.

For any integer $k\geq 1$ , by concavity of $\ln x$ ,

\frac{1}{2}\left(\ln k+\ln\left(k+1\right)\right)\leq\int^{k+1}_{k}\ln xdx.

Lemma 1.5.4 (Lemma 5.8 [MU17]).

n!\leq e\sqrt{n}\left(\frac{n}{e}\right)^{n}.

Proof.

Since $\ln n!=\sum_{i\in[1,n]}\ln i$ , and we have the following from lemma 1.5.3

\sum_{i\in[1,n]}\ln i\leq\int^{n}_{1}\ln xdx+\frac{1}{2}\ln n=n\ln n-n+1+\frac% {1}{2}\ln n,

which completes the proof by exponenting over $e$ on both sides. ∎

Corollary 1.5.5.

By lemma 1.5.1 and lemma 1.5.4, we have

\left(\frac{n}{e}\right)^{n}\leq n!\leq e\sqrt{n}\cdot\left(\frac{n}{e}\right)% ^{n}\text{ and }\frac{1}{e\sqrt{n}}\cdot\left(\frac{e}{n}\right)^{n}\leq\frac{% 1}{n!}\leq\left(\frac{e}{n}\right)^{n}.

1.5.2 Birthday Paradox and Balls-and-Bins model

Suppose there are $n$ possible birthdays, and there are $m$ people in a room. Then, the probability that all $m$ are having different birthdays is

\prod_{j\in[0,m-1]}\left(1-\frac{j}{n}\right)\leq\prod_{j\in[0,m-1]}\exp\left(% -\frac{j}{n}\right)\leq\exp\left(-\frac{m^{2}}{2n}\right).

Hence, when $m=\sqrt{2n\ln 2}$ , the probability goes to $1/2$ .

But through union bound, we can also give a loose bound as follows. Consider event $E_{k}$ being the $k^{\mathrm{th}}$ people failed to have distinct birthday from all previous $k-1$ people. Then $\Pr\left[E_{k}\right]=\left(k-1\right)/n$ . Through union bound, the probability of the first $k$ people failed to have distinct birthdays is upper bounded by

\Pr\left[\bigcup_{i\in[1,k]}E_{i}\right]\leq\sum_{i\in[1,k]}\Pr\left[E_{i}% \right]=\frac{k(k-1)}{2n}.

The upper bound indicates that when $k=\left\lceil\sqrt{n}\right\rceil$ , the probability of having distinct birthdays is at most $1/2$ .

Moreover, assuming that first $\left\lceil\sqrt{n}\right\rceil$ birthdays are distinct, then the next $\left\lceil\sqrt{n}\right\rceil$ birthdays are different from the first $\left\lceil\sqrt{n}\right\rceil$ birthdays with probability upper bounded by

\left(1-\frac{\left\lceil\sqrt{n}\right\rceil}{n}\right)^{\left\lceil\sqrt{n}% \right\rceil}\leq\frac{1}{e}.

Therefore, once there are $2\left\lceil\sqrt{n}\right\rceil$ people out there, the probability of having all distinct birthdays is at most $1/e<1/2$ .

Remark 1.5.6.

The idea of union bound is used throughout the Poisson approximation and balls-and-bins model later on, after introduction of theorem 1.5.15.

Exercise 1.5.7 (Exercise 5.4 [MU17]).

Consider the extended birthday paradox, but with no 3 having same birthdays.

Proof.

Let there be $k$ people, and there be $n$ days in a year.

Suppose there are $j$ pairs of same birthdays, then we first consider the number of pair choices out of $k$ people. We can choose 2 people continuously from $k$ people, then rule out all the duplicate choices, as we don’t care about the ordering, and thus we have number of choices in total

\binom{k}{2}\binom{k-2}{2}\cdots\binom{k-2j+2}{2}\cdot\frac{1}{j!}=\frac{k!}{2% ^{j}(k-2j)!}\cdot\frac{1}{j!}=\binom{k}{2;\ldots;2}\cdot\frac{1}{j!}.

For each choice, there are $k-j$ days to be distinct, the rest $j$ people should have same birthdays as their pairs, leading to probability

\frac{1}{n^{j}}\cdot\prod_{i\in[1,k-j]}\left(1-\frac{i-1}{n}\right).

Now that the probability $p_{j}$ with $j$ pairs of same birthdays is

p_{j}=\frac{k!}{2^{j}(k-2j)!}\cdot\frac{1}{j!}\cdot\frac{1}{n^{j}}\cdot\prod_{% i\in[1,k-j]}\left(1-\frac{i-1}{n}\right),

summing over $p_{j}$ over $j\in\left[0,\left\lfloor\frac{k}{2}\right\rfloor\right]$ is the exact probability. ∎

Exercise 1.5.8 (Exercise 5.8 [MU17]).

$n$ balls are thrown independently and uniformly at random into $n$ bins.

•

Find the conditional probability that bin 1 has one ball given that exactly one ball fell into the first three bins.
•

Find the conditional expectation of the number of balls in bin 1 under the condition that bin 2 received no balls.
•

Write an expression for the probability that bin 1 receives more balls than bin 2.

Proof.

If conditioned that there are only 1 ball in first 3 bins, then the probability that a ball is in bin 1 is $1/3$ .

We introduce independent Bernoulli trials $\{X_{i}\}_{i\in[1,n]}$ with probability $1/n$ indicating if the $i^{\mathrm{th}}$ ball falls in bin 1. Then the conditional probability of $X_{i}=1$ given that the $i^{\mathrm{th}}$ ball does not fall into bin 2 is

\Pr\left[X_{i}=1\mid i^{\mathrm{th}}\text{ ball does not fall in bin 2}\right]% =\frac{1}{n-1}.

Therefore, the conditional expectation of $X=\sum_{i\in[1,n]}X_{i}$ under the condition that bin 2 has no balls is

	$\displaystyle\operatorname*{\mathbb{E}}\left[X\mid\text{bin 2 has no balls}\right]$	$\displaystyle=\sum_{i\in[1,n]}\operatorname*{\mathbb{E}}\left[X_{i}\mid\text{% bin 2 has no balls}\right]$
		$\displaystyle=\sum_{i\in[1,n]}1\cdot\Pr\left[X_{i}=1\mid i^{\mathrm{th}}\text{% ball does not fall in bin 2}\right]=\frac{n}{n-1}.$

There are only 3 cases related to balls in bin 1 and bin 2, one of more, less, or equal. By symmetry, former 2 cases are equal. Therefore, we need only the equal case to derive the exact result.

We choose $k\in\left[0,\left\lfloor\frac{n}{2}\right\rfloor\right]$ balls each for bin 1 and bin 2, and the probability is given by

p_{e,k}=\binom{n}{k;k}\left(\frac{1}{n}\right)^{k}\left(\frac{1}{n}\right)^{k}% \left(1-\frac{2}{n}\right)^{n-2k}=\binom{n}{k;k}\left(\frac{1}{n}\right)^{2k}% \left(1-\frac{2}{n}\right)^{n-2k}.

Therefore, the exact probability for the equal case is $p_{e}=\sum_{k}p_{e,k}$ , and the desired probability is $(1-p_{e})/2$ . ∎

Lemma 1.5.9 (Lemma 5.1 [MU17]).

When $n$ balls are thrown independently and uniformly at random into $n$ bins, the probability that the maximum load is more than $3\ln n/\ln\ln n$ is at most $1/n$ for $n$ sufficiently large.

Proof.

Suppose for the $i^{\mathrm{th}}$ bin receives at least $M$ balls, let it be event $E_{i}$ , then the probability is

\Pr\left[E_{i}\right]=\binom{n}{M}\frac{1}{n^{M}}.

If any bins are receiving with at least $M$ balls, by union bound, the probability is upper bounded by

\Pr\left[\bigcup_{i\in[1,n]}E_{i}\right]\leq\sum_{i\in[1,n]}\Pr\left[E_{i}% \right]=n\binom{n}{M}\frac{1}{n^{M}}.

Since

\binom{n}{M}\frac{1}{n^{M}}\leq\frac{1}{M!}\leq\left(\frac{e}{M}\right)^{M},

where second inequality follows from lemma 1.5.1, the probability is then upper bounded by $n\left(e/M\right)^{M}$ .

Choose $M=3\ln n/\ln\ln n$ , then when $n$ is sufficiently large, the probability upper bound is at most $1/n$ . ∎

Exercise 1.5.10 (Exercise 5.12 [MU17]).

The following problem models a simple distributed system wherein agents contend for resources but “back off” in the face of contention. Balls represent agents, and bins represent resources.

The system evolves over rounds. Every round, balls are thrown independently and uniformly at random into $n$ bins. Any ball that lands in a bin by itself is served and removed from consideration. The remaining balls are thrown again in the next round. We begin with $n$ balls in the first round, and we wish when every ball is served.

•

If there are $b$ balls at the start of a round, what is the expected number of balls at the start of the next round?
•

Suppose that every round the number of balls served was exactly the expected number of balls to be served. Show that all the balls would be served in $O(\log\log n)$ rounds. (Hint: If $x_{j}$ is the expected number of balls left after $j$ rounds, show and use that $x_{j+1}\leq x_{j}^{2}/n$ .)

Proof.

We first consider the expected number of remaining balls. Only the bin with one and only one ball can serve the ball, and thus we can disregard the ball onwards. We introduce $n$ independent 0-1 random variables $\{X_{i}\}_{i\in[1,n]}$ for $i^{\mathrm{th}}$ bin has one and only one ball to serve. Therefore, the probability for a bin with only one ball is

\Pr\left[X_{i}=1\right]=\binom{b}{1}\frac{1}{n}\left(1-\frac{1}{n}\right)^{b-1% }=\frac{b}{n}\cdot\left(1-\frac{1}{n}\right)^{b-1},

where $b$ is the number of balls remaining by now.

Let $X=\sum_{i\in[1,n]}X_{i}$ be the number of bins can serve (or balls to disregard), by linearity of expectation, we have

\operatorname*{\mathbb{E}}\left[X\right]=n\cdot\frac{b}{n}\cdot\left(1-\frac{1% }{n}\right)^{b-1}=b\cdot\left(1-\frac{1}{n}\right)^{b-1}.

Therefore, the remaining balls next round is $b-b\cdot\left(1-1/n\right)^{b-1}$ .

Let $b$ be the remaining balls to serve after round $j$ , then $x_{j+1}=b-b\cdot\left(1-1/n\right)^{b-1}$ . Since

\left(1-\frac{1}{n}\right)^{b-1}\geq 1-\frac{b-1}{n},

we have $x_{j+1}\leq b(b-1)/n$ , and therefore $x_{j+1}\leq x_{j}^{2}/n$ .

Now we write $y_{j}=x_{j}/n$ , and therefore $y_{j+1}\leq y_{j}^{2}$ , and we want to know the number of rounds to reach a $y=1/n$ . Suppose $y_{j}=1/2$ for some constant number of rounds $j$ , we count the number of additional rounds $r$ until we have

y_{j}^{2^{r}}=\left(\frac{1}{2}\right)^{2^{r}}\leq\frac{1}{n}.

Therefore $r=O(\log\log n)$ , that all balls will be served in $O(\log\log n)$ rounds. ∎

1.5.3 Poisson Distribution

Exercise 1.5.11 (Exercise 5.6 [MU17]).

Let $X$ be a Poisson random variable with mean $\mu$ , representing the number of a page of this book. Each error is independently a grammatical error with probability $p$ and a spelling error with probability $1-p$ . If $Y$ and $Z$ are random variables representing the number of grammatical and spelling error (respectively) on a page of this book, prove that $Y$ and $Z$ are Poisson random variables with means $\mu p$ and $\mu(1-p)$ , respectively. Also, prove that $Y$ and $Z$ are independent.

Proof.

The sum of a finite number of independent Poisson random variables is a Poisson random variable, by looking at the MGFs. Now think in a reverse way, that a Poisson random variable can be thinned down to a finite number of independent Poisson random variables, which is the Poisson Thinning (Splitting) Property.

Let a Poisson variable $X$ with mean $\mu$ represent the errors of a page, then $Y$ be the random variable represent the grammatical errors with probability $p$ in these errors. The probability of $Y=k$ is the summation of all conditional probability conditioned over $X$ by

	$\displaystyle\Pr\left[Y=k\right]$	$\displaystyle=\sum_{x\geq k}\Pr\left[Y=k\cap X=x\right]$
		$\displaystyle=\sum_{x\geq k}\Pr\left[Y=k\mid X=x\right]\cdot\Pr\left[X=x\right]$
		$\displaystyle=\sum_{x\geq k}\binom{x}{k}p^{k}\left(1-p\right)^{x-k}\cdot\frac{% e^{-\mu}\mu^{x}}{x!}=\frac{e^{-\mu}p^{k}\mu^{k}}{k!}\sum_{x\geq k}(1-p)^{x-k}% \cdot\frac{\mu^{x-k}}{(x-k)!}$
		$\displaystyle=\frac{e^{-\mu}p^{k}\mu^{k}}{k!}\cdot e^{(1-p)\mu}=\frac{e^{-p\mu% }(p\mu)^{k}}{k!},$

which is the probability of a Poisson random variable with mean $p\mu$ being $k$ . By symmetry, $Z$ is a Poisson random variable with mean $(1-p)\mu$ by substituting $p$ with $1-p$ .

For $Y$ and $Z$ being independent, we prove by the property of independence as follows:

	$\displaystyle\Pr\left[Y=y\cap Z=z\right]$	$\displaystyle=\Pr\left[Y=y\cap Z=z\mid X=y+z\right]\cdot\Pr\left[X=y+z\right]$
		$\displaystyle=\binom{y+z}{y}p^{y}(1-p)^{z}\cdot\frac{e^{-\mu}\mu^{y+z}}{(y+z)!% }=p^{y}(1-p)^{z}\cdot\frac{e^{-\mu}\mu^{y+z}}{y!z!}$
		$\displaystyle=\frac{e^{-p\mu}p^{y}\mu^{y}}{y!}\cdot\frac{e^{-(1-p)\mu}(1-p)^{z% }\mu^{z}}{z!}$
		$\displaystyle=\Pr\left[Y=y\right]\cdot\Pr\left[Z=z\right].$

∎

Lemma 1.5.12 (Exercise 5.14 [MU17]).

If $Z$ is a Poisson random variable of mean $\mu\geq 1$ integer, then $\Pr\left[Z\geq\mu\right]\geq 1/2$ .

•

Show that $\Pr\left[Z=\mu+h\right]\geq\Pr\left[Z=\mu-h-1\right]$ for $0\leq h\leq\mu-1$ .
•

Argue that $\Pr\left[Z\geq\mu\right]\geq 1/2$ .

Proof.

We write $\Pr\left[Z=\mu+h\right]=\delta_{h}\cdot\Pr\left[Z=\mu-h-1\right]$ , where $h\in\left[0,\mu-1\right]$ . Therefore,

\delta_{h}=\prod_{j\in[\mu-h,\mu-1]}\frac{\mu}{j}\cdot\prod_{j\in[\mu+1,\mu+h]% }\frac{\mu}{j}=\prod_{k\in[1,h]}\frac{\mu^{2}}{\left(\mu-k\right)\left(\mu+k% \right)}=\prod_{k\in[1,h]}\alpha_{k}.

As $\alpha_{k}\geq 1$ for $k\in[1,h]$ , therefore $\delta_{h}\geq 1$ . Thus $\Pr\left[Z\leq\mu-1\right]\leq\Pr\left[Z\geq\mu\right]$ , and $\Pr\left[Z\geq\mu\right]\geq 1/2$ .

Moreover, since $\delta_{0}=1$ , therefore $\Pr\left[Z=\mu-1\right]=\Pr\left[Z=\mu\right]$ . ∎

Theorem 1.5.13 (Poisson Median Range Theorem [Cho94]).

Let $Z$ be a Poisson random variable of mean $\mu>0$ , and $m$ be the median of $Z$ . Then

\mu-\ln 2\leq m\leq\mu+\frac{1}{3}.

If $\mu$ is an integer such that $\mu\geq 1$ , then $\mu=m$ , and thus $\Pr\left[Z\geq\mu\right]\geq 1/2$ and $\Pr\left[Z\leq\mu\right]\geq 1/2$ .

1.5.4 Poisson Approximation

Theorem 1.5.14 (Theorem 5.6 [MU17]).

Let $\{X_{i}^{(m)}\}_{i\in[1,n]}$ be the number of balls in each bin of the $m$ balls and $n$ bins model, and $\{Y_{i}^{(m)}\}_{i\in[1,n]}$ be independent Poisson random variables of mean $m/n$ . The distribution of $\left(X_{1}^{(k)},\ldots,X_{n}^{(k)}\right)$ is the same as the distribution of $\left(Y_{1}^{(m)},\ldots,Y_{n}^{(m)}\right)$ conditioned on $Y^{(m)}=\sum_{i\in[1,n]}Y_{i}^{(m)}=k$ , regardless of the value of $m$ .

Theorem 1.5.15 (Theorem 5.7 [MU17]).

Let $f(x_{1},\ldots,x_{n})$ be a nonnegative function. Then

\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{n}^{(m)}\right)% \right]\leq e\sqrt{m}\cdot\operatorname*{\mathbb{E}}\left[f\left(Y_{1}^{(m)},% \ldots,Y_{n}^{(m)}\right)\right].

Proof.

By conditional expectation and theorem 1.5.14, we have

	$\displaystyle\operatorname*{\mathbb{E}}\left[f\left(Y_{1}^{(m)},\ldots,Y_{n}^{% (m)}\right)\right]$	$\displaystyle=\sum_{k\geq 0}\operatorname*{\mathbb{E}}\left[f\left(Y_{1}^{(m)}% ,\ldots,Y_{n}^{(m)}\right)~{}\middle\|~{}Y^{(m)}=k\right]\Pr\left[Y^{(m)}=k\right]$
		$\displaystyle=\sum_{k\geq 0}\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(k)}% ,\ldots,X_{n}^{(k)}\right)\right]\Pr\left[Y^{(m)}=k\right]$
		$\displaystyle\geq\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{% n}^{(m)}\right)\right]\Pr\left[Y^{(m)}=m\right].$

By definition of the Poisson random variable, $Y^{(m)}$ is a Poisson random variable of mean $\mu=m$ , thus

\Pr\left[Y^{(m)}=m\right]=e^{-m}\cdot\frac{m^{m}}{m!}.

By lemma 1.5.4, $\Pr\left[Y^{(m)}=m\right]\geq\left(e\sqrt{m}\right)^{-1}$ . Therefore, $\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{n}^{(m)}\right)% \right]\leq e\sqrt{m}\cdot\operatorname*{\mathbb{E}}\left[f\left(Y_{1}^{(m)},% \ldots,Y_{n}^{(m)}\right)\right]$ . ∎

Corollary 1.5.16.

Let $E$ be an event. If $E$ has probability $p$ in the Poisson case, where there are $n$ independent Poisson random variables of mean $m/n$ , then $E$ has probability at most $e\sqrt{m}\cdot p$ in the exact $m$ balls and $n$ bins case.

Proof.

Immediately from theorem 1.5.15. ∎

Theorem 1.5.17 (Theorem 5.10 [MU17]).

Let $f(x_{1},\ldots,x_{n})$ be a nonnegative function such that $\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{n}^{(m)}\right)\right]$ is either monotonically increasing or monotonically decreasing in $m$ . Then

\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{n}^{(m)}\right)% \right]\leq 2\operatorname*{\mathbb{E}}\left[f\left(Y_{1}^{(m)},\ldots,Y_{n}^{% (m)}\right)\right].

Exercise 1.5.18 (Exercise 5.15 [MU17]).

Prove that if $\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{n}^{(m)}\right)\right]$ is monotonically increasing in $m$ , then

\operatorname*{\mathbb{E}}\left[f\left(Y_{1}^{(m)},\ldots,Y_{n}^{(m)}\right)% \right]\geq\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{n}^{(m% )}\right)\right]\Pr\left[Y^{(m)}\geq m\right],

again under the condition that $f$ is nonnegative.

Make a similar statement for the case when $\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{n}^{(m)}\right)\right]$ is monotonically decreasing in $m$ .

Moreover, prove theorem 1.5.17 for the case that $\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{n}^{(m)}\right)\right]$ is monotonically increasing in $m$ .

Proof.

We derive the chain of inequalities as follows

	$\displaystyle\operatorname*{\mathbb{E}}\left[f\left(Y_{1}^{(m)},\ldots,Y_{n}^{% (m)}\right)\right]$	$\displaystyle=\sum_{k\geq 0}\operatorname*{\mathbb{E}}\left[f\left(Y_{1}^{(m)}% ,\ldots,Y_{n}^{(m)}\right)~{}\middle\|~{}Y^{(m)}=k\right]\Pr\left[Y^{(m)}=k\right]$
		$\displaystyle=\sum_{k\geq 0}\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(k)}% ,\ldots,X_{n}^{(k)}\right)\right]\Pr\left[Y^{(m)}=k\right]$
		$\displaystyle\geq\sum_{k\geq m}\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(% k)},\ldots,X_{n}^{(k)}\right)\right]\Pr\left[Y^{(m)}=k\right]$
		$\displaystyle\geq\sum_{k\geq m}\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(% m)},\ldots,X_{n}^{(m)}\right)\right]\Pr\left[Y^{(m)}=k\right]$
		$\displaystyle=\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{n}^% {(m)}\right)\right]\Pr\left[Y^{(m)}\geq m\right].$

The first equality holds from conditional expectation, the second equality holds from theorem 1.5.14, the third holds from nonnegativity of $f$ , the fourth holds from $\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{n}^{(m)}\right)\right]$ being monotonically increasing in $m$ .

Similarly, if $f$ is nonnegative and $\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{n}^{(m)}\right)\right]$ is monotonically decreasing in $m$ , the following holds

\operatorname*{\mathbb{E}}\left[f\left(Y_{1}^{(m)},\ldots,Y_{n}^{(m)}\right)% \right]\geq\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{n}^{(m% )}\right)\right]\Pr\left[Y^{(m)}\leq m\right].

By lemma 1.5.12, theorem 1.5.13, and $Y^{(m)}$ being a Poisson random variable of mean $\mu=m\geq 1$ integer, therefore we prove theorem 1.5.17 for the $\operatorname*{\mathbb{E}}\left[f\left(X_{1}^{(m)},\ldots,X_{n}^{(m)}\right)\right]$ being monotonically increasing/decreasing in $m$ . ∎

Corollary 1.5.19 (Corollary 5.11 [MU17]).

Let $E$ be an event whose probability is monotonically increasing or decreasing in the number of balls. If $E$ has probability $p$ in the Poisson case, then $E$ has probability at most $2p$ in the exact case.

Proof.

Immediately follow from theorem 1.5.17. ∎

Lemma 1.5.20 (Lemma 5.12 [MU17]).

When $n$ balls are thrown independently and uniformly at random into $n$ bins, the max load is at least $\ln n/\ln\ln n$ with probability at least $1-1/n$ for $n$ sufficiently large.

Proof.

In the Poisson case, there are $n$ independent Poisson random varables $\{Z_{i}\}_{i\in[1,n]}$ of mean $1$ .

If $Z_{i}\geq M$ for some load $M$ , then

\Pr\left[Z_{i}<M\right]<1-\Pr\left[Z_{i}=M\right]=1-\frac{1}{eM!}.

Considering all $n$ Poisson random variables, then the probability of all loads being lower than $M$ is

\Pr\left[\bigcap_{i\in[1,n]}Z_{i}<M\right]<\left(1-\frac{1}{eM!}\right)^{n}% \leq\exp\left(-\frac{n}{eM!}\right).

From corollary 1.5.16 or corollary 1.5.19, we want the probability upper bound to be less than $1/n^{2}$ , as $e\sqrt{n}/n^{2}=o(1)$ . By lemma 1.5.4 and relax by sufficiently large $n$ and $M$ by

M!\leq e\sqrt{M}\left(\frac{M}{e}\right)^{M}\leq M\left(\frac{M}{e}\right)^{M},

therefore let $M=\ln n/\ln\ln n$ , with less than $1/n$ probability in exact case the max load is no greater than $M$ . ∎

Remark 1.5.21.

For $n$ balls and $n$ bins, the maximum load is $\Theta(\log n/\log\log n)$ from lemma 1.5.9 and lemma 1.5.20 with probability approaches 1 as $n\to\infty$ .

Exercise 1.5.22 (Exercise 5.13 [MU17]).

Suppose that we vary the balls-and-bins process as follows. For convenience let the bins be numbered from $0$ to $n-1$ . There are $\log_{2}n$ players. Each player choose a starting position $\ell\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\left[0,n-1\right]$ , then places one ball in each of the bins numbered $\ell\mod n$ to $\ell+n/\log_{2}n-1\mod n$ . Argue that the maximum load in this case is only $O(\log\log n/\log\log\log n)$ with probability that approaches 1 as $n\to\infty$ .

Proof.

For the $j^{\mathrm{th}}$ player and the $i^{\mathrm{th}}$ bin, we introduce an independent 0-1 random variable $X_{i,j}$ , indicating if the $j^{\mathrm{th}}$ player puts ball in the $i^{\mathrm{th}}$ bin. $\Pr\left[X_{i,j}=1\right]=1/\log_{2}n$ , as the $j^{\mathrm{th}}$ player starts at most $n/\log_{2}n$ bins before the $i^{\mathrm{th}}$ bin. Therefore, $X_{i}=\sum_{j\in[1,\log_{2}n]}X_{i,j}$ is the load of the $i^{\mathrm{th}}$ bin, and by linearity of expectation, $\operatorname*{\mathbb{E}}\left[X_{i}\right]=\sum_{j}\operatorname*{\mathbb{E}% }\left[X_{i,j}\right]=1$ . We can apply Chernoff’s tail bound to upper bound the probability for $X_{i}\geq 1+\delta$ by

\Pr\left[X_{i}\geq 1+\delta\right]\leq\frac{e^{\delta}}{(1+\delta)^{1+\delta}}.

By union bound, if there exists bins with load exceeding $1+\delta$ , the probability is upper bounded by $n\cdot e^{\delta}/(1+\delta)^{1+\delta}$ .

Let $t=1+\delta$ be the load bound, then the probability upper bound is $n/e\cdot\left(e/t\right)^{t}$ . We want to have

\lim_{n\to\infty}\frac{n}{e}\cdot\left(\frac{e}{t}\right)^{t}=0

to bound all of the bin loads. Taking $\ln$ on both sides, $t\ln t-t=\omega(\ln n)$ , giving only $t=O(\log n/\log\log n)$ .

But there are at most $\log_{2}n$ players and $n$ balls, such result follow from vanilla remark 1.5.21. The problem lies in that we did not utilize the structure of the player model, giving a loose bound.

Looking at the balls-and-bins structure, we can divide the circle into $\log_{2}n$ intervals, each has length $n/\log_{2}n$ . Let $\{Y_{i}\}_{i\in[1,\log_{2}n]}$ be independent random variables for number of players in the $i^{\mathrm{th}}$ interval, following $\log_{2}n$ balls and $\log_{2}n$ bins model. An observation is that, for a bin in the $i^{\mathrm{th}}$ interval, its load is at most $Y_{i}+Y_{i-1}$ , relaxed by

Y_{i}+Y_{i-1}\leq 2\max\left(Y_{i},Y_{i-1}\right).

Therefore, the max load of a bin is $O(Y_{i})$ .

We continue with Chernoff tail bound for $Y_{i}$ , then union bound over $\log_{2}n$ intervals, rather than over all $n$ bins. Since $\operatorname*{\mathbb{E}}\left[Y_{i}\right]=1$ , the probability for existing $Y_{i}\geq 1+\delta$ is $\log_{2}n\cdot e^{\delta}/(1+\delta)^{1+\delta}$ .

Again we write $t=1+\delta$ to be the number of players in an interval, and we want

\lim_{n\to\infty}\frac{\log_{2}n}{e}\cdot\left(\frac{e}{t}\right)^{t}=0,

and therefore $t\ln t-t=\omega(\log\log n)$ . We conclude that $t=O(\log\log n/\log\log\log n)$ , and the load is $O(t)$ .

This $\log n$ balls and $\log n$ bins max load result matches remark 1.5.21. ∎

1.5.5 Recap on Coupon Collector’s Problem

Theorem 1.5.23 (Theorem 5.13 [MU17]).

Let $X$ be the number of coupons observed before obtaining one of each of $n$ types of coupons. Then, for a constant $c$ ,

\lim_{n\to\infty}\Pr\left[X>n\ln n+cn\right]=1-e^{-e^{-c}}.

Proof.

We can view this problem in balls-and-bins model: If balls are thrown independently and uniformly at random into bins, how many balls are thrown until all bins have at least one ball? We begin with a Poisson approximation, and later demonstrate that the Poisson approximation gives the right answer in the limit.

We begin by Poisson approximation, supposing $\{X_{i}\}_{i\in[1,n]}$ independent Poisson random variable of mean $\ln n+c$ , then the expected number of balls is $m=n\ln n+cn$ . Let $E$ be the event that no bin is empty, and let $X=\sum_{i\in[1,n]}X_{i}$ be the number of balls in bin. Since $\Pr\left[X_{i}=0\right]=\left(ne^{c}\right)^{-1}$ , then

\lim_{n\to\infty}\Pr\left[E\right]=\lim_{n\to\infty}\left(1-\frac{1}{ne^{c}}% \right)^{n}=e^{-e^{-c}}.

Let $b=\sqrt{2m\ln m}$ . By conditional probability, we have

	$\displaystyle\Pr\left[E\right]$	$\displaystyle=\Pr\left[E~{}\middle\|~{}\left\|X-m\right\|>b\right]\Pr\left[\left\|% X-m\right\|>b\right]$
		$\displaystyle+\Pr\left[E~{}\middle\|~{}\left\|X-m\right\|\leq b\right]\Pr\left[% \left\|X-m\right\|\leq b\right].$

Lemma 1.5.24.

$\Pr\left[\left|X-m\right|>b\right]=o(1)$ .

Proof.

We can use the Chernoff bound such that $\Pr\left[\left|X-m\right|>b\right]<2\exp\left(-2\ln m/3\right)=2m^{-2/3}=o(1)$ . ∎

Lemma 1.5.25.

$\left|\Pr\left[E~{}\middle|~{}\left|X-m\right|\leq b\right]-\Pr\left[E~{}% \middle|~{}X=m\right]\right|=o(1)$ .

Proof.

Since $\Pr\left[E\mid X=k\right]$ is monotonically increasing in $k$ , by conditional probability

	$\displaystyle\Pr\left[E~{}\middle\|~{}\left\|X-m\right\|\leq b\right]$	$\displaystyle=\sum_{k\in[-b,b]}\Pr\left[E\mid X=m+k\right]\cdot\Pr\left[X=m+k% \mid\left\|X-m\right\|\leq b\right]$
		$\displaystyle\leq\sum_{k\in[-b,b]}\Pr\left[E\mid X=m+b\right]\cdot\Pr\left[X=m% +k\mid\left\|X-m\right\|\leq b\right]$
		$\displaystyle=\Pr\left[E\mid X=m+b\right].$

Therefore, we relax the term by

\left|\Pr\left[E~{}\middle|~{}\left|X-m\right|\leq b\right]-\Pr\left[E~{}% \middle|~{}X=m\right]\right|\leq\Pr\left[E\mid X=m+b\right]-\Pr\left[E\mid X=m% -b\right],

which is interpreted as: when $m-b$ balls are thrown, there exists empty bins; after $m+b$ balls, all bins are filled.

Let $A$ be the event that $m-b$ balls thrown with empty bins, $S$ be the set for all possible empty bins $B\subseteq[1,n]$ after $m-b$ initial throws, and $F_{B}$ be the event that $B$ empty bins are filled after another $2b$ balls. The exact term follows

	$\displaystyle\Pr\left[E\mid X=m+b\right]-\Pr\left[E\mid X=m-b\right]$	$\displaystyle=\Pr\left[A\right]\cdot\sum_{B\in S}\left(\Pr\left[\text{empty % bins }B\subseteq[1,n]\mid A\right]\cdot\Pr\left[F_{B}\right]\right)$
		$\displaystyle\leq\sum_{B\in S}\left(\Pr\left[\text{empty bins }B\subseteq[1,n]% \mid A\right]\cdot\Pr\left[F_{B}\right]\right)$
		$\displaystyle\leq\max_{B\in S}\Pr\left[F_{B}\right].$

Since $\Pr\left[F_{B}\right]\leq\Pr\left[F_{r}\right]$ for some $r\in B$ by $F_{B}\subseteq F_{r}$ , the probability for all empty bins being filled is upper bounded by the probability of one of the empty bins in $B$ being filled, we upper bound $\Pr\left[F_{r}\right]\leq 2b/n=o(1)$ by union bound.

Therefore, we conclude the resulting difference by $o(1)$ . ∎

By lemma 1.5.24 and lemma 1.5.25, we conclude that

	$\displaystyle\lim_{n\to\infty}\Pr\left[E\right]$	$\displaystyle=\lim_{n\to\infty}o(1)+\left(\Pr\left[E\mid X=m\right]+o(1)\right% )\cdot(1-o(1))$
		$\displaystyle=\lim_{n\to\infty}\Pr\left[E\mid X=m\right],$

indicating as $n\to\infty$ , for $m$ balls $n$ bins exact case, all $n$ bins are filled with probability $e^{-e^{-c}}$ . ∎

1.5.6 Hashing and Random Graphs

Exercise 1.5.26 (Exercise 5.16 [MU17]).

We consider another way to obtain Chernoff-like bounds in the settings of balls and bins without using theorem 1.5.15. Consider $n$ balls and $n$ bins model. Let $X_{i}=1$ iff the $i^{\mathrm{th}}$ bin is empty, and $X=\sum_{i}X_{i}$ . Let $\{Y_{i}\}_{i\in[1,n]}$ be independent Bernoulli random variables with probability $(1-1/n)^{n}$ , and $Y=\sum_{i}Y_{i}$ .

•

Show that $\operatorname*{\mathbb{E}}\left[\prod_{i\in[1,k]}X_{i}\right]\leq\operatorname% *{\mathbb{E}}\left[\prod_{i\in[1,k]}Y_{i}\right]$ for any $k\geq 1$ .
•

Show that $\operatorname*{\mathbb{E}}\left[\exp\left(tX\right)\right]\leq\operatorname*{% \mathbb{E}}\left[\exp\left(tY\right)\right]$ for any $t\geq 0$ .
•

Derive a Chernoff bound for $\Pr\left[X\geq(1+\delta)\operatorname*{\mathbb{E}}\left[X\right]\right]$ .

Proof.

Considering the event that first $k$ bins are empty in $n$ balls and $n$ bins model, the probability is $\left(n-k\right)^{n}/n^{n}$ . On the other hand, since each $Y_{i}$ are independent, then $\prod_{i\in[1,k]}Y_{i}=1$ has probability $\left(1-1/n\right)^{nk}$ .

Since $\left(1-1/n\right)^{k}\geq 1-k/n$ , then $\operatorname*{\mathbb{E}}\left[\prod_{i\in[1,k]}X_{i}\right]\leq\operatorname% *{\mathbb{E}}\left[\prod_{i\in[1,k]}Y_{i}\right]$ for any $k\geq 1$ .

Expanding the prior claim, for any subsets of indices $S\subseteq[1,n]$ , $\Pr\left[\prod_{i\in S}X_{i}=1\right]\leq\Pr\left[\prod_{i\in S}Y_{i}=1\right]$ . We expand MGF function in its Taylor expansion, then we derive the following

	$\displaystyle\operatorname*{\mathbb{E}}\left[\exp\left(tX\right)\right]$	$\displaystyle=\operatorname{\mathbb{E}}\left[\sum_{k\geq 0}\frac{\left(tX% \right)^{k}}{k!}\right]=\sum_{k\geq 0}\frac{t^{k}}{k!}\cdot\operatorname{% \mathbb{E}}\left[X^{k}\right]=\sum_{k\geq 0}\frac{t^{k}}{k!}\cdot\operatorname% *{\mathbb{E}}\left[\left(\sum_{i\in[1,n]}X_{i}\right)^{k}\right]$
		$\displaystyle=\sum_{k\geq 0}\frac{t^{k}}{k!}\cdot\sum_{S\subseteq[1,n],\|S\|\leq k% }\Pr\left[\prod_{i\in S}X_{i}=1\right]$
		$\displaystyle\leq\sum_{k\geq 0}\frac{t^{k}}{k!}\cdot\sum_{S\subseteq[1,n],\|S\|% \leq k}\Pr\left[\prod_{i\in S}Y_{i}=1\right]=\operatorname*{\mathbb{E}}\left[% \exp\left(tY\right)\right].$

Since each $Y_{i}$ are independent, let $p=\left(1-1/n\right)^{n}$ , and therefore

\operatorname*{\mathbb{E}}\left[\exp\left(tY\right)\right]=\prod_{i\in[1,n]}% \operatorname*{\mathbb{E}}\left[\exp\left(tY_{i}\right)\right]=\left(p\cdot% \left(e^{t}-1\right)+1\right)^{n}.

By linearity of expectation, we have $\operatorname*{\mathbb{E}}\left[X\right]=\sum_{i\in[1,n]}\operatorname*{% \mathbb{E}}\left[X_{i}\right]=np$ . Therefore, the Chernoff bound is derived as follows

\Pr\left[X\geq\left(1+\delta\right)np\right]\leq\frac{\operatorname*{\mathbb{E% }}\left[\exp\left(tX\right)\right]}{\exp\left(\left(1+\delta\right)npt\right)}% \leq\frac{\operatorname*{\mathbb{E}}\left[\exp\left(tY\right)\right]}{\exp% \left(\left(1+\delta\right)npt\right)}\leq\left(\frac{e^{\delta}}{(1+\delta)^{% 1+\delta}}\right)^{np}.

∎

Remark 1.5.27.

This trick in balls-and-bins model is analogous to the Poisson approximation. The spirit is the same: both are replacing dependent counts with independent random variables whose marginal behaviors matches that of the exact model. Poisson approximation captures more than just the expected load per bin, it captures the correct distributional shape and small-count probabilities, and approximate the joint distribution via independence, giving a limit theorem for the exact case. The Bernoulli trick preserves the expected emptiness per bin via independent random variables, allowing Chernoff to be applied, but it is more of a bounding device than a limit theorem.

Remark 1.5.28.

This trick can be extended to $m$ balls and $n$ bins, and be used in Bloom Filter analysis on the number of zeroes ( $k$ hash functions, $m$ disallowed passwords, and $n$ bits to store, yielding $k m$ balls and $n$ bins model).

Exercise 1.5.29 (Exercise 5.23 [MU17]).

Bloom filter can be used to estimate set differences. Suppose there are sets $X$ and $Y$ both with $n$ elements. Create Bloom filters for $X$ and $Y$ , using the same number of bits $m$ and the same $k$ hash functions. Determine the expected number of bits where Bloom filters differ as a function of $m, n, k$ , and $\left|X\cap Y\right|$ .

Proof.

Let $A=X\setminus Z$ , $B=Y\setminus Z$ , $Z=X\cap Y$ , and $\left|Z\right|=c$ . We want to know the probability of some bit being set by only one of $A$ or $B$ , and not by $Z$ . Therefore, we define following events

•

$E_{i,0}$ be the event that $i^{\mathrm{th}}$ bit set by $A$ not by $B$ ,
•

$E_{i,1}$ be the event that $i^{\mathrm{th}}$ bit set by $B$ not by $A$ ,
•

$E_{i,2}$ be the event that $i^{\mathrm{th}}$ bit not set by $Z$ ,

and let $\{W_{i}\}_{i\in[1,m]}$ be 0-1 random variables such that $W_{i}=1$ if and only if $(E_{i,0}\cup E_{i,1})\cap E_{i,2}$ , and $W=\sum_{i}W_{i}$ .

Since $E_{i,0}$ and $E_{i,1}$ are symmetric, WLOG we analyze $E_{i,0}$ . Assuming hash function set a random bit to 1, then

\Pr\left[E_{i,0}\right]=\left(1-\frac{1}{m}\right)^{k(n-c)}\cdot\left(1-\left(% 1-\frac{1}{m}\right)^{k(n-c)}\right).

On the other hand, not being set by $Z$ for $i^{\mathrm{th}}$ bit is event $E_{i,2}$ , which follow $\Pr\left[E_{i,2}\right]=(1-1/m)^{kc}$ .

Therefore, $\Pr\left[W_{i}=1\right]=2\Pr\left[E_{i,0}\right]\Pr\left[E_{i,2}\right]$ , and by linearity of expectation,

\operatorname*{\mathbb{E}}\left[W=\sum_{i\in[1,m]}W_{i}\right]=2m\left(1-\frac% {1}{m}\right)^{kn}\cdot\left(1-\left(1-\frac{1}{m}\right)^{k(n-c)}\right).

∎

Definition 1.5.30.

In $G_{n,p}$ model we consider all undirected graphs on $n$ distinct vertices, an edge is connected between 2 distinct vertices with probability $p$ , thus a graph with a given set of $m$ edges has probability $p^{m}(1-p)^{\binom{n}{2}-m}$ . The expected number of edges in the graph is $p\binom{n}{2}$ , and each vertex has expected degree $(n-1)p$ .

In $G_{n,N}$ model we consider all undirected graphs on $n$ distinct vertices with exact $N$ edges. There are $\binom{\binom{n}{2}}{N}$ distinct graphs to select with equal probability.

Remark 1.5.31.

The relation between $G_{n,p}$ and $G_{n,N}$ has following properties: Let $p=N/\binom{n}{2}$ , the number of edges in $G\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}G_{n,p}$ is concentrated around $N$ . Conditioned on $G\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}G_{n,p}$ having $N$ edges, then $G$ is uniform over $G_{n,N}$ .

Such relation is similar to the one between Poisson approximation and the balls-and-bins model.

Lemma 1.5.32.

The distribution of $G_{n,p}$ conditioned on the graph sampled has $N$ edges is the same as $G_{n,N}$ regardless of $N$ .

Lemma 1.5.33.

Let $E$ be an event. If $\Pr\left[E\right]=t$ in the $G_{n,p}$ model, then $\Pr\left[E\right]=O(Nt)$ in the $G_{n,N}$ model where $N=p\binom{n}{2}$ .

Proof.

By the probability lower bounding from conditional probability (trick used in theorem 1.5.15), we have

	$\displaystyle\Pr\left[E\text{ in }G_{n,p}\right]$	$\displaystyle=\sum_{k\geq 0}\Pr\left[E\text{ in }G_{n,p}\mid\text{graph % sampled in }G_{n,p}\text{ has }k\text{ edges}\right]\cdot\Pr\left[\text{graph % sampled in }G_{n,p}\text{ has }k\text{ edges}\right]$
		$\displaystyle\geq\Pr\left[E\text{ in }G_{n,N}\right]\cdot\Pr\left[\text{graph % sampled in }G_{n,p}\text{ has }N\text{ edges}\right].$

Let $M=(1-p)\binom{n}{2}$ . To lower bound the probability of graph sampled in $G_{n,p}$ with $N$ edges, the probability follows

\Pr\left[\text{graph sampled in }G_{n,p}\text{ has }N\text{ edges}\right]=% \binom{\binom{n}{2}}{N}\cdot p^{N}\left(1-p\right)^{M}=(N+M)!\cdot\frac{p^{N}}% {N!}\cdot\frac{\left(1-p\right)^{M}}{M!}.

By result from corollary 1.5.5, we can lower bound components as follows:

$\displaystyle\left(N+M\right)!$	$\displaystyle\geq\left(\frac{N+M}{e}\right)^{N+M}$
$\displaystyle\frac{p^{N}}{N!}$	$\displaystyle\geq\frac{p^{N}}{e\sqrt{N}}\cdot\left(\frac{e}{N}\right)^{N}$	$\displaystyle=\frac{e^{N}}{e\sqrt{N}}\cdot(N+M)^{-N}$
$\displaystyle\frac{\left(1-p\right)^{M}}{M!}$	$\displaystyle\geq\frac{\left(1-p\right)^{M}}{e\sqrt{M}}\cdot\left(\frac{e}{M}% \right)^{M}$	$\displaystyle=\frac{e^{M}}{e\sqrt{M}}\cdot(N+M)^{-M},$

The probability is lower bounded by $O(N^{-1})$ , therefore the probability for the event happening in $G_{n,N}$ is $O(Nt)$ . ∎

Remark 1.5.34.

Using Stirling bound, then the probability for the event to happen in $G_{n,N}$ can be improved to $O(nt)$ .

Definition 1.5.35.

A graph property is a property that holds for a graph, and all the isomorphisms of the graph. We say a graph property is monotone increasing if whenever the property holds for $G=(V,E)$ , it holds for any graph $G^{\prime}=(V^{\prime},E^{\prime})$ with $E\subseteq E^{\prime}$ . Monotone decreasing property is defined similarly, that whenever the property holds for $G=(V,E)$ , it holds for any graph $G^{\prime}=(V^{\prime},E^{\prime})$ with $E^{\prime}\subseteq E$ .

Lemma 1.5.36 (Lemma 5.14 [MU17]).

For a given monotone increasing graph property, let $P_{n,N}$ be the probability that the property holds for a graph in $G_{n,N}$ and $P_{n,p}$ be the probability that the property holds for a graph in $G_{n,p}$ . Let $p^{+}=(1+\varepsilon)N/\binom{n}{2}$ and $p^{-}=(1-\varepsilon)N/\binom{n}{2}$ for a constant $\varepsilon\in(0,1)$ . Then

P_{n,p^{-}}-e^{-O(N)}\leq P_{n,N}\leq P_{n,p^{+}}+e^{-O(N)}.

Proof.

The main theme of the proof is by relaxation from conditional probability, then apply Chernoff bound.

Let $X$ be the random variable for the number of edges of a graph that is sampled from $G_{n,p^{-}}$ . We relax $P_{n,p^{-}}$ by

	$\displaystyle P_{n,p^{-}}$	$\displaystyle=\sum_{k\leq N}P_{n,k}\cdot\Pr\left[X=k\right]+\sum_{k>N}P_{n,k}% \cdot\Pr\left[X=k\right]$
		$\displaystyle\leq P_{n,N}\cdot\Pr\left[X\leq N\right]+\sum_{k>N}P_{n,k}\cdot% \Pr\left[X=k\right]$
		$\displaystyle\leq P_{n,N}+\Pr\left[X>N\right]$

The first equality follow from conditional probability, the second inequality holds from monotone increasing property has $P_{n,N}\geq P_{n,k}$ for all $k\leq N$ , and the last inequality holds from bounding valid probability by 1.

Now we bound $\Pr\left[X>N\right]$ by Chernoff bound, as $X$ is the sum of $\binom{n}{2}$ independent Bernoulli random variables with probability $p^{-}$ , then

\Pr\left[X>N\right]=\Pr\left[X>\frac{1}{1-\varepsilon}p^{-}\binom{n}{2}\right]% <\Pr\left[X>\left(1+\varepsilon\right)p^{-}\binom{n}{2}\right]\leq\exp\left(-% \frac{1}{3}\varepsilon^{2}p^{-}\binom{n}{2}\right)=\exp\left(-\frac{% \varepsilon^{2}(1-\varepsilon)}{3}N\right),

as $1/(1-\varepsilon)>1+\varepsilon$ for $0<\varepsilon<1$ , which proves the $P_{n,N}\geq P_{n,p^{-}}-e^{-O(N)}$ .

Similarly, let $X$ be the random variable for the number of edges of a graph that is sampled from $G_{n,p^{+}}$ . Then

	$\displaystyle P_{n,p^{+}}$	$\displaystyle=\sum_{k<N}P_{n,k}\cdot\Pr\left[X=k\right]+\sum_{k\geq N}P_{n,k}% \cdot\Pr\left[X=k\right]$
		$\displaystyle\geq P_{n,N}\cdot\Pr\left[X\geq N\right]$
		$\displaystyle\geq P_{n,N}-\Pr\left[X<N\right].$

Again by Chernoff bound,

\Pr\left[X<N\right]=\Pr\left[X<\frac{1}{1+\varepsilon}p^{+}\binom{n}{2}\right]% <\Pr\left[X<\left(1-\frac{\varepsilon}{2}\right)p^{+}\binom{n}{2}\right]\leq% \exp\left(-\frac{\varepsilon^{2}}{8}p^{+}\binom{n}{2}\right)=\exp\left(-\frac{% \varepsilon^{2}(1-\varepsilon)}{8}N\right),

as $1/(1+\varepsilon)<1-\varepsilon/2$ for $0<\varepsilon<1$ , which proves the $P_{n,N}\leq P_{n,p^{+}}+e^{-O(N)}$ , and we complete the proof. ∎

Remark 1.5.37.

The spirit is similar to the Poisson approximation theorem 1.5.17. In the $n$ balls $m$ bins model, we replace dependent bins with independent $m$ Poisson random variables of mean $n/m$ . In the random graph case, we replace dependent $N$ edges among all possible $\binom{n}{2}$ edges with each lined up with probability $N/\binom{n}{2}$ independently.

Lemma 1.5.38.

For a given monotone increasing graph property, let $P_{n,N}$ and $P_{n,p}$ be notions follow from lemma 1.5.36. Let $N=p\binom{n}{2}$ , $N^{+}=(1+\varepsilon)N$ , and $N^{-}=(1-\varepsilon)N$ for a constant $\varepsilon\in(0,1)$ . Then

P_{n,N^{-}}-e^{-O(N)}\leq P_{n,p}\leq P_{n,N^{+}}+e^{-O(N)}.

Proof.

We prove with a similar strategy to lemma 1.5.36.

Let $X$ be the random variable for the number of edges of a graph sampled from $G_{n,p}$ . $X$ can be seen as the sum of $\binom{n}{2}$ independent Bernoulli random variables with probability $p$ . By conditional probability,

	$\displaystyle P_{n,p}$	$\displaystyle=\sum_{k\leq N^{+}}P_{n,k}\cdot\Pr\left[X=k\right]+\sum_{k>N^{+}}% P_{n,k}\cdot\Pr\left[X=k\right]$
		$\displaystyle\leq P_{n,N^{+}}\cdot\Pr\left[X\leq N^{+}\right]+\sum_{k>N^{+}}P_% {n,k}\cdot\Pr\left[X=k\right]$
		$\displaystyle\leq P_{n,N^{+}}+\Pr\left[X>N^{+}\right].$

By Chernoff bound, the upper tail of $X$ can be bounded as follows

\Pr\left[X>N^{+}\right]\leq\exp\left(-\frac{1}{3}\varepsilon^{2}N\right)=\exp% \left(-O(N)\right).

Similarly, again by conditional probability,

	$\displaystyle P_{n,p}$	$\displaystyle=\sum_{k<N^{-}}P_{n,k}\cdot\Pr\left[X=k\right]+\sum_{k\geq N^{-}}% P_{n,k}\cdot\Pr\left[X=k\right]$
		$\displaystyle\geq P_{n,N^{-}}\cdot\Pr\left[X\geq N^{-}\right]$
		$\displaystyle\geq P_{n,N^{-}}-\Pr\left[X<N^{-}\right].$

By Chernoff bound, the lower tail bound of $X$ can be bounded as follows

\Pr\left[X<N^{-}\right]\leq\exp\left(-\frac{1}{2}\varepsilon^{2}N\right)=\exp% \left(-O(N)\right).

Therefore, we complete the proof on both sides. ∎

Exercise 1.5.39 (Exercise 5.19 [MU17]).

An undirected graph on $n$ vertices is disconnected if there exists a set of $k<n$ vertices such that there is no edge between this set and the rest of the graph. Otherwise, the graph is connected. Show that there exists a constant $c$ such that if $N\geq cn\log n$ then, with probability $1-o(1)$ , $G\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}G_{n,N}$ is connected.

Proof.

Let $P_{n,N}$ be the probability of $G\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}G_{n,N}$ being connected, $P_{n,p}$ be the probability of $G\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}G_{n,p}$ being connected, where $p=N/\binom{n}{2}$ . The proof strategy follows: Since connectedness is a monotone increasing graph property, we apply lemma 1.5.36 such that we bound $P_{n,N}$ by

P_{n,p^{-}}-\exp\left(-O(N)\right)\leq P_{n,N}\leq P_{n,p^{+}}+\exp\left(-O(N)% \right),

where $p^{+}=(1+\varepsilon)p$ and $p^{-}=(1-\varepsilon)p$ . Suppose $P_{n,p^{+}}$ and $P_{n,p^{-}}$ are both $1-o(1)$ , then we complete the proof.

We continue by analyzing $G_{n,p}$ model. For disconnected subset, the vertex size ranges in $\left[1,\left\lfloor\frac{n}{2}\right\rfloor\right]$ by symmetry. Let $E$ be the event that $G\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}G_{n,p}$ being disconnected. Then $\Pr\left[E\right]$ is union bounded by

\Pr\left[E\right]\leq\sum_{k\in\left[1,\left\lfloor\frac{n}{2}\right\rfloor% \right]}\binom{n}{k}\left(1-p\right)^{k(n-k)}=\sum_{k\in\left[1,\left\lfloor% \frac{n}{2}\right\rfloor\right]}a_{k}.

We want to show that $\Pr\left[E\right]=o(1)$ as $n\to\infty$ . Observing that

\frac{a_{k+1}}{a_{k}}=\frac{n-k}{k+1}\cdot(1-p)^{n-2k-1},

then for a fixed $k$ , as $n\to\infty$ , $a_{k+1}/a_{k}\to 0$ . Suppose for some $K$ , we have $\frac{n}{2}\cdot(1-p)^{n-2K-1}<1$ , then $\{a_{k}\}_{k\in[1,K]}$ are monotone decreasing. We thus separate into 2 cases:

•

$\sum_{k\leq K}a_{k}\leq Ka_{1}=Kn(1-p)^{n-1}$ , and the upper bound approaches $Kn\exp\left(-p(n-1)\right)$ as $n\to\infty$ .
•

$\sum_{k>K}a_{k}<2^{n}(1-p)^{\alpha n^{2}}$ by binomial coefficients for some $\alpha$ , and the upper bound approaches 0 when $n\to\infty$ .

Let $p=O(\log n/n)$ with a sufficiently large constant, then the former bound approaches $0$ when $n\to\infty$ .

The rest follow from both $P_{n,p^{+}}=P_{n,p^{-}}=1-o(1)$ when $\varepsilon$ is sufficiently small. Bounding by lemma 1.5.36, then when $N\geq cn\log n$ we complete the proof. ∎

Theorem 1.5.40 (Theorem 5.15 [MU17]).

Let $N=\frac{1}{2}\left(n\ln n+cn\right)$ . Then the probability that there are no isolated vertices (vertices with degree 0) in $G_{n,N}$ converges to $e^{-e^{-c}}$ as $n\to\infty$ .

Proof.

The main idea is utilizing the balls-and-bins model to model adding edges in the $G_{n,N}$ model.

We introduce edges to the graph $G=(V,E)$ , with $\left|V\right|=n$ and $E=\varnothing$ on initialization.

Repeat $\ell=N+\sqrt{n}$ times, each time toss 2 balls into $n$ bins at random.

•

If they gets into the $i^{\mathrm{th}}$ and $j^{\mathrm{th}}$ bin, with $i\neq j$ , edge $(i,j)\not\in E$ , and $\left|E\right|\leq N$ , introduce the edge.
•

Otherwise, take back the 2 balls from the bins.

Conditioning on having $N$ edges, the distribution of the resulting $G$ is equivalent to sampling from $G_{n,N}$ .

Lemma 1.5.41.

After repeating $\ell$ times, as $n\to\infty$ , $\Pr\left[\left|E\right|=N\right]=1-o(1)$ .

Proof.

There are 2 mutually exclusive cases that an edge introduction trial get rejected: Either the 2 balls are tossed into the same bin, with probability $r_{0}=n/\left(n+\binom{n}{2}\right)$ ; or rejected by prior introduction, upper bounded by $r_{1}=N/\binom{n}{2}$ .

Let $\{X_{i}\}_{i\in[1,\ell]}$ be independent 0-1 random variables of probability $r=r_{0}+r_{1}$ , and $X=\sum_{i}X_{i}$ . Then $X$ is a random variable upwards relaxing the number of rejections in the edge introduction trials.

Since by linearity of expectation $\operatorname*{\mathbb{E}}\left[X\right]=\ell r=O(\log^{2}n)$ , then by Markov/Chernoff concentration inequality, we have $\Pr\left[X>\sqrt{n}\right]=o(1)$ , which completes the proof. ∎

Let $E_{i}$ be the event that $G$ has no isolated vertices after the $i^{\mathrm{th}}$ edge introduction trial. Next corollary is immediate.

Corollary 1.5.42.

As $n\to\infty$ , $\Pr\left[E_{\ell}\right]=\Pr\left[E_{\ell}\mid\left|E\right|=N\right]$ .

Let $M_{n,m}$ be the event that $n$ balls and $m$ bins model having no empty bin.

On one hand, $\Pr\left[E_{\ell}\right]$ is upper bounded by the $2\ell$ balls and $n$ bins model without empty bins, as:

•

Repeated edge introduction does not matter in bin emptiness.
•

2 balls into the same bin means bin filled in the balls-bins model, rather than being rejected in the $G_{n,N}$ model.

A direct application of theorem 1.5.23 implies that as $n\to\infty$ , $\Pr\left[E_{\ell}\right]\leq\Pr\left[M_{2\ell,n}\right]=e^{-e^{-c}}$ .

On the other hand, $\Pr\left[E_{\ell}\mid\left|E\right|=N\right]$ is lower bounded by the $2N$ balls and $n$ bins model with no empty bin, as

•

Repeated edge introduction is allowed in the balls-and-bins model.
•

2 balls tossed into the same bin fills 1 bin rather than 2.

A direct application of corollary 1.5.42 and theorem 1.5.23 implies that as $n\to\infty$ , $\Pr\left[E_{\ell}\right]\geq\Pr\left[M_{2N,n}\right]=e^{-e^{-c}}$ .

Since we have sandwiched $\Pr\left[E_{\ell}\right]=e^{-e^{-c}}$ as $n\to\infty$ , therefore we conclude the proof ¹¹1 The proof is inspired by the math stackexchange link. More specifically, I was thinking of sandwiching by $G_{n,p}$ , but this solution suggested a way of sampling $G_{n,N}$ graph from the balls-and-bins model, and inspired me sandwiching by different number of balls. . ∎

Theorem 1.5.43.

Let $p=(\ln n+c)/n$ . The probability that there is no isolated vertices in $G_{n,p}$ converges to $e^{-e^{-c}}$ as $n\to\infty$ .

Proof.

This is immediate after theorem 1.5.40 and lemma 1.5.38. ∎

1.5.7 Hamiltonian Cycles in Random Graphs

Definition 1.5.44.

Let $G$ be an undirected graph. Suppose that a path $P=v_{1},\ldots,v_{k}$ is a simple path in $G$ , and that $(v_{k},v_{i})$ is an edge in $G$ . Then

P=v_{1},\ldots,v_{i},v_{k},v_{k-1},\ldots,v_{i+1}

is also a simple path, which we refer to as the rotation of $P$ with the rotation edge $(v_{k},v_{i})$ .

On input a graph $G=(V,E)$ with associated “used/unused-edges” lists for each vertex, the modified Hamiltonian cycle finding algorithm follows:

•

Start with a random vertex as the head of the path.
•
Repeat the following until a Hamiltonian cycle is closed, or the “unused-edges” of the head vertex is empty.
- –
  
  Let the current path be $P=v_{1},\ldots,v_{k}$ with $v_{k}$ being the head.
- –
  Execute one of the following 3 cases with probabilities specified as follows.
  - *
    
    With probability $1/n$ , reverse the path and make $v_{1}$ the new head.
  - *
    
    With probability $\left|\text{used-edges}(v_{k})\right|/n$ , sample $(v_{k},v_{i})\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\text{used-edges% }(v_{k})$ , rotate $P$ with edge $(v_{k},v_{i})$ , and let $v_{i+1}$ be new head (if the edge is $(v_{k},v_{k-1})$ , take no action).
  - *
    
    Otherwise, sample $(v_{k},u)\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\text{unused-edges}(% v_{k})$ . If $u$ is not on the path, make $u$ the new head by $v_{k+1}=u$ ; or $u=v_{i}$ , then rotate $P$ by $(v_{k},v_{i})$ and make $v_{i+1}$ the new head (if the edge is $(v_{k},v_{k-1})$ , take no action).
- –
  
  Update “unused-edges” and “used-edges” list accordingly.

We construct a special random graph model similar to $G_{n,p}$ . Assuming each of the $n-1$ possible edges connected to a vertex $v$ is initially on the “unused-edges” list for vertex $v$ independently with probability $q$ . We also assume the order of these edges are in random order.

Remark 1.5.45.

One way of looking at it is, before beginning the Hamiltonian cycle finding algorithm, we create the “unused-edges” list for each vertex $v$ by inserting each possible edge $(u,v)$ with probability $q$ . The corresponding graph $G$ is the graph including all edges that were inserted into some “unused-edges” list. But notice that an edge $(u,v)$ could initially be on the “unused-edges” list for $v$ but not for $u$ . The independence among each “unused-edges” list is helpful for analysis onwards.

The following lemma says, regardless of the viewed vertices, the next vertex to view is still uniformly random, if the “unused-edges” list is not empty in the head vertex.

Lemma 1.5.46.

Suppose the modified Hamiltonian cycle algorithm runs on the random graph model as described. Let $V_{i}$ be the head vertex after the $i^{\mathrm{th}}$ time step. Suppose for any vertex $u$ , as long as the $i^{\mathrm{th}}$ time step the unused edges list is not empty for the head vertex,

\Pr\left[V_{i+1}=u\mid V_{i}=v_{i},V_{i-1}=v_{i-1},\ldots,V_{1}=v_{1}\right]=% \frac{1}{n}.

Proof.

The first 2 cases are both with probability $1/n$ to make $u$ new head of path.

For the last case, there are at most $p=n-\left|\text{used-edges}(v_{i})\right|-1$ options for $v_{i}$ ’s unused edges, at the $i^{\mathrm{th}}$ time step. To make $u$ the new head, $u$ has to be in the previously sampled $\text{unused-edges}(v_{k})$ , and the probability follows

\Pr\left[V_{i+1}=u~{}\middle|~{}\bigcap_{j\in[1,i]}V_{j}=v_{j}\cap\text{third % case}\right]=q\cdot\sum_{k\in[0,p-1]}\left(\binom{p-1}{k}q^{k}(1-q)^{p-1-k}% \cdot\frac{1}{k+1}\right)-(1-q)^{p-1}=\frac{1}{n}.

(or actually we can prove by symmetry, that for any possible option, the probability is the same, and it splits up the whole sample space.) Thus we complete the proof. ∎

Now the problem looks exactly like the coupon collector’s problem, that the probability of finding a new vertex to add to the path, when there are $k$ vertices are left to be added, is $k/n$ .

Theorem 1.5.47.

Suppose the input to the modified Hamiltonian cycle algorithm initially has the probability of adding edges to the unused edges list $q\geq 20\ln n/n$ . Then the algorithm managed to find a Hamiltonian cycle in $O(n\ln n)$ time steps with probability $1-O(n^{-1})$ .

Proof.

We start by upper bounding the event $\mathcal{E}$ that the algorithm failed to find such cycle, splitting by:

•

The algorithm ran for $3n\ln n$ steps with no empty unused edges list, and failed to close a Hamiltonian cycle.
•

The algorithm drained some unused edges list in the first $3n\ln n$ steps, and failed to close a Hamiltonian cycle.

Let the first event be $\mathcal{E}_{1}$ . We relax the second event by lifting the constraint of “failed to close a Hamiltonian cycle”, and we let the relaxed event be $\mathcal{E}_{2}$ . We thus have $\Pr\left[\mathcal{E}\right]\leq\Pr\left[\mathcal{E}_{1}\right]+\Pr\left[% \mathcal{E}_{2}\right]$ .

We start with $\mathcal{E}_{1}$ bounding first. Failing to close a Hamiltonian cycle can be considered as either failing to traverse all vertices, or failing to close by traversing back to starting vertex. We model the vertices traversal conditioned on no unused edges list empty by balls-and-bins model in coupon collector’s problem, and let $\mathcal{E}_{1,a}$ be the event that all coupons are collected before $2n\ln n$ time steps. By conditional probability, we have

	$\displaystyle\Pr\left[\mathcal{E}_{1}\right]$	$\displaystyle=\Pr\left[\mathcal{E}_{1}\mid\mathcal{E}_{1,a}\right]\Pr\left[% \mathcal{E}_{1,a}\right]+\Pr\left[\mathcal{E}_{1}\mid\neg\mathcal{E}_{1,a}% \right]\Pr\left[\neg\mathcal{E}_{1,a}\right]$
		$\displaystyle\leq\Pr\left[\mathcal{E}_{1}\mid\mathcal{E}_{1,a}\right]+\Pr\left% [\neg\mathcal{E}_{1,a}\right],$

where the first term means not closing the Hamiltonian cycle in at least $n\ln n$ steps after traversing all vertices, and the second term means the coupon collector’s problem does not stop before $2n\ln n$ steps.

The first term is upper bounded by

\Pr\left[\mathcal{E}_{1}\mid\mathcal{E}_{1,a}\right]\leq\left(1-\frac{1}{n}% \right)^{n\ln n}\leq\frac{1}{n}.

The second term is upper bounded by union bounding over all $n$ vertices not being picked after $2n\ln n$ trials

\Pr\left[\neg\mathcal{E}_{1,a}\right]\leq n\left(1-\frac{1}{n}\right)^{2n\ln n% }\leq\frac{1}{n}.

Therefore, $\Pr\left[\mathcal{E}_{1}\right]\leq 2/n=O(n^{-1})$ .

Now we bound $\Pr\left[\mathcal{E}_{2}\right]$ . In this case, either all vertices have at least $10\ln n$ unused edges initially, but some gets hit hard; or some vertices have too few unused edges on initialization. Let $\mathcal{E}_{2,a}$ be the event that some vertices have too few unused edges. By conditional probability

	$\displaystyle\Pr\left[\mathcal{E}_{2}\right]$	$\displaystyle=\Pr\left[\mathcal{E}_{2}\mid\mathcal{E}_{2,a}\right]\Pr\left[% \mathcal{E}_{2,a}\right]+\Pr\left[\mathcal{E}_{2}\mid\neg\mathcal{E}_{2,a}% \right]\Pr\left[\neg\mathcal{E}_{2,a}\right]$
		$\displaystyle\leq\Pr\left[\mathcal{E}_{2}\mid\neg\mathcal{E}_{2,a}\right]+\Pr% \left[\mathcal{E}_{2,a}\right].$

The first term can be upper bounded by some vertex being visited too often. An unused edges list can be emptied after at least $10\ln n$ visits. Let $X$ be the number of visits, which is upper bounded by a sum of $3n\ln n$ independent Bernoulli trials of probability $1/n$ . By Chernoff bound,

\Pr\left[X\geq 10\ln n\right]\leq\frac{1}{n^{2}}.

By union bounding over all $n$ vertices, the $\Pr\left[\mathcal{E}_{2}\mid\neg\mathcal{E}_{2,a}\right]\leq 1/n$ .

The second term can be bounded similarly. Let $Y$ be the initial number of unused edges. Then

\operatorname*{\mathbb{E}}\left[Y\right]=(n-1)q\geq 19\ln n

for a sufficiently large $n$ . By Chernoff bound for $\Pr\left[Y\leq 10\ln n\right]$ , then union bounding over $n$ vertices, $\Pr\left[\mathcal{E}_{2,a}\right]\leq 1/n$ .

Therefore, $\Pr\left[\mathcal{E}\right]\leq 4/n=O(n^{-1})$ , and we complete the proof. ∎

Remark 1.5.48.

The operation of rotating in definition 1.5.44 is derived from [Pós76], which is often referred to as the Pósa’s rotation-extension technique.

	$\displaystyle\Pr\left[E~{}\middle\|~{}\left\|X-m\right\|\leq b\right]$	$\displaystyle=\sum_{k\in[-b,b]}\Pr\left[E\mid X=m+k\right]\cdot\Pr\left[X=m+k% \mid\left\|X-m\right\|\leq b\right]$
		$\displaystyle\leq\sum_{k\in[-b,b]}\Pr\left[E\mid X=m+b\right]\cdot\Pr\left[X=m% +k\mid\left\|X-m\right\|\leq b\right]$
		$\displaystyle=\Pr\left[E\mid X=m+b\right].$

	$\displaystyle\operatorname*{\mathbb{E}}\left[\exp\left(tX\right)\right]$	$\displaystyle=\operatorname{\mathbb{E}}\left[\sum_{k\geq 0}\frac{\left(tX% \right)^{k}}{k!}\right]=\sum_{k\geq 0}\frac{t^{k}}{k!}\cdot\operatorname{% \mathbb{E}}\left[X^{k}\right]=\sum_{k\geq 0}\frac{t^{k}}{k!}\cdot\operatorname% *{\mathbb{E}}\left[\left(\sum_{i\in[1,n]}X_{i}\right)^{k}\right]$
		$\displaystyle=\sum_{k\geq 0}\frac{t^{k}}{k!}\cdot\sum_{S\subseteq[1,n],\|S\|\leq k% }\Pr\left[\prod_{i\in S}X_{i}=1\right]$
		$\displaystyle\leq\sum_{k\geq 0}\frac{t^{k}}{k!}\cdot\sum_{S\subseteq[1,n],\|S\|% \leq k}\Pr\left[\prod_{i\in S}Y_{i}=1\right]=\operatorname*{\mathbb{E}}\left[% \exp\left(tY\right)\right].$

1.5 Balls, Bins, and Random Graphs

1.5.1 A few things I should have noted about e

Lemma 1.5.1.

Proof.

Exercise 1.5.2 (Exercise 5.7 [MU17]).

Proof.

Lemma 1.5.3.

Lemma 1.5.4 (Lemma 5.8 [MU17]).

Proof.

Corollary 1.5.5.

1.5.2 Birthday Paradox and Balls-and-Bins model

Remark 1.5.6.

Exercise 1.5.7 (Exercise 5.4 [MU17]).

Proof.

Exercise 1.5.8 (Exercise 5.8 [MU17]).

Proof.

Lemma 1.5.9 (Lemma 5.1 [MU17]).

Proof.

Exercise 1.5.10 (Exercise 5.12 [MU17]).

Proof.

1.5.3 Poisson Distribution

Exercise 1.5.11 (Exercise 5.6 [MU17]).

Proof.

Lemma 1.5.12 (Exercise 5.14 [MU17]).

Proof.

Theorem 1.5.13 (Poisson Median Range Theorem [Cho94]).

1.5.4 Poisson Approximation

Theorem 1.5.14 (Theorem 5.6 [MU17]).

Theorem 1.5.15 (Theorem 5.7 [MU17]).

Proof.

Corollary 1.5.16.

Proof.

Theorem 1.5.17 (Theorem 5.10 [MU17]).

Exercise 1.5.18 (Exercise 5.15 [MU17]).

Proof.

Corollary 1.5.19 (Corollary 5.11 [MU17]).

Proof.

Lemma 1.5.20 (Lemma 5.12 [MU17]).

Proof.

Remark 1.5.21.

Exercise 1.5.22 (Exercise 5.13 [MU17]).

Proof.

1.5.5 Recap on Coupon Collector’s Problem

Theorem 1.5.23 (Theorem 5.13 [MU17]).

Proof.

Lemma 1.5.24.

Proof.

Lemma 1.5.25.

Proof.

1.5.6 Hashing and Random Graphs

Exercise 1.5.26 (Exercise 5.16 [MU17]).

Proof.

Remark 1.5.27.

Remark 1.5.28.

Exercise 1.5.29 (Exercise 5.23 [MU17]).

Proof.

Definition 1.5.30.

Remark 1.5.31.

Lemma 1.5.32.

Lemma 1.5.33.

Proof.

Remark 1.5.34.

Definition 1.5.35.

Lemma 1.5.36 (Lemma 5.14 [MU17]).

Proof.

Remark 1.5.37.

Lemma 1.5.38.

Proof.

Exercise 1.5.39 (Exercise 5.19 [MU17]).

Proof.

Theorem 1.5.40 (Theorem 5.15 [MU17]).

Proof.

Lemma 1.5.41.

Proof.

Corollary 1.5.42.

Theorem 1.5.43.

Proof.

1.5.7 Hamiltonian Cycles in Random Graphs

Definition 1.5.44.

Remark 1.5.45.

1.5.1 A few things I should have noted about $e$