数理解析特論 - Keio

数理解析特論

服部哲弥 1995.4–1995.6

1 バスはなぜ来ないか − 平均（期待値）について （４月２０日）

レポート問題１解答例

レポート１，２の解答例もほしいという要望がありましたので，ひとまずレポート１の解答例を作ってみ ました．

解答 1

（９５９２０ 似内卓君の答．説明が殆どないから参考にしにくいかも知れませんが，正答です．正しく 理解している，と判断しうる最短の解答でしょう．なお，既に何人かの方から指摘がありましたように，

この問1(3)は問題文が自己矛盾していました．ここではほとんどの方が解答していたように，r, aはそ のままとして，従って，平均到着台数が(3) のみ単位時間当たりa/2 という問題である，ということに しておきます．）

（１） E[Z] = ¹_aa

0 tdt= ^a₂

（２） E[z] =³_43a^{2 3}_2a

0 tdt+¹₄²_a¹_2a

0 tdt

=⁵₈a

（３） E[z] =_ra^r _ra

0 tdt+_(1−r)a^1−r _(1−r)a

0 tdt

=¹₂a(2r²−2r+ 1)

（４） E[z] =a

解答 2

この問題，何人の方から，「問2の答え方には困りました．」という主旨のコメントを頂きました．一部 の方には返事しましたが，私の考えていた要点は概ね，

(1)客の苦情が，平均運行間隔と自分の平均待ち時間の測定値とのずれに基づくものなので，そこにきち んと答える．つまり，ずれうることを示す．

(2)客は数学者でなく，講義も聞いていないという条件なので，数学をできるだけ使わずに示す．

(3)問題文に明記はないが，大学にいる者として，「神様の思し召し」や「問答無用」ではなく，本質的な 部分（今の場合は純粋数学的論理でずれが起こりうること）で嘘をつかずに説明する．

(4)その範囲で説得力があるほどよい．例えば一般には簡潔なほど納得しやすいだろう．

(5)それ以外の条件（ソフトな対応など）は，情景を皆さんが自由に考えて，面白く創作して下さればよ い（しなくても数学としては全然構わない）．

といったところでした．当然，「正解」なるものはありませんが，「そのまま実際にバス会社で利用できる」

文面が理想です．そういう意味ではちょっと最初にしては難しかった？避けて通った（問１だけにした）

諸君が多かったようです．解いてくれた中から二つばかり例をあげておきます．

（山田 勝也君の解答．）運行間隔の平均は10分になっておりますが，交通事情やバスの込み具合に伴 う乗り降りの時間により実際の間隔にはばらつきがあります．

運転間隔が短い時は，一つ前のバスを逃してもすぐに次のバスが来ます．ですが，間隔が狭いというこ とはその時間帯にお客様が停留所に到着されている可能性も低いということです．間隔が長ければ，短い

時に比較して時間的にお客様が来る確率が高いわけです．より間隔のあいた時間帯に到着する確率が高く なりますので，平均運行間隔の10分より長くお待ち頂くことが多くなっております．

従いまして，平均の運転間隔よりも平均待ち時間の方が長くなり，時刻表よりもバスの来る量が少なく 感じられると思われます．

しかし，今説明致しましたような理由でありますので，決して間引き運転はしておりません．

（９５９０８ 齋藤君の解答）バス（１号車・２号車・３号車…）は営業所を１０分間隔で出発して行 きます。これらのバスが１０分の間隔をきちんと保って予定どうりに走行すれば、バス停で平均５分待て ばバスが来ることになります。しかし、信号や渋滞などで何台かのバスが遅れた場合、バスを待つ時間は 平均で５分より長くなってしまいます。

極端な例を挙げますと、１号車・２号車・３号車…と１０分間隔でバスは出発したとします。ここで、

１号車・３号車・５号車…はことごとく信号が赤で後ろから予定どおり来ているバスに追いつかれてしま いました。このため、バスは２０分間隔で２台ずつ走行することになります。そのため平均で１０分待た なければバスに乗れません。さらに、１号車と２号車・４号車と５号車・７号車と８号車…が遅れ、後ろ から予定どおり走行してくる３号車・６号車・９号車…に追いつかれた場合、３０分間隔で３台のバスが 走行していることになり、バスに乗るため平均で１５分待つことになります。このようにバスが１０分間 隔で出発していても交通事情などにより平均１５分待たなければ乗れないようなバスの走行間隔が生じて しまうわけです。

この他，説得文をかく前に分析をしてくれた９５９０９ 佐野 桜太君は，

「まず、運行状態を調べる。

E[z] = _T

0

t Tdt=1

2T = 15 T = 30

バスは30分毎に3台来るような状態らしい。」

と書いてくれました．これはなかなか鋭いと思います．（説得する前に現状を分析するのは特論の主旨から 考えても極めて適切です．）

それから，95901 秋田 幸治君は

「かなり待たされてからバスが来たが、とてもバスの中が混んでいると言う時には次のバスはすぐ来ると 思いますのでそちらにお乗りになるのが良いと思います。」

と書いてくれました．これも，問題の主旨には直接関係ありませんが，状況を分析した結果の提案であり，

鋭いと思います．説得力を増す，という主旨からはよい内容ではないでしょうか？

基本的な内容をふまえた上で，さらにこのようなオリジナルな内容がつけ加わっていると，私の好み です．

数理解析特論

服部哲弥 1995.4–1995.6

2 切符売り場の行列 − 分散について （４月２７日）

レポート問題２解答例

今のところ，解答例配布希望が数名，配布不希望がゼロ，また，解答の引用不可はゼロ，引用可は誤答時 匿名希望１を含めて数名，ということで，ほとんどの方は「どっちでもいいよ」というところか，という 気もしますが，希望が複数あるので解答例配布も可能な限り続けます．

レポート２の解答例です．レポート１の問２とほぼ同じ主旨での出題ですので，ans1.tex問２の説明も 参照して下さい．一言で言えば，理想は「そのままＹ駅に提案できる文書」ということです．その観点か らは，短すぎるレポートが多かったかも知れません．

レポート２特有の論点としては，講義 lec2で説明したように，「時間が限られているときに買いはぐれ る可能性が小さい」という論点が入っていた方がいいと思います．また，問１はＹ駅への意見ですが，駅 はこの問題について検討したことがあるので，ある程度説得力ある説明が必要だ，という面もあります．

他方問２は広告文ですから，低姿勢で，しかし，人目につくように，という「キャッチ・コピー」の作り 方の練習という要素もあるでしょう．

当然，「正解」なるものはありませんが，あくまで例ということで諸君の解答の中からあげてみます．

問 1

９５９２５山田君の例．

担当者様

この度、指定券前売り窓口での「一列待ち」を中止した理由の一つとして、平均時間は変わらないとい う回答を頂きました。

これについて、確かに「並列待ち」と「一列待ち」の平均待ち時間は変わらないのですが、それを一列 待ちをやめる理由にするのは適切ではないと考えます。

たいていの客は、次の約束までの間や仕事の休み時間を利用して窓口に来るか、乗る直前に来て発車ま での時間に並びます。待てる時間が限られている時には、平均待ち時間ではなく、客に対する処理時間の ばらつきが重要になってきます。つまり、処理時間の分布の範囲が大きいと、券を買いそびれる確率が高 くなるのです。

「並列待ち」と「一列待ち」を比較すると、「並列待ち」はどの窓口が早く処理されるか分からないの で客はそれぞれの窓口に均等に並びます。そうすると窓口毎に見る処理時間の散らばり具合は、窓口が空 き次第客が処理を受ける「一列待ち」の場合より大きくなってしまうのです。

従って、駅の窓口業務のような、客が並んでいられる時間が限られている場合は、「並列待ち」だと「一 列待ち」より買いそこなう可能性が高くなるので、平均待ち時間が同じだからといって「一列待ち」をや めるのは早計です。

駅のサービス面と、処理効率の低下によるさらなる待ち時間の延長を考慮して、より買いそびれる可能 性を低く押える「一列待ち」に戻すよう提案します。

機械システム 軽部 周君の例．

貴駅では、待ち時間の平均が変わらないことを理由に、「一列待ち」をやめたと聞きました。確かに、平 均時間は従来の「並列待ち」と変わりません。しかし、「一列待ち」には「並列待ち」に較べ、大きな利 点があると思います。それは、「並んだ順番通りに切符が買える」ということです。

これまでの「並列待ち」では、自分の並んでいる切符売場よりも、隣の売場の方が速く進む場合があり ます。「後から来た人が、並んだ場所が良かったために自分よりもずっと先に切符を買い終わった」など ということは日常茶飯事です。このような事態を避けるため、客は皆、より速く順番がまわってきそうな 売場を探します。しかし、どの列が速いかを判断することは非常に難しく、どこに並んだら良いかわから なくなってうろうろしたり、待っている間に違う列に移ってしまう人もいます。これは、切符売場の混雑 の一因となっていると考えられます。また、「並列待ち」では、何人かのグループがそれぞれの売場に一 人づつ並び、一番速く順番がまわってきた人の所に集まって買う、といったようなことが行われており、

苛立ちを感じます。

「一列待ち」にすれば、並列待ちの時のようなギャンブル的要素が無くなり、並ぶ時に考える必要が無 くなります。「並んだ順番通りに切符が買える」ことが判っているため、精神的に穏やかでいることがで きます。更に、遅い客が切符売場を長時間占領してしまう場合でも、後の人は別の空いている売場に行く ことができ、「前の人が遅かったために、時間内に切符を買うことができなかった」という不幸な事態を 避けることができます。それに、遅い客自身にとっても、後ろの人の目を気にせず、安心して切符を買う ことができると思います。

まとめると、「並列待ち」の場合は確率的（ギャンブル的）要素が強く、その時の運によって待ち時間 が大きく変化します。それに対し、「一列待ち」は順番通りに切符を買うことができるため、並んでいる 人数から、だいたいの待ち時間を予測することができます。以上の理由から、一列待ちにすることにより 切符売場がより利用しやすいものになると思われますので、是非ご一考をお願い致します。

そのほかのオリジナルな案．

この問題は「平均だけが問題なのではなく，分散（ばらつき）も実社会に影響を与える」という（数学 的）事実をＹ駅に説得する問題です．Ｙ駅は平均の意味は理解しているけど，分散の重要性には気がつい ていません．そこで，「ばらつく」とはどういうことか，具体的に説明する方がよいと思われます．例えば，

95907木幡 直樹君は，

「例えば、１７分待たされた人と３分待たされた人がいたとします。この２人で平均をとると(17+3)/2 = 10 分が平均待ち時間となりますが、両者の待ち時間には大きな開きがあります。次に１２分待たされた人と ８分待たされた人がいたとします。これも２人の平均待ち時間は１０分となりますが、両者の待ち時間に はそれほど差がありません。

このように、実際の待ち時間には、ばらつきがあるのです。したがって、この待ち時間の散らばり具合 が小さくなるような待ち方の方が、予想以上に待たされて前売り券を買い損なってしまう危険性が少なく なるのです。」

と書いてくれました．表現はまだ手直しの余地があるかも知れませんが，このような，具体的な数字での 説明もあった方がよいかも知れません．

９５９０４ 加茂川 雅彦君は，

「逆に極端に待ち時間が短い人も少なくなるから平均待ち時間は確かに同じですが、待つ人がより平等な 分一列待ちの方が良いと思います。大体の待ち時間を予想しやすい(分散が小さいから予想が外れにくい) という利点もあります。」

という書き方でした．これもよい論点ではないでしょうか．

問 2

95910 澤田 東 君の例．

JRは券購入を確実にします JRはあなたを必要以上に待たせません

JRではこのたび「一列待ち」を採用することになりました。「一列待ち」は従来の「並列待ち」と比較 し、格段に券の買い損ないが少なくなります。また、列は長く見えますが、複数の窓口で処理する分、人 の流れは滑らかです。今までより長く待つことはありません。前の人の不手際でいらいらすることもあり ません。

95915 高橋 望 君の例．

並ぶ時間は見た目の通りです。

余った時間に合わせて並んでください。

10人待っていれば、約2分。

40人待っていれば、約8分。

（ただし、一人あたりの所要時間は1分、5つの窓口の場合）

猪狩 理君の例．

＜＜一列待ちで券を買いそこないを減らせます＞＞

今までに、指定券を買おうと窓口に並んで、買い損なったことはありませんか？

今回、我社が採用した「一列待ち」は、確実に指定券を買いそこなう確率を減らします。

お客様の中には、「一列待ち」は「並列待ち」よりも券を買うのに時間がかかりそうだと思われる方も いらっしゃるでしょう。しかし、「一列待ち」も「並列待ち」も、券を買う平均時間は変わりません。

それではなぜ、「一列待ち」では買い損なう確率が低くなるのでしょう。それについて御説明致します。

並列待ちの場合、お客様は各指定券売り窓口に自然に均等に並ぶ傾向があります。しかし、ここで運悪 く、券を買うのに時間の掛かる人の多い窓口に並んだ場合、このお客様は前売券を買い損ねてしまいます。

これに比べ、一列待ちの場合は、空いた窓口につぎつぎにお客様が入るため、先ほど述べたような不幸 にみまわれる可能性が低くなるのです。

こんないいことだらけの「一列待ち」に皆さん御協力を！！

数理解析特論

服部哲弥 1995.4–1995.6

3 確率，密度，一様分布， · · ·  − 確率論の基礎 （５月１１日）

レポート問題３解答例

問１（95912  鈴木 馨 君の解答から．一部改変．）

Ωを全体集合、Ωの集合族をFとすると、

Ω∈ F である。

φはΩの補集合であるので、

φ∈ F である。

Ai∈ F 、i= 1,2,· · ·, においてAi をφとすると、Ai は互いに素であるから、

P _∞

n=1

An

= ∞ n=1

P[An] となるが、左辺はP[φ]に等しいので，

P[φ] = ^∞

n=1

P[φ]

= P[φ] +P[φ] +· · · となる。

上式を満たすのは P[φ] = 0のときのみであるので、P[φ] = 0が成り立つ。

注意：前半でφ∈ F と言ったおかげで，確率の定義からP[φ]は（非負）実数値でなければならないこ とになる．（これがP がF で定義された非負実数値をとる関数，ということ）．P[φ] =P[φ] +P[φ] +· · · を満たすというと，P[φ] =∞（発散）の可能性を考える人もいるかもしれないが，非負実数値でないと いけない，ということは∞ではない，ということも意味する！

問２ Anは、

An = 2ⁿ×3⁻ⁿ

= 2

3 _n

A は確率の連続性より、

P[A] = lim

n→∞P[A_n]

= lim

n→∞

2 3

_n

= 0

数理解析特論

服部哲弥 1995.4–1995.6

4 確率変数，期待値，分散，独立性， · · · ^{（５月１８日）}

レポート問題４解答例

（９５９０９ 佐野 桜太 君の解答から）

(1)V [X] = E[X

] − E[X]

V[X] = E[(X−E[X])²]

= E[X²−2XE[X] +E[X]²]

= E[X²]−2E[XE[X]] +E[E[X]²]

= E[X²]−2E[X]E[X] +E[X]²E[1]

= E[X²]−E[X]²

(2)a が定数のとき V [aX] = a

V [X]

V[aX] = E[a²X²]−E[aX]²

= a²E[X²]−(aE[X])²

= a²(E[X²]−E[X]²)

= a²V[X]

(3)X と Y が独立ならば V [X + Y ] = V [X] + V [Y ]

V[X+Y] = V[X] +V[Y] + 2E[(X−E[X])(Y −E[Y])]

X、Y は独立なので、(X−E[X])と(Y −E[Y])も独立

V[X+Y] = V[X] +V[Y] + 2E[X−E[X]]E[Y −E[Y]]

= V[X] +V[Y] + 2(E[X]−E[E[X]])(E[Y]−E[E[Y]])

= V[X] +V[Y]

講評．

(3)「X、Y は独立なので、(X−E[X])と(Y −E[Y])も独立」は，講義の(4.6)式でn= 2, f1(x) = x−E[X], f2(x) =x−E[Y], X1 =X,X2=Y,とおけば得られます．これを思いつかなくても，(4.6)

で単純にn= 2, f1(x) =f2(x) =x,X1=X,X2=Y, とおけば，

E[X Y ] = E[X ] E[Y ] が出るので，

E[(X−E[Y])(Y −E[Y])]

= E[XY −E[X]Y −E[Y]X+E[X]E[Y]]

= E[XY]−E[X]E[Y]−E[Y]E[X] +E[X]E[Y] (E[X], E[Y]は定数)

= E[XY]−E[X]E[Y]

= E[X]E[Y]−E[X]E[Y]

= 0 と明快に解決します．

(2) で(1)を利用したのはスマートでした．(3)で佐野君がいきなり使った式 V[X+Y] = V[X] +V[Y] + 2E[(X−E[X])(Y −E[Y])]

を導くときにも(1)を利用することができます．

今のところ，早く出してくれたレポートの中から解答例を選んでいます．もっと完璧なレポートが後か ら来ることもあるので，解答例が最善でない場合もあります．また，大筋は決まっていても，いろんな書 き方があり得ます．だから，解答例はあくまで基礎的な参考と考えて，各自自分の書き方を見つけて下 さい．

数理解析特論

服部哲弥 1995.4–1995.6

5 少しだけ，確率過程 − １．離散時間の場合 （５月２５日）

レポート問題５解答例

問１． （竹越康治君，菅井明君，加茂川雅彦君の解答から）

例１（竹越君）

Xn(ω) =Xn−1(ω) +ωn, n= 1,2,3,· · ·, ω= (ω₁, ω2,· · ·)∈Ω ωを確率変数とみなし,帰納法を用いて解く.

(i).n= 1の時.

E[X1] = E[X0] + E[ω1]

= 0 +¹₂×1 + ¹₂×(−1)

= 0 (ii).n=kの時,E[Xk] = 0と仮定すると,

E[Xk ] = E[Xk−1] + E[ωk]

= 0 (iii).n=k+ 1の時,

E[Xk+1 ] = E[Xk ] + E[ωk+1]

= E[Xk ] + 0 (∵ E[ωk+1] = 0) 

= 0

以上より,E[Xn] = 0であることが示された.これはnの値によらず,常に期待値０である.

例２（菅井君）

１回目に硬貨の表が出た場合

Xn=n １回目に硬貨の裏が出た場合

Xn=−n

一回目の試行において硬貨の表が出る確率と裏が出る確率は等しいから

E[Xn] = 1 2n+1

2(−n)

= 0 よって、nの値により期待値は変わらない

例１についての考察（加茂川君）

「プラスの分とマイナスの分が同じになるのでトータルすると期待値E[Xn]はE[Xn−1]と同じで、0で ある。ただし、これは一回目の硬貨を投げる前の期待値である。一度でも硬貨を投げた結果を用いてよい ならば、E[Xn] =E[xn−1]となる。ただし、このような期待値であるにもかかわらず実際にXn=Xn−1

になることはあり得ない。」

問２． （久津美英之君，神崎修大君，軽部周君の解答から）

Mathematica source program （久津美君）

1: Suiho[time_]:=

2: Module[{d0,e0,time0,list,listxy,g1},

3: d0=0;

4: e0=0;

5 time0=time;

6: SeedRandom[];

7: list=Table[Random[Integer]*2-1,{t,1,time0}];

8: listx=Table[d0+=list[[i]],{i,1,time0}];

9: listxy=Table[{i,e0+=list[[i]]},{i,1,time0}];

10: fp="list.dat";

11: OpenWrite[fp,FormatType->TextForm];

12: Write[fp,listxy ];

13: Close[fp];

14: g1=ListPlot[listx,AxesLabel->{"time","value"},PlotJoined->True];

15: Return[listx];

16: ];

プログラムの説明（久津美君）

このプログラム(Suiho)は,乱数の発生回数を引数として,シュミレーションするものです。

7行目のlist=· · ·というところで,±1の乱数列を発生させています。

そして,次の8行目のlist=· · ·で,逐次の和を求めています。

9行目から13行目は,できた値を配列として, ’list.dat’出力しています。

14行目のg1=· · ·で, グラフを出力しています。

考察（神崎君）．

期待値は0 になるはずなのに, 結果を見ると,はっきりとそういえないものとなってしまった。 どうや ら, n を大きくすると,歩く範囲も広がっていくようだ。

考察（軽部君）．

平均Xn/nが0に収束していく様子がうかがえる。

講評

問１．「隠しヒント」に気づいた方もいましたが，何人くらい気がついたのでしょう．

「第１の例については (5.5)と (5.7)に注意して，期待値の線型性（第４回の式(4.3)）からnについ て帰納法で計算できる．ωn は Ωの要素ω からその第n項を取り出す関数（確率変数）とみなせる．第 ２の例は確率がゼロでない見本が有限個しかないので「素朴」に計算できる．」

竹越，菅井両君の解答とこのヒントが同じ内容を指していることが分かりますか？

加茂川君の考察は（言葉遣いは数学的に不正確だけれども，それにも関わらず）非常に良い指摘なので，

紹介しました．加茂川君が「一度でも硬貨を投げた結果を用いて」という言葉で問題にしているのは，条 件付き期待値と呼ばれる重要な概念です．正しくはE[X_n| F_n−1]，または，E[X_n|X1, X2, · · ·, Xn−1] などという記号を使います．これは X1, X2, · · ·,Xn−1 が決まったときのXn の条件付き期待値を表し ます．簡単に言うと，第n−1回目までの硬貨投げの結果を決めたとき（X1 などを特定の値に決めたと き），n回目の結果（これはまだ投げていないので決まっていない）の期待値をX1,X2,· · ·,Xn−1 の値 を用いて表したものを意味する記号です．加茂川君の言いたかったことは，

E[X_n|X1, X2, · · ·, Xn−1] =Xn−1

と書けば正しい主張になります．例１では，n回目にどこにいるかの条件付き期待値（平均値）はn−1 回目にコマがいる場所に等しい，ということです．n−1 にいた場所Xn−1 から右か左に１つだけ進み，

どちらに行くかは確率1/2なので，平均すると，Xn の（条件付き）期待値はXn−1に等しいのです．こ の式が成り立つとき，確率過程{Xn}はマルチンゲールである，と言います．賭事の用語で「公平な賭」

という意味だそうです．

この概念は講義の余裕がなくて触れることができず，残念に思っていたので紹介する良い機会になりま した．

「Xn =Xn−1になることはあり得ない。」というのは，条件付き期待値E[Xn | Fn−1] がX1,X2,· · ·, Xn−1 の値に応じて変化するという意味では確率変数なのに，決してXn そのものではなく，あくまで

（条件付きの）平均である，という微妙な２面性を意識したのだと思います．これは条件付き確率を理解 する上できちんと押さえないといけないポイントです．加茂川君はさらに例２がマルチンゲールでない，

ととることのできる指摘もしています．これも正しい．

問２は，特にsource programに説明をつけて下さった点を買って久津美君の解答を紹介しました．ち なみに，「最短ソース賞？」は多分高橋望君の Mathematica２行です．

RW[n_Integer] :=

ListPlot[FoldList[Plus,0,Table[Sign[Random[ ] - 1/2],{n}]],PlotJoined -> True]

長いのはC（C++)でくんでくれたものが大抵長いです（当然ですが）．CでもMathematicaでも，解

答としての優劣はありません．（危険だから良い子は最短競争なんかしないでね(笑)．）

得られたデータについての考察も問うていたのですが，解答が少なかったようです．神崎君，軽部君は 大事なことを指摘していると思います．「期待値は0になるはずなのに,結果を見ると,はっきりとそういえ ない」というのは，期待値は0でもサンプル（見本）毎には0ではない，という事実に，虚心坦懐にデー タを見ることで気がついた，ということでしょう．期待値というのはいろんなケース（見本）の平均です．

賭事の利益の期待値は場所代（手数料）分だけマイナスだ，あるいは，胴元のいない「家庭麻雀（こんな 言葉もう死語だろうか？）」では期待値0 だ，というのはよく知られていると思います．これは「破産す る場合と大儲けする場合の平均をとると0」と言っているのであって，実際に経験（シミュレーション）

してみると，平均0で収支とんとんどころか，とんでもない破産してしまった，という，よくあ（っては 困）る悲劇と同じことです．どれくらい極端なことが起こりうるかを示す量が標準偏差（分散の平方根）

です．「nを大きくすると,歩く範囲も広がっていく」というのは，xn の期待値はnによらず 0だが，標 準偏差はnとともに増大する，という事実をデータから読みとったことになります．

また，軽部君は Xn だけでなくXn/n も作図してくれました．図は割愛しますが，0 に近づきます．

これは標準偏差の増大がnの１次式よりはゆっくりである，という事実を読みとったことになります．

さらに，神崎君と軽部君の考察をつきあわせてみると，Xn/n^a が0< a <1のどこかでぎりぎり増大 と 0への収束の境目になっている，と予想できます．実は a= 1/2 がその「境目」です．これは中心極 限定理に関係する重要な結果です．軽部君のはa= 1 に相当します．これは大数の定理に関係します．神 崎君のはa= 0に相当します．

他にもいろんなことが考察できます．実際，多分誰もが図を見て感じるであろう，とても重要な，しか し，知らないと説明の非常にしにくい，性質があります．それで，何人かの出してくれた図がどうしても おかしい，と指摘しました．長くなるので，説明はここまでとして，後は各自工夫して下さい．

データやグラフ等を実験や計算機計算などで得た場合は問われなくても，方法の説明（source program の場合はプログラムの意味と実行させるのに必要な環境の簡単な説明が概ね相当）や結果の考察も提出す るようにしたほうが良いと思います．

外山史君：「今回の講義の、酔歩の例は、４年前の情報工学序論という講義で、聞いたような、気がし ます？」

えー，覚えていて下さってどうもありがとうございました．その後まもなく序論は廃止になったので，

若い諸君には数学以外の講義をする機会がなくなりました．皆さんは私の専門に近いところを序論で聞け た数少ない世代です．

数理解析特論

服部哲弥 1995.4–1995.6

6 少しだけ，確率過程 − ２． Poisson ^{過程 （６月１日）}

レポート問題６解答例

問１． （齋藤宣人君の解答から）

(I) (6.2)の証明。

Poisson分布の定義(6.1)から ∞ n=0

nQ[{n}] = ^∞

n=0

n·µⁿ

n! exp(−µ)

= ^∞

n=1

µⁿ

(n−1)!exp(−µ)

= ∞ n=1

µ·µⁿ⁻¹

(n−1)! exp(−µ)

= µ

∞ i=0

µⁱ

i! exp(−µ)

である。ここで、

∞ i=0

µⁱ

i! = exp(µ)であるから、

∞ n=0

nQ[{n}] =µexp(µ) exp(−µ) =µ . (II) _∞

n=0Q[{n}] = 1 の証明。

Poisson分布の定義(6.1)より ∞ n=0

Q[{n}] =^∞

n=0

exp(−µ) 1

n!µⁿ= exp(−µ)^∞

n=0

µⁿ n!

である。ここで、

∞ n=0

µⁿ

n! = exp(µ)であるから、

∞ n=0

Q[{n}] = exp(−µ)·exp(µ) = 1.

(III) 指数分布の密度について，_∞

0 ρλ(t)dt= 1，及び，平均が1/λ になることの証明。

指数分布の密度(6.4)から

_∞

0 ρλ(t)dt = _∞

0 λexp(−λ t)dt

= λ· _∞

0 exp(−λ t)dt

= λ· 1

−λexp(−λ t) _∞

0

= λ· { 1

−λ(0−1)}

= λ· 1

= 1 λ

となる。また、平均は、

_∞

0 t·ρλ(t)dt = _∞

0 t·λexp(−λ t)dt

= λ

_∞

0 t·exp(−λ t)dt となり、ここで、部分積分法を用いて、

λ· _∞

0 t·exp(−λ t)dt = λ· _∞

0 t· 1

−λexp(−λ t)

dt

= λ

t·exp(−λ t)

−λ _∞

0 − _∞

0

exp(−λ t)

−λ dt

= [−t·exp(−λ t)]^∞₀ + _∞

0 exp(−λ t)dt

= 0 + 1

−λ(0−1)

= 1

λ となる。

(IV) 平均1/λ の指数分布に従う確率変数T についての確率 P[T ≥a]。

P[T ≥a] = _∞

a ρλ(t)dt

= _∞

a λexp(−λ t)dt

= λ· 1

−λexp(−λ t) _∞

a

= λ· 1

−λ(0−exp(−λ a))

= exp(−λ a) である。

問２． （軽部周君の解答から）

軽部君は，Poisson過程Xtのsample path，到着数Xt−Xsの統計分布，Event間隔T の統計分布，

の３種類のシミュレーション（乱数によるサンプル列生成）を解答してくれました．このうち，最初の２ つについてプログラムを引用します．Event間隔Tの統計分布は，軽部君も指摘していることですが，こ の問のヒントのようにやると一番最初に求まるので，ここでは割愛します．また，結果の図も割愛します．

/*---*/

/* Poisson過程の sample path by 94114 軽部 周 */

#include <stdlib.h>

#include <math.h>

#define P 0.5

#define DN 200010

#define RAND() ((double)rand()/(2147483647.0+1.0))

void data_save(double *, double *, long int, char *);

int main()

{ long int n,N,sd; double u; double *Num, *Xdata; char sname1[30];

N=60;

Num = (double *)calloc(DN,sizeof(double));

if( Num == NULL ){ printf(" Num error !!!\n"); exit(1); } Xdata = (double *)calloc(DN,sizeof(double));

if( Xdata == NULL ){ printf(" Xdata error !!!\n"); exit(1); } printf(" SEED =") ; scanf("%ld",&sd) ; /* 乱数の初期値 */

sprintf(sname1,"%dq21.dat",sd);

srand(sd);

for(n=1;n<N+1;n++) {

u = -log(RAND()); Num[n]=Num[n-1]+u; Xdata[n]=Xdata[n-1]+1.0;

}

data_save(Num, Xdata, n-1, sname1);

return 0;

}

void data_save(double *x1, double *x2, long int nn, char *sname1) { long int ii; FILE *fd1;

fd1 = fopen(sname1,"w");

for(ii = 0; ii <= nn-1; ii++){

fprintf(fd1,"%3.2lf %9.6lf\n",*(x1+ii),*(x2+ii));

} fclose(fd1);

}

/*---*/

/* 到着数の統計分布 by 94114 軽部 周 */

/*---*/

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define P 0.5

#define DN 200010

#define RAND() ((double)rand()/(2147483647.0+1.0))

void data_save(double *, double *, long int, char *);

int main()

{ long int s,n,N,sd,g,f,t; double u,T; double *Num, *Xdata, *Mdata;

char sname1[30];

N=200;

Num = (double *)calloc(DN,sizeof(double));

if( Num == NULL ){ printf(" Num error !!!\n"); exit(1); } Xdata = (double *)calloc(DN,sizeof(double));

if( Xdata == NULL ){ printf(" Xdata error !!!\n"); exit(1); } Mdata = (double *)calloc(DN,sizeof(double));

if( Mdata == NULL ){ printf(" Mdata error !!!\n"); exit(1); } printf(" SEED =") ; scanf("%ld",&sd) ; /* 乱数の初期値 */

printf(" s =") ; scanf("%ld",&s) ; printf(" t =") ; scanf("%ld",&t) ; sprintf(sname1,"%ld%ldq22.dat",s/10,t/10);

srand(sd);

for(g=1; g<501; g++){ T = 0.0;

for(n=1;n<N+1;n++)

{ u = -log(RAND()); T = T + u;

if( T >= s && T < t ){ Xdata[g]=Xdata[g]+1.0; } }

} for(g=1;g<501;g++){

f = (long int)Xdata[g]; Num[f] = f; Mdata[f] = Mdata[f]+1.0;

}

data_save(Num, Mdata, N, sname1);

return 0;

}

void data_save(double *x1, double *x2, long int nn, char *sname1) { long int ii;

FILE *fd1;

fd1 = fopen(sname1,"w");

for(ii = 0; ii <= nn-1; ii++){

fprintf(fd1,"%3.2lf %9.6lf\n",*(x1+ii),*(x2+ii));

} fclose(fd1);

}

図１に、Poisson過程Xtのsample pathを示す。上の図が乱数の初期値333 のとき、下の図が初期値 888のときである。Eventの発生間隔が一定でないので、同じ時間内でも、Xtの値には差が生じている。

図２に、時間(s, t]の間の到着数Xt−Xsの統計分布を示す。一つのサンプル時間は、T200までとって ある。（Eventが200回発生するまで。）サンプルの総数は500本である。上図は時間(80,100]の場合、下

図は時間(50,150]の場合である。どちらの場合も、山が一つできている。(s,t]の値を変えて、もっと調べ

てみたが、分布の形はいずれも単峰型であった。

問３． （中村英樹君，猪狩理君，池田敦典君，の解答から）

プログラム（中村君）

/* 一次元酔歩問題 --- 分散 (report6.c)

* Copyright (C) Hideki Nakamura */

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define frand() ((double) rand()/(pow(2,31)+1)) /* 乱数を決定する関数 */

/* 使用法 */

void usage(char *name) {

fprintf(stderr,"Usage: %s[-n<Number>][-f<Number>][-t<Number>]\n",name);

fprintf(stderr," -n< 歩数> <default:20>\n");

fprintf(stderr," -f< 乱数の初期値> <default:1>\n");

fprintf(stderr," -t< サンプル数> <default:100>\n");

exit(1);

}

/* 分散の計算 */

void random(int N, int first,int T) { int i,j,k,X; double X2,V;

srand(first); /* 乱数の初期値を決定する関数 */

for(k=1;k<=N;k++){

X2=0; V=0;

for(j=1;j<=T;j++){

X=0;

for(i=1;i<=k;i++){ /* X(n) の計算 */

if(frand()<0.5) X+=1; else X-=1;

}

X2=X2+pow(X,2); /* X(n)^2 の計算 */

}

V=X2/T; /* Vn (分散)の計算 */

printf("%d %f\n",k,V);

} }

/* オプションの取得 */

void main(int argc, char *argv[])

{ int N=20; int T=100; int first=1; /* default */

char *name;

static char option[]="n:N:f:F:t:T";

name=argv[0];

if(argc > 4) usage(name);

while((argc > 1)&&(argv[1][0] == ’-’)){

switch(argv[1][1]){

case ’n’:

case ’N’: N=atoi(&argv[1][2]); break;

case ’f’:

case ’F’: first=atoi(&argv[1][2]); break;

case ’t’:

case ’T’: T=atoi(&argv[1][2]); break;

default: usage(name); exit(1);

} argc--;

argv++;

}

random(N,first,T);

}

考察（猪狩君）

T=10000, N=1000, n=10とした場合の結果のグラフとT=100, N=100, n=10とした場合の結果のグ ラフを載せてあります。

この結果から、Tを大きくするほどV n=nに近づき、グラフも直線になることがわかりました。これ は、sample数を大きくすることによって、ある地点でのXの値のばらつきが小さくなるためではないか と思われます。また、sample数を比較的小さくすると、ある地点の値のばらつきが大きくなるので、グ ラフもジグザグになったのではないかと思います。

考察（池田君）

歩数n= 50, 3つの初期状態,サンプル数T = 10,30,50,100,300,500,1000,3000,5000の9通りについ て図示する。図1〜図3に初期状態1のときを,図4〜図6に初期状態2のときを,図7〜図9に初期状態 3のときを図示した。また,図10には各初期状態についてT = 50000におけるVnををしめした。各グラ フの縦軸はXnの分散のサンプル平均Vn,横軸は歩数nとする。

T を十分大きなものにするとVn=nに近づく様子がうかがえる。

講評

解答及びプログラムはページ数節約のため空行等削らせてもらいました．見にくくしてすみません．

問１

非常に丁寧に書かれています．レポート解答としてここまで丁寧に書く必要はありませんが，分からな かった諸君が勉強するには大変好都合かと思います．

問２

問２は挑戦してくれる諸君が少なかったのですが，軽部君の解答はその中で質的にも輝いていました．

当然のことですが，Poisson過程のsample pathはWiener過程のsample pathとは全然異なります．バ スの累積到着台数と思って見れば納得できるでしょう．自分でプログラムを走らせてsmaple pathを作っ て眺めるとおもしろいと思います．

圧巻は，図２の、到着数Xt−Xsの統計分布です．（図を割愛してすみません．）講義の理論によれば，

これはPoisson分布になるはずですが，軽部君の考察には「分布の形はいずれも単峰型」と，Poisson分

布の特徴の一つが見えていることに言及があります．s,tを与えると到着数の理論的な平均が分かるので，

Poisson分布が決まるので，その「理論曲線」も図示して比べてみるとおもしろかったかも知れません．

問３

問２に比べるとプログラムは易しいし，前回の続きという意味でも楽だったかも知れません．その割に は安易に少ないデータで問題文の予想に合っていると判断する向きが多かったようです．

中村君のプログラムは，本体以外の，使用法(help)やパラメータ取得に行数を費やした点で一つの参考 になるかと思い，紹介しました．

考察に関しては，サンプル数T に注目してください．T は 10000くらい以上をとるとやっと見た目に かなりなめらかなVn のグラフになってきます．「ばらつきの相対誤差はサンプル数の平方根の逆数」とい う目安があります（統計誤差）．T = 10000で1/√

T = 1%となって，かなりばらつき（図では凸凹）が 減ります．

また，なめらかになってきても Vn =nにならずに，Vn =a n でaが1 から少しずれているように見 えるデータがあります．一つの問題は平均値(Vn)を求める際に単純に足して総サンプル数で割ると，桁 落ちで値が小さくなることです．

一般に {X_i},i= 1,2,3,· · ·, nの平均Aを求めるには S=0

do 10 i=1,n S=S+X_i 10 continue

A=S/n

ではnが大きいとき急速に誤差がたまります．

A=X_1 do 10 i=2,n A=A+(X_i-A)/i 10 continue

のようにやった方が計算誤差が減ります．

（これで解決しなければ，乱数に問題があるかも知れません．乱数の「空打ち」を途中でいれるなどの 工夫をしたものと比較することで，そのような問題を検討することができます．）

問３のような問題で，サンプル数をいくらにするかは，状況によって違います．多少凸凹でも傾向が見 えれば十分な場合もあるだろうし，データを増やすと理論曲線に近づいていく，その様子（複数の図）を 示すのがよい場合もあり，また，場合によっては，非常に詳しく調べると理論曲線からずれることが分か る場合すらあるかも知れません．今回の場合は複数の図を示すのが説得力があるかも知れません．凸凹が どの程度出るはずかは統計誤差として見当がつくので，比べるのも良いことです．

数理解析特論

服部哲弥 1995.4–1995.6

7 少しだけ，確率過程 − ３． Wiener ^{過程 （６月８日）}

レポート問題７解答例 ご意見頂きました．

(1)今回はなかなか難しく、問題１しか分かりませんでした。

(2)ここ２回くらい、だんだんと難しくなってきて苦戦しています。

(3)本音をいうと,問２(酔歩)を解きたかったのですが,問題の意味が良く分かりませんでした。

少し難しくなりすぎましたか？つい，いろいろ勉強してほしいと思って，欲が出るもので…．レポートの 方はこのあとは楽しようと思えば楽できるようになっていますので，心配せず，何とか最後までついてき て下さい．いろいろ挑戦したい諸君はもちろんどんどんやって下さい．歓迎です．

それから，細かいことですが，

Wiener

ウィーナー．（ウィンナーソーセージではありません．）

問１． （西秀和君の解答から，一部訂正）

問題文の式の左辺を変形する。

_∞

−∞

√ 1

2πv1 ×√1

2πv2 ×exp

−(x−z−m1)² 2v1

×exp

−(z−y−m2)² 2v2

dz

= 1

2π√ v1v2

_∞

−∞exp

−1 2

(x−z−m1)²

v1 +(z−y−m2)² v2

dz (1)

指数部は次のように変形できる．

−1 2

(x−z−m1)²

v1 +(z−y−m2)² v2

dz

= −1 2

1 v1 + 1

v2

z²−2

x−m1

v1 +y+m2

v2

z+

(x−m1)²

v1 +(y+m2)² v2

(2) 公式を用いるため式 (2)を次の形に書く．

1

2(−a(z−b)²+c) =1

2(−az²+ 2abz−ab²+c) (3)

式 (2)と式(3)よりa, b, cを求める。まずaは a=

1 v1 + 1

v2

=v1+v2

v1v2 . (4)

次にbは

v1+v2

v1v2 b =

x−m1

v1 +y+m2

v2

.

=

(x−m1)v2+ (y+m2)v1

v1v2

b = (x−m1)v₂+ (y+m2)v₁ v1+v2

cは

c = v1+v2

v1v2 ×

(x−m1)v₂+ (y+m2)v₁ v1+v2

₂

−(x−m1)²

v1 −(y+m2)² v2

= −(x−m1)²v1v2−2(x−m1)(y+m2)v1v2+ (y+m2)²v1v2

v1v2(v1+v2)

= −((x−m1)−(y+m2))² v1+v2 . 式 (1)は、

1 2π√

v1v2exp

−((x−m1) + (y+m2))² 2(v₁+v2)

∞

−∞exp

−a(z−b)² 2

dz (5)

と変形される．ここで、公式

_∞

−∞exp 1

2(−a(z−b)²)

dz= 2π

a に式(4)を代入すると

2π

v1v2

v1+v2

=

2πv₁v2

v1+v2

となる。よって、式 (5)より，式(1)は 1

2π√ v1v2 ×

2πv1v2

v1+v2 ×exp

−((x−y)−(m1+m2))² 2(v1+v2)

= 1

2π(v₁+v2)exp

−((x−y)−(m1+m2))² 2(v₁+v2)

となる．この式と、問題文の式の右辺を比較すると

M = m1+m2

V = v1+v2

となる。

特にm1=m2= 0,v1=t−u,v2=u−s,のときは，問題文の式の右辺はρ0,t−s(x−y)となる。

問２． （鈴木馨君の解答（abc 言語）から）

PUT 40 IN r PUT r/2 IN rr PUT 8/r IN rrr PUT 100 IN c PUT 1000 IN n PUT 40/n IN nn PUT c**(-1/2) IN cc PUT {} IN z

FOR i IN {0..r}:

PUT 0 IN z[i]

FOR j IN {1..c}:

PUT floor(random*2) IN p PUT p*2-1+x IN x

PUT x*cc IN x

PUT floor(x/rrr+rr) IN x IF x>=0 AND x<=r:

PUT z[x]+1 IN z[x]

FOR i IN {0..r}:

WRITE "(" , (i-rr)*rrr , "," , z[i]*nn , ")%" / QUIT

近似はCの値が小さいせいか、あまり良い近似とはいえない結果が出てしまった。機会があれば、もっ と大きいCについても結果を出してみたい。

問３． （外山史君の解答（ Mathematica ）から）

<<Statistics‘NormalDistribution‘;

Yk = Table[Random[NormalDistribution[0,1]],{i,1,1000}];

Xnt = Sum[(Sin[n*t]/n)*Yk[[n]],{n,1,1000}];

Xt = Sqrt[2/Pi]*Xnt;

Plot[Xnt,{t,0,Pi}, Frame -> True,

AxesLabel -> {"t","Xt"}, PlotLabel -> "N = 1000"];

１行目は、正規分布 NormalDistribution[0,1]を使うために必要な手続きです。あとは単に、XN,tの式 に代入させているだけです。講義の図と比べてみると、グラフが丸まった感じになっている以外は、あま りかわりがないので、うまくいっているような気がします。

講評

問１はかなり多くの諸君が選んでくれたので，問題はないと思います．みなさん，aの符号をわざわざ 負になるように定義しているけど，なぜでしょう？西君の解答から不自然な符号をなおし，一部訂正の上 紹介しました．

Wiener過程による解釈は次のようなことです．

時刻sのとき位置yから出発したWiener過程が，tのとき yにいる確率密度はρ0,t−s(x−y)で与え られる．これが計算結果．他方，これを時刻uのときにいる場所で分類すると，「時刻sのとき位置yか ら出発したWiener過程が uのとき zにいて，かつ，tのときyにいる確率密度」をまず考えて，次に zを時刻uのときにいる可能性のある場所全部（つまり実数全部）で積分すれば同じ値になるはず．これ が元の式．

という，考察を式変形で導いたことになります．

興味があるとの感想にも関わらず，今回は問２が殆どいませんでした．鈴木君の解答の図（割愛）はガ ウス分布の傾向を見せていて，良い兆候です．恐らく正しいと思います．見事でした．データを増やして どうなるか見てみたいものです．

abc言語というのは私はなじみがありませんでしたが，なじみのない方も恐らく鈴木君のプログラムは 読めると思います．

> 対話型のインタプリタ言語で、無限長整数が扱えるのが特徴です。

ということだそうです．

問３で，問題文に「一様収束」云々と書いてありましたが，これは，乱数を同じものにすれば，N を増 やしていくとグラフとして収束することを意味します．N を増やしながらグラフをいくつか書いていく際 に，同じ乱数の列を利用すれば収束が見えます．例えばN= 10のときY0 からY10までを乱数を使って 選びますが（Yn は lec7の問３参照），それらを変えずにY11 からY100 までを乱数で選んで，N = 100 のグラフを書く，というようにN を増やしていけば収束が見えるはずです．いくつか試して下さい．

もう一つチェックポイントとしては，上記のように乱数を変えなければ，特に，t=π のときX は N に無関係に一定になります．というのはt=π の値はY0だけで決まるからです．

このY0項を落とすと，X(0) =X(π) = 0となるサンプルだけを選んだことになります．（0で始まって 0 でとまる．このように到着点も決めた選び方をBrownian bridgeと呼びます．）外山君のプログラムを 見ると，Y0の項が抜けているので，そのままだと，Brownian bridgeになっています．Wiener過程に直 すのは，諸君への宿題としましょう．

数理解析特論

服部哲弥 1995.4–1995.6

8 Simple random walk ^と self-avoiding walk ^{− マルコフ性}

（６月１５日）

レポート問題８解答例 問３は自由課題としましたので，解答例は問１と問２のみとします．

問１． （プログラム）

Self-avoiding walkの本数を数えるプログラムを作ってくれた，佐野桜太，齋藤宣人，澤田東，廣田守

４君のうち，澤田君と廣田君のは殆ど同じで，両方とも基本的には齋藤君と同じアルゴリズムです．澤田 君と廣田君の方が整理されたプログラムになっていますが，今回はちょっと早く提出のあった齋藤君のを ３者代表とします．趣の異なる佐野君のプログラムと合わせて，２件を紹介します．

佐野君

#include <stdio.h>

void now(); void next(); void back();

int i,j; /* 現在の座標 */

int k; /* 現在の歩数 */

int c; /* 道のり数 */

char **z; /* 移動空間 */

int *walk; /* 道のり */

int n; /* 規定歩数 */

char root=’0’; /* 道筋表示(off:0,on:1) */

/*---*/

/* 走査点の移動 */

/*---*/

void shift(int s,int *si,int *sj) { switch (s) {

case 1:

*si = *si-1;

break;

case 2:

*sj = *sj-1;

break;

case 3:

*si = *si+1;

break;

case 4:

*sj = *sj+1; } }

/*---*/

/* ポインタを配列に展開 */

/*---*/

void open() { int s,t;

t=2*n-1;

if (NULL==(z=(char **)malloc((sizeof (char *))*t))) printf("Not open z.");

for (s=0;s<t;s++) if (NULL==(z[s]=(char *)malloc(t))) printf("Not open z.");

if (NULL==(walk=(int *)malloc((sizeof (int))*n))) printf("Not open walk.");

}

/*---*/

/* 変数の初期化 */

/*---*/

void init() { int s,t,u;

u=2*n-1;

for (s=0;s<u;s++) for (t=0;t<u;t++)

z[s][t]=’0’;

for (s=0;s<=u;s++) walk[s]=1;

i=n-1; j=n-1;

z[i][j]=’1’; /* 開始点 */

if (n>1) z[i+1][j]=’1’; /* 原点 */

k=0; c=0; }

/*---*/

/* 現在地を調べる */

/*---*/

void now() { int m;

if ((k==n-1) || (5==walk[k])){

if (k==n-1) { c++;

if (root==’1’) { for (m=0;m<n-1;m++)

printf("%d.",walk[m]);

printf("\n");

} }

z[i][j]=’0’;

walk[k]=1;

k--;

if (k>=0) { back();

walk[k]++;

else

next(); }

/*---*/

/* 前の点に戻る */

/*---*/

void back() { int t;

switch (walk[k]) { case 1:

shift(3,&i,&j);

break;

case 2:

shift(4,&i,&j);

break;

case 3:

shift(1,&i,&j);

break;

case 4:

shift(2,&i,&j);

break; } }

/*---*/

/* 次の点に行く */

/*---*/

void next() { int ni,nj;

while (walk[k]<5) { ni=i;

nj=j;

shift(walk[k],&ni,&nj);

if (’0’==z[ni][nj]) { i=ni;

j=nj;

z[i][j]=’1’;

k++;

now();

}

else walk[k]++; } }

/*---*/

/* メイン */

/*---*/

main()

{ printf("歩数を入力して下さい。\n"); scanf("%d",&n);

open(); init();

while (k>=0) now(); c*=4;

printf("道の総本数 C(%i) = %i\n",n,c); }

齋藤君

/* by norichi */

/* H7.6.20 */

#define D 100 /* D > 5 */

#include <stdio.h>

void walk(int, int, int);

int count=0; int array[D][D]; int Num=0;

void main(void) { int box;

box = (D-1)/2;

printf("Input number ’N (<=%d)’>> ",box);

scanf("%d",&Num);

if (Num<=2){

if (Num==1) printf("C_1 = 4 !! \n");

else printf("C_2 = 12 !! \n");

}else{

array[box][box]=2;

array[(box-1)][box]=2;

array[(box-2)][box]=1;

walk(box,(box-2),2);

array[(box-2)][box]=0;

array[(box-1)][(box+1)]=1;

walk((box+1),(box-1),2);

array[(box-1)][(box+1)]=0;

array[(box-1)][(box-1)]=1;

walk((box-1),(box-1),2);

printf(" C_%d = %d !! \n ",Num,(count*4));

}

printf("All Over !!\n");

exit(99);

}

void walk(int x,int y,int n) { int box;

if (n == Num){

count=count+1;

}else{

box = array[y-1][x];

if (box==0){

array[y-1][x]=1;