# Another probability question (not homework!) **URL:** \ **Category:** Factual Questions\ **Created:** [February 5, 2017, 5:11am UTC](https://boards.straightdope.com/t/another-probability-question-not-homework/779049 "2017-02-05T05:11:26Z")\ **Posts on this page:** 9\ **Page:** 2
**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\ **Post date:** [February 6, 2017, 5:25am UTC](https://boards.straightdope.com/t/another-probability-question-not-homework/779049/21 "2017-02-06T05:25:52Z")
> [@moes\_lotion](#): > > What delighted me was that I found (and I don’t know if this is already a well known result) a neat identity, > > Sum(k = 0 to n)[nCk]^2 = (2n)! / (n!)^2, that is the sum of the squares of n choose k, for k from 0 to n, is equal to 2n factorial (not 2 times n factorial) divided by n factorial squared. This is a specific case of the more general [Vandermonde’s identity](https://en.wikipedia.org/wiki/Vandermonde%27s_identity). ---
**Author:** ![moes\_lotion](https://avatars.discourse-cdn.com/v4/letter/m/7ba0ec/32.png) [@moes\_lotion](https://boards.straightdope.com/u/moes_lotion)\ **Post date:** [February 6, 2017, 6:34am UTC](https://boards.straightdope.com/t/another-probability-question-not-homework/779049/22 "2017-02-06T06:34:29Z")
> [@Lance\_Turbo](#): > > This is a specific case of the more general [Vandermonde’s identity](https://en.wikipedia.org/wiki/Vandermonde%27s_identity). Beaten to the finish line by a mere 714 years by Zhu Shijie! ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [February 6, 2017, 12:10pm UTC](https://boards.straightdope.com/t/another-probability-question-not-homework/779049/23 "2017-02-06T12:10:40Z")
But random bits aren’t free. Generating even one random bit has a nonnegligible cost to it, certainly greater than the cost of one comparison. And if you’re using true random numbers instead of pseudorandom, then you want to budget out those random bits carefully. Generating a random number from 1 to 32 requires only 5 bits, and if you have a standard package that generates 8 random bits at a time, you’re not going to want to just throw out the extra 3 every time you generate a number in that range. So “generate a random number in a given range” should not be counted as constant cost. ---
**Author:** ![Quercus](https://avatars.discourse-cdn.com/v4/letter/q/7ab992/32.png) [@Quercus](https://boards.straightdope.com/u/Quercus)\ **Post date:** [February 6, 2017, 2:55pm UTC](https://boards.straightdope.com/t/another-probability-question-not-homework/779049/24 "2017-02-06T14:55:42Z")
> [@moes\_lotion](#): > > This is what I truly appreciate about the Straight Dope, thanks everyone for your insights. > > To answer the one question, why the change to the method? I coded the original application almost 12 years ago and it has survived as a desktop application with only minor upgrades all this time. Bowing to the inevitable, it is being updated to be web-based and I am supervising the process, but no longer coding anything. The fill-an-array-and-shuffle method was proposed by the new development team, I get to approve it or insist that they use the original method. I just wanted to make sure that I was on firm ground when I reject their proposal. Just saying, you may want to double check anything else this team does related to statistics or probability… ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [February 6, 2017, 3:02pm UTC](https://boards.straightdope.com/t/another-probability-question-not-homework/779049/25 "2017-02-06T15:02:01Z")
Generating truly random bits with special hardware may indeed be expensive, but in practice, when cost is an issue aren’t M “true” bits used as a PRNG seed to generate N bits where N is much larger than M? How big can M get before this approach becomes cryptologically insecure? > [@Chronos](#): > > … Generating even one random bit has a nonnegligible cost to it, certainly greater than the cost of one comparison. … Generating a random number from 1 to 32 requires only 5 bits … **Chronos** , of course your point has some validity but when does this become of practical relevance? There is a pretty good PRNG which generates 64 pseudo-random bits with 43 Intel[sup]®[/sup] instructions so, with a net cost of\* less than 1 instruction per bit\*, generating a random bit is certainly _ **not** _ greater than the cost of one comparison! High quality PRNG’s like Marsaglia 's KISS or the famous Twister aren’t much slower than the pretty good generator just mentioned. It appears that my cheap laptop generates well over 1 billion pseudo-random bits per second with any of these generators. The overhead of saving unnecessary PRNG bits for subsequent use may become significant, or even be counterproductive. The PRNG’s are _unbranching_ code, which gets much better pipeline performance than branching overheads. And BTW, generating a random number from 1 to 17 is _more difficult_ than generating a random number from 1 to 32, and _will often require more than 5 bits!_ (In fact if you insist that each of the 17 possibilities for x have probability _exactly_ 1/17, there is no finite algorithm guaranteed to find x! I’ll bet many programmers use a simple “good-enough” way to find x in which the wastage of bits from a 32-bit PRNG turns into a feature, not a bug!) ---
**Author:** ![markn\_1](https://avatars.discourse-cdn.com/v4/letter/m/f9ae1b/32.png) [@markn\_1](https://boards.straightdope.com/u/markn_1)\ **Post date:** [February 6, 2017, 3:23pm UTC](https://boards.straightdope.com/t/another-probability-question-not-homework/779049/26 "2017-02-06T15:23:37Z")
The cost of calling a RNG is of course of practical importance when evaluating an algorithm, but it’s irrelevant to the big-O complexity of the algorithm. Big-O doesn’t measure the absolute cost of the algorithm, it merely measures _how the cost changes as the input size changes_. If the input size changes from n to 10n, how much longer does the algorithm run? Is it twice as slow, 10 times slower, 100 times slower, or 10 billion times slower? An O(n[sup]2[/sup]) algorithm can be faster than an O(n) algorithm, for small values of n. And “small” may be even large enough to cover all practical uses, in which case the O(n[sup]2[/sup]) algorithm is preferable. Evaluation of an algorithm must consider the actual runtime for practical values of n, but that doesn’t change the big-O value of the algorithm. ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [February 6, 2017, 6:59pm UTC](https://boards.straightdope.com/t/another-probability-question-not-homework/779049/27 "2017-02-06T18:59:15Z")
> [@markn\_1](#): > > and multiplication is O(n[sup]2[/sup]). Not true–multiplication is only O(n_log(n)) (actually, there might be another factor of log(log(n)) in there; I need to work it out again). Multiplication is just convolution of two vectors, which can be done in n_log(n) time by first taking the Fourier transform of each one, multiplying them term-by-term, doing the inverse transform, and then performing the carry operation. All of these are O(n\*log(n)) or less. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [February 6, 2017, 9:50pm UTC](https://boards.straightdope.com/t/another-probability-question-not-homework/779049/28 "2017-02-06T21:50:20Z")
> [@Dr.Strangelove](#): > > Not true–multiplication is only O(n_log(n)) (actually, there might be another factor of log(log(n)) in there; I need to work it out again). Multiplication is just convolution of two vectors, which can be done in n_log(n) time by first taking the Fourier transform of each one, multiplying them term-by-term, doing the inverse transform, and then performing the carry operation. All of these are O(n\*log(n)) or less. The classic Schönhage–Strassen algorithm is O(n log n log log n). If you really want to tweak things then there’s Martin Fürer’s algorithm with time complexity of O(n log n 2[sup]Θ(log\* n)[/sup]). (It’s barely an improvement but it does show that the bound is more likely to be just Θ(n log n). If you have constant time log n operations from hardware then you can go lower. **markn+**'s comment on it being O(n[sup]2[/sup]) is common. Too often people assume that the method they are taught in school for an operation is the fastest. A simple algorithm reduces the exponent to log[sub]2[/sub] 3 quite easily. Lots of examples of this sort of thing. ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [February 6, 2017, 10:04pm UTC](https://boards.straightdope.com/t/another-probability-question-not-homework/779049/29 "2017-02-06T22:04:07Z")
Yeah, as I recall the limit for the “straightforward” fast algorithm is that the elements of your vector need to be big enough to fit components of size O(n), which means you need O(log(n)) bits of precision, which gives the extra log(log(n)) dependency. Of course, we could make the same argument as above; 64-bit math is enough for billions of digits, and is constant time on modern machines. So we might just say that multiplication is O(n\*log(n)) for n\