TCS: Probability Theory for Computer Science

Probability Theory for Computer Science

Finishing NL = coNL

The first part continues Lecture 9. Since PATH is NL-complete under log-space reductions, it suffices to give an NL algorithm for its complement, NOPATH

Let $G$ have $n$ vertices, with source $s$, and define

$$R_i=\{v:\text{some path from }s\text{ to }v \text{ has length at most }i\} \qquad r_i=|R_i|$$

We have $r_0=1$, and every reachable vertex belongs to $R_{n-1}$ because a reachable vertex has a simple path from $s$

Certifying a Complete Reachable Set

Suppose the exact count $r_i$ is already known. Enumerate all vertices $u$ in a fixed order. For each one, nondeterministically choose whether to count it

Whenever the machine chooses to count $u$, require a path certificate from $s$ to $u$ of length at most $i$. Verify the path while retaining only its current vertex and a step counter

Finally require that exactly $r_i$ vertices were counted. Every counted vertex is in $R_i$, no vertex is counted twice, and the cardinality is correct. Therefore every surviving branch has enumerated exactly $R_i$

The machine never stores the set itself. The exact count forces the nondeterministic enumeration to be complete

From r_i to r_(i+1)

For a specified vertex $v$, repeat that certified enumeration and record whether some counted $u$ satisfies $u=v$ or $(u,v)\in E$. On any branch that survives the count check, this flag is true exactly when $v\in R_{i+1}$

Perform this procedure for each $v$ and count the true flags. This computes $r_{i+1}$: all surviving branches return the correct number, and at least one sequence of correct guesses survives

Starting from $r_0$, repeat until the count of all reachable vertices is known. A final certified enumeration checks whether $t$ is absent and accepts exactly in that case

Only a constant number of vertex identifiers, path counters, and cardinalities are retained, each using $O(\log n)$ bits. The loops are sequential rather than a recursion stack storing all earlier sets

Finite Probability Spaces

A finite probability space consists of a set $\Omega$ and nonnegative weights $p(\omega)$ summing to one. An event is a subset of $\Omega$, with probability

$$\Pr[A]=\sum_{\omega\in A}p(\omega)$$

For $n$ independent fair coin flips, $\Omega=\{0,1\}^n$ and each outcome has probability $2^{-n}$

Union Bound and Conditioning

For $\Pr[B]>0$, conditional probability is

$$\Pr[A\mid B]=\frac{\Pr[A\cap B]}{\Pr[B]}$$

This gives the product rule and, for a partition $B_1,\ldots,B_k$ with positive probabilities, the law of total probability

$$\Pr[A]=\sum_{j=1}^k\Pr[B_j]\Pr[A\mid B_j]$$

Bayes’ rule reverses the conditioning

$$\Pr[B\mid A]=\frac{\Pr[A\mid B]\Pr[B]}{\Pr[A]} \qquad\Pr[A]>0$$

Independence

Two events are independent when $\Pr[A\cap B]=\Pr[A]\Pr[B]$. For several events, mutual independence requires the corresponding product identity for every subset of the events

Pairwise independence alone is weaker. If $X,Y$ are independent fair bits and $Z=X\oplus Y$, any two of $X,Y,Z$ are independent, but the three satisfy a deterministic parity constraint

Birthday Collisions

Sample $m$ times independently and uniformly from a set of size $N$. For $m\le N$, the exact probability of no repetition is

$$\Pr[\text{no collision}] =\prod_{j=0}^{m-1}\left(1-\frac jN\right)$$

When $m$ is on the order of $\sqrt N$, logarithmic expansion gives

$$\Pr[\text{collision}] \approx1-\exp\left(-\frac{m(m-1)}{2N}\right)$$

There are roughly $m^2/2$ candidate pairs, so a collision becomes likely after about $\sqrt N$ samples. With the usual uniform 365-day birthday model, 23 people already give collision probability slightly above one half

For an ideal hash function with $b$ output bits, this corresponds to a generic collision-search scale of $2^{b/2}$ evaluations. Finding a preimage of one specified digest is a different task, with generic search scale $2^b$

Random Variables and Expectation

A random variable is a function $X:\Omega\to\mathbb R$. Its expectation is

$$\mathbb E[X]=\sum_{\omega\in\Omega}p(\omega)X(\omega)$$

This is useful when a complicated quantity is a count. For example, the number of colliding pairs among $m$ uniform samples has expectation

$$\sum_{i<j}\mathbb E[\mathbf1_{X_i=X_j}] =\binom m2\frac1N$$

For independent random variables with finite expectations of the relevant products, $\mathbb E[\prod_iX_i]=\prod_i\mathbb E[X_i]$

Variance

$$\operatorname{Var}(X) =\mathbb E[(X-\mathbb E[X])^2] =\mathbb E[X^2]-\mathbb E[X]^2$$

Its square root is the standard deviation. The variance of a sum includes covariances; for pairwise independent variables with finite second moments, those covariance terms vanish

$$\operatorname{Var}\left(\sum_iX_i\right) =\sum_i\operatorname{Var}(X_i)$$

Useful Distributions

For the geometric distribution, $\Pr[X=k]=(1-p)^{k-1}p$ for $k\ge1$ and $0<p\le1$. Counting only failures before the first success gives a different convention and mean

The standard Gaussian has density

$$\phi(x)=\frac1{\sqrt{2\pi}}e^{-x^2/2}$$

A vector of independent standard Gaussians has a density depending only on its Euclidean norm, so its distribution is invariant under orthogonal transformations. Sums of independent Gaussian variables are Gaussian, with means and variances adding

Coupon Collector

Suppose each independent draw returns one of $n$ coupon types uniformly. Let $T$ be the number of draws required to see every type

When $i-1$ types have been seen, the probability of obtaining a new type is $(n-i+1)/n$. The waiting time $T_i$ for the next new type is geometric, so

$$\mathbb E[T_i]=\frac n{n-i+1}$$

Linearity of expectation gives

$$\mathbb E[T]=\sum_{i=1}^n\mathbb E[T_i] =n\sum_{j=1}^n\frac1j =nH_n=\Theta(n\log n)$$

For a tail estimate, a fixed type is missing after $m$ draws with probability $(1-1/n)^m\le e^{-m/n}$. Taking a union bound over all types gives

$$\Pr[T>m]\le ne^{-m/n}$$

Thus $m\ge n(\ln n+\ln(1/\delta))$ is sufficient to collect everything with probability at least $1-\delta$

Concentration Inequalities

Markov

The pointwise inequality $X\ge t\mathbf1_{X\ge t}$ proves the result after taking expectations

Chebyshev

Apply Markov to the squared deviation $(X-\mu)^2$, where $\mu=\mathbb E[X]$

$$\Pr[|X-\mu|\ge t] \le\frac{\operatorname{Var}(X)}{t^2}$$

For a sum of pairwise independent fair bits, the variance is $n/4$, so

$$\Pr[|X-n/2|\ge\varepsilon n] \le\frac1{4\varepsilon^2n}$$

This already proves concentration using only pairwise independence. Full independence allows a much stronger exponential tail

Chernoff and Hoeffding

The exponential-moment method applies Markov after exponentiating

$$\Pr[X-\mu\ge t] \le e^{-\lambda t}\mathbb E[e^{\lambda(X-\mu)}] \qquad\lambda>0$$

For a sum of independent variables, the exponential moment factors into a product. Bounding the individual factors and optimizing $\lambda$ gives the tail bound

For independent fair bits $X_i$, put $Y_i=2X_i-1$. Since

$$\mathbb E[e^{\lambda Y_i}] =\frac{e^\lambda+e^{-\lambda}}2 =\cosh\lambda\le e^{\lambda^2/2}$$

the sum $S=\sum_iX_i$ satisfies

$$\Pr[S-n/2\ge t] \le\exp(n\lambda^2/2-2\lambda t)$$

Taking $\lambda=2t/n$ and applying symmetry yields

$$\Pr[|S-n/2|\ge t]\le2e^{-2t^2/n}$$

More generally, Hoeffding’s inequality for independent $X_i\in[a_i,b_i]$ gives

$$\Pr\left[\left|\sum_iX_i-\mathbb E\sum_iX_i\right|\ge t\right] \le2\exp\left(-\frac{2t^2}{\sum_i(b_i-a_i)^2}\right)$$

For independent $X_i\in[0,1]$, with $X=\sum_iX_i$ and $\mu=\mathbb E[X]$, useful multiplicative forms are

$$\begin{aligned} \Pr[X\le(1-\varepsilon)\mu] &\le e^{-\varepsilon^2\mu/2} && (0<\varepsilon<1)\\ \Pr[X\ge(1+\varepsilon)\mu] &\le e^{-\varepsilon^2\mu/(2+\varepsilon)} && (\varepsilon>0) \end{aligned}$$

Each bound has hypotheses: Markov requires nonnegativity, Chebyshev uses a finite variance, and these Chernoff bounds require the stated independence and range restrictions

Sampling and Randomized Computation

For independent Bernoulli samples of mean $p$, estimate $p$ by $\widehat p=\sum_iX_i/n$. Hoeffding gives

$$\Pr[|\widehat p-p|\ge\varepsilon] \le2e^{-2n\varepsilon^2}$$

To obtain error at most $\varepsilon$ with failure probability at most $\delta$, it suffices that

$$n\ge\frac1{2\varepsilon^2}\ln\frac2\delta$$

The dependence is quadratic in inverse accuracy and logarithmic in inverse failure probability. This is the tool behind majority-vote error reduction for randomized algorithms in Lecture B

The Probabilistic Method

To prove that an object with a property exists, sample a random object and show that the property has positive probability

For a Ramsey example, independently color each edge of $K_n$ red or blue with equal probability. A fixed set of $k$ vertices forms a monochromatic clique with probability

$$2\cdot2^{-\binom k2}=2^{1-\binom k2}$$

The union bound over all $k$-vertex subsets gives

$$\Pr[\text{some monochromatic }K_k] \le\binom nk2^{1-\binom k2}$$

If the right-hand side is below one, a coloring without a monochromatic $K_k$ exists. Writing $R(k,k)$ for the least size forcing one in every coloring, we conclude

$$\binom nk2^{1-\binom k2}<1 \quad\Longrightarrow\quad R(k,k)>n$$

Choosing $n$ on the scale of $2^{k/2}$ gives an exponential lower bound. The existence argument does not by itself give an efficient deterministic method for finding the coloring