Re: Other Efforts

saurvok@exo.com
Wed, 11 Jun 1997 10:22:18 -0700


>> .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.

I dont understand why you are dividing it by 2. The random search must be
from the whole key space.

>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.

I have no idea what you are saying there.

--------------------------
Assume you had 100 keys and the soultions was key 75.
A sequential search from the start would require searching 75% of the
key space.
Randomly searching(no dupes) would statistically require how many keys to
be checked before find the right one? I dunno..Im not a statistician or
anything but I thought it would be 50%. On average..after fifty random
picks...we would hit the right key?

Now if we move the soultion to key 10....the sequential method has to
search only 10% of the space..while the random method stays the same.

Now over many many contest....the sequential method will find it sooner,
later in the middle etc.....but it will 'average' out to be 50%.

We aren't doing lots of contests..we have just this one. We dont know where
the key is. If we use sequential and start at the beginning....and the key
for this 1 contest is at the end....we would have to search alot more.
So we could gamble and hope the this one time the key is closer to the
front than the back and save time, or use the random method at get the 50%.