# Re: Other Efforts

**Aaron Williams** (*aaronw@eng.adaptec.com*)

*Wed, 11 Jun 1997 13:59:14 PST*

** Reply to note from Justin Dolske <dolske@cis.ohio-state.edu> Wed, 11 Jun

1997 14:25:12 -0400 (EDT)

Of course Murphy's law says that if you search all the keys sequentially

between 1 and 100 the solution will be 100 and if you choose randomly it

will be the last random key you choose :)

*> *

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

*> *

*> *

-----------------------------------------------------------------------------

Aaron Williams

Adaptec, Inc.

aaronw@eng.adaptec.com

(408) 945-8600 x3425

Inter-Networking Technology

Check out our web site at HTTP://www.adaptec.com/networking/ATM.html

Personal Java-based home page at HTTP://24.1.65.193 (9am-midnight PST only)