probability question for math-heads

geeman at best.com geeman at best.com
Wed Oct 23 23:27:54 PDT 1996


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!

TIA, etc.  -- and hey: doesn't Nickelodeon have a trademark on GAK?






More information about the cypherpunks-legacy mailing list