ネッ トワーク障害発生の定量的評価への誕生日重複問題の非線形近似理論的方法 東京理科大学理工学部情報科学科 児玉賢史 東京理科大学理工学部情報科学科 Tong Yao 東京理科大学理工学部情報科学科 明石重男 1. 序章 \ovalbox{\tt\small REJECT} 6 0人のクラスで、同じ誕生日を持つ生徒が2人以上存在する確率は、9 9パーセン ト以上である』 という話を聴いたことがある人は多いと思われる。しかし、この話を厳密 に解釈するためには、『9 9パーセント以上の確率』 という言葉の意味をもう少し正確に 理解しておく必要がある。この言葉は、『60人のグループを1 00組用意したとき、同 じ誕生日を持つ人たちがいるグループが約99組も存在する』 ということである。一般に 1年は3 6 5 日あるため、感覚としては1 00人く らい集めないと同じ誕生日を持つ人た ちがいないように思われることから、この結果は意外に感じてしまう。ちなみに 『2 3人 のクラスで、同じ誕生日を持つ生徒が2人以上存在する確率は、約5 0パーセントである』 という結果も有名な話である。 フグという魚が内臓に毒を持っていることは良く知られているが、与えるえさによって ある程度まで減らすことができるらしい。話の真偽は別として、このような仮定で進めた 場合、『フグの持つ毒を5パーセントまで減らすことが可能になった』 という内容は、2 通りの意味に解釈することが可能である。つまり、『任意に選び出したフグに含まれる毒 を調べてみたところ、通常のフグの毒の5パーセント分しか含まれていなかった』 という 解釈と、『20匹のフグを任意に選び出して調べたとき、1 9匹のフグは無毒であったが 1匹だけが通常のフグと同じ含有量の毒を持っていた』 という解釈が考えられる。同じ5 パーセントでも、この2種類の解釈には、現実的に大きな相違点が存在する。例えば、『フ グに含まれる毒が5パーセントに減らされた場合に、食用にしても安全である』 ことを仮 定すると、前者の解釈の場合、全てのフグを食用にしても安全であることになる。しかし ながら、後者の解釈の場合では、2 0匹のフグのうち1 9匹は食用にしても安全であるが、 残りの1匹については、以前と同じ危険性が残ることになる。このように、代表値として の確率論的数値の持つ意味を正確に解釈することは、非常に重要であり、同じようなこと が『大都市で排出され光化学スモッグの原因となっている自動車の排気ガスの5パーセン ト削減』 などという話についても適用できることが知られている。 2. 表計算ソフ トを用いた誕生日重複問題への解答 『6 0人のクラスで誕生日の重複が起きない確率』 を\mathrm{P} とおく。このとき 『6 0人のク ラスで同じ誕生日を持つ生徒が2人以上存在する確率』は、 1-\mathrm{P}で与えられる。従って、 正確な\mathrm{P}の値は、例えば表計算ソフ ト等を用いることで、前述の問題の結果を得ることが できる。具体的には、 \mathrm{P} = (1-0/365)*(1-1/365)* (1—59/365) = 0.005893
を求めればよく、これは、一般的な表計算ソフ トを利用すれば容易に出力可能である。以 下の表1.に順次計算した結果を示す。 表1. 表計算ソフトを用いて演算した場合 以上で、『1グループ 2 3人で約5 0パーセント』 であること、さらに 『60人で約9 9 パーセント』 であることが確認することができた。次の章では、表計算ソフトを用いない 計算方法を提示する。 3. 区分求積近似法を用いた誕生日重複問題への解答 前節でも述べた 『誕生日重複問題』 は、『常識では意外に思えるが、真実であるような 事柄に対して、数学的に正当化できる説明を与える確率論』 の立場では、数値シミュレー ション的役割を果たしている。しかし表計算ソフ トによる演算は、あくまで数値実験的傾
向が強く、今回のような場合は、単純な 『確認的役割』 になってしまう。以下では、『\mathrm{P}
の近似値』 を、区分求積法を用いて求めることを考える。最初に、
\mathrm{P} = $\Pi$_{\mathfrak{b}=0}^{59} (1-\mathrm{k}/365)
に対して \log 演算を適用した後、積演算を和演算に置き換え、365で割ることにより、 以下のように刻み幅1/365の区分求積近似計算式が得られる。具体的には、
(1/365)*\log \mathrm{P} = (1/365)
$\Sigma$_{\mathrm{k}=0}^{59}\log(1-\mathrm{k}/365)
\displaystyle \int
[0, 60/365]\log(1-\mathrm{x})\mathrm{d}x=
[(\mathrm{x}-1)\log(1-\mathrm{x}) -- \mathrm{x}]_{[0}
, 60/365] = (-305/365)\log(305/365) — 60/365 という結果が得られることになる。上の式における2番目の等号が、区分求積を定積分に よって近似していることに注意して、 305/365 = 0.835616 \log(305/365) = -0.179590 -305\log(305/365)=54.7736 という結果を代入すると、\mathrm{P}の近似値
=\exp[-60 -- 305 \log(305/365)]
= 0.005373が得られ、この値は、前節で表計算ソフトを用いて計算した値に近いことが確認される。 このような近似計算が可能である理由として、次の2点を挙げることができる。 (1) 1/3 6 5 ずつ減少する階段関数に対して、『非線形関数である対数関数』 を用い た近似を行ったこと。 (2) 刻み幅が 1/3 6 5という小さな値であることに注目して、『階段関数の面積計 算』 を、『階段関数を近似する対数関数の定積分計算』 に帰着させたこと。(通常は 面積を階段関数で近似することが行われる。) 今回の例にもあてはまることだが、一般に不連続的に変化する関数を連続関数で近似す る場合は、線形関数で近似する場合よりも非線形関数で近似する場合の方が有効性が高い。 そのような具体例と して、ファンデル ワールスの方程式と呼ばれる 『気体の状態方程 式』 が存在する。一般に、理想気体では気体の体積と絶対温度とは正比例関係にあるが、 実在気体では、分子間力などの影響を無視できず、高温になるほど、分子運動が激しくな るため、必ずしも正比例や反比例関係にはならないことが知られている。
4. ネットワーク孤立地域発生に関する数学的評価 計算機を用いて実際に数値を計算する場合、通常の数学では考えられないようなことが 起こり得る。例えば、『区分求積分を用いた定積分の近似計算』 においては、『刻み幅を小 さく取れば取るほど近似精度が向上する』 と思われがちだが、そうならない場合があり、 また、『非常に大きな数を用いた計算』 においても、『一の位や十の位などの値が切り捨て られてしまう』 という桁落ち現象が発生するといった場合がある。このような事実は、計 算機を用いた数値計算の世界では、『非常に大きな数値』 や 『非常に小さな数値』 が表れ ないような演算処理を考えなくてはならないということを意味している。ここで順列と組 み合わせに関して、『\mathrm{n}個の中から、重複を認めないで\mathrm{r}個選び出す場合の数』 に対する 『\mathrm{m}個の中から、重複を認めないで\mathrm{r}個選び出す場合の数』の比率を求めることを考えた 場合、具体的には、
mCr/nCr = [\mathrm{m}(\mathrm{m}-1). . (\mathrm{m}-(\mathrm{r}-1))]/[\mathrm{n}(\mathrm{n}-1). . (\mathrm{n}-(\mathrm{r}-1))]
を計算することになる。そこで、 \mathrm{r} \leqq \mathrm{m} \leqq \mathrm{n} と仮定して、 \mathrm{I}(\mathrm{n},\mathrm{m},\mathrm{r}) を次の式で定義す る。
\mathrm{r}-1
\mathrm{I}(\mathrm{n},\mathrm{m},\mathrm{r}) = (1/\mathrm{n}) $\Sigma$
\mathrm{k}0 \log(\mathrm{m}/\mathrm{n}-\mathrm{k}/\mathrm{n})
ここで、先程と同様の区分求積法による近似を用いると、 \mathrm{n} が十分大きいとき、 I(n,m,r)
\displaystyle \int
[0,\mathrm{r}/i\mathrm{J}^{\log}
(\mathrm{m}/n‐x) dxという式が得られる。数学的に厳密に述べるならば、 \mathrm{s} および \mathrm{t} を\mathrm{s}\leqq \mathrm{t} を満たす正定数 として、 \mathrm{S} = \mathrm{r}/\mathrm{n} および \mathrm{t} = \mathrm{m}/\mathrm{n} という関係が成立するという仮定の下で \mathrm{n} を十
分大きい自然数とした場合、
\displaystyle \lim_{\mathrm{n}\rightarrow\infty} \mathrm{I}(\mathrm{n}, nt, ns) =
\displaystyle \int
[0, \mathrm{s}]\log
(t‐x) dx =(S‐t)
\log(\mathrm{t}-\mathrm{s}) +tlogt —
\mathrm{s} が成立することを意味している。従って、(1/\mathrm{n})\log(_{\mathrm{m}}\mathrm{C}\mathrm{r}/\mathrm{n}\mathrm{C}\mathrm{r}) I(n,m,r) — \mathrm{I}(\mathrm{n},\mathrm{n},\mathrm{r}) という関係が得られるので、
hm\mathrm{n}\rightarrow\infty (1/\mathrm{n})\log(_{\mathrm{n}\mathrm{t}\mathrm{C}\mathrm{n}\mathrm{s}}/nCns) =(\mathrm{s}-\mathrm{t})\log(\mathrm{t}-\mathrm{s}) + tlogt — (s—1) \log(1-\mathrm{s})
が導かれる。この式は、例えば 「『 1から9 0までの数字を書いた9 0枚のカードの中か ら10枚を選ぶ場合の数』に対する 『1から10 0までの数字を書いた1 00枚のカード の中から10枚を選ぶ場合の数』 の比率が求まれば、『1から9 0 0までの数字を書いた 9 00枚のカードの中から100枚を選ぶ場合の数』に対する 『1から100 0までの数 字を書いた1 0 0 0枚のカードの中から100枚を選ぶ場合の数』の比率も、近似的に計 算可能である」 ということを示している。 ここで、上式の左辺に関する具体的計算例を以下に示す。表2では、 \mathrm{s}=0.1 および \mathrm{t}= 0.9 とした場合の計算結果をまとめたものである。 \mathrm{n} が大きくなるにつれて、ntCns/ nCns の値が、 \mathrm{S} と \mathrm{t}のみで決定される値に収束することが確認可能である。
表2. 近似解の演算結果
一方、上記の右辺に関する極限値は、
(\mathrm{s}-\mathrm{t})\log(\mathrm{t}-\mathrm{s}) + \mathrm{t}Iog\mathrm{t} — (s—1) \log(1-\mathrm{s}) -0.1113
となるので、数値実験からも、この極限式が成立していることが示された。なお、この方 法は、一般化された組み合わせにも拡張することができる。例えば、「4種類の商品 PI,P2, . \mathrm{Q}\mathrm{I},\mathrm{Q}2, \backslash RI,R2, 、SI,S2, を、それぞれ\mathrm{p}個、 \mathrm{q}個、 \mathrm{r}
個、 \mathrm{s}個選んで組み合わせる場合の数」 は、 [(\mathrm{p}+\mathrm{q}+\mathrm{r}+\mathrm{s})!]/[\mathrm{p}!\mathrm{q}!\mathrm{r}!\mathrm{s}!] 通りであり、 (\mathrm{p}+\mathrm{q}+\mathrm{r}+\mathrm{s})\mathrm{C}(\mathrm{q}+\mathrm{r}+\mathrm{s})\cdot(\mathrm{q}+\mathrm{r}+\mathrm{s})\mathrm{C}(\mathrm{r}+\mathrm{s})
. (r
+s)Cs
=(p
+q
+r
+s)Cp (q
+r
+s)Cq (r
+s)Cr
と一致するため、上式を組み合わせることで、 \mathrm{p}+\mathrm{q}+\mathrm{r}+\mathrm{s}が十分大きい場合の組み合わせ総 数計算にも応用することが可能である。 5. ネットワークの頑健性評価へ簡単な応用 下の図1.は、パソコンとルーターを用いて相互通信するための一例を表している。ル ーターには、他のルーターを接続するための 「ルーター用インターフェイス」 が2個と、 パソコンを接続するための 「パソコン用インターフェイス」 という機材が1個備え付けら れていて、パソコンも、ルーターなどのネットワーク機器と接続するための 「インターフ ェイス」 を1個備えているものとする。当然であるが、ルーターに備え付けられたインタ ーフェイスが故障すると、そのインターフェイスと繋がっている反対側のインターフェイ スを持つルーターやパソコンとは通信ができなくなってしまう。このような状況下では、 『1台のルーターに含まれる2個のルーター用インターフェイスが同時に故障する状況』 は、『そのルーターに接続しているパソコンが自分以外のいずれのパソコンとも通信不可 能となる状況』 を引き起こす。下の図1.では、3台のルーターと3台のパソコンが正3 \mathrm{R} .2 La ptop ‐PT La ptop-1O. 1. 1.2 図1. ルーターとパソコンとの相互接続の例角形のリング状に配置されており、図中の丸印の部分がインターフェイスを表している。 ここで、上述の設定を拡張する形で、リング状に設置された3 6 5台のルーターのそれ ぞれに1台のパソコンが接続されている状況下を考える。このとき 『23個のインターフ ェイスが故障した』 という条件の下で、『1台のルーター内部で、同時に2個の接続イン ターフェイスが故障する条件付確率』 はどのようにして計算できるかという 『インターフ ェイス故障に伴うネソ トワーク接続環境の頑健性問題』 を考えることにする。ちなみに、 『同時に2個のインターフェイスが故障する状況』 というのは、『そのルーターに接続さ れているパソコンが、両サイ ドのパソコンと通信ができなくなってしまう状況』つまり『他 のパソコンと通信不可能になる状況』 を意味しているが、この問題は、先に述べた 『誕生 日重複問題』 に帰着することができる。具体的には、 (1) 3 6 5台のルーター = 1年3 6 5 日 (2) 23個の故障したインターフェイス = 2 3人のグループ (3) 2個のインターフェイスが同時に故障しているルーターの存在 =誕生日が共通している2人の存在 という対応付けにより、リングタイプのネッ トワーク トポロジーにおけるネッ トワーク孤 立地域の発生状況は、誕生日重複問題へ帰着できることがわかる。更に次の図2.では、 冗長経路を想定して、左右方向に大動脈としての2本のルートを有するネッ トワークを考 えているが、楕円形で囲まれた部分の4個のルーターのうち、1台のルーターにおけるイ ンターフェイスが2個同時に故障した場合、別のルーターに、膨大な負荷がかかり、結果 として、データ転送の遅延を引き起こすことが考えられる。 Router4 Router9 図2. ルーター同士の相互接続の例 このような冗長経路を設定したネッ トワークでは、今回の問題は、ネッ トワーク輻較を引 き起こす確率を定量的に評価することに応用できると考えられる。 参考文献 [1] 明石 重男 , 児玉 賢史,桜井 良子,お誕生日重複問題への非線形近似法の応用 , 理大 科学フォーラム,2011(12), 44‐48. [2] 株式会社ソキウス ジャパン編著,徹底攻略 Cisco CCNP ROUTE 教科書,インプレ スジャパン,2012年.
[3] 株式会社ソキウス ジャパン編著,徹底攻略 Cisco CCNP SWITCH 教科書,インプ レスジャパン,2012年.
