Formal Methods II

Why simulate?
We're being showed techniques for

The fraction of problems that can be solved exactly with a sane amount of effort is quite small. -N. Gershenfeld.

Answer: Why work hard when a slave (computer simulation) can do it for you?

We've already given up on exactness!

So what can we do?

1. Analytic Integration
2. Numerical Integration.
Computationally intensive in multiple dimensions.
Analog Computation
It's not that bad if you can draw accurately! You can get an approximation of the answer.

Monte Carlo Integration
It's particularly efficient and accurate, especially for high dimensional functions, as long as the function is reasonably well behaved.

Integral can be estimated by randomly selecting n points and taking the average.

So all slide 10 is saying is that you are taking the average of it
.
.
...................................
.
. this area
.
...................................
a b

Monte Carlo Integration directly applies to multidimensional f.

13
Buffon was tossing needles and used this to come up with an estimation of π.

Turns out that they needed only really small sample sizes. But it turned out that they weren't estimating π at all!

So it doesn't really work if you know the answer already. That's what he means by, if you just stare at these numbers, you never really know when you're done.

You should do repeated examples and estimate variance. If it's .0025, you'll have 3 digit accuracy, and you're done.

16
What do you do about controlling your variance?
Increase the sample size! If you do this enough, you'll eventually get convergence. But with complex problems, you could be waiting billions of years for this.

Just showing that variance is controlled by sample size. Variance decreases directly proportional to the sample size.

Pseudo random numbers are simply too random! In 2 dimensional random noise, you still get clumps and stuff which are radiation and gravitation of super galaxies etc on a TV, for example.
In quasi-random, we help them clump together quicker.

We are just being pointed to these techniques.

18
Random walks have been used to model even such things as the stock market.

neo-conservatives

Some other applications of random walks
Behaviour of liquids and gasses in physics.