At 11:28 PM +0000 10/23/96, 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?

It obviously depends on your definitions of period, gap, clusters, patterns, etc. These would have to be pinned down before a precise answer could be given. For example, if the sequence is 30 digits long, or 5 digits long, etc. But the general _framework_ for looking at this problem would probably be the Poisson distribution. That is, if the _expected_ ("average") number of gaps, runs, whatever, is "m", then the number "s" of actual gaps/runs that is 0, 1, 2, 3, 4, ...., n, is given by the Poisson distribution: P [s; m] = (exp (-m)) (m ^ s) / (s!) (I read this like this: "The Poisson probability of seeing s occurrences given that m are expected is e to the minus m times m to the s divided by s factorial." I literally remember the formula from this verbal pattern, having used it much in my earlier career.) Thus, if one _expected_ to see m = 3 occurrences of some event, then one would likely see 0 occurences (exp (-3)) (3 ^ 0) / (0!) = 0.0497 = 5% of the time, to see 1 occurrence (exp (-3)) (3 ^ 1) / (1!) = 0.149 = 15% of the time, to see 2 occurences (exp (-3)) (3 ^ 2) / (2!) = 0.224 = 22.4% of the time, and so on, even having a chance of seeing s = 10 occurences given by: (exp (-3)) (3 ^ 10) / (10!) = 0.00081 As expected, the cumulative probability of all the occcurrences is 1.00. (In fact, the Poisson distribution can be derived from some very basic considerations, such that the sum of all outcomes must be 1, and that the past history of occurrences does not effect the next outcome.) In this example, I would put the expected value of the "gap" between the same values (e.g., gap between 1s, gap between 0s) at exactly 0.5, for this random sequence. (This is the weakest part of this post, as it's possible I'm falling into a kind of trap by putting the expected value at one half. If anyone thinks differently, e.g. that it should be "1," we can discuss this. But the framework is otherwise unchanged.) Thus, P [0; 0.5] = (exp (-m)) (m ^ s) / (s!) = 0.6065 P [1; 0.5] = (exp (-m)) (m ^ s) / (s!) = 0.3033 P [2; 0.5] = (exp (-m)) (m ^ s) / (s!) = 0.0758 P [3; 0.5] = (exp (-m)) (m ^ s) / (s!) = 0.0126 P [4; 0.5] = (exp (-m)) (m ^ s) / (s!) = 0.0016 etc. There are other ways of looking at this situation, such as the binomial expansion (e.g., Pascal's triangle), but the results should be the same. (Of course, as they all are interrelated.) (In particular, for various "clumps" and "clusters" of bits in a random distribution, e.g., "how often does the pattern "101111011" occur in random sequences of length 30," one could explicitly calculate the permutations and combinations, exactly as one would calculate hands of poker or bridge, a well-known easy problem in statistics and probability.) I like the Poisson approach as a first cut because it works for any form of a random process where some value is "expected" and one wants to know the distribution of "actuals." Clicks on a Geiger counter in some period, number of persons ahead of one in a supermarket checkout line, number of Prussian soldiers kicked to death each year by their horses, etc. The Poisson also works for finite distributions, e.g., a sequence of 10 digits, whereas Gaussian probabilities are best for continuous/unlimited distributions. (In the limit, of course, they are the same.) I hope this helps. (BTW, the Poisson distribution is what I used several months ago to show that the probability of finding a key with a random search (no coordination between various searchers) is sufficiently high. If the _expected_ value of finding the key is say "1" (effort the same as coordinated search), then the probability of _not_ finding the key is given by P [0; 1] = exp (-1) = 36.8%. If twice the effort is put into this, then P [0; 2] = exp (-2) = 13.5%, and so on. So, with several times the effort, the probability the key has not been found is low.) --Tim May "The government announcement is disastrous," said Jim Bidzos,.."We warned IBM that the National Security Agency would try to twist their technology." [NYT, 1996-10-02] We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^1,257,787-1 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."