Is Random.NextBytes biased?

Your analysis is indeed correct. But the defect is one part in two billions i.e. 1 / 2^31 so fairly negligible.

The question that one should ask is, is it even detectable ? For example, how many samples N does one need to establish the bias with say 99% certainty. From what I know, N > s^2 z^2 / epsilon^2, with

• z = 2.58,
• epsilon = 1 / 2^32 and
• s^2 = p - p^2
• p = 1/2^8 - 1/2^31

this would require 4.77x10^17 samples, a number so large it will hardly be the most obvious defect.