初めまして。今日も元気に数式と本をフォローしているHIROYUKIです。ALHではエンジニアをしています。スタバの紙ナプキンは書き味がよくてお気に入りです。

　さて、先月翻訳が出たクリストファー・G・ブリントンとムン・チャンの『パワー・オブ・ネットワーク』という本を読んでいたら、Wi-Fiについて解説している第2章で「ALOHAプロトコル」というのが取り上げられていました。ALHで「ALOHA」といえば、5つの「キョウソウ」のスタイルの頭文字をつなげたものを指します。

（5つの「キョウソウ」の図。英語のフレーズの頭文字を数字の順につなげると「ALOHA」になります。）

　そんなわけで、「こんなところにもALOHAが！」と思いつつ、そのプロトコルの背景にある確率の計算方法に興味が湧き、ちょっと式を立てて計算してみました。

（紙ナプキンで計算をしていたスタバから出た後、青山をブラブラしていたら見つけた中華そばのお店に置いてあっただるま。ALOHAとは縁もゆかりもない確率が最大ですね。）

ルーターのデータ送信問題の設定（レベル：高校数学）

　あるルーターR1が別の端末にデータを送ろうとしているとき、他のルーター（R2, R3, … , Rn）はデータ送信を控えれば、R1は他のルーターのデータ送信と衝突せずにデータを送信することができます。では、ある時点（タイムスロット）で n 台のルーターがみんな同じ確率 p でデータ送信を試すとしたら、p をどういう値にすればR1のデータ送信がうまくいく確率を最大にできるでしょうか。

　R1はデータを送信するので確率は p 、それ以外の n - 1 台のルーターはデータを送信しないので確率は (1 -p)^(n - 1) なので、R1のデータがうまく送信される確率 f(p) は f(p) = p(1 - p)^n と表せます。この f(p) が最大になるようにするにはどんな p を設定すればいいかというのが問題です。

　さて、ここで高校の数学で学んだ微分の登場です。ある関数 f(x) の最大値を求めたいときに、その関数を一回微分した f '(x) を計算して、f '(x) = 0 になるときの x を求め、それをもとに関数のグラフの増減表を作って最大値を求めるという手順でした。

（Wi-Fiルーターが3台の場合の計算。スループットも求めました。右上に懐かしの増減表が...）

　今回の場合、関数 f(p) の一階微分 f '(p) が0になるときの p を計算してもとの f(p) に代入すれば、ルーターR1の通信がうまくいく確率の最大値を求められます。pはデータを送信する確率だったので、0でも1でもダメで、その間の値をとる必要があるので、0 < p < 1とすれば、最適化問題の標準的な書き方に従って次のように定式化できます。

max f(p) = p(1 - p)^(n - 1)
s.t. 0< p < 1, n ∈ N (N：自然数)

ルーター5台なら？

（プーさんがのしかかるWi-Fiルーター。微分ともALOHAとも、そしてだるまとも関係ない確率がさいだ…）

　さてルーターの台数を5台(n = 5)と仮定すると
f(p) = p(1 - p)^4
= p(1 - 4p + 6p^2 - 4p^3 + p^4)
= p^5 - 4p^4 + 6p^3 - 4p^2 + p
一階微分は
f '(p) = 5p^4 - 16p^3 + 18p^2 - 8p + 1
f '(p) = 0 とすると
f '(1) = 5 - 16 + 18 - 8 + 1 = 0 なので
f '(p) = (p - 1)(5p^3 -11p^2 + 7p - 1)
= (p - 1)(p - 1)(5p^2 - 6p + 1)
= (p - 1)(p - 1)(p - 1)(5p - 1)
= (5p - 1)(p - 1)^3

となります。ここでふと思ったんですが、一階微分した式の中にも (1 - p) の累乗があって、もとの f(p) より次数が一つ小さくなっています。n = 3 や n = 8 の場合も計算していたんですが、同じような結果でした。そこでふと思いました。

「あれ、これってもしかして公式が作れるのでは？」

公式を作ってみる

　ということで計算してみました。f(p) = p(1 - p)^n のとき、その一階微分は

f '(p) = (1 - np)(1 - p)^(n - 1)

で表せるだろうという予想です。実際に証明してみます。

証明）
f(p) = p(1 - p)^(n - 1) のとき積の微分の公式を使って
f' (p) = 1*(1 - p)^(n -1) + p(n -1)*(-1)*(1 - p)^(n -2)
= (1 - p - np + p)(1 - p)^(n -2)
=(1 - np)(1 - p)^(n -2)
0 < p < 1 のとき、f '(p) = 0 を満たす p は常に p = 1/n となる。またこのとき f(p) の最大値は
f(1/n) = (1/n){1 - (1/n)}^(n -1)
= (1/n){(n - 1)/n}^(n -1)
= {(n -1)^(n -1)}/n^n　　　Q.E.D

　プログラムに計算をさせたい場合、そのプロセスを単純化することができれば計算量が減り、それに応じて必要なメモリや処理のミスを減らすことができます。

　今回の場合、公式を証明したことによって、最大値をとるときの p の値も最大値も、ルーターの台数 n さえわかればすぐに計算できることになります。

　たとえば n が4なら、最大値をとるときのp は 1/4、最大値は 3^3/4^4 = 27/256 = 0.10546875 ≒ 11%、n が8なら p は 1/8、最大値は 7^7/8^8 = 823543/16777216 = 0.049086... ≒ 5%です。 最適化問題を解く場合、普通なら上の計算例のようにもとの関数の一階微分を求めてその因数分解をしなければならなかったりするんですが、いちいちそんなことをしなくても済むわけです。

どこで何が役立つか〜経済学の場合〜

　僕は大学で経済学を専攻していましたが、エンジニアになってアルゴリズムの背後にある数式を見る機会が増え、よく思うことがあります。それは経済学もコンピュータ科学も、「限られたリソースをどう効率的に使うか」ということをテーマにしているので、それを数理的に扱おうとすると同じようなアプローチをとることになる場合が少なくないということです。

　上の最適化問題など、経済学ではしょっちゅう出てきます。

コストの最小化（min C = wL + rK s.t. y = f(L, K) ）、

利潤の最大化（max π = TR - TC）、

あるいは個人の効用の最大化（max u(x1, x2) = (x1^α) * (x2^β) s.t. p1x1 + p2x2 = I ）…。

こういうときに高校、大学で数学の勉強をがんばっておいてよかったと思います。

　「文系からでもプログラマーになれるのだろうか…」と不安に思う人も少なくないみたいですが、僕の場合は大学で学んだことが思わぬところで役に立っています。そして、こういうちょっとした発見が社内でシェアされ、文系理系職歴問わず、様々なバックグラウンドを持つ社内の人たちとの間でやりとりが生まれていきます。ALOHAのA、All for One（協奏）が生まれる瞬間です。

　ここ数年、人工知能の分野ではディープラーニング（深層学習）が流行っていますが、ディープラーニングを成り立たせているのは交差エントロピーやReLU、誤差逆伝播(back propagation)などのいくつかの数式です。こういう数式は「専門的」としてあまり表に出てはきませんが、今回のALOHAプロトコルの単純系の計算のように、丁寧に中身を見ていくと、より簡単に答えを計算できるやり方があるかもしれません。「それって本当に一番効率のいいやり方なの？」とブラックボックスの中身をあえてのぞいてみるのも面白いものですね。