パターンとはあらかじめ与えられた，あるいは決められた文字列のこととする．待ち時間 とはパターンが最初に現れるまでに要する時間のことである．ABCというパターンに対し，
DWABCという列のとき，待ち時間は5である． ABCというパターンが現れるまでの待ち
時間は3以上である．
放字のパターンであれば，どのパターンでも待ち時間Tの平均E（T）＝ΣnP（T＝n）
n＝1
は同じだろうか．次のことをマルチンゲールの理論を応用して示してみよう．
A，B，C，．．．，X，Y，Zの26文字がランダムに現れるとき，パターンABRACADABRAが 現れるまでの待ち時間の平均は
E（T） ＝ 26ii 十 264 十 26
となる．
（2しn，乱，fPn）を
S2tn ＝ ｛A， B， C， … ， X， Y， Z｝） 3n ＝ ？（utn）， EISn（｛A｝） ＝ 9Pn（｛B｝） ＝ ＝＝ S）3n（｛Z｝） ＝ Slt7
の確率空間とする．そして，
（Ω，∫，P）一H（Ut・ふ調 nEN
と定義する．Ωの要素ωは各CViを鶏の要素としてω＝（ω1，ω2，＿）と書ける．確率変数
XnをXn（ω）＝Wnと定義し
ゐ＝｛の，Ω｝， ろ＝σ（x、，x2，＿，一x。），
T＝ inf｛n ： Xn−lo ＝： A 7 Xn−g ＝ B， Xn−s ＝ R， Xn−7 ＝ A，… ， Xn−2 ＝ B， Xn−1 ＝ R， Xn ＝ A｝
と定義するとTは｛鑑｝一停止時間で，ABRACADABRAが最初に現れるまでの待ち時間で
ある．時間の単位は特になんでもよいので，1日を単位時間としてこの問題を考えてみる．今，あるカジノに大文字のアルファベット26文字が並んだ公平な，すなわち各アルファ
ベットの所に球が止る確率端のルーレットがあるとする・そこ一駅・人ず噺しレ・
ギャンブラーが現れ，
文字Aの所に球が止るという事象
に1＄賭け，負ければ去る．勝てば26＄受け取り，次の日に 文字Bの所に球が止るという事象
に26＄賭け，負ければ去る．勝てば262＄受け取り，次の日に 文字Rの所に球が止るという事象
に262＄賭け，負ければ去る．勝てば263＄受け取る．以下同じように，文字A，C，A，D，A，B，R の所に球が止るという事象に賭ける．そして，10回連続で勝つと11回目に
文字Aの所に球が止るという事象
に2610＄賭け，負ければ去りゲームは続く．勝てば2611＄受け取り，ABRACADABRAが現
れたことになり，その時点ですべてのゲームは終了するものとする．n日目のカジノの儲けをYnとすると，次のようになる．｛ω：Xl（ω）＝A｝などωを省略して簡単に｛x1＝A｝と
書く．
Y， ＝ II｛x，1．｝ 一 （26 一 1）1｛x，＝A｝
Y2 ＝ 261｛x，＝A，x，IB｝ ＋ II｛x，IA｝ 一 （262 一 26）1｛x，＝A，x，＝B｝ 一 （26 一 1）1｛x，＝A｝
5．マルチンゲールの応用
80
Y3 ＝： 2621｛x，＝A，x，＝B，x，tR｝ ＋ 26J｛x，＝A，x，IB｝ ＋ II｛x，IA｝
一 （263 一 262）1｛x， ．，，A，x，＝B，x，＝R｝ 一 （262 一 26）」｛x，＝A，x， ．．B｝ 一 （26 一 1）1｛x， ．，A｝
Y4 ＝ 263J｛x， ．．A，x，＝B，x，．R，x，：A｝ ＋ 262」｛x，＝A，x，＝B，x，tR｝ ＋ 261｛x，＝A，x，IB｝ ＋ II｛x，tA｝
一 （264 一 263）1｛x，＝A，x，．B，x，＝R，x，．A｝ 一 （263 一 262＞1｛x，＝A，x， ，．B，x，＝R｝
一 （262 一 26）J｛x，＝A，x， ．．B｝ 一 （26 一 1）1｛x， ＝A｝
Ys ＝＝ 2641｛x，，．A，x，．．B，x，＝ R，X，＝A，Xsla｝
十 263J｛x，．．A，x，＝B，x， ：R，XsIA｝
十 2621｛x， ．，A，x，＝B，XsIR｝
十 26J｛x， ．．A，XsIB｝
＋ II｛x，IA｝
一 （265 一 264）1｛x，．A，x，＝B，x，＝R，X4＝A，Xs＝C｝
． （264 一 263）1｛x，＝A，x， ，＝B，x，＝R，Xs＝A｝
一 （263 一 262）1｛x，＝A，x，＝B，Xs＝＝R｝
一 （262 一 26）」｛x，＝A，X，＝B｝
一 （26 一 1）1｛x，＝A｝
以下同じようにY6，Y7，Y8，Yg，YIOをXl，X2，．．．，XIOを用いて表わすことがで．きる．さら
に，n≧11のとき
Yn ＝ 26101｛X．一lo＝＝A，Xn−g＝B，Xn−s＝R，Xn−7＝A，Xn−6 ＝C，Xn−s＝A，Xn−4＝D，Xn−3＝A，Xn−2＝B，Xn−1＝R，XntA｝
＋ 2691｛Xn−g＝A，Xn−s＝B，Xnm7＝R，Xn−6＝A，Xn−s＝C，Xn−4 ＝A，Xn−3＝D，Xn−2＝A，Xn−1 ＝＝B，XnlR｝
＋268」｛X．一s＝A，Xn−7＝B，Xn−6＝R，Xn−s＝A，Xn−4＝C，Xn−3＝A，Xn−2＝D，Xn−1＝A，XnlB｝
＋ 2671｛X．一7 ＝A，Xn−6＝B，Xn−s＝R，Xn−4＝A，Xn−3＝ C，Xn−2＝A，Xn−1＝D，XntA｝
十 2661｛X．一6＝A，Xn−s＝ B，Xn−4＝R，Xn−3 ＝＝A，Xn−2＝C，Xn−1＝ A，XnlD｝
＋ 2651｛X．一s＝A，Xn−4＝ B，Xn−3 ＝R，Xn−2＝A，Xn−i ＝C，XnlA｝
＋ 264J｛x．一4＝＝A，Xnin3＝B，Xn−2＝R，Xn−1＝A，Xn4C｝
＋ 2631｛x．一3＝＝A，Xnm2＝B，Xn−1＝R，XnlA｝
十 2621｛x．一2＝A，Xn−1 ＝B，Xn：R｝
十 261｛Xn−i＝ A：XnlB｝
＋ II｛xnXA｝
一 （2611−2610）1｛x．一lo＝A，x．一g ＝B，X．一s ：R，X．一7＝A，Xn−6＝a，Xn−s ＝＝A，Xn−4＝D，Xn−3＝ A，Xn−2 ＝＝B，Xn−1＝R，X 一 （2610 一 269）1｛x．一g＝A，X．一s＝B，X．m7＝R，Xn−6＝A，Xn−s＝＝C，Xn−4＝A，Xn−3＝D，Xn−2＝A，Xn−1＝B，Xn＝R｝
一 （2610 一 268）1｛x．一s＝A，X．一7＝B，X．一6＝R，Xn−s＝A，Xn−4＝C，Xn−3＝A，Xn−2＝D，Xnml ＝A，Xn＝B｝
一 （268 一 267）1｛．x．一7＝A，X．一6＝B，Xn−s＝R，Xn−4 ：A，Xn−3＝C，Xn−2＝A，Xn−1 ＝D，Xn＝A｝
一 （267 一 266）1｛x．一6＝A，X．一s＝B，Xn−4＝ R，Xn 3 ＝A，Xn−2＝C，Xn−1＝A，Xn＝D｝
m （266 一 265）1｛x．一s＝A，X．一4 ＝B，Xn−3＝＝R，Xn−2＝A，Xn一＝C，Xn ＝A｝
一 （265 一 264）1｛x．．4＝A，X． 3＝B，Xn−2＝R，Xn−i＝A，Xn＝C｝
一 （264 h 263）J｛x．一3＝A，Xn−2＝B，Xn−1＝R，Xn＝A｝
一 （263 一 262）1｛x．一2＝A，Xn−i＝ B，Xn＝R｝
一 （262 一 26）1｛xn−i＝A，Xn＝B｝
一 （26 一 1）1｛Xn＝A｝
と書ける．第η日目までのカジノの儲けの合計は れ
M・一ΣYk kニ1
と書ける．ただし，M・＝0とする・このとき，M＝（Mn：n≧0）が｛ろ｝一マルチンゲールに なることを以下に示す．Mn−1は鑑一1一可測だから，
E［Mn 1 ■n＿i］＝ E［Mn＿i十Yn 1 J ln＿1］
＝ E［Mn＿ilfn＿1］十珂y弛1フ㌦＿1］
＝ Mn＿1十 E［Yn I JFn＿1］
となる．従って，E［Y。 lf。一i］＝0となることを示せばよい．
」｛X。．、。＝・A，X。一，一B，…，Xn．、＝・R，Xn≠A｝＝1｛X。一，。＝A｝1｛Xn．，ニB｝…1｛Xn．、一R｝1｛Xn≠A｝
1｛X。一、。一A，X。一，一B，…，X。．、＝R，X。＝A｝＝1｛X。一、。一A｝1｛X。．，ニB｝…1｛X。一、一R｝1｛Xn＝A｝
であり，・｛Xn．、。．A｝1｛Xn．、．・｝…」｛X。一、．R｝ほ鑑．、一可測，・｛Xn≠A｝，・｛Xn一。｝は」PTn．、とち蚊
であることに注意すると，
E［26101｛x。一、。．A，x。一，．B，．，xn≠A｝一（261L 2610）1｛x。一、。．A，x。一、一B，。．．，x。＝A｝1．7 1。一、］＝0
となることが分かる．
同様に，
E［26gl｛x。一、．A，x。．，．B，…，xn≠R｝一（2610 一・269）」｛x。．，．A，x。一，．B，…，xn−R｝1鑑．、］＝O
E［261｛xn＿1ニA，xn≠B｝一（262−26）1｛xn＿1＝A，xn＝B｝lfn＿i］＝O E［II｛Xn≠A｝一（26−1）1｛Xn＝A｝1JPTn＿il＝0
となり，E［Yn 1．」「n＿1］＝0となる．ゆえに，
E［Mn l■n＿1］＝Mn＿1， a．s。
となる．
n＞11のとき
ユ
IMp 一一 M・一・1一臥1≦Σ 26k kニ0
ユ
だから，Σ26k 〈 krであるK＞・をとると，任意のnとωに対し h＝O
IM．一Mn＿11≦K が成り立つ．よって，任意のηに対し
E（IM・1）≦E（Σ臥1）＜n一κ＜・・
h＝1
5．マルチンゲールの応用
82
となる．定義よりMは．71nに適合している．ゆえに， Mは｛鑑｝一マルチンゲールである．次に，1＞＝11，εを26−11＞ε＞0となるようにとると，
｛T g n＋ 11｝ D ｛X．＋i ＝ A， Xn＋2 ＝ B， … ） Xn＋ii ＝ A｝
なので，任意のnに対し
P（T S n＋ 111」1 ln） ） P（｛Xn＋i ＝ A， Xn＋2 ＝ B） … ） Xn＋ii ＝＝ A｝I」1 n）
＝珂1｛Xn＋、．A｝1｛Xn＋，．B｝…」｛Xn＋、、。A｝1鑑］
＝ E（1｛xn＋i＝A｝）E（」｛xn＋2＝B｝） E］（1｛Xn＋ii＝A｝）
1 ： T． ＞e 2611
となり，補題2．6より一E（T）＜○○となる．よって，定理2．4Doobの任意停止定理より，
E（MT） ＝＝ E（Mo） ＝O
が成り立つ．そして，MTは
MT＝＝T一（2611一ト264十26）
と書けるので，
E（T） ＝ 26ii 十 264 十 26
となる．
同様に，11文字のパター一一ンMATHEMATICS，GAUSSGAUSSGが現れるまでの待ち時
間の平均は，それぞれE（T）＝2611，E（T）＝2611＋266＋26であることが分かる．11文字のパターンでは，AAAAAAAAAAAなど同じ文字を打つのにかかる平均待ち時間が最大で，
E（T）＝2611十2610十…十262十26となる．