# Monte Carlo sampling a binomial expansion

I want to figure out the following question

$$1 = (10 - 9)^{100} = 10^{100}-100 \times 10^{99} \ 9 + \frac{100 \times 99}{2} 10^{98} \ 9^{2} - \frac{100 \times 99 \times 98 }{3}10^{97} 9^{3} \pm...$$

is there any suggestion how to sample this expansion using Monte Carlo.

-
What would it mean to "sample this expansion"? –  joriki Oct 25 '12 at 20:04
In fact, this is the question I want to figure out. The problem stated as above. –  Eric Oct 25 '12 at 20:26

Are you trying to sample the individual terms in the series? In other words, each term in the expansion looks like $(-1)^k\binom{100}{k}(10)^{n-k}(9)^k$ where you can temporarly drop the $(-1)^k$ to see that sampling a binomial distribution with $n=100$ and probability coefficient $p=10/19$ will give you want you want:

$$P(B(n,p)=k)=\binom{100}{k}p^k(1-p)^{n-k}$$

so

$$(-1)^k\binom{100}{k}(10)^{n-k}(9)^k=(-1)^k\cdot 19^n\cdot P(B(n,p)=k)$$

In other words, flip $n=100$ biased coins of probability $p=10/19$ and then count the number of heads that appear. Repeat over and over to get an approximation of the binomial distribution.

-
Thanks for the detailed explanation. I am familiar with the binomial distribution, but I am not still sure I can use it because I have to sample this expansion such a way that I can find the left hand side. By the way, I should note that I have to control the minus sign, otherwise an error will increase. –  Eric Oct 25 '12 at 23:42
@Eric: I'm not sure I understand. By sampling the above distribution a ton of times, you'll get close approximations to the above probabilities. You then need to multiply them by $19^n$ and then by $(-1)^k$ to adjust for the minus sign. –  Alex R. Oct 26 '12 at 3:35