This LaTex file is composed using LaTex.It's my probability homework published here only with the purpose of making more people get to know and use LaTex well!
\begin
Discover why over 20 million people worldwide trust Overleaf with their work.
\documentclass[a4paper]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\geometry{left=2.5cm,right=2.5cm,top=2.5cm,bottom=2.5cm}
\title{Probability Homework 8 Solution}
\author{Wang Jindong\\
201418013229092\\
\ttfamily{wangjindong@ict.ac.cn}}
\begin{document}
\maketitle
\section{Problem 1}
First we consider random 4 vertices in n-vertices graph. Once one of edges is colored, then the remain $({}_2^4)-1 = 5$ edges have the probability $Pr(A_i) = 2^{-5}$ to color to the same color. Where $A_i$ denote the event that clique $i$ is monochromatic in $({}_4^n)$ cliques. Also we define that if clique $i$ is monochromatic then random variable $A_i=1$, otherwise $A_i=0$. So $E(A_i) = 2^{-5}$.\\
In order to calculate $E(\sum A_i)$ we yields:
\begin{equation*}
E(\sum A_i) = ({}_4^n)2^{-5}
\end{equation*}
Using the Lemma 6.2 we have $Pr(\sum A_i \le ({}_4^n)2^{-5})>0 $
So there exist one 2-coloring that has at most $({}_4^n)2^{-5}$ $K_4$ are monochromatic.
Color the edge independently and uniformly. Denote $X = \sum A_i$. Let $p = Pr(X \le ({}_4^n)2^{-5}$. Then we have
\begin{equation*}
\begin{split}
({}_4^n)2^{-5} &= E[X] \\
&= \sum_{i \le ({}_4^n)2^{-5}} i Pr(X=i) + \sum_{i \ge ({}_4^n)2^{-5}+1} i Pr(X=i) \\
&\ge p + (1-p) ({}_4^n)2^{-5}+1 \\
\end{split}
\end{equation*}
So we have
\begin{equation*}
\frac{1}{p} \le ({}_4^n)2^{-5}
\end{equation*}
Thus, the expected number of samples is at most $({}_4^n)2^{-5}$. Testing to see if $X \le ({}_4^n)2^{-5}$ can be done in $O(n^4)$ time. So the algorithm can be done in polynomial time.
\section{Problem 2}
Consider a graph in $G_{n,p}$ with $p = c\frac{\ln{n}}{n}$. Use the second moment method to prove that if $c < 1$ then, for any constant $\epsilon > 0$ and for $n$ sufficiently large, the graph has isolated vertices with probability at least $1-\epsilon$.
Solution:\\
We consider the event $X_i$ denotes that the $i^{th}$ vertex is isolated. So
\begin{equation}
X_i = \left \{ \begin{array}{ll}
1 & if\ v_i\ is\ isolated \\
0 & otherwise
\end{array}
\right.
\end{equation}
Let
\begin{equation}
X = \sum_{i=1}^{n} (1-p)^{n-1}.
\end{equation}
so that
\begin{equation}
E[X] = n (1-p)^{n-1}
\end{equation}
In order to prove that if $c < 1$ then, for any constant $\epsilon > 0$ and for $n$ sufficiently large, the graph has no isolated vertex with probability at most $\epsilon$. That means $Pr(X=0)=o(1)$.\\
We wish to compute
\begin{equation}
Var[x] = Var[\sum_{i=1}^{n} X_i].
\end{equation}
Applying Lemma 6.9, we see that we need to consider the covariance of the $X_i$.
\begin{equation}
\begin{split}
Cov[X_iX_j] &= E[X_iX_j]-E[X_i]E[X_j]\\
&= (1-p)^{2n-3} - (1-p)^{n-1}*(1-p)^{n-1}\\
&= p(1-p)^{2n-3}
\end{split}
\end{equation}
So
\begin{equation}
Var[X] \le E[X] + \sum Cov[X_iX_j] = E[X] + o(pn^2(1-p)^{2n-3})
\end{equation}
Then
\begin{equation}
\begin{split}
Pr(X=0) &\le \frac{Var[X]}{E[X]^2}\\
&=\frac{1}{n (1-p)^{n-1}} + \frac{p}{1-p}
\end{split}
\end{equation}
for $p = c\frac{\ln{n}}{n}$ and $c<1$ with $n \to \infty$, $Pr(X=0) \to o(1)$. So the graph has isolated vertices with probability at least $1-\epsilon$.
\section{Problem 3}
Prove the Asymmetric Lovasz Local Lemma: Let $\mathbb{A} = \{A_1, \dots, A_n\}$ be a set of finite events over a probability space, and for each $1 \le i \le n$, $\tau(A_i) \in \mathbb{A}$ is such that $A_i$ is mutually independent of all events not in $\tau(A_i)$. If $\sum_{A_j \in \tau(A_i)} Pr(A_j) \le 1/4 $ for all $i$, then $ Pr(\bigwedge_{i=1}^n \bar{A_i}) \ge \prod_{i=1}^n (1 - 2Pr(A_i))> 0$. [Hint: let $x(A_i) = 2Pr(A_i)$ and use the general Lovasz Local Lemma.]
Solution:\\
First we need to prove a lemma that if $0\le a_i \le 1/2$ for all $i=1,2,\dots,n$, then $\prod_{i=1}^n (1-2a_i) \ge 1-2\sum_{i=1}^n a_i$.\\
Induction for $n$. When $n=1$, the inequality holds obviously. Assume that when $n=k$, the inequality holds. Consider the case when $n=k+1$,
\begin{equation}
\begin{split}
\prod_{i=1}^{k+1}(1-2a_i) &= \prod_{i=1}^k (1-2a_i) (1-2a_{k+1}) \\
&\ge (1-2\sum_{i=1}^k a_i)(1-2a_{k+1})\\
&= 1-2\sum_{i=1}^{k+1} a_i + 4\sum_{i=1}^k a_i a_{k+1}\\
&\ge 1-2\sum_{i=1}^{k+1} a_i
\end{split}
\end{equation}
So the inequality holds.
Using the general Lovasz Local Lemma, we set $x(A_i) = 2Pr(A_i)$. Then
\begin{equation}
\begin{split}
x(A_i)\prod_{A_j\in \Gamma(A_i)}(1-x(A_j)) &= 2Pr(A_i)\prod_{A_j\in \Gamma(A_i)}(1-2Pr(A_j))\\
&\ge 2Pr(A_i) (1-2\sum_{A_j\in \Gamma(A_i)}Pr(A_j)\\
&\ge 2Pr(A_i) (1 - 2 * 1/4)\\
&= Pr(A_i)
\end{split}
\end{equation}
So the general Lovasz Local Lemma condition holds. Then we have the result
\begin{equation}
\begin{split}
Pr(\bigwedge_{i=1}^n \bar{A_i}) &\ge \prod_{i=1}^n (1 - x(A_i))\\
&\ge \prod_{i=1}^n (1 - 2Pr(A_i))\\
&> 0.
\end{split}
\end{equation}
\section{Problem 4}
Given $\beta > 0$, a vertex-coloring of a graph $G$ is said to be $\beta$-frugal if (i) each pair of adjacent vertices has different colors, and (ii) no vertex has $\beta$ neighbors that have the same color.\\
Prove that if $G$ has maximum degree $\Delta \ge \beta^\beta$ with $\beta \ge 2$, then $G$ has a $\beta$-frugal coloring with $16\Delta^{1+1/\beta}$ colors. [Hint: you may want to define two types of events corresponding to the two conditions of being $\beta$-frugal. Then the result in question 1 can be used.]
Solution:\\
By the following equation
\begin{equation}
({}_\beta^{\Delta+1}) = ({}_\beta^\Delta)+({}_{\beta-1}^{\Delta})
\end{equation}
we can prove that $({}_\beta^\Delta)$ is monotonically increasing for $\Delta$ when $\beta$ is given.\\
Let the number of colors used to $\beta$-frugal coloring be $N=16\Delta^{1+1/\beta}$, and the algorithm assigns each vertex a uniformly random color.\\
Now we define two types of events with total number of $m + n$, when n is the number of vertices, and $m$ is the number of edges:
\begin{itemize}
\item The pair vertices of $e_i$ has the same color;
\item The vertex $v_i$ has $\beta$ neighbors that have the same color.
\end{itemize}
Define $d_i$ is the degree of vertex $i$.\\
For each event $A_i$ in type $I$,
\begin{equation}
Pr(A_i)=\frac{1}{N}
\end{equation}
For each event $A_i$ in type $II$,
\begin{equation}
\begin{split}
Pr(A_i) &= ({}^{d_i}_\beta) (\frac{1}{N})^{\beta-1}\\
&\le ({}^\Delta_\beta) (\frac{1}{N})^{\beta-1}
\end{split}
\end{equation}
Consider the number of dependent events of each event in type $I$. First, each edge connected to the two vertices in the given edge has an event in type $I$, whose total number is at most $2(\Delta ? 1)$. Second, each vertex of the edge has an event in type $II$, whose total number is exactly 2. Thus, for each event $A_i$ in type $I$,
\begin{equation}
\begin{split}
\sum_{A_j \in \Gamma(A_i)} Pr(A_j) &\le 2(\Delta-1)\frac{1}{N} + 2({}^\Delta_\beta)(\frac{1}{N})^{\beta-1}\\
&= 2[(\Delta-1)\frac{1}{16\Delta^{1+1/\beta}}] + ({}^\Delta_\beta) (\frac{1}{16\Delta^{1+1/\beta}})^{\beta-1}\\
&\le 2[\frac{1}{16} + \Delta \dot (\Delta-1) \cdots (\Delta-\beta+1)]
\end{split}
\end{equation}
This definition for events is hard to prove. Another proof from Alistair Sinclair is in the last section.
\section{Problem 5}
\end{document}