Littleの公式で読み解く 生物学的待ち行列

Littleの公式で読み解く
生物学的待ち行列
豊泉 洋
早稲田大学
1
オダギリくんの選択
昇進
独立
転職
http://www.lifecard-choice.com/top.html
2
自己犠牲、利他主義
✦
自分の繁殖機会を逸するようなリスクを背負って、他の個
体を助ける行動。
✦
鳥の警戒音
✦
苦い虫
✦
働きバチ
✦
溺れている人を助ける
✦
なぜ、組織に属して自己犠牲を？
✦
社会性昆虫の研究
✦
アリ、ハチ、シロアリ・・・
3
進化論との矛盾？
✦
社会性昆虫による組織社会の進化は、ダー
ウィンの進化論に矛盾する？
協調
ただ乗り
？
進化論的に有利
4
進化論的説明
どうやって「自己犠牲」遺伝子が広まるか？
✦
群選択(group selection) - 他のグループとの闘争
✦
近親者選択(kin selection) - Fisher 1930, Hamilton 1963
✦
互恵的利他行動 （囚人のジレンマ） - 親切の交換 - Trivers 1971
✦
信号理論 - リスクを引き受けるだけの能力がある- Zahavi 1987
✦
操作理論 - 単に利己的な遺伝子に操作されている - Dawkins 1982
5
別解
✦
集団に属することで、その集団のトップに
なって、自分（自己犠牲遺伝子）が有利に繁
殖できるチャンスがある。
リスクがあるのに、不確定な未
来に投資して、本当に利益があ
るのか？
6
Social Queueを作るハチ
✦
Hairy-Faced Hover Wasp
✦
学名:Liostenogaster flavolineata
✦
マレーシアのスズメ バチの仲間
✦
女王のみが繁殖し、他はヘルパーとなる。
✦
近親者ではないのに、集団に加わる。
✦
厳格な年功序列によるsocial queueを作る
7
Social Queue
女王
dominant
dominantだけが繁殖
helper
dominantになる前に死
亡する可能性あり
新参者
到着順の階級
8
To Join or Not to Join
✦
Social queueに参加すると・・・
利点
dominantになれば、他のhelperの助けを得て、有
利な条件で繁殖できる
欠点
✦
繁殖できないかもしれない
単独で繁殖すると・・・
利点 必ず、繁殖機会が得られる
欠点
helperをあてにできないので、自分の力で巣を運営
しなければならない
9
social queue
Life time
C1
C0
C-3
C-2
helper
C-1
C2
dominant
女王の期間中に、他の個体
数分の利益を得る。
R
0
time
10
独立であるとともに、queue 内の位置にも独立に決まるとす
M/G/∞ queue の系内客数過程となる。
の social queue は厳格な年功序列制度を持つため、queu
る。したがって、N (0) > 0 ならば、C0 はヘルパーとして活
刻 0 に queue にいた個体全てが死滅している場合に、C0
進化上、個体（利己的な遺伝子）の「成功」は繁
ominant になれた場合に、その時点を T 、C0 の死亡時点
殖可能性(fitness)によって測ることができる。
次のように定義する。
!" D
N (t)dt C0 が dominant,
T
R=
0
C0 が non dominant,
Reward = Fitness
nt になってから寿命を全うするまでに、自分の繁殖を手伝
Fitnessは、dominantになっている期間のhelperの数
の地位を確保する前に死亡した場合には、利益は 0 と考え
に依存すると仮定する。
益は次のように表すことができる。
# X
11
オダギリくんの選択
昇進
独立
転職
http://www.lifecard-choice.com/top.html
12
スズメバチの選択
昇進
独立
転職
13
どうやって評価するか？
✦
確率的な分析
✦
Markov過程の理論を使う
-
豊泉、スズメバチの作る待ち行列, 2006年度待ち行列シンポジウム「ユビキタ
スネットワーク社会における情報通信サービスの設計・評価法」
-
www.f.waseda.jp/toyoizumi/research/papers/social_queue.pdf
-
確率的なモデルを作る
-
Markov性を利用して分析する
14
M/M/∞ queue
15
Sample Path
16
どうやって評価するか？
0) = n の条件付きで考える。n ≥ 1 の場合、dominant になるためには、
✦
確率的なモデル
-
X0 ≥ max Xe,i ,
i=1,...,n
到着過程がどうなっているか？
ある。ここで、Y = maxi=1,...,n Xe,i とすると、
0
-
滞在時間の分布は？
dP {Y ≤ x} = nGe (x)n−1 dGe (x),
それぞれに相関は？
とY
- の独立性より
確率論を駆使した、複雑な議論
P {C0 is dominant|N (0−) = n} = P {X0 ≥ Y }
! ∞
=
P {X0 ≥ x}dP {Y ≤ x}
0
! ∞
=n
(1 − G(x))Ge (x)n−1 dGe (x).
0
17
どうやって評価するか？
サンプルパス解析
Littleの公式を使う
18
Littleの公式
✦
系内客数と滞在時間の関係式
✦
PASTAと並び、待ち行列理論でもっともよ
く使われる基本的な性質
✦
どんな待ち行列にも使用可能（到着やサー
ビスに制限なし！）
19
個体数と滞在時間
滞在時間
個体数の変化
time
20
当てはめてみると
time
21
面積の保存
「持ち込まれた滞在時間の全体」＝「系内客数過程の積分値」
W6
W5
W4
W3
W2
N (t)
!
L(t)
!W
Wnn
n=1
n=0
W1
"" t
t
L(s)
00
L(s)ds
L(s)ds
time
L = λW
22
0
"
t
L(s)ds
L = λW
L =：Littleの公式
λW
(2)
0
L = λW
面積の保存より、
"
0
t
L(s)ds
=
"
t
N (t)
!
(3)
W
n
N (t)
!
n=1
L(s)ds =
0
(3)
Wn
十分長い期間を考えれば、
"
(4)
(4)
n=1
1 t"
t
L(s)ds
E[L] = lim
1
t 0 L(s)ds
E[L]t→∞
= lim
t→∞ t 0
N (t)
!
N (t)
N (t)
1
!
N (t) 1
= lim
W
n
=
lim
W
t→∞t→∞t t N N
(t)(t)n=1 n
(5)
(5)
(6) (6)
n=1
= λE[W
= λE[W
] ]
(7) (7)
23
1
E[L] = lim
t→∞ t
"
t
L(s)ds
0
ところでSocial Queueでは？
Life time
C1
C2
C6
C5
C4
helper
C3
N (t) 1
= lim
t→∞
t N (t)
dominant
= λE[W ]
"
t
L(s)ds =
0
R1
R4
R2
0
T
N (t)
!
N (t)
!
W
n=1
Rn
n=1
R5
D
1
time
24
利得の期待値
!
1 t
L(s)ds
E[L] = lim
先ほどと同様に、
t→∞ t 0
!
t
1
E[L] = lim
Nt→∞
(t)t
N (t)
L(s)ds
"
1
= lim
t→∞
NN
(t)(t)1
t
= lim
t→∞
= λE[R]
= λE[R]
0
t
R
" n
(9)
(1
N (t)
n=1 Rn
N (t) n=1
(10)
(11)
(1
前の結果と合わせて、
E[W ] = E[R]
(1
25
N (t) 1
= lim
t→∞
t N (t)
Rn
n=1
= λE[R]
Social
queueの公平性
E[W ] = E[R]
平均的に、自分が働いた分だけ、利得
がある。期待値的には、参加しても、
参加しなくても、利得は同じ。
宝くじが好きなハチは参加？
26
!
分業による効率化
1
E[L] = lim
t→∞ t
t
L(s)ds
0
N (t) 1
= lim
t→∞
t N (t)
= λE[R]
N (t)
"
n=1
組織が大きくなれ
L
ば、女王の利益は
大きくなる
E[W ] = E[R]
H(t)：時刻tでの
女王の利益
H(t) = 2L(t) − 1
27
R
N (t) 1
= lim
t→∞
t N (t)
利益の分配
= λE[R]
N (t)
"
Rn
n=1
トップに位置する女王のみが利益を得る。
E[W ] = E[R]
W6
W5
W4
H(t) = eaL(t) − 1
W3
W2
H(s)
W1
G1
G2
G4
G5
!
0
t
H(s)ds =
N (t)
"
Gn
n=1
time
28
H(t) = eaL(t) − 1
(13)
H = λG
!
t
H(s)ds =
0
✦
N (t)
"
Gn
(14)
n=1
先ほどと同様な議論より、
1
E[H] = lim
t→∞ t
!
t
H(s)ds
0
N (t)
N (t) 1 "
= lim
Gn
t→∞
t N (t) n=1
= λE[G]
(15)
(16)
(17)
29
t→∞
=
t
N0(t)
N (t)
n=1
"
N (t) 1
= lim
λE[G]t→∞ t N (t)
選択
= λE[G]
Gn
n=1
集団を組んだことにより、より大きな利益
が得られ、
E[H] E[H]
≥ E[L]
≥ E[L]
の時には、
E[H]
E[L]
E[G] =
≥
= E[W ]
λ
λ
したがって、social queueに参加した方が得
になる！
2
30
E[H]
E[L]
E[H]
E[L]
簡単な例:M/M/∞
E[W
]
=
E[R]
E[G]==
≥
=
E[G]
≥
=E[W
E[W] ]
λλ
λλ
集団サイズに対して指数関数的に利得が増加
する。
L(t)
H(t)
=
2
L(t) − 1
L(t)
H(t) =
= 22 −−11
λ/µ
E[H(t)] = e λ/µ − 1
−1
E[H(t)] = e
! t
N (t)
"
個人が得る利得の期待値は？
λ/µ
H(s)ds e=
−G
1n
0 E[G] = eλ/µ
n=1
−1
λ
E[G] =
λ
! t
1 2
H(s)ds
E[H] = lim
t→∞ t
31
本当にいつでも得なのか？
✦
eλ/µ − 1
E[G] =
λ
(2
女王になれるのは、ほんの一握り。
eλ/µ − 1
E[G] =
λ−λ/µ
µ
1
P {top} =
λ
(1 − e
)≈
E[L(t)]
eλ/µ − 1
E[Gtop ] =
eλ/µ−λ/µ
−1
)
E[Gtop ]µ(1
= − e −λ/µ
µ(1 − e
)
(2
(2
32
本当にいつでも得なのか？
✦
eλ/µ − 1
E[G] =
λ
(2
社長になれるのは、ほんの一握り。
eλ/µ − 1
E[G] =
λ−λ/µ
µ
1
P {top} =
λ
(1 − e
)≈
E[L(t)]
eλ/µ − 1
E[Gtop ] =
eλ/µ−λ/µ
−1
)
E[Gtop ]µ(1
= − e −λ/µ
µ(1 − e
)
(2
(2
33