算法高级教程2.2Numericalprobabilisticalgorithm.pptVIP

* Summary Introduction Buffon’s needle Computing π Numerical Integration * 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. * 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 * Approximate π : n/k as an estimator of π Approximate w : w ≥ L , w is estimated by * How fast this ‘algorithm’ converge? Convergence analysis Estimate π : Xi each needle Xi =1 if i-th needle fall across a crack, 0 otherwise. * X estimate of 1/π after dropping n needles. * X is normal distributed * With n needles, estimate π will have less precision than estimate 1/π by one digit. when * Given n , the value of π is between and Example : How many n to estimate π within 0.01 of the correct value with the confidence 99% ? precision 0.001 (one more digit than estimate 1/π) n 1.44 million with probability at least p * 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. * 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” * 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