### Basic Probability Tools

This lecture will review everything you learned in 6.042.

- Basic tools in probability
- Expectations
- High probability events
- Deviations from expectation

### Deviations from Expectation

Sometimes expectation isn't enough. Want to study *
deviations*---** probability** and ** magnitude** of deviation
from expectation.

Example: coupon collection/stable marriage.

- Probability didn't get $k^{th}$ coupon after $r$ rounds is $(1-1/n)^r \le e^{-r/n}$
- which is $n^{-\beta}$ for $r=\beta n\ln n$
- so probability didn't get
*some*coupon is at msot $n\cdot n^{-\beta} = n^{1-\beta}$ (using**union bound**) - we say “time is $O(n\ln n)$
**with high probability**” because we can make probability $n^{-\beta}$ for**any**desired $\beta$ by changing constant that doesn't affect assymptotic claim. - sometime say “with high probability” when prove it for
**some**$\beta > 1$ even if didn't prove it for all. - Saying “almost never above $O(n\ln n)$” is a much stronger statement than saying “$O(n\ln n)$ on average.”

Lower bound:

- After $n\lg n$ steps, $1-1/n$ chance of getting given coupon
- So chance of getting all $< (1-1/n)^n \approx 1/e$ (note negative correlation)
- So reasonable chance of
*not*being faster. - Can show bound is very tight.

** Do Exact Balls in Bins here next time**

### Tail Bounds---Markov Inequality

At other times, don't want to get down and dirty with problem. So have developed set of bounding techniques that are basically problem independent.

- few assumptions, so applicable almost anywhere
- but for same reason, don't give as tight bounds
- the more you require of problem, the tighter bounds you can prove.

Markov inequality.

- $\Pr[Y \ge t] \le E[Y]/t$
- $\Pr[Y \ge tE[Y]] \le 1/t$.
- Only requires an expectation! So very widely applicable.

Example: coupong collecting $\Pr[> tn\log n]=O(1/t)$.

Application: $ZPP=RP \cap coRP$.

- If $RP \cap coRP$
- just run both
- if neither affirms, run again
- Each iter has probability $1/2$ to affirm
- So expected iterations 2:
- So $ZPP$.

- If $ZPP$
- suppose expected time $T(n)$
- Run for time $2T(n)$, then stop and give default answer
- Probability of default answer at most $1/2$ (Markov)
- So, $RP$.
- If flip default answer, $coRP$

Does this mean can switch Las Vegas to Monte Carlo? Yes.

Monte Carlo to Las Vegas? No, unless have checker.

### Chebyshev.

Can make Markov much stronger by generalizing: $\Pr[h(Y) > t] \le E[h(Y)]/t$
for ** any positive** $h$.

Better than Markov because uses more info: variance.

- Remind variance, standard deviation. $\sigma_X^2 = E[(X-\mu_X)^2]=E[X^2]-\mu_X^2$
- For many distributions, this amount of variation is “right amount”
- $E[XY] = E[X]E[Y]$ if independent
- variance of independent variables: sum of variances
- $E[(\sum X_i)^2] = E[\sum X_i^2 + 2\sum X_iX_j]$
- second terms expand as $E[X_i]E[X_j]$
- so canceled by $\mu_{X_i}\mu_X{j}$ terms in $(\sum \mu_{X_i})^2$

- $\Pr[|X-\mu| \ge t\sigma] = \Pr [(X-\mu)^2 \ge t^2\sigma^2] \le 1/t^2$
- Or $\Pr[|X-\mu| \ge d] \le \sigma^2/d^2$
- So chebyshev predicts won't stray beyond stdev.
- binomial distribution. variance $np(1-p)$. stdev $\sqrt{n}$.
- requires (only) a mean and variance. less applicable but more powerful than markov
- Real applications later.

Example: coupon collecting.

- Start with geometric random variable with success prob. $p$
- mean $1/p$
- Variance:
- $E[Y^2] = E[Y^2\mid 1 \mbox{ step}]\cdot p + E[Y^2\mid >1 \mbox{ step}]\cdot (1-p)$
- $E[Y^2]=p+E[(Y+1)^2](1-p)=p+(E[Y^2]+2E[Y]+1)(1-p)$
- $Z=(1-p)z+(2-p)/p$
- $Z=(2-p)/p^2$
- variance $(1-p)/p^2< 1/p^2$

- Coupon collection is sum of independent vars: variance upper bound \[ \sum_n \left(\frac{n}{n-i+1}\right)^2=n^2 \sum\frac1{i^2}=O(n^2) \]
- so $\Pr[2nH_n] < O(n^2)/(nH_n)^2=O(1/\ln^2 n)$

### Median Finding

In homework, simple randomized linear-time algorithm

- But, what's the constant?
- Optimum deterministic: $ \ge (2+\epsilon)n$
- Can we do better randomized?

Sampling idea

- List $L$
- median of sample looks like median of whole. neighborhood.
- analysis via Chebyshev bound

Approximation

- choose $s$ samples
*with replacement* - (replacement simplifies analysis)
- what guess for median?
- sort, take $x_{s/2}$
- will it be near median?
- $\Pr[< x_{n/4}]$ is probability choose $s/2$ items less than $x_{n/4}$
- each choice has probability $1/4$
- so expect to choose only $s/4$ in smallest quarter
- variance is $s(1-1/4)/4=3s/16$
- $\sigma = \sqrt{3s}/4$
- $s/2$ such small choices would be deviation by $s/4=\sqrt{s/3}\sigma$
- so probability $3/s$ by Chebychev
- same analysis shows unlikely to exceed $x_{3n/4}$
- combine with union bound
- conclude probably in middle half
- similarly conclude
*any*constant error has probability $O(1/s)$

Exact Algorithm?

- choose $s$ samples
*with replacement* - take fences before and after sample median
- keep items between fences. sort.
- count items on both sides of fences
- find right element in between
- $s=n^{3/4}$ samples $x_1,\ldots, x_s$ in sorted order.
- Sample with replacement to keep analysis clean
- lemma: $x_r$ near $rn/s$ position of original list.
- To find median element, look at two positions in sorted order of sample: $a$ at pos. $s/2-\sqrt{n}$ and $b$ at $s/2+\sqrt{n}$

Analysis

- works so long as median is between fences
- fast so long as
**few items**between fences - Will prove (i) in class, (ii) in homework
- Expected number preceding median is $s/2$.
- What about variance:
- each sample indicator has variance $p(1-p)=1/4$
- so $s$ choices have variance $< s/4$
- so $\sigma = \sqrt{s/4}\le n^{3/8}/2$
- chebyshev: prob. less than $s/2-\sqrt{n}$ involves deviation by $n^{1/8}\sigma$ so probability $O(n^{-1/4}$).

Running time:

- Sorting takes $O(n^{3/4}\log n)=o(n)$ time
- Comparing to fences takes $2n$ time
- Fail probability $O(n^{-1/4})$

Want to improve?

- usually, repetition works
- but here, we're looking at the constant
- even repeating once kills the constant
- but we almost always succeed first time
- (later we'll see failure probability much smaller than shown here)

Randomized is strictly better:

- Gives important constant factor improvement
- Optimum deterministic: $ \ge (2+\epsilon)n$
- We claimed $2n$ above
- But actually $\le (3/2) n+o(n)$ w.h.p. since half of items will fail first comparison

### Pairwise Independence

pseudorandom generators.

- Motivation.
- Idea of randomness as (complexity theoretic) resource like space or time.
- pseudorandom generators turn a little “real” randomness into lots of “fake” randomness”
- can be used in many randomized algorithms
*without change to algorithm or analysis*

Pairwise independence

- $\Pr[X_i = a \wedge X_j=b] = \Pr[X_i=a]\Pr[X_j=b] \forall i,j,a,b$
- equivalently $\Pr[X_i=a \mid X_j=b] = \Pr[X_i = a]$
- sometime full independence unnecessary
- e.g. pairwise independent vars sufficient for Chebychev bounds

More bits

- Given $t$ independent random vars $\mod n$
- For each subset, define random variable as sum over subset, $\mod n$
- Any two subsets differ on a variable, so pairwise independent
- from $t$ independent random bits, get $2^t-1$ pairwise independent
- So with $2\log p$ random bits get $p^2$ pairwise independent bits

Generating larger numbers over $Z_p$.

- Want random numbers in range $[1,\ldots,p]$
- pick random $a,b$
- $i^{th}$ random number $ai+b$
- Works because invertible over field
- Note that each $ai+b$ is uniform random since $b$ is
- Must stop after $p$ values since arithmetic loops back
- Uses $2\log p$ random bits to generate $p$ random values in $1,\ldots,p$.
- If want over nonprime field, use “slightly larger” $p$

Application: median

- median only depended on chebyshev
- which only depended on pairwise independence
- so $O(\log n)$ bits suffice for result

Application: conserving Random Bits

- Suppose $RP$ algorithm using $n$ bits.
- Reduce error to $2^{-t}$ using $t$ independent trials with $tn$ bits
- What do with $2n$ bits?
- two direct draws:
- error prob. 1/4.

- pseudorandom generator
- set $p \sim 2^k$ so algorithm takes one integer in $Z_p$
- Note all bits in this one integer are independent.
- random variable for number of correct outcomes
- $\mu = t/2$.
- $\sigma = \sqrt{t}/2$.
- error if no cert,
- i.e. $Y-E[Y] \ge t/2$,
- prob. $1/t$ by Chebyshev
- even though only pairwise independent
- so long as $t \le p$ i.e. $t \le 2^k$

- Trades time for randomness:
- with $tn$ random bits can get error $2^{-t}$ with $t$ trials
- with $2n$ random bits, can get same probability with $2^t$ trials