Re: Other Efforts

Justin Dolske (dolske@cis.ohio-state.edu)
Wed, 11 Jun 1997 14:25:12 -0400 (EDT)


On Wed, 11 Jun 1997 saurvok@exo.com wrote:

> I have no idea what you are saying there.

You're making this much more difficult than it is! Here's something
resembling an inductive proof, maybe this will help.

Situation: 100 keys, key is hidden somewhere, but we don't know where. We
both start searching (me linearly, you randomly), but don't share any
information about what we've already tested.

I pick key #1 to test. You pick key #57. Which of these keys is more
likely to be The Key? Neither. Both keys have a 1 in 100 chance of being
the correct key, because we don't know where The Key is among all the
keys.

I now pick key #2. You pick key #29. Which of these keys is more likely to
be The Key? Neither. Both keys have a 1 in 99 chance of being the correct
key, because we don't know where The Key is, among all the remaining keys.

I now pick key #3. You pick key #72. Which of these keys is more likely to
be The Key? Neither. Both keys have a 1 in 98 chance of being the correct
key, because we don't know where The Key is, among all the remaining keys.

I now pick key #4. You pick key #34. Which of these keys is more likely to
be The Key? Neither. Both keys have a 1 in 97 chance of being the correct
key, because we don't know where The Key is, among all the remaining keys.

Repeat until the key is found.

Can you see that at each step, any key that is choosen has an equal
probability of being the key? If not, you should just sit down and think
about this for a few hours.

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

It completely depends on the particular "random" order you search in. You
might look at key #75 first, and find it immediately. Or, you might look
at 50 keys before looking at key #75. or, you might look at every key
except for #75 first.

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

You're trying to second-guess the contest. Didn't you read what I already
posted about this?

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) -=-=-=-=-=-=-=-=-=-=-=-=-
Did you hear about the new corduroy pillow?
...It's making headlines all over town.