Can the statistical width of the avalanche effect be calculated?

Question

This question follows on from my answer to calculation-of-the-avalanche-effect-coefficient earlier. I have reproduced the graph for this question.

Consider the red line which represents the number of bits changed for a single flipped input bit to SHA-512. This is for 100,000 random bit flips. The graph is normal, as expected for a full avalanche effect. From preparing this graph, I can say that the mean (of course) is 256 bits, which is 512 /2. As expected. (I actually get 255.5 but that could be my fault).

The standard deviation of this normal curve is approximately 11.3 obtained empirically. That's for a SHA hash with a block size of 512 bits.

Q. Is there a calculable mathematical relationship between the standard deviation and the block size, or must it always be determined empirically?

Answer 1

Q. Is there a calculable mathematical relationship between the standard deviation and the block size, or must it always be determined empirically?

This is a well studied problem in probability.

If we consider each output bit as an independent random variable (and if they're not independent, your hash function is broken), each such random variable has a standard deviation of $0.5$ (if $0$ and $1$ have equal probabilities; again, if this is not true, your hash function is broken). The sum of $N$ such independent samples will have a standard deviation of $0.5 \sqrt{N}$. In your case, $N=512$; this gives us a standard deviation of $11.3137...$, which is just what you see.