Friday, May 6, 2011

Looking for a random bit

It is natural to look around us and quickly spot number patterns -- numbers or sequences that are surely not there by chance -- even when we are just making up the pattern almost in spite of ourselves. But how do you come up with a random number?

I was wondering about that driving home last night. Imagine you're having a nightmare, being chased down an alley, and you have to make a split decision whether to turn right or left, so that the ennemy chasing you won't be able to guess. Flip a coin - but what if you don't have a coin? How do you quickly make up a random decision?

As I was driving, I looked around me for features that would help me find a random number. I would have been happy with just one small random bit. Street lights, signs, speed limits, curves of the road. Branches of tall, dark trees. Gas stations. Dark sky. My cell phone was dead, and neither my car clock nor my car radio work any more. There was no random bit in sight.

If I had been hiking in a mountain, I could have given myself a goal some distance away, then counted my steps mod 2; however that would not have been really random, because, as I got close to the goal, I could have shortened or lengthened my steps in spite of my efforts for objectivity, and ended up with a number that would have been biased in some way. I am Eve, and the random bit must be protected against my malicious attempts to influence the result!

I could just come up with a number, 0 or 1, but how do I know it's random?

I could take my pulse -- how many heart beats before I get to the light? -- mod 2, except that there is always a slight uncertainty in that counting; plus, I was driving.

Finally I found an approximate solution: count, mod 2, the number of cars coming the other way, from that point on until I got home. That almost worked, except that one car came out of an intersection and turned into my street as I was just driving by, so I (Eve) had to make a subjective choice whether or not to include it; so I could have manipulated the final result in that way; but I decided it should be included and did not change my mind later.

This train of thoughts affected my driving -- it's not unusual. In the present case, when I got to the turn into my street, I sped up to go across the intersection quickly, so that no other car could come by while I was turning and present me with another subjective borderline case. I got lucky, and the intersection stayed empty while I was turning; and when I got home, my number was 33. Mod 2, that's a 1. Finally, I found a pretty good random bit!

Did I miss something obvious, I wonder? It seemed ludicrously difficult.

We are wired to find patterns, but it is much harder to spot randomness.

1. how about something like the following:
the next three cars coming the other way define two intervals I1 and I2
if I1<I2 then your bit is 1, otherwise it is 0

2. "Invent a fairly long sentence at random, then calculate the parity of the number of syllables that it contains" - 31 syllables, random bit = 1.

Or alternatively the parity of the number of letters in some favourite phrase: "Allons enfants de la Patrie, le jour de gloire est arrive!", 46 letters, random bit = 0.

3. A colleague used to do this in his statistics class. He would ask a student to generate 10 bits either by tossing a coin, or by making up 10 random bits (but not tell him which option they took.) He could tell every time by looking at the bits whether they were truly coin tosses or not!

4. Christian: fairly non-random because cars come in clusters -- they all started from the same red light. So l1 will be approximately equal to l2, and it'll be up to my subjective judgment which interval is smaller.

James: Nice. That seems pretty good. The length mod 2 is, I think, pretty close to random unbiased, and I have to commit to the sentence before counting letters, so I can't fool myself, at least, assuming I know how to spell every word unambiguously -- no "color" versus "colour" choices!

5. At the moment of you needing the bit, you could look at your speedometer and get a bit based on its parity...

6. David: I can only read my current speed approximately using my speedometer's needle. I know that I'm between 45 and 50mph, for example. No random bit lurking there.

7. What about if it's closer to the 5 or to the 10? What about looking at the parity of your odometer reading (this is assuming you only need 1 bit).

You could also do something like... if you pass the next tree/pole/pedestrian/store, its being on left/right can give you your bit.

I'm a little wary of the thing James is suggesting because it seems like it would take too much time, and would probably distract me if I'm driving.