Delay Estimation for Truly Random Binary Sequences or How to Measure the Length of Rip van Winkle’s Sleep

Given a sequence generated by a binary symmetric memoryless source and a delayed version of the same sequence, the problem is to determine the delay. As a measure of complexity we use the number of comparisons of two digits in the sequence. A straightforward exhaustive search would compare the sequences after having delayed one of them each of the N possible delay values. On the average, two bits are compared before a mismatch is discovered. Hence the exhaustive method requires on the order of 2N binary comparisons before all but one of the possible delay values are eliminated.