日の目を見なかった問題たち その1
はじめに
とてもオモシロイ、心に響くものがあるにもかかわらず、いろいろな理由から
ついに日の目をみずに終わってしまった問題。
みなさんもこうした問題を一つくらい持っているのではないでしょうか?
ときどき思い出しては見るものの、今さら発表するほどのモノでもなく、
さりとて忘れ去ってしまうにはちょっと愛着がある…。
そんな問題にも無理やり日の目をあててみると、実は他の人にとってもオモシ
ロかったり、自分では気付きもしなかった、なにがしかの意義を指摘してもら
えたり、あわよくばそこからおもしろい研究材料が見つかるかもしれません。
そんな下心を抱きながら、勝手に『日の目を見なかった問題たち』シリーズを
はじめることにしました(『その2』は、どなたか引き継いで下さい)。
今回は第一段(?)ということで、私が乱数や Randomized Algorithm を好きに
なったきっかけを作ってくれた問題(問題というよりはアルゴリズムなのです
が)を紹介したいと思います。
log nなんて簡単に計算できる
与えられた長さ n に対して、ちょっとコインを投げるだけで、
log nなんて簡単に計算できるんですが、ご存じですか?
こんなアルゴリズムでO.K.なのです…
- 用語
- コインを投げて、同じ結果が続くものを『連』と呼びま
す。例えばコインを4回投げた結果が「表表裏表」となった場合、
これは3つの連[表表][裏][表]が連続したものと考えます。
- アルゴリズム
- コインを投げて連をn個作り、これらの連の長さの最大値を出力する。
たったこれだけのアルゴリズムです。ただ単純に連の長さを数えているだけで、
ほとんど計算らしい計算はしていないように見えますね。
ところがこのアルゴリズム、計算の結果が
log n ± 3 の範囲に収まる確率は、実に90%を越えます。
しかもなんとその確率はnには依存しないんです。すごいと思いませんか。
どうしてそうなるんでしょう??
直感的な説明
| 図1:最長の連の長さがlog nになることの説明 |
|---|
 |
上記のアルゴリズムの計算結果がだいたい log n になる、という事実の
厳密な証明はひとまず置くことにして『なぜそうなるのか?』という素朴な疑
問に対する直感的かついいかげんな説明もどきを紹介することにします。
まず明らかに、連の長さの最小値は1です。
次にコインを投げたとき、確率1/2で前回と違う面が出て、
そのとき連の成長はそこでストップします。
つまり大雑把にいえばn個の連のうち、
n/2個は長さが1になるわけです。
以下同様に、n/4個の連は長さが2、
n/8個の連は長さが3、…、n/(2i)個は
長さがiになります。
ここで最長の連は1つしかなかろう、とあたりをつけると、
n/(2l)=1と
おくことができて l =log nとなるわけです。
LAの会誌29号を読んで以来 LaTeX + tgif + tgif2tex を愛用することにしているので、
ついでに図1にこの様子を示しておきます
。
かなりいいかげんですが、これでだいたい『なぜ log n になるの?』とい
う素朴な疑問に対する答にはなっているのではないか、と思います
(おまけクイズです。nが2のベキ乗のとき
n/2 + n/4 + n/8 + … + n/(2log n) = n-1
になります。あれ、この説明では連の個数が一つ足りませんね。
足りない連はどこにいってしまったのでしょう…??)。
なぜ日の目を見なかったのか…?
この問題は実は loglog n の強領域構成可能性という問題にからんで
思い付いたアルゴリズムです。当時、私の研究室の先輩である陳さんから、
彼がそのころ考えていたアルゴリズムを聞いたのがきっかけでした。
陳さん自身もこれに関連した結果を昔LAで発表しています[Che88]。
その後、こうした結果がすでに知られていたことがわかりました[KV87]。
これらの関連する研究の中で取り上げられているアルゴリズムは、
ここで取り上げたアルゴリズムとは微妙に違っています。
既存のアルゴリズムでは、コイントスの回数がnになっていて、
一方私のアルゴリズムでは連の個数がnになっています。
このほんのわずかな違いが、解析をかなり簡単にしているのではありますが、
それだけではちょっとアピール度が少なくて、
イマイチの感があります[Ueh93b]。
その他もろもろのことがあって、結局このアルゴリズム自身は
きちんとした形で発表することもなくお蔵入りしてしまいました。
蛇足とおまけ問題
今回紹介したアルゴリズムは、本来の目的である loglog n の強領域構成
可能性の証明については結局日の目を見ることはありませんでしたが、
私を乱数や Randomized Algorithm の世界に引きずり込んでくれた思い出深い
問題です。また他の人に『Randomized Algorithm のどこがおもしろいの?』と
聞かれたときに『例えばlog nなんて簡単に計算できるんだよ』という
宣伝に使うことができます。アルゴリズムが簡単に説明できて、しかも計算結果
がけっこう意外でおもしろいのではないか、と思います。
ここまで読んで下さった方は、Randomized Algorithm のおもしろさを
少しでも感じていただけたのではないか、と一方的に思い込むことにします。
本格的に勉強してみたくなった方には文献[MR95]をお奨めします。
ここではせっかくなので、もう少しだけおまけの問題を
さしあげることにしましょう。
あなたは道でコインを拾いました。どうもイカサマコインのようです。
表の出る確率は、いつでも一定の値ではあるようですが、
1/2ではないようです。具体的にいくつかはわかりません。
さてここで問題です。
- おまけ問題初級:
- このイカサマコインを使って、表が出る確率が1/2であるようなコインを
模倣するアルゴリズムを考えて下さい。
- おまけ問題中級:
- このイカサマコインは、表が出る確率がわかりませんので、
このままではイカサマに使うことはできません。
これを使って、自分に有利なイカサマコインを模倣する
アルゴリズムを考えましょう。
具体的に、互いに素な正整数n,m (0<n<m) が与えられたとして、
表が出る確率が n/m であるようなコインを模倣する
アルゴリズムを考えて下さい。
- おまけ問題上級:
- おまけ問題初級、中級のそれぞれのアルゴリズムで、
イカサマコインを投げる回数の期待値を
なるべく小さくなるようにして下さい。
どれもそれほど極端にムツカシイわけではありませんので、
頭の体操だと思ってお楽しみ下さい。
でもどうしても気になって気になって、ついに夜も眠れなくなった方のために、
手がかりを示しておくことにしましょう。
実はおまけ問題初級には通称『von Neumann のアルゴリズム』と呼ばれる、
シンプルな解答があります[Neu51]。
おまけ問題中級は私のオリジナルですが、Knuth と Yao による研究を参考に
すると、答を捻り出すことができます[KY76]。
おまけ問題上級は…かの von Neumann のアルゴリズムをどうやって改善する
か、が頭のひねりどころです。
ある程度の改善はわりとなんとかなるのですが、どこまで改善できるか、
という厳密な下界はまだわかっていないようです[SW84]。
2005年8月1日追記:
上記の『改善』については解かれてしまいました．詳しくは以下の文献を御覧下さい．
- [PL05]
- S.-i. Pae and M.C. Loui. Optimal Random Number Generation from a Biased Coin.
Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 1079-1088, 2005.
- [Che88]
- 陳 致中.
How to prove results about probabilistic Turing machines using
loglog(n) space by conventional arguments.
情報基礎理論ワークショップ, 1988.
- [Ueh93b]
- 上原隆平.
確率Turing Machineにおける低いレベルの領域強 構成可能性について.
情報基礎理論ワークショップ, 1993.
- [KV87]
- M. Karpinski and R. Verbeek.
On the Monte Carlo Space Constructible Functions and Separation
Results for Probabilistic Complexity Classes.
Information and Computation, 75:178-189, 1987.
- [KY76]
- D.E. Knuth and A.C. Yao.
The complexity of nonuniform random number generation.
In J.F.Traub, editor, Algorithms and Complexity, New Directions
and Results, pages 357-428. Academic, New York, 1976.
- [MR95]
- R. Motwani and P. Raghavan. Randomized Algorithms.
Cambridge, 1995.
- [Neu51]
- J. von Neumann.
Various techniques used in connection with random digits. Notes by
G.E.Forsythe. National Bureau of Standards.
Applied Math Series, 12:36-38, 1951.
Reprinted in von Neumann's Collected Works 5 (Pergamon Press, 1963),
768-770.
- [SW84]
- Q.F. Stout and B. Warren.
Tree Algorithms for Unbiased Coin Tossing with a Biased Coin.
The Annals of Probability, 12(1):212-222, 1984.
