Re: Statistical Analysis ...

SubGenius (subg@atheist.tamu.edu)
Mon, 16 Jun 1997 13:03:51 +0600


-----BEGIN PGP SIGNED MESSAGE-----

>>BTW - if you chopped the keyspace in thirds, and picked one of them
>>randomly, then monty hall showed you the key is not in one of the other
>>thirds.. should you switch your pick to the remaining third ??

>Of course you should, because in the time it took for Monty to show
>you that one of the other thirds didn't have the key, your massively
>parallel custom-built DES cracker finished searching the third you picked
>and didn't find it either.

+---------------------------------SubG------------------------------------+
How about this:

Alice, Bob and Carol are the only three parties participating in a
brute force search of a large keyspace. The keyspace is randomly
divided into three hunks of equal sizes[1], and the hunks are randomly
distributed to the three parties involved.

There is a Large Reward associated with being the party to supply the
contest arbiter with the correct key. This Large Reward will be
given out to the first party to submit the correct key, regardless
of whether the winning key is part of the party's assigned keyspace.

After the portions of keyspace are assigned but before any work can
be done with them, Bob is run over by a dogsled and killed. Shortly
thereafter, a black helicopter lands and informs the Alice and Carol
that it has been determined that Bob's portion of the keyspace does
not contain the key[2].

Monty Hall twist:

Assuming that Alice and Carol are keeping their efforts private, what
can either of them do to maximise their individual chances of winning?

Game Theoretical twist:

Given the answer to the above, and realising that this is a two person
zero sum game, is the strategy dictated by simple probability
the best strategy in this sort of competition?

Rubber Hose crypto twist:

Carol seduces one of Alice's programmers and learns from her
that Alice has abandoned the keyspace that was originally
assigned to her and has started a random search of the segment of
keyspace originally assigned to Carol[3].

What should Carol do with this knowledge to maximise her chances of
finding the winning key?

Yours etc.,

SubGenius

- -----
1 How we get a keyspace with a number of keys evenly divisible by
three left as an exercise for the Gentle Reader.
2 Stipulated: The information is correct.
3 Stipulated: The information is correct.

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBM6WAA0OoGXQKy1gNAQGa5wQAil4QFafkZKActUYDYjaz4G+OAJNfERu2
SCfYa9TxtZWHizucFJIOtyzDCvBntWZjlNIJDkAZbbz4x2vv4C/ISKuhenEq8O/L
r2jwbYaaWLWN9wrqth8Zg4hMBf1rszDBZLxpsQVO7RT7VrlLgbHuXsk0Q0PlDjSe
6CNECNP+0kM=
=rwMo
-----END PGP SIGNATURE-----