Transcript Document
Summary
Introduction
Buffon’s needle
Computing π
Numerical Integration
1
Numerical Probabilistic Algorithms
Numerical probabilistic algorithms are one type
of random algorithm that always yields
approximate answers to numerical problems.
Given an instance, could return different answers
Typically the longer you let the algorithm run,
the better the answer.
Range/Confidence interval.
2
1 Buffon’s needle
18th century, George Louis Leclerc, compte de Buffon.
Probability that a needle will fall across a crack is 1/π
(each drop is independent to the others)
Plank width
=w
Needle length
L = w/2
3
Approximate π :
n/k as an estimator of π
Approximate w :
w ≥ L , w is estimated by
p 2 L / w
p 1/
2 Ln
w
k
4
How fast this ‘algorithm’ converge?
Convergence analysis
Estimate π : Xi each needle Xi =1 if i-th needle
fall across a crack, 0 otherwise.
Pr{ X i 1}
E[ X i ]
1
1
1 1
Var[ X i ] 1
5
X estimate of 1/π after dropping n needles.
n
X Xi / n
i 1
n 1 1
Pr{ X k / n} 1
k
1
E[ X ]
1 1
Var[ X ] 1 / n
k
nk
6
X is normal distributed
Pr{ X E[ X ] 1.645 Var[ X ]} 90%
Pr{ X 1 / } 90%
1 1
1.645 1 / n
n 0.588 / 2
Pr{ X E[ X ] 2.576 Var[ X ]} 99%
n 1.440 / 2
7
X
1
1
2
X
1
9.8
10
1
2
when
0.00415
With n needles, estimate π will have less
precision than estimate 1/π by one digit.
8
Given n , the value of π is between
n
k
and
n
k
with probability at least p
Example : How many n to estimate π within
0.01 of the correct value with the confidence
99% ?
n 1.440 / 2
n >1.44 million
precision 0.001 (one more
digit than estimate 1/π)
9
Computing π
The number of randomly thrown points that fall
in the circle area k divided by the number of total
points in the square area n is approximately
equal to π divided by 4. Namely, k/n=π/4. So
π=4k/n.
10
So, we can compute π by generating two
numbers for x and y component of a simulated
throw. Then we can figure out by using
Pythagorean theorem if this throw is inside or
outside the circle. We count this hits, and after
doing this thousands of times (or more), we can
get an estimate value of π.
Accuracy of the estimate depends on the number
of “throws”
11
An example code would be (assuming we set
the r= 1):
Computingπ(n)
1 k←0
2 for i←1 to n do
2
x ← Randomf(0,1)
3
y ← Randomf(0,1)
4 d ← x*x + y*y
6
7
if d≤1 then
k ← k +1
8 return k/n
12
2 Numerical Integration
How to estimate the value of an integral?
b
f ( x)dx
a
Where f(x) be a bounded function such that 0 f(x) c
and a x b.
13
Random thrown point method
Consider
simple case: a=0,b=c=1
14
Throw point (x,y) into the square with random
uniformly distributed,then the probability that the
random point falls within the area under the curve f(x) ?
1
Pr{ y f ( x)}
f ( x)
0 0
1
dydx f ( x)dx
0
Assume that we throw n points (xi,yi), i=1,…,n. If the
random point (xi,yi) is thrown into , then yi f(xi) . If
there are k points within , then Γ≈ k/n.
15
Integrate(f, n)
1 k←0
2 for i←1 to n do
3 x←Randomf(0,1)
4 y←Randomf(0,1)
5 if y≤f(x) then k←k+1
6 return k/n
16
In general, let M, L denote the maximum and minimum
of f(x) respectively.
Let x=a+(b-a)z, then Γ=cΓ*+d. Where
1
c ( M L)(b a), d L(b a), * f * ( z )dz
0
1
f * ( z)
[ f (a (b a ) z ) L], (0 f * ( z ) 1)
M L
17
Method 2
Let f(x) be a bounded function such that 0
f(x) c and a x b. Let S be the rectangle:
S = {(x,y) | a x b, 0 f(x) c}
f(x)
c
miss
hit
f(x)
a
b
x
18
Let(x, y) be a random vector uniformly
distributed over the rectangle S, with pdf:
if ( x, y ) S
1
,
f xy c(b a)
otherwise
0,
What is the probability that the random vector
(x, y) falls within the area under the curve f(x)
?
19
Denoting Ω = {(x,y) | y f(x)}, we obtain:
b
f ( x)dx
area () a
p
area ( S ) c(b a) c(b a)
If n points are generated randomly, then the parameter
p can be estimated as:
n
p
n
where nΩ is the number of points within Ω.
So Γ≈nΩ/n*(c(b-a)).
20
Homework
Exercises: page 32
2
Experiments:
微信红包设计算法。
21