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!
\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}