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)