Re: Other Efforts

Justin Dolske (dolske@cis.ohio-state.edu)
Wed, 11 Jun 1997 02:46:33 -0400 (EDT)


On Tue, 10 Jun 1997 saurvok@exo.com wrote:

> > The order the keyspace is searched in doesn't matter.
>
> I disagree.
>
> Its true, over many many contests on average it wouldn't matter.
> But this is 1 contest....and the key could be at the end..or middle..or
> start....

*sigh* I suggest you re-read what I wrote about second-guessing. You're
right, the key could be *anywhere*. But if that's true, IT DOES NOT MATTER
what order you search in.

> .pick the wrong sequential method and you could spend alot more time then
> the average 50% of key space. So, picking a key randomly from the entire
> space each time (assuming no duplicate picks) will give the average 50%
> time..no matter where the key is.

Wrong. If you pick the "wrong" random order, you will not hit the key
at the 50% mark. There's nothing magical about a random search.

If your theory was true, we would only have to test 1 key to win the
contest! Proof:

Using your "assured by 50%" method, let us name the random keys we search
K1, K2, K3, K4, K5 ... K(N/2). N is the total number of keys that exist,
and we need only seach half of them.

We now have N/2 canidate keys, and the "true" key must be one of them, by
your reasoning. So why search them all? Let's use your random search on
these N/2 keys we have selected. Now we're assured of finding the key
after testing only N/2/2 (N/4) keys. Repeat until you're assured of
finding the key after testing only 1 key.

Justin Dolske <URL:http://www.cis.ohio-state.edu/~dolske/>
(dolske@cis.ohio-state.edu)
Graduate Fellow / Research Associate at The Ohio State University, CIS Dept.
-=-=-=-=-=-=-=-=-=-=-=-=-=- Random Sig-o-Matic (tm) -=-=-=-=-=-=-=-=-=-=-=-=-
"The folly of mistaking a paradox for a discovery, a metaphor for a proof,
a torrent of verbiage for a spring of capital truths, and oneself for
an oracle, is inborn in us." -- Paul Vale'ry, 1895