BRS-неравенство

BRS-неравенство — это сокращенное название неравенства Брюсса-Робертсона-Стила . Это неравенство дает удобную верхнюю границу ожидаемого максимального числа неотрицательных случайных величин, которые можно суммировать, не превышая заданную верхнюю границу. $s>0$.

Например, предположим, что 100 случайных величин $X_{1},X_{2},...,X_{100}$ все равномерно распределены по $[0,1]$, не обязательно независимый, и пусть $s=10$, сказать. Позволять $N[n,s]:=N[100,10]$ быть максимальным количеством $X_{j}$ можно выбрать в $\{X_{1},X_{2},...,X_{100}\}$ такие, что их сумма не превосходит $s=10$. $N[100,10]$ является случайной величиной, так что можно сказать о границах ее ожидания? Как будет определяться верхняя граница $E(N[n,s])$ вести себя, если изменить размер $n$ образца и сохраняет $s$ фиксированный или, альтернативно, если кто-то сохраняет $n$ фиксированный, но варьируется $s$? Что можно сказать о $E(N[n,s])$, если равномерное распределение заменить другим непрерывным распределением? В общем, что можно сказать, если каждый $X_{k}$ может иметь свою собственную непрерывную функцию распределения $F_{k}$?

Общая проблема

Позволять $X_{1},X_{2},...$ быть последовательностью неотрицательных случайных величин (возможно, зависимых), совместно непрерывно распределенных. Для $n\in \{1,2,...\}$ и $s\in \mathbb {R} ^{+}$ позволять $N[n,s]$ быть максимальным количеством наблюдений среди $X_{1},X_{2},...,X_{n}$ что можно суммировать, не выходя за рамки $s$.

Теперь, чтобы получить $N[n,s]$ можно подумать о просмотре списка всех наблюдений: сначала выберите самое маленькое, затем добавьте второе самое маленькое, затем третье и так далее, пока накопленная сумма не превысит $s$. Следовательно $N[s,n]$ можно определить в терминах статистики возрастающего порядка $X_{1},X_{2},\cdots ,X_{n}$, обозначенный $X_{1,n}\leq X_{2,n}\leq \cdots \leq X_{n,n},$, а именно по

${\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)$

Какова наилучшая общая верхняя граница для $E(N[n,s])$ если требуется только непрерывность совместного распределения всех переменных? И потом, как вычислить эту границу?

Одинаково распределенные случайные величины.

Теорема 1. Пусть $X_{1},X_{2},\cdots ,X_{n}$ быть одинаково распределенными неотрицательными случайными величинами с абсолютно непрерывной функцией распределения $F$. Затем

$E(N[n,s])\leq nF(t),$ (2)

где $t:=t(n,s)$ решает так называемое BRS-уравнение

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

В качестве примера приведем ответы на вопросы, поставленные в начале.Итак, пусть все $X_{1},X_{2},\cdots ,X_{n}$ быть равномерно распределены по $[0,1]$. Затем $F(t)=t$ на $[0,1]$, и, следовательно, $dF(x)/dx=1$ на $[0,1]$.Уравнение BRS принимает вид

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

Решение $t={\sqrt {2s/n}}$, и, следовательно, из неравенства (2)

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

Поскольку всегда есть $N[n,s]\leq n$, эта оценка становится тривиальной для $s\geq nE(X)=n/2$.

Для примера вопросов с $n=100,s=10$ это дает $E(N[100,10])\leq {\sqrt {2000}}\approx 44.7$.Как видно из (4), удвоение размера выборки $n$ и сохранение $s$ фиксированный, или наоборот, выход для равномерного распределения в нетривиальном случае один и тот же верхний предел.

Обобщенное BRS-неравенство

Теорема 2. Пусть $X_{1},X_{2},\cdots ,X_{n}$ быть положительными случайными величинами, которые совместно распределены так, что $X_{k}$ имеет абсолютно непрерывную функцию распределения $F_{k},~k=1,2,\cdots ,n.$.Если $N[n,s]$ определяется как и раньше, тогда

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

где $t:=t(n,s)$ является единственным решением BRS-уравнения

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

Очевидно, что если все случайные величины $X_{i},i=1,2,\cdots ,n$ имеют одинаковое предельное распределение $F$, затем (6) перехватывает (3), а (5) перехватывает (2).Еще раз следует отметить, чтоникакая гипотеза независимости вообще не требуется.

Уточнения BRS-неравенства

В зависимости от типа дистрибутива $F_{k}$, уточнения теоремы 2 могут представлять реальный интерес. Мы лишь упомянем один из них.

Позволять $A[n,s]$ — случайный набор этих переменных, которые можно суммировать, чтобы получить максимальное случайное число $N[n,s]$, то есть,

$\#A[n,s]=N[n,s]$,

и пусть $S_{A[n,s]}$ обозначим сумму этих переменных.Так называемыйостаток $s-S_{A[n,s]}$по определению всегда неотрицательен, и он имеет:

Теорема 3. Пусть $X_{1},X_{2},\cdots ,X_{n}$ быть совместно непрерывно распределены с маргинальными функциями распределения $F_{k},k=1,2,\cdots ,n$, и пусть $t:=t(n,s)$ есть решение (6). Затем

$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)

Таким образом, улучшение в (7) по сравнению с (5) заключается в

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

Ожидаемый остаток в числителе обычно сложно вычислить или оценить, но существуют приятные исключения. Например, если все $X_{k}$ являются независимыми экспоненциальными случайными величинами, то свойство отсутствия памяти подразумевает (если s превышено) симметрию распределения невязки и выброс по $s$. Для фиксированного $s$ тогда можно показать, что: ${\frac {s-E(S_{A[n,s]})}{t(n,s)}}\to 1/2{\rm {~as~}}n\to \infty$. Это улучшение колеблется вокруг $1/2$, и сходимость к $1/2$, (моделирование) кажется быстрым.

Источник

Первая версия BRS-неравенства (теорема 1) была доказана в лемме 4.1 Ф. Томаса Брусса и Джеймса Б.Робертсон (1991). Более того, в данной статье доказывается, что верхняя оценка асимптотически точна, если случайные величины не зависят друг от друга. Обобщение на произвольные непрерывные распределения (теорема 2) принадлежит Дж. Майклу Стилу (2016). Теорема 3 и другие уточнения BRS-неравенства появились позднее и доказаны в работе Брюсса (2021).

Приложения

BRS-неравенство является универсальным инструментом, поскольку оно применимо ко многим типам задач и поскольку вычисление BRS-уравнения часто не требует большого труда. Также, в частности, следует отметить, что максимальное число $N[n,s]$ всегда доминирует над максимальным количеством выборов при любом дополнительном ограничении, например, для онлайн- выборов без отзыва. Примеры, изученные в Steele (2016) и Bruss (2021), затрагивают многие приложения, включая сравнения между iid-последовательностями и не-iid-последовательностями, проблемы конденсации точечных процессов , «неуклюжие» процессы, алгоритмы выбора , задачи о рюкзаке , Бореля-Кантелли задачи типа . , теорема Брюсса-Дюринка и онлайн- стратегии тайлинга .

Ссылки

Брусс Ф.Т. и Робертсон Дж.Б. (1991) «Лемма Вальда» для сумм порядковой статистики случайных переменных iid , Adv. Прил. Вероятно., Том. 23, 612–623.

Брусс Ф.Т. и Дуринкс М. (2015), Ресурсно-зависимые ветвящиеся процессы и оболочка общества , Ann. прил. Вероятно., Том. 25 (1), 324–372.

Стил Дж. М. (2016), Неравенство Брюсса-Робертсона: разработки, расширения и приложения , Math. Приложение, Vol. 44, № 1, 3-16.

Брусс Ф.Т. (2021), BRS-неравенство и его приложения , Пробаб. Обзоры, Том 18, 44–76.