The monte carlo method (1 of 6)

What is MC?

Collection of tools for estimating values through simulation and sampling
The method consists of an approach to obtain an approximation for a value
We require an efficient process that generates a sequence of i.i.d. random samples such that $E[X_{i}]=V$

"i.i.d" means independent and identically distributed

Example: stock prices

Suppose we want to estimate the expected price of a stock sometime in the future
We may develop a model where price $p(Y_{1},...,Y_{k})$ depends on the r.v.'s $Y_{i}$ .
Repeatedly generate independent vectors from the joint distribution of the $Y_{i}$ and generate several
Use the $X_{j}$ to estimate expected future price

Sharp P

We say that a decision problem $\Pi$ is in NP if for any YES instance of $\Pi$ , there exists a proof that is a YES instance that can be verified in polynomial time
The class associated with the problem of counting solutions to problems in NP-decision problems is denoted #P (e.g. counting the number of Hamiltonian cycles is #P-complete)