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:

$\text{in circle}⟺\sqrt{x^2+y^2}\le 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^{\prime }=4W/m$ is an estimator for $\pi$.

The Chernoff bound gives us a good estimate of how close $W^{\prime }$ is to $\pi$.

$\begin{array}{rl}Pr[|W^{\prime }-\pi |\ge ϵ\pi ]& =Pr[|W-\frac{m\pi }{4}|\ge \frac{ϵm\pi }{4}]\\ & \le 2{\mathrm{e}}^{\frac{-m\pi {ϵ}^2}{12}}\end{array}$

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

A Chernoff Bound

Let $X_1,\dots ,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]|\ge \delta E[X]]\le 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=\mathrm{\varnothing }$. 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.