CSCE 411 Lecture 24

Lecture Slides

« previous | Wednesday, October 24, 2012 | next »

The Monte Carlo Method: Estimating Pi

How do we calculate $\pi$

Main idea: Given a 2×2 square centered at (0,0) with a circle of radius 1 inscribed. The area of the circle is $\pi$ and the area of the square is 4.

Imagine a drunk and blindfolded guy throwing darts at this circle. Choose random $(x,y)$ points and determine whether they are in the circle or not:

${\mbox{in circle}}\iff {\sqrt {x^{2}+y^{2}}}\leq 1$

The number of points in the circle ÷ Total number of sample points ≈ $\pi /4$.

Let $Z$ equal 1 if a point is in the circle, and 0 otherwise. Therefore $Pr[Z=1]=\pi /4$.

How many darts does the drunk and blindfolded guy need to throw?

Let $W=\sum _{i=1}^{m}Z_{i}$, where $Z_{i}$ is the value of $Z$ after the $i$^th dart.

Thus $W'=4W/m$ is an estimator for $\pi$.

The Chernoff bound gives us a good estimate of how close $W'$ is to $\pi$.

${\begin{aligned}Pr[|W'-\pi |\geq \epsilon \,\pi ]&=Pr\left[\left|W-{\frac {m\,\pi }{4}}\right|\geq {\frac {\epsilon \,m\,\pi }{4}}\right]\\&\leq 2\mathrm {e} ^{\frac {-m\,\pi \,\epsilon ^{2}}{12}}\end{aligned}}$

Therefore, the probability (that $W'$ deviates significantly from $\pi$) exponentially decreases with $m$ (number of trials).

A Chernoff Bound

Let $X_{1},\ldots ,X_{m}$ be random variables such that $Pr[X_{i}=1]=p_{i}$ and $Pr[X_{i}=0]=1-p_{i}$

Let $X=\sum _{i=1}^{m}X_{i}$.

For $0<\delta <1$, we have

$Pr[|X-E[X]|\geq \delta \,E[X]]\leq 2\mathrm {e} ^{\frac {-E[X]\,\delta ^{2}}{3}}$

Minimum Cut Algorithm

Lecture Handout

An example randomized algorithm

Start out with a connected, undirected, loop-free multi-graph $G=(V,E)$ with $n$ vertices, where there can be multiple edges between each vertex.

G1 = [[a,b], [a,c], [a,d], [b,e], [b,d], [c,d], [c,d], [c,f], [d,e], [d,f], [e,f]]
G2 = [[a,b], [a,c], [a,d], [b,d], [c,d]]

A cut in the multigraph is a partition of the vertex set $V$ into two disjoint nonempty sets $V=V_{1}\cup V_{2}$, where $V_{1}\cap V_{2}=\emptyset$. The size of the cut is given by the number of edges in $E$ that cross the cut.

If $e$ is an edge of $G$, then $G/e$ is the multigraph obtained from $G$ by contracting the edge $e=\{x,y\}$. I.e. we identify $x$ and $y$, replacing them with a new node containing the union of incident edges of $x$ and $y$ and remove any resulting self-loops.

G1/[c,d] = [[a,b], [a,cd], [a,cd], [b,e], [b,cd], [cd,f], [cd,f], [cd,e], [e,f]]
G2/[a,d] = [[ad,b], [ad,b], [ad,c], [ad,c]]
G2/[a,d]/[ad,b] = [[abd,c],[abd,c]]

Contract edges at random to get a final number. This can give a wrong answer, but repeating the algorithm multiple times and returning the minimum result of all runs decreases the probability that it will be wrong.