Polling
Outline
- Set has size $u$, contains $s$ “special” elements
- goal: count number of special elements
- sample with probability $p=c(\log n)/\epsilon^2 s$
- with high probability, $(1\pm\epsilon)sp$ special elements
- if observe $k$ elements, deduce $s \in (1\pm\epsilon)k/p$.
- Problem: what is $p$?
Related idea: Monte Carlo simulation
- Probability space, event $A$
- easy to test for $A$
- goal: estimate $p=\Pr[A]$.
- Perform $k$ trials (sampling with replacement).
- expected outcome $pk$.
- estimator $\frac{1}{k}\sum I_i$
- prob outside $\epsilon < \exp(-\epsilon^2 kp/3)$ ($\epsilon < 1$)
- for prob. $\delta$, need \[ k=O\left(\frac{\log 1/\delta}{\epsilon^2 p}\right) \]
- Define $(\epsilon,\delta)$-approximation scheme
- what if $p$ unknown? For now, assume confirming proposed $p$.
- What if $p$ is small?
More general estimation
- Have random variable $X$
- Want to estimate $E[X]$
- turns out can do this with few samples if $\mu < \sigma$.
- Proof in HW.
- What if want to estimate $\sigma$?
- Just need to estimate mean of random variable $X^2$.
- There are schemes that are “competitive” versus unknown $\mu,\sigma$
Another generalization: conditional sampling
- choose from some distribution, conditioned on some event
- if event common, just choose from distribution till event happens
- rare events hard to condition on.
- Choosing a random graph coloring is easy
- Choosing a random legal graph coloring is hard (and useful in physics)
For now we'll study “sampling for (better) algorithms.” Later, “algorithms for (better) sampling”
Handling unknown $p$
- Sample $n$ (unknown) times till get $\mu_{\epsilon,\delta}=O(\log \delta^{-1}/\epsilon^2)$ hits
- w.h.p, $p \in (1\pm\epsilon)\mu_{\epsilon,\delta}/n$
- let $k = \mu_{\epsilon,\delta}/p$
- so when take $k$ samples expect $\mu_{\epsilon,\delta}$ hits
- consider first $k/(1+\epsilon)$ samples
- expect $\mu_{\epsilon,\delta}/(1+\epsilon)$ hits
- Chernoff says w.h.p $< (1+\epsilon)\mu_{\epsilon,\delta}/(1+\epsilon)=\mu_{\epsilon,\delta}$ hits
- so won't have enough hits to stop before this point
- similar argument that won't stop too late
- instead will stop at some point in proper interval
- and this get good estimate
Discussion
- For error probability $\delta$, need $kp=\mu_{\epsilon,\delta}=(4/\epsilon^2)\ln 2/\delta$
- So, can get tiny probability of error cheaply, but sensitive to $\epsilon$.
- Note for many apps, want “with high probability:” $\delta=1/n^2$, so $kp \approx \log n$.
- Note also, to get good sample, need $k >> 1/p$.
- i.e., sample needed is larger as event we want to detect is rarer.
- Sampling without replacement gives lower probability of large deviation
Transitive closure
Problem outline
- databases want size
- matrix multiply time
- compute reachibility set of each vertex, add
Sampling algorithm
- generate vertex samples until $\mu_\epsilon\delta$ reachable from $v$
- deduce size of $v$'s reachability set.
- reachability test: $O(m)$.
- number of sample: $n/$size.
- $O(mn)$ per vertex---ouch!
Can test for all vertices simultaneously
- increase mean to $O(1/\epsilon^2\log (n/\delta))$,
- so $\delta/n$ failure probability per vertex
- so $\delta$ overall (union bound)
- $O(mn)$ for all vertices (still ouch).
Avoid wasting work
- stop propagating to a vertex once it has seen enough
- if a vertex has seen $k$ samples, so have all its predecessors
- so no need to forward observations
- so send at most $\log n/\delta$ samples over an edge
- also, after $O(n\mu_{\epsilon,\delta/n})$ samples, every vertex has $\log n/\delta$ hits. No more needed.