読者です 読者をやめる 読者になる 読者になる

感じるままに連ねたい(連ねさせろ)

2017/3/25付けでブログを書き始めようと思いまして作りました。趣味興味に関すること、備忘録などをグダグダと書いていくブログです。

最短経路の確率について

setrecです。どうも。この記事は5000字くらいから成ります。

長いので心して読んでください

 

数学の確率についての話をします。

 

私は、受験生時代、数学Aの「場合の数と確率」の分野が苦手でした

(今でも多少苦手です)

が、今となっては受験対策として、する必要がないわけで、

そうなると、もはやイヤイヤやる必要もないわけで、

したがって、趣味として問題集に載っている問題などを、

暇つぶしに解いたりしてるわけですが、趣味としてやってみると、

意外や意外、なんだおもしろいじゃんと

感じることができるようになるまでには、なれました。

そこで、きっと同じ境遇(数Aの「場合の数と確率」の分野が苦手)

の人もいると思うので、ちょっと気づいたことをまとめてみます。

 

そもそも、なんであれだけ場合の数と確率が、嫌いになったのかと思い返してみると、

ある問題に対峙してからでした。

 

f:id:setrec:20170331090317p:plain

「上図のような格子状の街路がある。A点からB点まで最短距離で移動する。

このとき、P点を通る場合の数を求めよ。」

 

こういう問題ありますよね。

そんなん求めてどうするのよ、とか考えるのは時間のムダっていうのは、

高校1年生の秋くらいに、定期テスト中に学びました。

 

いや、この問題は、簡単なんですよ。

A点からP点に行く経路が 5C2=10(通り)、

P点からA点に行く経路が 4C2=6(通り)、

なので積の法則を用いて、求める場合の数は 10×6=60(通り)

という具合に答えが出せますし、

 

もし、さらに、Q点なる点が追加されて、

「P点またはQ点を通る場合の数を求めよ」なんて問題になったとしても、

ほんの少し計算量が増えて、和集合の要素の個数に関する公式

{ n(P∨Q) = n(P) + n(Q) - n(P∧Q) }を用いるだけですから、

たいしたことはないんです。

 

ただこれが、

「P点を通る確率を求めよ。

ただし、右もしくは上に移動するときの確率はそれぞれれ1/2とする」

という問題になると、

たちまち難しくなるんですよね。

いや、答え(解き方)を知ってる人からすれば、何が難しいの、

というような問題ですけどね、初見だと確実に引っかかりますよね、これ。

 

初見のときの私はというと、

”右もしくは上に移動するときの確率がそれぞれ1/2???”

シラネ。えーっと、A点からB点までの総経路が 9C4=126(通り)で、

P点を通る経路が、さっき求めた10(通り)だから、答えは...

10/126=5/63 だ!

 

それで自信満々に模範解答を見て、ペケを食らうんですよね。

あのときのポカン具合と、そのあとのパニックは、

ドッグフードを目の前で消された時の、犬たちの反応の比じゃないですよね。

 

www.youtube.com

 

おかえりなさい。

そもそも確率を計算するには、「同様に確からしい」という前提条件が必要なんです。

確率計算が苦手な人の大半は、この「同様に確からしい」という概念を、

理解できていないのだと思われます。

(ここでは「同様に確からしい」という概念の説明はしません。

後日、記事を書いて追って説明するつもりです。)

 

実際、この最短経路の確率の問題では、

経路1つ1つが「同様に確からしく」ないです。

 

したがって、(P点を通る総経路)/(A点からB点まで行く総経路)

では正しい答えが、求まらなかったのです。

このことは、3枚の赤いカードと1枚の白いカードの計4枚のカードから、

目を伏せて1枚取るとき、赤いカードを引く確率が1/2ではないことと、

ちょうど似ています。

ちなみに、これの正しい答えは3/4です。

 

なぜ1/2でないかというと、「同様に確からしい」ように確率を計算するには、

(この場合なら)すべてのカードを区別して扱う必要があるからです。

全てのカードを区別して扱うとは、すべてのカードを対等に扱う、ということであり、

全てのカードを対等に扱うとは、「同様に確からしい」ということである、

という解釈で構いません。

 

すなわち、確率を計算するには、「同様に確からしく」ある必要があり、

それを実現するには、すべてのカードを対等に(区別して)扱う必要があるのです。

 

1/2と答えてしまう人は、赤のグループ、白のグループという風に、

考えてしまっているのではないでしょうか。

赤のグループには3枚、白のグループには1枚のカードが、ある状態ですから、

これでは、グループとしては対等ではありません。

(赤のグループ VS 白のグループなら、

赤グループの方が勢力が、強いイメージ?になってしまう)

よって1/2{(赤のグループの数)/(全体のグループの数)}は間違いです。

 

これを対等にするには、赤1、赤2、赤3、白1の4枚のカードとして扱う必要があります。

これならば、グループもなにも、赤1VS赤2VS赤3VS白1 という風にそれぞれが、

対等な状態でありますから、「同様に確からしい」と言えます。

(赤のカードは仲間同士ではないというイメージ?笑)

よって、3/4{(赤の枚数)/(全体の枚数)}は正しい答えであります。

(ざっくりとした説明です、ご了承ください。)

 

さて、確率の前提条件についての話はこれくらいにして、

なぜ、最短経路の経路1つ1つが「同様に確からしく」ないか、を説明します。

f:id:setrec:20170331090317p:plain

さて...説明すると言いましたが、

経路1つ1つが、「同様に確からしく」ないことの説明が、非常に難しいです。

例えば、A点からB点までの総経路は126(通り)ですが、

これを、すべて→と↑の順列で表現すると...

 

(→、→、→、→、↑、↑、↑、↑、↑)

(→、→、→、↑、→、↑、↑、↑、↑)

(→、→、→、↑、↑、→、↑、↑、↑)

(中略)

(↑、↑、↑、↑、↑、→、→、→、→)

 

のようになります。

なんかパッと見、対等っぽいから、対等として話を進めよう!としても、

対等にはなりません。(つまり、私が初見で解いた時の解き方では、無理です。)

ではなぜ対等ではないか。

 

他のサイトを参考にして考えてたり、誰かと話し合ったり、

確率について、深く深く研究しているわけでもないので、

これが理由です!と言い切れる明確な理由は、まだないです。

 

「は?」とか言わないでください。

でも、この辺りが原因じゃないかなあ~という所までは、考えています。

 

1つ目。

まず、「偶然の度合い」という視点からの考察です。

確率は、そもそも、結果が偶然によって決まるもの、

についてしか、考えることができません。

だから「偶然の度合い」が変化すると(つまり、経路が一様でないと)、

対等とは認められないのではないか、という仮説です。

 

「偶然の度合い」について説明します。

問題設定では、「右もしくは上に移動する確率はそれぞれ1/2」と書かれていますが、これは、”分岐点では”という意味を含蓄しています。

つまり、分岐点ではないところ(右もしくは上にしか行けないところ)では、

その移動する確率は1である、という意味です。

最短経路の問題では必ずこういう場所が存在します。

(というか、存在してしまいます。)

そして、そのために「偶然の度合い」が一様ではなくなっています。

さきほど、すべての経路を順列表示しましたが、今度は、そのすべての経路について、

1つの移動がどの確率で起こったかを(確率)を付けて表記してみます。

すると...

 

(→(1/2)、→(1/2)、→(1/2)、→(1/2)、↑(1)、↑(1)、↑(1)、↑(1)、↑(1) )

(→(1/2)、→(1/2)、→(1/2)、↑(1/2)、→(1/2)、↑(1)、↑(1)、↑(1)、↑(1) )

(→(1/2)、→(1/2)、→(1/2)、↑(1/2)、↑(1/2)、→(1/2)、↑(1)、↑(1)、↑(1) )

(中略)

(↑(1/2)、↑(1/2)、↑()1/2、↑(1/2)、↑(1/2)、→(1)、→(1)、→(1)、→(1) )

 

はい、なんとなく言いたいことがわかると思います。

今度は、さらに(1/2)を〇で、(1)を×で表示してみます、矢印は省きます。

 

(〇、〇、〇、〇、×、×、×、×、×)

(〇、〇、〇、〇、〇、×、×、×、×)

(〇、〇、〇、〇、〇、〇、×、×、×)

(中略)

(〇、〇、〇、〇、×、×、×、×)

 

はい、疲れました。

この〇とか×が何を表すかと、言いますと、

〇は任意に移動、×は強制的に移動、

ということです。

 

アレアレ?

強制の数が変わると、「偶然の度合い」も変わっちゃいません?

1つめの順列と2つ目の順列って、その順列が確定するまでに要した手数、

と言うか、その順列が確定するまでに任意に選べる矢印の数が、

一致してませんよね。

そうすると、感覚的に同様に確からしいとは、言えないんじゃないんですか?

これって、トリビアになりませんか?

 

2つ目。

A点からB点まで行く確率が1であるということ。

はい、またすぐ「は?」とか言うでしょ。

説明します。

 

そりゃ、「最短で行く」って言うんだから、

「行く」って言ってんだから、そら絶対「行く」んだから、

A点からB点まで行く確率は1でしょ。

 

そうですよ?

 

「行け」ば、「行き」さえすれば、確率は1なんですよ。

ということは、一般的に言うと、四角形の対角線上にある2点(対角点?)の、

1点(A点)から、もう1点(B点)まで行く確率は、1です。

 

そうすると、「P点を通る確率」って、「P点に行く確率」じゃないですか。

だって、P点とB点が四角形の対角点(勝手に変な名前付けてすみません)

とみなせば、P点からB点まで行く確率って、1じゃないですか。

積の法則を用いれば、1はどんな数にかけても、結果に影響を及ぼしませんから、

結局「P点に行く確率」で良いわけです。

 

じゃあ、「P点に行く確率」をもし、定義通りに求めようとしても

(P点を通る総経路)/(A点からB点に行く総経路)で求まらないのも、

ぼんやり納得いきませんか?

 

以上の2つが、最短経路の確率を、

確率の定義通りには、求められない理由に近い何か、

なんじゃないかなあ~と思ってます。いろいろ考えたり、考察するのが楽しいですね。

 

f:id:setrec:20170331090317p:plain

 

ところで、正しい答えはどうやって求めるの?って?

もう記事終わりたかったですけど、さすがにそうはいきませんか。

はい、解説します。

 

模範解答「書き込んでいくだけ」。

例えば、A点から右もしくは上に行く確率はそれぞれ1/2ですから、

A点の1つ右、1つ上の点はそれぞれ1/2の確率で移動します。

A点の右上の点(2/4となっている点)に移動する確率を出したければ、

移動前の点の確率に移動確率をかけたものの和で出ます。

(つまり、2/4=1/4 + 1/4 = 1/2 × 1/2 + 1/2 × 1/2 ということです。)

という風に順番に計算していけば、求めたい点に移動する確率はすべて出せます。

f:id:setrec:20170331115158p:plain

 

ちなみに、この例では 10/32 = 5/16 となりやはり、

私が、初見で解いた時の答えは、ちゃんと間違っていたわけですね。

でも、これって数学なの...?(数学の参考書に載っていた解法です)

だって、書き込んでいくだけってさ...

と個人的には思ったので、少し数学チックに

補足します。

 

さきほど、P点を通る確率は、P点に行く確率だと言いました。

この図では、P点に行く総経路は、10(通り)あります。

この10(通り)を順列表示してみると...

(→→↑↑↑)

(→↑→↑↑)

(→↑↑→↑)

(→↑↑↑→)

(↑→→↑↑)

(↑→↑→↑)

(↑→↑↑→)

(↑↑→→↑)

(↑↑→↑→)

(↑↑↑→→)

 

です。(間違ってないよな...)

これらはすべて同時には起こりません。

よって、順列1つ1つの確率を求めて、

最後にまとめて足せばよいわけです。(和の法則)

ちなみに、1つの順列中では、同時に起こり得る経路ですから、

積の法則を用います。

 

試しに計算してみると...

1つ目より、1/2 × 1/2 × 1 × 1 × 1 = 1/4

2つ目より、....

 

やっぱり、もういいですか。勘弁してください。

 

と、まあこんな感じで、「最短経路の確率問題」についての考察は以上です。

ずいぶん記事が長くなってしまいました。

最後まで読んでくださった数学マニア様、

もしくは数学大好き人間様に感謝を申し上げます。

 

それから、趣味程度にやっているだけですので、

厳密な議論ではないことに注意してください。

また、誤植、指摘などあれば、教えてください。

 

それでは、また。