BRS不平等

BRS不等式は、Bruss-Robertson-Steele不等式の略称です。この不等式は、与えられた上限を超えずに合計できる非負確率変数の最大数の期待値の便利な上限を与えます。 ${\displaystyle s>0}$

例えば、100 個のランダム変数がすべて 上に均一に分布していて、必ずしも独立していないと仮定し、 とします。 を において、その合計が を超えないように選択できるの最大数とします。はランダム変数なので、その期待値の境界については何が言えるでしょうか。サンプルのサイズを変更してを固定したままにした場合、または を固定したまま を変化させた場合、 の上限はどのように振る舞うでしょうか。均一分布を別の連続分布に置き換えた場合、 について何が言えるでしょうか。一般に、 が独自の連続分布関数 を持つ可能性がある場合は何が言えるでしょうか。 ${\displaystyle X_{1},X_{2},...,X_{100}}$ ${\displaystyle [0,1]}$ ${\displaystyle s=10}$ ${\displaystyle N[n,s]:=N[100,10]}$ ${\displaystyle X_{j}}$ ${\displaystyle \{X_{1},X_{2},...,X_{100}\}}$ ${\displaystyle s=10}$ ${\displaystyle N[100,10]}$ ${\displaystyle E(N[n,s])}$ ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle E(N[n,s])}$ ${\displaystyle X_{k}}$ ${\displaystyle F_{k}}$

一般的な問題

を、共連続分布に従う非負確率変数（従属変数を含む場合もある）の列とする。 および について、を超えずに合計できる観測値の最大値とする。 ${\displaystyle X_{1},X_{2},...}$ ${\displaystyle n\in \{1,2,...\}}$ ${\displaystyle s\in \mathbb {R} ^{+}}$ ${\displaystyle N[n,s]}$ ${\displaystyle X_{1},X_{2},...,X_{n}}$ ${\displaystyle s}$

さて、 を得るには、すべての観測値のリストを見て、まず最小のものを選び、次に2番目に小さいもの、さらに3番目に小さいものを加え、というように累積和が を超えない限り繰り返していくことが考えられる。したがって、は の昇順統計量、 で表され、すなわち で 定義することができる。${\displaystyle N[n,s]}$ ${\displaystyle s}$ ${\displaystyle N[s,n]}$ ${\displaystyle X_{1},X_{2},\cdots ,X_{n}}$ ${\displaystyle X_{1,n}\leq X_{2,n}\leq \cdots \leq X_{n,n},}$

${\displaystyle {\begin{aligned}N[n,s]={\begin{cases}0&,{\rm {~if~}}~X_{1,n}>s,\\\max\{~k\in \mathbb {N} :~X_{1,n}+X_{2,n}+\cdots +X_{k,n}\leq s\}&,{\rm {~otherwise}}.\end{cases}}\end{aligned}}(1)}$

すべての変数の結合分布の連続性のみを求める場合、最も適切な一般的な上限値は何でしょうか？そして、その上限値をどのように計算するのでしょうか？ ${\displaystyle E(N[n,s])}$

同一に分布するランダム変数。

定理1絶対連続分布関数を持つ非負確率変数を同一分布に従うものとし、 ${\displaystyle X_{1},X_{2},\cdots ,X_{n}}$ ${\displaystyle F}$

${\displaystyle E(N[n,s])\leq nF(t),}$ （2）

ここで、いわゆるBRS方程式を解く。 ${\displaystyle t:=t(n,s)}$

${\displaystyle n\int _{0}^{t}x\,dF(x)\,=\,s}$ （3）

例として、冒頭で提起した問いへの答えを示します。したがって、すべてが上で一様に分布しているとします。次に上で、そして上でも分布するとします。BRS方程式は次のようになります。 ${\displaystyle X_{1},X_{2},\cdots ,X_{n}}$ ${\displaystyle [0,1]}$ ${\displaystyle F(t)=t}$ ${\displaystyle [0,1]}$ ${\displaystyle dF(x)/dx=1}$ ${\displaystyle [0,1]}$

${\displaystyle n\int _{0}^{t}xdx=nt^{2}/2=s.}$

解は であり、したがって不等式（2）より ${\displaystyle t={\sqrt {2s/n}}}$

${\displaystyle E(N[n,s])\leq n\,F(t)=n{\sqrt {2s/n}}={\sqrt {2sn}}}$ （4）

常に であるため、この境界は に対して自明になります。 ${\displaystyle N[n,s]\leq n}$ ${\displaystyle s\geq nE(X)=n/2}$

これを含む例題では となります 。(4)からわかるように、サンプル数を2倍にしてを固定したままにするか、その逆を行うと、非自明なケースにおける一様分布の上限は同じになります。 ${\displaystyle n=100,s=10}$ ${\displaystyle E(N[100,10])\leq {\sqrt {2000}}\approx 44.7}$ ${\displaystyle n}$ ${\displaystyle s}$

一般化BRS不等式

定理2.が共分布する正確率変数で、絶対連続分布関数 を持つとする。が前述のように定義されるとき、 ${\displaystyle X_{1},X_{2},\cdots ,X_{n}}$ ${\displaystyle X_{k}}$ ${\displaystyle F_{k},~k=1,2,\cdots ,n.}$ ${\displaystyle N[n,s]}$

${\displaystyle E(N[n,s])\leq \sum _{k=1}^{n}F_{k}(t)}$ 、（5）

BRS方程式の唯一の解は どこにあるか${\displaystyle t:=t(n,s)}$

${\displaystyle \sum _{k=1}^{n}\int _{0}^{t}\,x\,dF_{k}(x)=s.}$ （6）

明らかに、すべての確率変数が 同じ周辺分布に従う場合、(6)は(3)を、(5)は(2)を再現します。ここでも、独立性仮説は全く必要ないことを指摘しておきます。 ${\displaystyle X_{i},i=1,2,\cdots ,n}$ ${\displaystyle F}$

BRS不等式の改良

分布の種類によっては、定理2の改良が非常に興味深いものとなる場合があります。ここではそのうちの一つについてのみ触れます。 ${\displaystyle F_{k}}$

を、最大乱数 を生成するために合計できる変数のランダム集合とします。つまり、 ${\displaystyle A[n,s]}$ ${\displaystyle N[n,s]}$

${\displaystyle \#A[n,s]=N[n,s]}$ 、

そして、これらの変数の和を とします。いわゆる残差 は定義により常に非負であり、以下の式が成り立ちます。 ${\displaystyle S_{A[n,s]}}$ ${\displaystyle s-S_{A[n,s]}}$

定理3.が周辺分布関数で共連続分布し、 が(6)の解であるとする。すると、 ${\displaystyle X_{1},X_{2},\cdots ,X_{n}}$ ${\displaystyle F_{k},k=1,2,\cdots ,n}$ ${\displaystyle t:=t(n,s)}$

${\displaystyle E(N[n,s])\leq \left(\sum _{k=1}^{n}F_{k}(t(n,s))\right)-{\frac {s-E(S_{A[n,s]})}{t(n,s)}}}$ （7）

したがって、(5)と比較した(7)の改善は、

${\displaystyle {\frac {s-E(S_{A[n,s]})}{t(n,s)}}}$ 。

分子の期待残差は通常、計算や推定が困難ですが、優れた例外も存在します。例えば、すべてが独立した指数確率変数である場合、メモリレス特性は（s を超える場合）、残差の分布対称性と におけるオーバーシュートを意味します。 を固定すると、が成り立ちます。この改善は の周りで変動し 、 への収束は（シミュレーションでは）速いようです。 ${\displaystyle X_{k}}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle {\frac {s-E(S_{A[n,s]})}{t(n,s)}}\to 1/2{\rm {~as~}}n\to \infty }$ ${\displaystyle 1/2}$ ${\displaystyle 1/2}$

ソース

BRS不等式の最初のバージョン（定理1）は、F. Thomas BrussとJames B. Robertson (1991)の補題4.1で証明されました。この論文ではさらに、確率変数が互いに独立である場合、上界は漸近的にタイトであることが証明されています。任意の連続分布への一般化（定理2）は、J. Michael Steele (2016)によるものです。定理3とBRS不等式のその他の改良は比較的新しいもので、Bruss (2021)で証明されています。

アプリケーション

BRS不等式は、多くの種類の問題に適用でき、BRS方程式の計算がそれほど複雑ではないことが多いため、汎用性の高いツールです。また、特に注目すべき点は、追加の制約（例えば、リコールなしのオンライン選択など）の下では、最大数は常に選択の最大数よりも大きいということです。Steele (2016) とBruss (2021) で研究された例は、iidシーケンスと非iidシーケンスの比較、凝縮点過程の問題、「厄介な」過程、選択アルゴリズム、ナップザック問題、Borel-Cantelli型問題、Bruss-Duerinckx定理、オンラインタイリング戦略など、多くの応用範囲に触れています。 ${\displaystyle N[n,s]}$

参考文献

Bruss FT および Robertson JB (1991) 「iid ランダム変数の順序統計量の合計に関する Wald の補題」、Adv. Appl. Probab.、Vol. 23、612-623。

Bruss FTとDuerinckx M.（2015）、資源依存分岐プロセスと社会のエンベロープ、Ann. of Appl. Probab.、Vol. 25（1）、324-372。

Steele JM (2016)、「Bruss-Robertson 不等式: 詳細、拡張、および応用」、Math. Applicanda、Vol. 44、No 1、3-16。

Bruss FT (2021) 「BRS不等式とその応用」Probab. Surveys, Vol.18, 44-76.