[FoRK] Crypto protocol for only good news?

Karl Anderson < kra at monkey.org > on > Fri Aug 18 16:24:23 PDT 2006

mattj at newsblip.com writes:

> Now, if you're not so risk averse, and you want a greater chance of
> hearing about a win, you replace the coin toss with some random number
> generator. Have the bartender read you the friend's message 90% of the
> time, and tell you "Null" for the other 10%.  This way, you have a 45%
> chance of hearing "Win", and if you hear "Null", there's still an 18%
> chance that your team won.
>
> Conversely, if you're highly risk averse, you can reverse the 90-10
> rule, which will give you a 5% chance of learning of a win, and a 45%
> chance that a "Null" is really a win.  Of course, you can pick any
> point you prefer on that spectrum.

The interesting thing is that the the more you're smearing the
reported outcome, the less information can be conveyed by the channel
- the entropy is greatest when there's an equal chance of either
outcome, and this is the same whether the bartender is truthful 90% of
the time or 10% of the time.

http://en.wikipedia.org/wiki/Image:Binary_entropy_plot.png

That's interesting because regardless of the bartender's truthfulness,
when he says "win", you know that there's a 100% chance of a win.  He
says "win" less often when he's less truthful, but "null" means more
when he's more truthful.

How about extending this by adding more iterations?  Put N black beans
in a jar for a win, and N white beans for a lose, and have the
bartender flip the coin for each black bean.  Hm, I don't think that
that's so interesting, the first black bean tells you a win, and you
can get the same outcome with one bean and a different coin.  What if
the beans are put in one of those daily pill dispensers, and you only
open one after each drink?  Then you get incrementally more
information (and you're better able to handle the white beans as they
stack up).  How  about if they're ordered, so the black beans are all
placed last?

-- 
Karl Anderson      kra at monkey.org      http://monkey.org/~kra/

More information about the FoRK mailing list