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),}$ （２）

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

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

例として、冒頭で提起した質問に対する答えを示します。したがって、すべてがに均一に分布しているとします。次に、そして に分布します。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}}}$（４）

常に となるため、この境界は に対して自明になります。 ${\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}$

定理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)}$、（５）

は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}$

分布の種類によっては、定理 2 の改良が非常に興味深いものになることがあります。ここではそのうちの 1 つについてのみ説明します。 ${\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 {sE(S_{A[n,s]})}{t(n,s)}}}$（７）

したがって、（５）と比較した（７）の改善は、

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

分子の期待残差は、通常、計算や推定が困難ですが、優れた例外が存在します。たとえば、すべてが独立した指数ランダム変数である場合、メモリレス特性は、（s を超えた場合）残差の分布対称性と を超えるオーバーシュートを意味します。 を固定した場合、次が示されます。 この改善は の周りで変動し 、 への収束は（シミュレーションでは）速いようです。 ${\displaystyle X_{k}}$${\displaystyle s}$${\displaystyle s}$${\displaystyle {\frac {sE(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 シーケンスの比較、凝縮点プロセスの問題、 「厄介な」プロセス、選択アルゴリズム、ナップザック問題、ボレル-カンテリ型の問題、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。