出来の悪いコインで、フェアなコイントスを実現する方法

Essential Algorithms: A Practical Approach to Computer Algorithms』という本を読んでいる。僕の知るかぎり、まだ日本語には翻訳されていないはずだ。勤務先が O’Reilly Safari への加入をサポートしてくれているので、ありがたく読ませてもらっている。

第二章で「コインをはじいたときに、表が出る確率と裏が出る確率が同様に確か ではない コインがあると仮定する。このコインで公平なコイントスを実現するにはどうすればよいか?」という話がある。少し意訳気味だけど、要旨は変えていない。なかなか面白い問いではないだろうか?

本に掲載されている答えはこうだ。

  1. コインを二度はじく。
    • 表、裏の順に出たら、表とみなす
    • 裏、表の順に出たら、裏とみなす
    • この他の場合は、またコインを二度はじく

これでなぜフェアなコイントスができるのだろうか?

この作りの悪いコインをはじいたとき、表が出る確率が P であるとしよう。このとき、裏が出る確率は 1 - P である。このとき:

  • 表、裏の順に出る確率は: P * (1 - P)
  • 裏、表の順に出る確率は: (1 - P) * P

つまり、これらは同じ確率になる。だから、このように組み合わせることでフェアでないコインでも、フェアなコイントスができるというわけだ。

言われてみれば当たり前だけど、なかなか思いつかないよなあ、と思った。

広告

コメントを残す

コメントを投稿するには、以下のいずれかでログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中