# RA.PS3

My Solution for Randomized Algorithms for the Fall 2015 semester, Problem Set 3. Keep your Academic Integrity plz.

# Randomized Algorithms: Problem Set 3

Himemiya

## 1 Problem 1

Suppose there are two parameters $k,l$ to be determined. Our algorithm runs as follows:

Input set $S$ of $n$ elements over totally ordered domain.

1. 1.

Pick a multi-set $R$ of $\lceil n^{k}\rceil$ elements in $S$, chosen independently and uniformly at random with replacement, and sort $R$;

2. 2.

Let $d$ be the $\lfloor\frac{1}{2}n^{k}-n^{l}\rfloor$-th smallest element in $R$, and let $u$ be the $\lfloor\frac{1}{2}n^{k}+n^{l}\rfloor$-th smallest element in $R$;

3. 3.

Construct $C=\{x\in S|d\leq x\leq u\}$ and compute the ranks $r_{d}=|\{x\in S|x\leq d\}|$ and $r_{u}=|\{x\in S|x\leq u\}|$;

4. 4.

If $r_{d}>\frac{n}{2}$ or $r_{u}<\frac{n}{2}$ or $|C|>4n^{1-k+l}$ then return FAIL;

5. 5.

Sort $C$ and return the $(\lfloor\frac{n}{2}\rfloor-r_{d}+1)$-th element in the sorted order of $C$.

We now bound the probability that the algorithm returns a FAIL. Let $m\in S$ be the meadian of $s$. By Line 4, we know that the algorithm returns a FAIL if and only if at least one of the following events occur:

• $\mathcal{E}_{1}$: $Y=|\{x\in R|x\leq m\}|<\frac{1}{2}n^{k}-n^{l}$;(which is equivalent to $r_{d}>\frac{n}{2}$)

• $\mathcal{E}_{2}$: $Z=|\{x\in R|x\geq m\}|<\frac{1}{2}n^{k}-n^{l}$;(which is equivalent to $r_{u}<\frac{n}{2}$)

• $\mathcal{E}_{3}$: $|C|>4n^{1-k+l}$.

### 1.1 Bound $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$

Let $X_{i}$ be the $i$-th sampled element in Line 1 of the algorithm. Let $Y_{i}$ be an indicator random variable such that

 $Y_{i}=\begin{cases}1\text{ if }X_{i}\leq m,\\ 0\text{ otherwise.}\end{cases}$

Clearly $Y=\sum_{i=1}^{k}Y_{i}$. Note that

 $p=\Pr[Y_{i}=1]=\Pr[X_{i}\leq m]=\frac{1}{n}\lceil\frac{n}{2}\rceil\geq\frac{1}% {2}.$

Recall a form of the Chernoff bound: For a sequence of $m$ independent random variables on $\{0,1\}$ such that for all $i$, $\Pr[Y_{i}=1]=p$ for some $p$, $\Pr[\sum Y_{i}\geq(p+\tau)m]\leq\exp(-2m\tau^{2})$ and similarly $\Pr[\sum Y_{i}\leq(p-\tau)m]\leq\exp(-2m\tau^{2})$. Let $m=n^{k}$, $\tau=n^{l-k}$.

 $\displaystyle\Pr[\mathcal{E}_{1}]$ $\displaystyle=\Pr[Y<\frac{1}{2}n^{k}-n^{l}]$ $\displaystyle\leq\Pr[Y\leq(p-\tau)m]$ $\displaystyle\leq\exp(-2m\tau^{2})$ $\displaystyle=\exp(-2n^{2l-k}).$

By similar analysis, we can bound

 $\Pr[\mathcal{E}_{2}]\leq\exp(-2n^{2l-k}).$

### 1.2 Bound $\mathcal{E}_{3}$

By the Pigeonhole Principle, $\mathcal{E}_{3}$ happens only when at least one of these two events happen:

• $\mathcal{E}^{\prime}_{3}$: at least $2n^{1-k+l}$ elements of $C$ is smaller than $m$;

• $\mathcal{E}^{\prime\prime}_{3}$: at least $2n^{1-k+l}$ elemetns of $C$ is greater than $m$.

Note that $\mathcal{E}^{\prime}_{3}$ implies that the rank of $d$ is at most $\frac{1}{2}n-2n^{1-k+l}$, and thus there are at least $\frac{1}{2}n^{k}-n^{l}$ elements in $R$ whose rank are at most $\frac{1}{2}n-2n^{1-k+l}$. Let $X_{i}$ be an indicator random variables to indicate whether the $i$-th sample’s rank is at most $\frac{1}{2}n-2n^{1-k+l}$. Let $X=\sum_{i=1}^{n^{k}}X_{i}$. Hence

 $p=\Pr[X_{i}=1]={\frac{1}{2}n-2n^{1-k+l}\over n}=\frac{1}{2}-2n^{-k+l}.$

Recall a form of the Chernoff bound: For a sequence of $m$ independent random variables on $\{0,1\}$ such that for all $i$, $\Pr[X_{i}=1]=p$ for some $p$, $\Pr[\sum X_{i}\geq(p+\tau)m]\leq\exp(-2m\tau^{2})$ and similarly $\Pr[\sum X_{i}\leq(p-\tau)m]\leq\exp(-2m\tau^{2})$. Let $m=n^{k}$, $\tau=n^{l-k}$.

 $\displaystyle\Pr[\mathcal{E}_{3}^{\prime}]$ $\displaystyle=\Pr[X\geq\frac{1}{2}n^{k}-n^{l}]$ $\displaystyle=\Pr[X\geq(p+\tau)m]$ $\displaystyle\leq\exp(-2m\tau^{2})$ $\displaystyle=\exp(-2n^{2l-k}).$

The probability that $\mathcal{E}_{3}^{\prime\prime}$ occurs will have the same bound by symmetry. By the union bound,

 $\Pr[\mathcal{E}_{3}]\leq\Pr[\mathcal{E}_{3}^{\prime}]+\Pr[\mathcal{E}_{3}^{% \prime\prime}]=2\exp(-2n^{2l-k}).$

### 1.3 Combine Together

By the union bound, the probability our algorithm fails is at most

 $4\exp(-2n^{2l-k}),$

which will be less than $4/e^{2}$ if $2l\geq k$.

To make our algorithm efficient, we let $|C|\leq n^{k}$. Thus we have $1-k+l\leq k\iff k\geq(1+l)/2$. Recall that $2l\geq k$, it holds that $2l\geq(1+l)/2\iff l\geq 1/3$. Therefore $k\geq(1+l)/2\geq 2/3$, we can sample $n^{2/3}$ elements in $R$.

## 2 Problem 2

### 2.1

#### 2.1.1

 $\displaystyle\Pr[X\geq t]$ $\displaystyle=\Pr[\lambda X\geq\lambda t]$ $\displaystyle(\lambda>0)$ $\displaystyle=\Pr[e^{\lambda X}\geq e^{\lambda t}]$ $\displaystyle\leq\frac{\mathbb{E}[e^{\lambda X}]}{e^{\lambda t}}$ (Markov’s Inequality) $\displaystyle=\exp((\ln\mathbb{E}[e^{\lambda X}])-\lambda t)$ $\displaystyle=\exp(-(\lambda t-\Psi_{X}(\lambda)))$ $\displaystyle\leq\exp(-\Psi_{X}^{*}(t))$

#### 2.1.2

We define $f(\lambda):=\lambda t-\Psi_{X}(\lambda)$. Since $\lambda t$ is a line and $\Psi_{X}(\lambda)$ is strictly convex, $f(\lambda)$ should be a strict concave function over $\lambda\geq 0$, and $\Psi_{X}^{*}(\lambda)$ is achieved at the unique point where $f^{\prime}(\lambda)=0$.

With the assumption that $\Psi_{X}(\lambda)$ is continuously differentiable, we have

 $\displaystyle f^{\prime}(\lambda)=t-\Psi^{\prime}_{X}(\lambda)$

Therefore, $\Psi_{X}^{*}(t)$ is achieved at the unique $\lambda\geq 0$ satisfying $\Psi^{\prime}_{X}(\lambda)=t$.

### 2.2 Normal random variables.

#### 2.2.1

$\Psi_{X}(\lambda)=\ln\mathbb{E}(e^{\lambda X})$
$\mathbb{E}(e^{\lambda X})=\exp(\frac{\lambda^{2}\sigma^{2}}{2}+\lambda\mu)$ (Computed by WolfarmAlpha)
$\Psi_{X}(\lambda)=\frac{\lambda^{2}\sigma^{2}}{2}+\lambda\mu$

$\because\Psi^{\prime}_{X}(\lambda)=\mu+\sigma^{2}\lambda$
$\therefore\Psi_{X}^{*}(t)$ is achieved at $\lambda=\frac{t-\mu}{\sigma^{2}}$

 $\displaystyle\therefore\Psi_{x}^{*}(t)$ $\displaystyle=\frac{t-\mu}{\sigma^{2}}t-(\frac{(\frac{t-\mu}{\sigma^{2}})^{2}% \sigma^{2}}{2}+\frac{t-\mu}{\sigma^{2}}\mu)$ $\displaystyle=\frac{(t-\mu)^{2}}{2\sigma^{2}}$

#### 2.2.2

$\Pr[X\geq t]\leq\exp(-\Psi_{X}^{*}(t))=\exp(-\frac{(t-\mu)^{2}}{2\sigma^{2}})$

### 2.3 Poisson random variables.

#### 2.3.1

$\Psi_{X}(\lambda)=\ln\mathbb{E}(e^{\lambda X})$
$\mathbb{E}(e^{\lambda X})=\exp(\nu(e^{\lambda}-1))$ (Computed by WolfarmAlpha)
$\Psi_{X}(\lambda)=\nu(e^{\lambda}-1)$

$\because\Psi^{\prime}_{X}(\lambda)=\nu e^{\lambda}$
$\therefore\Psi_{X}^{*}(t)$ is achieved at $\lambda=\ln\frac{t}{\nu}$

 $\displaystyle\therefore\Psi_{x}^{*}(t)$ $\displaystyle=t\ln\frac{t}{\nu}-(\frac{t}{\nu}-1)\nu$ $\displaystyle=t\ln\frac{t}{\nu}-t+\nu$

#### 2.3.2

$\Pr[X\geq t]\leq\exp(-\Psi_{X}^{*}(t))=\exp(t-\nu-t\ln\frac{t}{\nu})$

### 2.4 Bernoulli random variables.

$\Psi_{X}(\lambda)=\ln\mathbb{E}(e^{\lambda X})=\ln(pe^{\lambda}+1-p)$
let $\Psi^{\prime}_{X}(\lambda)=\frac{pe^{\lambda}}{pe^{\lambda}+1-p}=t$, we get $\lambda=\ln\frac{(1-p)t}{(1-t)p}$.

 $\displaystyle\therefore\Psi_{X}^{*}(t)$ $\displaystyle=t\ln\frac{(1-p)t}{(1-t)p}-\ln[\frac{(1-p)t}{1-t}+(1-p)]$ $\displaystyle=t\ln\frac{(1-p)t}{(1-t)p}-\ln\frac{1-p}{1-t}$ $\displaystyle=(1-t)\ln\frac{1-t}{1-p}+t\ln\frac{t}{p}=D(Y\|X)$

### 2.5 Sum of independent random variables.

#### 2.5.1

 $\displaystyle\Psi_{X_{i}}(\lambda)$ $\displaystyle=\ln\mathbb{E}(e^{\lambda X_{i}})$ $\displaystyle\Psi_{X}(\lambda)$ $\displaystyle=\ln\mathbb{E}(e^{\lambda\sum_{i=1}^{n}X_{i}})$ $\displaystyle=\ln\mathbb{E}(\prod_{i=1}^{n}e^{\lambda X_{i}})$ $\displaystyle=\ln\prod_{i=1}^{n}\mathbb{E}(e^{\lambda X_{i}})$ (independent!) $\displaystyle=\sum_{i=1}^{n}\ln\mathbb{E}(e^{\lambda X_{i}})=\sum_{i=1}^{n}% \Psi_{X_{i}}(\lambda)$

#### 2.5.2

$\because X_{1},X_{2},...,X_{n}$ are i.i.d. random variables
$\therefore\Psi_{X}(\lambda)=n\Psi_{X_{i}}(\lambda)$, for some i
$\therefore\Psi^{\prime}_{X}(\lambda)=n\Psi^{\prime}_{X_{i}}$
Assuming the unique $\lambda=\lambda_{0}$ makes $\Psi^{\prime}_{X}(\lambda_{0})=n\Psi^{\prime}_{X_{i}}(\lambda_{0})=t$
$\because\Psi^{\prime}_{X_{i}}(\lambda_{0})=\frac{t}{n}$

 $\displaystyle\therefore\Psi_{X_{i}}^{*}(\frac{t}{n})$ $\displaystyle=\frac{t}{n}\lambda_{0}-\Psi_{X_{i}}(\lambda_{0})$ $\displaystyle n\Psi_{X_{i}}^{*}(\frac{t}{n})$ $\displaystyle=t\lambda_{0}-n\Psi_{X_{i}}(\lambda_{0})$ $\displaystyle=t\lambda_{0}-\Psi_{X}(\lambda_{0})=\Psi_{X}^{*}(t)$

$\therefore\Psi_{X}^{*}(t)=n\Psi_{X_{i}}^{*}(\frac{t}{n})$

#### 2.5.3

We consider Binomial random X as sum of $n$ i.i.d. Bernoulli random variables $X_{1},X_{2},...,X_{n}$. Then $\Pr[X\geq t]\leq\exp(-\Psi_{X}^{*}(t))=\exp(-n\Psi_{X_{i}}^{*}(\frac{t}{n}))$. Let $Y\in\{0,1\}$ is a Bernoulli random variable with parameter $\frac{t}{n}$ and $X\in\{0,1\}$ is a Bernoulli random variable with parameter $p$, we can conclude that $\Pr[X\geq t]\leq\exp(-nD(Y\|X))$.

#### 2.5.4

$\Psi_{X_{i}}(\lambda)=\ln\mathbb{E}(e^{\lambda X_{i}})$
$\mathbb{E}(e^{\lambda X_{i}})=\frac{pe^{\lambda}}{e^{\lambda}(p-1)+1}$
$\Psi^{\prime}_{X_{i}}(\lambda)=\frac{1}{e^{\lambda}(p-1)+1}$
Let $\Psi^{\prime}_{X_{i}}(\lambda)=\frac{t}{n}$, then $\lambda=\ln\frac{n-t}{t(p-1)}$.

 $\displaystyle\Psi_{X_{i}}^{*}(\frac{t}{n})$ $\displaystyle=\frac{t}{n}\lambda-\Psi_{X_{i}}(\lambda)$ $\displaystyle=\frac{t}{n}\ln\frac{n-t}{t(p-1)}-\ln\frac{p(n-t)}{(p-1)n}$
 $\displaystyle\Pr[X\geq t]$ $\displaystyle\leq\exp(-\Psi_{X}^{*}(t))$ $\displaystyle=\exp(-n\Psi_{X_{i}}^{*}(\frac{t}{n}))$ $\displaystyle=\exp(n\ln\frac{p(n-t)}{(p-1)n}-t\ln\frac{n-t}{t(p-1)})=\frac{p^{% n}t^{t}}{n^{n}}(\frac{n-t}{p-1})^{n-t}.$

## 3 Problem 3

### 3.1

#### 3.1.1 Union Bound

We constuct a mapping uniformly at random. Let $X_{1},\cdots,X_{n}$ be independent Poisson trials and $X=\sum X_{i}$, $\mathbf{E}[X]=n/2$. Let $\delta=\sqrt{8r\ln 2}$,$d=(n/2)(1-\delta)$. We have

 $\displaystyle\Pr[\text{the distance between any 2 codewords is at most d}]$ $\displaystyle=\Pr[X\leq d]$ $\displaystyle=\Pr[X\leq(1-\delta)\mathbf{E}[X]]$ $\displaystyle<\exp(-\frac{\delta^{2}n/2}{2})$ (Chernoff bound) $\displaystyle=\exp(-2k\ln 2)$ $\displaystyle=2^{-2k}.$

Due to the union bound,

 $\displaystyle\Pr[\exists x,y\in\{0,1\}^{k}\text{ s.t. }d(C(x),C(y))\leq d]$ $\displaystyle\leq{\left({{2^{k}}\atop{2}}\right)}\Pr[X\leq d]$ $\displaystyle<2^{2k-1}\times 2^{-2k}$ $\displaystyle=1/2<1.$

Therefore there exists a boolean code of code rate $r=k/n$ and distance $(\frac{1}{2}-\sqrt{2\ln 2}\sqrt{r})n$.

#### 3.1.2 Lovász Local Lemma

Consider arbitrary a pair of points $a,b\in\{0,1\}^{k}$, $a$’s coordinates are smaller than $b$ in lexicographic order. We define a bad event $\mathcal{E}_{(a,b)}$ as $d(C(a),C(b)). Observe that in the dependency graph of bad events, a bad event is adjacent to at most $2(2^{k}-2)$ other bad events. Thus, due to the Lovász Local Lemma, the probability that all the bad events do not happen will be larger than $0$ if the probability that a single bad event happen is at most $1/(e2(2^{k}-2))>1/(2e2^{k})>\exp(-k-2)$.

Let $\delta=\sqrt{cr}$, $d=(n/2)(1-\delta)$. Due to the Chernoff bound as previous section, a bad event happens with probability at most $\exp(-\frac{\delta^{2}n}{4})$. The target mapping exists if $(\delta^{2}n)/4\geq k+2$. In another word,

 $c\geq 4+{2\over k}.$

Therefore there exists a boolean code of code rate $r=k/n$ and distance $(\frac{1}{2}-\sqrt{1+\frac{1}{2k}}\sqrt{r})n$.

### 3.2

We construct the boolean matrix $A$ uniformly at random. For each entry of $A$, let the entry be $0$ or $1$ with probability of $1/2$ respectively.

Consider arbitrary two different messages $a$ and $b$, and some $1\times k$ vector $v$ in $A$. Let $x_{i}$ denote the $i$-th entry of vector $x$. Let $c=a+_{mod2}b$, i.e. $\forall c_{i},c_{i}=a_{i}+_{mod2}b_{i}$. Observe that

 $\displaystyle va\neq vb$ $\displaystyle\iff$ $\displaystyle va+_{mod2}vb=1$ $\displaystyle\iff$ $\displaystyle v(a+_{mod2}b)=1$ $\displaystyle\iff$ $\displaystyle vc=1.$

Since $a$ and $b$ are different messages, $c\neq 0$. Observe that for all $i\in[1,k]$, only the $i$’s such that $v_{i}=c_{i}=1$ will influence the value of $vc$. Let $S=\{i\in[1,k]|v_{i}=c_{i}=1\}$. Clearly, $vc=1\iff|S|$ is odd, and $\Pr[|S|$ is odd$]=1/2$. Let $A=[v_{1}^{T},v_{2}^{T},\cdots,v_{n}^{T}]^{T}$,

 $\Pr[d(Aa,Ab)\leq d]=\Pr[\sum_{i=1}^{n}v_{i}c\leq d].$

By coupling $v_{i}c$ with $X_{i}$, we have

 $\displaystyle\Pr[d(Aa,Ab)\leq d]$ $\displaystyle=\Pr[X\leq d]$ $\displaystyle=\Pr[X\leq(1-\delta)\mathbf{E}[X]]$ $\displaystyle<\exp(-\frac{\delta^{2}n/2}{2})$ (Chernoff bound) $\displaystyle=\exp(-2k\ln 2)=2^{-2k}.$

Due to the union bound,

 $\displaystyle\Pr[\exists a,b\in\{0,1\}^{k}\text{ s.t. }d(Aa,Ab)\leq d]$ $\displaystyle\leq{\left({{2^{k}}\atop{2}}\right)}\Pr[X\leq d]$ $\displaystyle<2^{2k-1}\times 2^{-2k}$ $\displaystyle=1/2<1.$

Therefore there exists a linear boolean code of code rate $r=k/n$ and distance $(\frac{1}{2}-\sqrt{2\ln 2}\sqrt{r})n$.

## 4 Problem 4

### 4.1

For each position $i\in\{1,2,\cdots,n\}$ of the binary string, we define an indicator random variable $Y_{i}$ to indicator whether there is a run which has length at least $k$ and starts from $i$. Obviously $X_{k}=\sum Y_{i}$. Let $T[i]$ denote $i$-th value of the binary string. Observe that

• $Y_{1}=1\iff\forall i\in[1,k],T[i]=1$,

• $\forall i\in[2,n-k+1],(Y_{i}=1\iff T[i-1]=0\land\forall j\in[i,i+k-1],T[j]=1)$,

• $\forall i\in[n-k+2,n],Y_{i}=0$.

Due to the linearity of expection,

 $\displaystyle\mathbb{E}[X_{k}]$ $\displaystyle=\sum_{i=1}^{n}\mathbb{E}[Y_{i}]$ $\displaystyle=\sum_{i=1}^{n}\Pr[Y_{i}=1]$ $\displaystyle=\Pr[Y_{1}=1]+\sum_{i=2}^{n-k+1}\Pr[Y_{i}=1]+\sum_{i=n-k+2}^{n}% \Pr[Y_{i}=1]$ $\displaystyle=2^{-k}+(n-k+1-2+1)2^{-k-1}+0$ $\displaystyle=(1+\frac{n-k}{2})2^{-k}.$

### 4.2

Let $Z_{i}$ be an indicator random variable to indicate whether the $i$-th element in the string is $1$. Let $\boldsymbol{Z}=(Z_{1},\cdots,Z_{n})$, $X_{k}=f(Z_{1},\cdots,Z_{n})$, where $f$ is a function of random variables and $X_{k}$ denote the number of runs in $S$ of length $k$ or more. Observe that for any $x_{1},\cdots,x_{n}\in\{0,1\}$ and any $w\in\{0,1\}$,

 $\forall i\in[1,n],|f(x_{1},\cdots,x_{i},\cdots,x_{n})-f(x_{1},\cdots,w,\cdots,% x_{n})|\leq 1.$

$f$ satisfying the Lipschitz condition with constant $1$. Then due to the Method of Bounded Differences,

 $\displaystyle\Pr[|X_{k}-\mathbb{E}[X_{k}]|\geq t]$ $\displaystyle=\Pr[|f(\boldsymbol{Z})-\mathbb{E}[f(\boldsymbol{Z})]|\geq t]$ $\displaystyle\leq 2\exp(-\frac{t^{2}}{2\sum_{i=1}^{n}c_{i}^{2}})$ $\displaystyle=2\exp(-\frac{t^{2}}{2n}).$

## 5 Problem 5

### 5.1

Without lost of generality, we assume there exists $c\geq 0$ s.t.

 $\frac{\mathbf{E}[\exp(c|X|)]}{\exp(c\delta)}\leq\min_{t\geq 0}\frac{\mathbf{E}% [\exp(t|X|)]}{\exp(t\delta)}.$

Note that due to the Taylor series of exponential function and the linearity of expectation,

 $\displaystyle\frac{\mathbf{E}[\exp(c|X|)]}{\exp(c\delta)}$ $\displaystyle=\exp(-c\delta)\sum_{i=0}^{\infty}\frac{\mathbf{E}[(c|X|)^{i}]}{i!}$ $\displaystyle=\exp(-c\delta)\sum_{i=0}^{\infty}\frac{\mathbf{E}[|X|^{i}]c^{i}}% {i!}$ $\displaystyle=\sum_{i=0}^{\infty}\exp(-c\delta)\frac{(c\delta)^{i}}{i!}\frac{% \mathbf{E}[|X|^{i}]}{\delta^{i}}.$

Recall that for some $X\sim\operatorname{Pois(\lambda)},\Pr[X=k]=\exp(-\lambda)\lambda^{k}/k!$. This implies if we sample $K$ which follows a Poisson distribution with parameter of $c\delta$ at random, the expected $K$th-moment bound will be as good as the Chernoff bound.

For $k=0$, the moment bound will be $1$. Observe that unless $\forall i(\mathbf{E}[|X|^{i}]=\delta^{i})$, there is another moment bound which is strictly different with $1$. Due to the Pigeonhole Principle, there exists an integer $k$ which is strictly less than the expected value. In another word, there exists a choice of $k$ such that the $k$th-moment bound is strictly stronger than the Chernoff bound.

If $\forall i(\mathbf{E}[|X|^{i}]=\delta^{i})$, then $|X|$ will be a constant $\delta$. The moment bound and Chernoff bound will be trivial $1$.

### 5.2

Because it it difficult to such a $k$ such that $k$th-moment bound is strictly stronger than the Chernoff bound.