I'm making a computer game and I've reduced the problem into something simple: How can I show the player the number of heads he "tossed" given some number of coins = n? Naive expected value is worthless, since if coins = 3, we would always give 1 heads or 2 heads, depending how you round (Expected value = 3*0.5 = 1.5).
The solution is to instead simply sample the uniform distribution 3 times, then just say what we got. It could return 3 heads, 2, 1, 0. However, instead of doing 3 calculations, we can just do one sample on a normal distribution. Here is the one for 3 coins:
HHH
HHT
HTH
HTT
THH
THT
TTH
TTT
0 heads = 1
1 heads = 3
2 heads = 3
3 heads = 1
Average = 0*1 + 3*1 + 3*2 + 1*3 / 8 = 12/8 = 1.5
Variance = (0-1.5)^2 * 1/8 + (1-1.5)^2 * 3/8 + (2-1.5)^2 * 3/8 + (3-1.5)^2 * 1/8 = 0.75
StdDev = sqrt(0.75) = 0.866666
We have our parameters. Now, just sample a standard normal distribution and return the number of heads as: average + sample*stdDev.
So how do I do this for arbitrary n? Is there a nice way to calculate mean and stdDev on the fly? And can we extend it to not just be coins (50% probability). Ideally, I want to figure out how to do this with arbitrary probability p of heads, (1-p) of tails. In this case, HHH wouldn't be 1/8, it would be p^3, and so on.
So to summarize, we are looking for:
Given n coins with probability of heads = p, tails = 1-p, "flip" the n coins and return the number that are heads. With a normal distribution, flipping just means getting a standard normal value and converting it to our mean and stdDev. Or, it could be any other way to efficiently solve the problem. The whole point is to give a fair, believable number of heads with as little computation as possible. When n gets big, like 100,000, it becomes too expensive to run n individual trials and sum the number of heads.
Best Answer
As commented http://en.wikipedia.org/wiki/Binomial_distribution.
$$\mu=np$$
$$\sigma=\sqrt {np(1-p)}$$
$$B(X\le x)\approx N(X\le x+0.5)$$