[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: probability question for math-heads
On Wed, 23 Oct 1996, [email protected] 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