CSCE 411 Lecture 24

Lecture Slides

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

The Monte Carlo Method: Estimating Pi

How do we calculate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 < \delta < 1} , we have

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V,E)} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} into two disjoint nonempty sets Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V = V_1 \cup V_2} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_1 \cap V_2 = \emptyset} . The size of the cut is given by the number of edges in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} that cross the cut.

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} is an edge of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G/e} is the multigraph obtained from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} by contracting the edge Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e=\{x,y\}} . I.e. we identify Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} , replacing them with a new node containing the union of incident edges of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.