132

c オペレーションズ・リサーチ
Newton の不等式を用いたオッズ問題の解析
松井知己，穴太克則
本稿では，オッズ問題とその変種に対し，その最適戦略と勝利確率の下界について議論する．特に，いく
つかの変種を特殊ケースとして含む一般的な問題が， Newton の不等式を用いることによって統一的に議論
できることを示す．
キーワード：古典的秘書問題，オッズ問題，Newton の不等式
文タイトルになっている！）．
1. はじめに
オッズ問題において，成功確率を pi = 1/i と定めた
確率変数の列 X1 , X2 , . . . XN を，独立なベルヌイ
問題は，古典的秘書問題と本質的に等価であることが
試行の列とする．各確率変数は成功または失敗のどち
知られている．Bruss [2] では，r1 + r2 + · · · + rN ≥ 1
らかの値をとるものとする．本稿では，確率変数 Xi
ならば，最適停止規則を用いたときの勝利確率は必ず
の値が成功のときは Xi = 1 と表し，失敗のときは
1/e 以上であることが示された．古典的秘書問題にお
Xi = 0 と表す．以下では，確率変数 Xi の成功確率
いて人数 (N ) が大きくなると，最適停止規則を用いた
を pi = Pr[Xi = 1] と表し，議論の簡略化のために
際の勝利確率は 1/e に収束することが知られており，
[∀i, 0 < pi < 1] が成り立つと仮定する．さらに失敗確
上記の下界を（漸近的に）達成している．
率 qi = Pr[Xi = 0] とオッズ ri = pi /qi を定義する．
2. 問題
すべての成功確率 (p1 , p2 , . . . , pN ) が与えられたと
オッズ問題については，様々な変種が研究されてい
して，以下のような（プレイヤが一人の）ゲームにつ
いて考えよう．確率変数の実現値は X1 , X2 , . . . の順に
る．Tamaki [3] は，与えられた正整数に対し，選択
逐次得られるとし，プレイヤは各確率変数の観測直後
回数は（高々）1 回とし，最後から番目までの（個
にそれを『選択する』か『選択しない』のどちらかを
の）成功のうちどれかに対応する確率変数を選択した
選ばねばならない1 ．Bruss の提唱したオッズ問題では，
ならば勝利すると定義した問題について議論している．
選択回数は（高々）1 回とし，最後の成功に対応する
Bruss and Paindavein [4] は，与えられた正整数に
確率変数を選択したならば，プレイヤは勝利したと定
対し，選択回数は（高々）回とし，最後の成功，最後
義する．オッズ問題の目的は，プレイヤの勝利確率を
から 2 番目の成功，. . . ，最後から番目までの成功，
最大化する方法，最適停止規則と呼ぶ，を求めること
これらすべてに対応する確率変数を選択したならば勝
である．
利すると定義した問題について議論した．この問題は，
Bruss は [1] において，最適停止規則が閾値戦略
選択回数を（高々）1 回とし，最後からちょうど番
で得られることを示した．閾値戦略とは，特定のイ
目の成功に対応する確率変数を選択したならば，勝利
ンデックス i∗ に対し『Xi∗ 以降の確率変数で最初
したと定義する問題と等価である．
に 1 の値を取るものを選択する』というものである．
本稿で議論するのは，オッズ問題に対する次のよ
Bruss [1] は，閾値を i = min{i ∈ {1, 2, . . . , N } |
うな変種である．正整数と k が与えられ，これは
ri + ri+1 + · · · + rN < 1} と定めた閾値戦略が最適停
1 ≤ k ≤ < N を満たすとする．本稿で扱う問題は，
∗
止規則となることを示した（この主定理がそのまま論
『最
オッズ問題において，選択回数は（高々）1 回とし，
後から k 番目の成功，最後から k + 1 番目の成功，. . . ，
まついともみ
東京工業大学大学院社会理工学研究科社会工学専攻
〒 152–8550 東京都目黒区大岡山 2–12–1
あのうかつのり
芝浦工業大学システム理工学部数理科学科
〒 337–8570 埼玉県さいたま市見沼区大字深作 307
c by
132（10）Copyright （ − k + 1 個の成功）のう
最後から番目までの成功』
1
本来は『停止する』と『停止しない』であるが，本稿で
は一般化した問題も同様に扱うために，選択という単語を
用いる．
ORSJ. Unauthorized reproduction of this article is prohibited.
オペレーションズ・リサーチ
ち，どれかに対応する確率変数を選択したならば勝利
トル r ∈ RN
+ と，任意の整数 1 < ∀m < N において，
すると定義した問題である．上記の問題は，設定が人工
Sm (r)2 ≥ Sm−1 (r)Sm+1 (r), が成り立つ．
的で不自然に感じられるかもしれないが，k = = 1 と
Newton の不等式より直ちに以下が得られる．
すれば Bruss [1]，k = 1 とすれば Tamaki [3]，k = とすれば Bruss and Paindavein [4] の研究した問題に
任意の正ベクトル r = (
r1 , r2 , . . . , rN ) > 0
補題 1.
対応しており，これら 3 つの問題を特殊ケースとして
と，1 ≤ m ≤ ≤ N を満たす正整数の対 (m, ) に対
含む一般的な問題である．
し，
あるいは上記の問題は，選択回数を（高々） k 回と
e−1 (
r)
r)
e (
が成り立つ．
≥
em−1 (
r)
em (
r)
したとき，選択した確率変数すべてが，最後の成功，最
略証.
後から 2 番目の成功，. . . ，最後から番目までの成功，
(1/2)(log(Sm −1 ) + log(Sm +1 )) が得られ，これより
の中に含まれているとき勝利とした問題と本質的に等
直ちに以下が導かれる：
価である．例えば N = 8，k = 3， = 4 の場合を
考えてみよう．確率変数列 (X1 , X2 , . . . , X8 ) の実現値
が (0, 1, 1, 0, 0, 1, 1, 1) であったとき，プレイヤは集合
{X3 , X6 , X7 , X8 } の中から 3 つを選択すれば勝利する
ことができる．プレイヤが勝利したならばプレイヤが
最初に選択したのは {X3 , X6 } のどちらかである．ま
た，プレイヤの最初の選択が {X3 , X6 } のどちらかで
あれば，それ以降の確率変数で実現値が成功であるも
のを，3 つまで連続して選択すればよい．この戦略を
Newton の不等式より中点対数凹性 log(Sm ) ≥
log(Sm ) + log(S−1 )
log(Sm−1 ) + log(S )
≥
,
2
2
Sm S−1 ≥ Sm−1 S ,
N
r)
e−1 (
m−1
N
−1
r)
em−1 (
r)
e−1 (
≥
em−1 (
r)
用いた際は，プレイヤが勝利したときに選択していた
補題 2.
N
m
S−1
S
=
≥
= Sm−1
Sm
N
N −m+1
N −+1
m
r)
e (
,
r)
em (
r)
r)
e (
e (
≥
.■
em (
r)
em (
r)
任意の正ベクトル r = (
r1 , r2 , . . . , rN ) > 0
確率変数の集合は {X3 , X6 , X7 } または {X6 , X7 , X8 }
と，0 ≤ m ≤ ≤ N を満たす正整数の対 (m, )
のどちらかとなる．ゆえに，この問題においてプレイヤ
に対し，
が勝利することのできる必要十分条件は，プレイヤの
r−1
最初の選択が {X3 , X6 } のどちらかとなることである．
3. Newton の不等式
正整数 m, N は 1 ≤ m ≤ N を満たすとしたとき，
任意の N -次元ベクトル r = (r1 , r2 , . . . , rN ) ∈ RN に
対して，m 次基本対称多項式（関数）em (r) を
em (r) =
B ⊆ {1, 2, . . . , N }
(1)
e (
r)
r−1 ) + e (
r−1 )
r −1 )
r1 e−1 (
e (
=
≥
.■
em (
r) r1 em−1 (
r−1 ) + em (
r−1 )
em (
r−1 )
て議論する．
i∈B
4. 最適停止戦略
と
定義する．上記の定義において，関数の項数は
m
補題 1 を正ベクトル r−1 に適用すると
e−1 (
r−1 )
r−1 )
e (
が得られ，以下が導かれる：
≥
em−1 (
r−1 )
em (
r−1 )
略証.
上記の補題を用いて，次節では最適停止戦略につい
ri ,
and |B| = m
N
e (
r)
r−1 )
e (
が成り立つ．ただし
≥
em (
r)
em (
r−1 )
= (
r2 , . . . , rN ) と定義する．
個となっていることに注意されたい．特に
e0 (r) = 1 と定める．次に m 次基本対称平均を
em (r)
(∀m ∈ {1, 2, . . . , N })
Sm (r) = N
m
本節では，オッズの部分ベクトル (ri , ri+1 , . . . , rN )
を r [i] と記し，確率 Pr[k ≤ Xi + · · · + XN ≤ ] を
P[i] と記す，このとき明らかに
em (r[i] )
P[i] = qi qi+1 · · · qN
em (r[i] ) = m=k
N
(1 + rj )
j=i
m=k
が成り立っている．ここで，添え字 i∗ を
と定義する．さらに S0 (r) = 1 とする．混乱の恐れが
ないときは Sm (r) を Sm と略記する．Newton は以下
e (r[i+1] )
def.
i∗ = min i 1 ≤ i ≤ N − , 1 >
(2)
ek−1 (r [i+1] )
の不等式を示した．
と定義し，閾値と呼ぶ．ただし，上記の min が空集合
定理 1. (Newton’s inequalities [5]) 任意の非負ベク
2015 年 3 月号
def.
に対するものであった際は i∗ = N − + 1 とする．
c by ORSJ. Unauthorized reproduction of this article is prohibited. （11）133
Copyright 表 1 既存の結果および，本稿で示す結果
モデル
条件
Bruss [1]
=k=1
B&P(†) [4]
=k≥1
Tamaki [3]
≥k=1
本稿
≥k≥1
下界
閾値の定義式 ()
ri +ri+1 +···+rN
e−1
[2]
(!)e
m
1
(!) exp −(!) m!
m=1
[7]
[6]
（‡ を参照）
[7]
1
[1]
e1 (r ) < 1
= e
0 (r )
e (r)
<1
e−1 (r)
[4]
e (r)
<1
e0 (r)
e (r)
<1
ek−1 (r)
[3]
[7]
† Bruss and Paindaveine.
1 m −k+1
−k+1
!
!
1
‡ exp −
.
m=k
m!
(k − 1)!
(k − 1)!
最適戦略は，閾値の定義式を満たす最小の i を用いた閾値戦略で得られる，ただしここで r =
(ri , ri+1 , . . . , rN ) である．
確率変数を選択する戦略は，最適停止戦略である．ま
このとき，以下の性質が成り立つ．
補題 3.
P[1] ≤ P[2] ≤ · · · ≤ P[i∗ −1] ≤ P[i∗ ] >
P[i∗ +1] > · · · > P[N −+1] .
この定理の証明は，紙面の都合で省略する．
略証．閾値 i∗ の定義と補題 2 より
5. 勝利確率の下界
e (r )
e (r )
e (r )
≥
≥ ··· ≥
≥1
ek−1 (r [1] )
ek−1 (r[2] )
ek−1 (r[i∗ ] )
[1]
かつ 1 >
たこのときの勝利確率は P[i∗ ] である．
[i∗ ]
[2]
e (r[N −+1] )
e (r[i∗ +1] )
≥
·
·
·
≥
.
ek−1 (r[i∗ +1] )
ek−1 (r[N −+1] )
本節では，定理 2 で得られた最適停止規則を用いた
際の勝利確率の下界について議論する．
Newton の不等式より，以下の補題が導かれる．
任意の正ベクトル r = (
r1 , r2 , . . . , rN ) > 0
補題 4.
が直ちに得られ，
ek−1 (r[i+1] ) − e (r[i+1] )
に対し，以下が成り立つ：
≤ 0 (0 ≤ ∀i ≤ i∗ − 1),
> 0 (i∗ ≤ ∀i ≤ N − ).
が導かれる．これより，∀i ∈ {1, 2, . . . , N − } にお
いて
Sk−1 (
r )−m ≥ Sm (
r)−k+1 S (
r)k−1−m ,
∀m ∈ {0, 1, 2, . . . , k − 1},
Sm (
r)
−k+1
≥ Sk−1 (
r)
−m
S (
r)
m−k+1
,
∀m ∈ {k, k + 1, . . . , },
P[i] − P[i+1] =
S (
r)
em (r[i] )
− P[i+1]
(1 + ri ) · · · (1 + rN )
ri ek−1 (r [i+1] ) − e (r[i+1] )
=
m=k
Sm (
r)
−k+1
(4)
,
略証. 数列 (log(S0 ), . . . , log(SN )) の凹性が Newton
の不等式より導かれ，これより
≤ 0 (0 ≤ i ≤ i∗ − 1),
log(Sk−1 ) ≥
> 0 (i∗ ≤ i ≤ N − ),
■
確率の列 (P[1] , P[2] , . . . , P[N −+1] ) の単峰性が上記
log(Sm ) ≥
の補題で示されたが，これより，閾値 i∗ を用いた閾値
戦略が最適停止戦略となることは，直観的に理解でき
るだろう．
定理 2. 閾値 i∗ に対し，Xi∗ 以降で最初に成功となる
c by
134（12）Copyright ≥ Sk−1 (
r)
m−
∀m ∈ { + 1, + 2, . . . , N }. (5)
(1 + ri ) · · · (1 + rN )
が成り立つ．
m−k+1
(3)
log(S ) ≥
( − k + 1) log(Sm ) + (k − 1 − m) log(S )
,
−m
∀m ∈ {0, 1, . . . , k − 1},
( − m) log(Sk−1 ) + (m − k + 1) log(S )
,
−k+1
∀m ∈ {k, k + 1, . . . , },
(m − ) log(Sk−1 ) + ( − k + 1) log(Sm )
,
m−k+1
∀m ∈ { + 1, + 2, . . . , N },
が得られ，直ちに不等式 (3)，(4) と (5) が導かれる．■
ORSJ. Unauthorized reproduction of this article is prohibited.
オペレーションズ・リサーチ
定理 3. 確率変数列 X1 , X2 , . . . , XN 上に定義された
と定義する．これは変数 {r2 , r3 , . . . , rN
} を固定して
オッズ問題において，選択回数が（高々）1 回であり，
得られる関数である．解 r の仮定と性質 (8) より
選択された変数が最後から m 番目の成功としたとき，
f (r1 )=ek−1 (r ) − e (r ) < 0
m が k ≤ m ≤ を満たすならば勝利とする．さらに
e (r¯ )
(1) ri > 0 (∀i), (2) 1 ≤ k ≤ < N , (3) 1 > e (r¯ )
k−1
¯ = (rN −+1, rN −+2 , . . . , rN ) ∈ R かつ
ただし r
e (r )
(4) e (r ) ≥ 1 が成り立つと仮定する．このとき，
k−1
いて [∃r ∈ (0, r1 ), f (r ) = 0] が得られる．このとき
最適停止規則を用いた際の勝利確率は
) は問題 P1 の許容解であ
明らかに (r , r2 , r3 , . . . , rN
m=k
N
θ
m
(1 + θ)
⎛
m
⎞
1
−k+1
が成り立ち，関数 f (r) の連続性と中間値の定理を用
る．解 r に対応する目的関数値 VN の値は
em (r −1 ) + r1 em−1 (r −1 )
⎜ k−1 ⎟
⎟
θ=⎜
⎝ N ⎠
ただし
N
N
<ek−1 (r −1 ) − e (r −1 ) = f (0)
VN =
m=k
(1 + r1 )(1 + r2 ) · · · (1 + rN
)
以上である．
略証.
(−1)
最適停止規則として (2) で定義された閾値を
用いた閾値戦略を採用するならば，確率変数の部分列
X1 , X2 , . . . , Xi∗ −1 を元の問題から消去しても，勝利
確率は変わらない．すなわち
ek−1 (r1 , r2 , . . . , rN ) − e (r1 , r2 , . . . , rN ) ≤ 0 (7)
が成り立つ場合のみ議論すればよい．仮定 (6) と (7)，
の下では，閾値 i∗ = 1 とした閾値戦略が最適停止戦略
であり，その際の勝利確率は
s. t. 0 < ri
ば，より小さな目的関数値を持つ解 r が存在して
ek−1 (r ) − e (r ) = 0 を満たす．
ベクトル r ∗ を問題 P1 の許容解で ek−1 (r ∗ ) −
def.
em (r)
(1 + r1 )(1 + r2 ) · · · (1 + rN )
(∀i ∈ {1, 2, . . . , N }),
m=k
Sk−1
1
−k+1
k−1
S
def.
および θ =
S
Sk−1
1
−k+1
N
e ( r ∗ )
⎜ k−1
θ=⎜
⎝ N
ek−1 (r ∗ )
1
⎞ −k+1
⎟
⎟
⎠
⎛
N
⎞
ek−1 (r−1 ) − e (r−1 ) > 0,
(8)
が成り立つ．
(9)
(i) 不等式 (3) より，∀m ∈ {0, 1, 2, . . . , k − 1},
の最適値である，ただし上記において r −1 = (r2 ,
∗
em (r )=
約式 (9) を等式で満たすものが存在することを示す．
問題 P1 の許容解 r は，ek−1 (r ) − e (r ) < 0 を満
=
で満たす許容解で，目的関数値がさらに小さなものが
=
1
あることを示そう．一変数関数 f (r) : [0, r ] → R を
N
m
N
m
Sm ≤
m
たしていると仮定する．このとき，制約式 (9) を等式
N
1
−k+1
⎜ k−1 ⎟
⎟
=⎜
⎝ N ⎠
ek−1 (r) − e (r) ≤ 0,
r3 , . . . , rN ) とする．上記の問題の最適解として，制
k−1
k−1
S
S
N
m
Sm
· m
Sk−1
−m
Sk−1
Sk−1−m
1
−k+1
1
−k+1
α θm
導入し
が成り立つ．
f (r) = ek−1 (r, r2 , r3 , . . . , rN
) − e (r, r2 , r3 , . . . , rN
)
2015 年 3 月号
と
定義する．このとき等式 ek−1 (r ∗ ) − e (r ∗ ) = 0 より，
⎛
def.
許容解 r が ek−1 (r ) − e (r ) < 0 を満たすなら
α =
率の下限は，以下の最適化問題
min. VN =
数値は r の目的関数値より小さい．ゆえに，P1 の
の下界または上界について議論する．簡単のために
em (r)
(1 + r1 )(1 + r2 ) · · · (1 + rN )
m=k
となる．ゆえに，最適停止戦略を用いたときの勝利確
P1
となる．性質 (8) ek−1 (r −1 ) − e (r −1 ) > 0 と
e (r∗ ) = 0 を満たすものとする．以下では em (r∗ )
def.
(1 + r2 ) · · · (1 + rN
)
r ∈ (0, r1 ) より，解 (r , r2 , r3 , . . . , rN
) の目的関
ek−1 (r2 , r3 , . . . , rN ) − e (r2 , r3 , . . . , rN ) > 0 (6)
VN =
=
ek−1 (r −1 ) − e (r −1 ) +
em−1 (r −1 )
1 + r1
m=k
(ii) 不等式 (4) より，∀m ∈ {k, k + 1, . . . , },
c by ORSJ. Unauthorized reproduction of this article is prohibited. （13）135
Copyright em (r∗ )=
Sm ≥
N
m
=
=
N
m
N
m
Sk−1
Sm
· m
k−1
Sk−1
S
−m m−k+1 1
−k+1
Sk−1 S
略証.
明らかに，不等式
1
−k+1
m=k
m
θm
m
(1 + θ)N
= exp −
α θm
N
N
(iii) 不等式 (5) より，∀m ∈ { + 1, + 2, . . . , N },
N
m
N
=
m
N
=
m
Sm ≤
S
S
k−1
k−1
N
m
·
α θm
m
m
k−1
S
S
Sm−k+1
m−
Sk−1
1
−k+1
N
θm
m
m=k
∗
N
N
∗
e (r∗ )
(1 + r1∗ )(1 + r2∗ ) · · · (1 + rN
1
)
m=0 m
=
=
∗
∗
VN
e (r )
e (r∗ )
m=k m
m=k m
k−1
N
e (r∗ )
em (r∗ )
e (r∗ )
m=+1 m
m=k m
= m=0
+
+
e (r∗ )
e (r∗ )
em (r∗ )
m=k m
m=k m
m=k N
k−1
N
N
α θm
α θm
m=0
m=+1
m
m
+ 1+
≤
N
N
m
α
θ
α θm
m=k
m=k
m
m
N
α N
θm
m=0
m
(1 + θ)N
=
=
N
N
α m=k
θm
θm
m=k
≥
m=k
N
m
m
θm
(1 + θ)N
θm =
N
m
⎞
N
m
−k+1
⎜ k−1 ⎟
⎜ ⎟
⎝
⎠
N
m
−k+1
N!
!(N − )!
(N − m)!m! (k − 1)!(N − k + 1)!
m
−k+1
1− N0 · · · 1− m−1
!
1
N
=
m
m! (k − 1)!
1− k−1 · · · 1− −1 −k+1
以下を満たすことが示される．
N
⎛
上記を用いると，解 r に対応する目的関数値 V が
すなわち V
m=k
1
θm
m
θ
N
N
=
∗
m
m
1
−k+1
が成り立つ．
∗
N
が成り立つ．これより ∀m ∈ {0, 1, . . . , N } において，
が成り立つ．
em (r∗ )=
≥ e−N θ
1
→
m!
!
(k − 1)!
m
−k+1
N
,
N
as N → ∞
が成り立つ．上記より
m=k
N
θm
m
lim
(1 + θ)N
N
≥ lim exp −
θ
N →∞
N →∞
⎛
= exp⎝−
1
!
(k − 1)!
1
⎞
⎠
m=k
N
θm
m
m=k
1
m!
!
(k − 1)!
m が得られる，ただし = − k + 1 である．
■
6. おわりに
本稿では，オッズ問題（の変種）について扱った．本
である．
稿で扱った問題は Bruss の問題 [1]，Bruss and Pain-
上記の値が問題 P1 の最適値となっていることは，解
daveine の問題 [4] さらに Tamaki の問題 [3] を特殊
r1 = r2 = · · · = rN = θ が P1 の許容解であり，上記
ケースとして含む一般的な問題である．本稿で得られ
の値を達成することで示される（詳細略）．
た勝利確率の下界は，それぞれのケースにおける以下
■
最後に N → ∞ として得られる漸近的な下界を示す．
系 1.
定理 3 の仮定の下では，
の結果に対応している：
(1) e−1（ = k = 1 の場合）．これは古典的秘書問題
の下界と一致している．この結果は [2] において
1 −k+1
!
exp −
(k − 1)!
m −k+1
1
!
×
m!
(k
−
1)!
m=k
は勝利確率の下界となる．
c by
136（14）Copyright 既に得られている．
(2)
（ = k ≥ 1 の場合）．これは Bruss and
(!)e
Paindaveine の問題 [4] において，成功確率を古
典的秘書問題の設定とした際の勝利確率と一致し
ている．
ORSJ. Unauthorized reproduction of this article is prohibited.
オペレーションズ・リサーチ
m
(!) (3) exp −(!)
（ ≥ k = 1 の場合）．
m!
m=1
これは Tamaki の問題 [3] において，成功確率を
1
古典的秘書問題の設定とした際の勝利確率と一致
している．この結果は [6] ですでに得られている．
本稿では紙面の都合で多くの証明を概略のみに留め
ている．詳細について興味を持っていただけた際は [7]
をご覧いただければ幸いである．
が得られる．最後の不等式は，{1/r1 , 1/r2 , . . . , 1/rN }
の分散の非負性から導かれる．
■
次に一般の場合について，それが上記のケースに帰
着されることを示す．
補題 6. 任意の N 次元ベクトル r = (r1 , r2 , . . . , rN )
に対し，(N − 1) 次元ベクトル s = (s1 , s2 , . . . , sN −1 )
が存在して，S1 (r) = S1 (s), S2 (r) = S2 (s), . . . ,
SN −1 (r) = SN −1 (s) が成り立つ．
参考文献
略証.
[1] F. T. Bruss, “Sum the odds to one and stop,” Annals
of Probability, 28, 1384–1391, 2000.
[2] F. T. Bruss, “A note on bounds for the odds theorem of optimal stopping,” Annals of Probability, 31,
1859–1861, 2003.
[3] M. Tamaki, “Sum the multiplicative odds to one
and stop,” Journal of Applied Probability, 47, 761–
777, 2010.
[4] F. T. Bruss and D. Paindaveine, “Selecting a sequence of last successes in independent trials,” Journal
of Applied Probability, 37, 389–399, 2000.
[5] I. Newton, Arithmetica universalis: Sive de compositione et resolutione arithmetica liber, Tooke, 1707.
[6] T. Matsui and K. Ano, “A note on a lower bound for
the multiplicative odds theorem of optimal stopping,”
Journal of Applied Probability, 51, 885–889, 2014.
[7] T. Matsui and K. Ano, “Compare the ratio of symmetric polynomials of odds to one and stop,” Discussion Paper, 2014-05, Department of Social Engineering, Tokyo Institute of Technology, 2014.
変数 x を持つ一変数多項式
g(x) = (x + r1 )(x + r2 ) · · · (x + rN )
を導入する．明らかに
g(x) = e0 (r)xN + e1 (r)xN −1
+ · · · + eN −1 (r)x + eN (r)x0
が成り立ち，その導関数は
g (x) = N e0 (r)xN −1 + (N − 1)e1 (r)xN −2
+ · · · + eN −1 (r)
となる．N 次多項式 g(x) が N 個の実根を持つことよ
り，導関数 g (x) は重根度を含めて N − 1 個の実根を
持つので，これを以下では (−s1 , −s2 , . . . , −sN −1 ) と
書く．すると明らかに
g (x)=N (x + s1 )(x + s2 ) · · · (x + sN −1 )
=N e0 (s)xN −1 + N e1 (s)xN −2
補遺
+ · · · + N eN −1 (s)
以下では r の要素がすべて正の場合について，New-
が成り立つ．ゆえに，g (x) の各項を比べると
ton の不等式の証明の概略を記す．最初に特別な場合
(N − k)ek (r) = N ek (s) (0 ≤ ∀k ≤ N − 1)
について示そう．
補題 5.
任意の N 次元正ベクトル r > 0 において
SN −1 (r)2 ≥ SN −2 (r)SN (r) が成り立つ．
略証.
が得られる．これを用いると
ek (r)
=
Sk (r)= N
簡単な変形により，
k
SN −1 (r) − SN −2 (r)SN (r)
⎛
⎞2
eN −2 (r) eN (r)
eN −1 (r )
−
=
⎝
⎠
N
N
N
2
N −1
N −2
N
(eN (r))2 N − 1 eN −1 (r) 2
2 eN −2 (r) =
−
N −1
N2
eN (r)
N eN (r)
N
2
(eN (r))2 N − 1 1
2 1
=
−
N −1
N2
ri
N i<j ri rj
i=1
N 1 2 N 1 2 ( )
( )
(eN (r))2
i=1 ri
i=1 ri
−
=
≥0
N −1
N
N
2015 年 3 月号
e (s)
N
k N −k
N
=
k
ek (s)
N −1
= Sk (s)
k
が成り立つ．
■
最後に Newton の不等式の証明の概要を記す．任
意の整数 1 < ∀m < N において，Sm (r)2 ≥
Sm−1 (r)Sm+1 (r) が成り立つことを示すには，補題 6
をベクトル r に繰り返し適用し，ベクトルの次元が
m + 1 次元になった所で補題 5 を適用すればよい．詳
細については紙面の都合上省略する．
c by ORSJ. Unauthorized reproduction of this article is prohibited. （15）137
Copyright

Download Report