On Wed, 23 Oct 1996, geeman@best.com wrote:
I'm too tired &/or busy to work this out, via Knuth --- maybe you can help, with some implications for the DES keysearch strategy.
What is the expected distribution, in a "random" binary sequence -- with all the fuzziness that implies as to what _exactly_ is "random" -- of gaps between runs of same-bits.
i.e. what is the expected distribution of sequence length between occurances of two (and only two) 1-bits in a row? how about sequences of 3 1-bits? ETc.
We know that in a _truly_ random sequence, taken over a long enough period, there should be all possible values of "gaps". But what is reasonable to expect in a "random" sequence as to how those gaps are distributed? Is my question equivalent to Knuth's gap test?
If anyone feels like proffering some education on this, if I find anything useful in my investigations I'll certainly credit the help!
The math heads are busy doing math, so I'll answer instead. The probability goes 1:2^1... 1:2^2... 1:2^3... 1:2^4... Two bits hold 4 possible values, 2 of which are bit-alike. Three bits hold 8 possible values, 2 of which are bit-alike, of course. 1:2^(bits-1) is exactly what you would expect from a RANDOM sequence. This was also implied in the followups to your previous thread re: DES keyspace optimization. Remember the Gambler's Fallacy... Regards, Doug