Re: Random choice (was Re: exit polls vs. election results)

From: Ron Crane <voting_at_lastland_dot_net>
Date: Mon May 23 2005 - 10:06:30 CDT

On May 23, 2005, at 3:09 AM, Edward Cherlin wrote:

> On Sunday 22 May 2005 11:28, Ron Crane wrote:
>> So let's take another swing at a transparent process that has
>> fewer weaknesses.
>>
>> One of the original procedure's weaknesses is the single
>> tosser. So let's replace her with a empty box into which the
>> participants deposit a single coin, then close the cover. Then
>> each participant shakes the box to her satisfaction. When all
>> are done, they open the box and read the value.
>>
>> Another weakness is that a biased coin biases fixed bits of
>> the output. Thus, officials could, for example, cheat in
>> odd-numbered precincts, then use a coin fixed to come up tails
>> (= 0) more often than heads, and somehow try to ensure that
>> that coin always formed the LSB of the output precinct
>> numbers. This'd be hard to do, but possible. So let's make any
>> one-sided bias counteract itself by repeatedly tossing the
>> coin twice until we get either a TH (=1) or an HT (=0)
>> sequence. Since p(TH) = p(HT) = p(H)p(T) no matter what p(T)
>> and p(H) are, this is guaranteed to be fair as long as the
>> probabilities don't change between the tosses. It'd be
>> possible to concoct a radio-controlled coin that would allow a
>> cheater to change the probabilities between the tosses, but
>> it's pretty darn unlikely.
>
> Vastly improved, but not anywhere near good enough.
>
>> This is transparent and practical. What are its weaknesses?
>>
>> -R
>
> Legion, Ron. I don't have time to list all the ones I know, and
> the pros know many more. Let's see...For ordinary coin tosses:
>
> o Easy: Swap the coins between tosses using sleight of hand. Make
> sure to swap your biased coin in for the LSB (or whatever chosen
> bit).
> o Easy, but also relatively easy to detect: Throw the coin so
> that it spins rather than tumbling.
> o Moderately difficult: Practice until you can toss a coin with
> exactly three and a half turns every time, or even just most of
> the time.

This method does not use open coin tosses, so cheats for open tosses
are interesting, but inapplicable.

> Then for the box. I don't know the methods for coins, but surely
> you have seen magicians put a card into an envelope, and then
> have it turn out to be the same as the card you pick after the
> envelope is sealed? It isn't the same trick, but the principle
> applies.

Actually in the method I've proposed, the coin goes through 2n shaking
cycles, during which it's shaken by all participants, to generate each
bit. The procedure makes an unfair coin fair, so unless the trickster
can swap the coin (or otherwise change its weighting, such as via the
radio-controlled gizmo I described) between a single bit's shaking
cycles, swapping it doesn't matter at all.

But that means we really don't need to use more than one coin. So let's
prevent anyone from swapping the coin until the entire precinct number
is generated. Let's have a box with an lockable cover in which there's
a window covered by a latchable sliding door. At the beginning of the
process the participants deposit a single coin, then lock the cover.
Shaking proceeds by latching the door, holding the box in full view of
all participants, and shaking it. Everyone shakes to her satisfaction.
They put the box on the table, trip the spring-loaded latch, and look
through the window to determine the coin's state. The chance of someone
opening the box and swapping the coin at any time, let alone between
halves of a shaking cycle, is very small.

> People do cheat at coin tossing games and every other form of
> gambling. Any stage magician or casino security expert would
> laugh loud and long at your assertion of transparency and
> practicality. (It might be worthwhile to see if we can recruit
> The Amazing Randi to the cause. He enjoys debunking those
> without professional training who claim that they can prevent
> cheating.) Casinos use physical layouts for dice tables to make
> cheating much harder, requiring throws to go end-to-end, and
> then employ eagle-eyed croupiers who know how to recognize all
> of the known dice cheats. Spinning rather than tumbling the dice
> is one of the easier methods, but is also one of the easier ones
> to detect.

Casinos also are dealing with dice on open tables surrounded by many
people, any of whom might use a moment of inattention to tip (or swap)
a die within her reach. We are discussing a single coin in a locked box
in full view of what should be a reasonably attentive (though, of
course, untrained) group of "croupiers".

> Please read some of "Scarne on Dice" or a book on
> coin tricks before you try to propose a secure randomizer using
> physical objects.

I'll look at one. Meanwhile, let's continue perfecting this process.
How can my new proposal be subverted?

-R

_______________________________________________
OVC discuss mailing lists
Send requests to subscribe or unsubscribe to arthur@openvotingconsortium.org
==================================================================
= The content of this message, with the exception of any external
= quotations under fair use, are released to the Public Domain
==================================================================
Received on Tue May 31 23:17:46 2005

This archive was generated by hypermail 2.1.8 : Tue May 31 2005 - 23:17:52 CDT