From: "Douglas B. Renner" <dougr@skypoint-gw.globelle.com>
Date: Thu, 24 Oct 1996 08:38:17 -0700 (PDT)
To: "geeman@best.com>
Subject: Re: probability question for math-heads
In-Reply-To: <326EAA23.2DB1@best.com>
Message-ID: <Pine.3.89.9610241300.A4269-0100000@skypoint-gw.globelle.com>
MIME-Version: 1.0
Content-Type: text/plain



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