Desigualdad BRS

La desigualdad BRS es el nombre corto de la desigualdad de Bruss-Robertson-Steele . Esta desigualdad proporciona un límite superior conveniente para el número máximo esperado de variables aleatorias no negativas que se pueden sumar sin exceder un límite superior dado . ${\displaystyle s>0}$

Por ejemplo, supongamos que 100 variables aleatorias están todas uniformemente distribuidas en , no necesariamente independientes, y sea , digamos. Sea el número máximo de que uno puede seleccionar en tal que su suma no exceda . es una variable aleatoria, entonces, ¿qué se puede decir sobre los límites para su expectativa? ¿Cómo se comportaría un límite superior para, si uno cambia el tamaño de la muestra y lo mantiene fijo, o alternativamente, si uno lo mantiene fijo pero varía ? ¿Qué se puede decir sobre , si la distribución uniforme se reemplaza por otra distribución continua? En toda generalidad, ¿qué se puede decir si cada uno puede tener su propia función de distribución continua ? ${\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}}$

Problema general

Sea una secuencia de variables aleatorias no negativas (posiblemente dependientes) que se distribuyen de forma continua de forma conjunta. Para y sea el número máximo de observaciones entre las que se puede sumar sin exceder . ${\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}$

Ahora bien, para obtenerlo se puede pensar en mirar la lista de todas las observaciones, primero seleccionar la más pequeña, luego sumar la segunda más pequeña, luego la tercera y así sucesivamente, siempre que la suma acumulada no exceda . Por lo tanto, se puede definir en términos de las estadísticas de orden creciente de , denotadas por , es decir, por ${\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)}$

¿Cuál es el mejor límite superior general posible si sólo se requiere la continuidad de la distribución conjunta de todas las variables? Y, entonces, ¿cómo calcular este límite? ${\displaystyle E(N[n,s])}$

Variables aleatorias distribuidas de forma idéntica.

Teorema 1 Sean variables aleatorias no negativas idénticamente distribuidas con función de distribución absolutamente continua . Entonces ${\displaystyle X_{1},X_{2},\cdots ,X_{n}}$ ${\displaystyle F}$

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

donde se resuelve la llamada ecuación BRS ${\displaystyle t:=t(n,s)}$

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

A modo de ejemplo, aquí están las respuestas a las preguntas planteadas al principio. Por lo tanto, supongamos que todos están distribuidos uniformemente en . Luego en , y por lo tanto en . La ecuación BRS se convierte en ${\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.}$

La solución es , y por tanto de la desigualdad (2) ${\displaystyle t={\sqrt {2s/n}}}$

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

Dado que siempre se tiene , este límite se vuelve trivial para . ${\displaystyle N[n,s]\leq n}$ ${\displaystyle s\geq nE(X)=n/2}$

Para las preguntas de ejemplo con este se obtiene . Como se ve en (4), duplicar el tamaño de la muestra y mantenerlo fijo, o viceversa, produce para la distribución uniforme en el caso no trivial el mismo límite superior. ${\displaystyle n=100,s=10}$ ${\displaystyle E(N[100,10])\leq {\sqrt {2000}}\approx 44.7}$ ${\displaystyle n}$ ${\displaystyle s}$

Desigualdad BRS generalizada

Teorema 2. Sean variables aleatorias positivas que se distribuyen conjuntamente de modo que tenga una función de distribución absolutamente continua . Si se define como antes, entonces ${\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)

¿Dónde está la solución única de la ecuación BRS? ${\displaystyle t:=t(n,s)}$

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

Claramente, si todas las variables aleatorias tienen la misma distribución marginal , entonces (6) recaptura (3) y (5) recaptura (2). Nuevamente, debe señalarse que no se necesita ninguna hipótesis de independencia. ${\displaystyle X_{i},i=1,2,\cdots ,n}$ ${\displaystyle F}$

Refinamientos de la desigualdad BRS

Dependiendo del tipo de distribución , los refinamientos del Teorema 2 pueden ser de verdadero interés. Mencionamos sólo uno de ellos. ${\displaystyle F_{k}}$

Sea el conjunto aleatorio de aquellas variables que se pueden sumar para obtener el número aleatorio máximo , es decir, ${\displaystyle A[n,s]}$ ${\displaystyle N[n,s]}$

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

y denotemos la suma de estas variables. El llamado residuo es por definición siempre no negativo, y se tiene: ${\displaystyle S_{A[n,s]}}$ ${\displaystyle s-S_{A[n,s]}}$

Teorema 3. Sea θ con distribución continua conjunta con funciones de distribución marginal , y sea la solución de (6). Entonces ${\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)

La mejora en (7) en comparación con (5) consiste por tanto en

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

El residuo esperado en el numerador es típicamente difícil de calcular o estimar, pero existen excepciones agradables. Por ejemplo, si todas son variables aleatorias exponenciales independientes, entonces la propiedad sin memoria implica (si se excede s) la simetría distribucional del residuo y el sobrepaso sobre . Para fijo se puede demostrar que : . Esta mejora fluctúa alrededor de , y la convergencia a , (simulaciones) parece rápida. ${\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}$

Fuente

La primera versión de la desigualdad BRS (teorema 1) fue demostrada en el lema 4.1 de F. Thomas Bruss y James B. Robertson (1991). Este artículo demuestra además que el límite superior es asintóticamente ajustado si las variables aleatorias son independientes entre sí. La generalización a distribuciones continuas arbitrarias (teorema 2) se debe a J. Michael Steele (2016). El teorema 3 y otros refinamientos de la desigualdad BRS son más recientes y se demostraron en Bruss (2021).

Aplicaciones

La desigualdad BRS es una herramienta versátil, ya que se aplica a muchos tipos de problemas y el cálculo de la ecuación BRS a menudo no es muy complejo. Además, y en particular, se observa que el número máximo siempre domina el número máximo de selecciones bajo cualquier restricción adicional, como por ejemplo para selecciones en línea sin recuperación. Los ejemplos estudiados en Steele (2016) y Bruss (2021) tocan muchas aplicaciones, incluidas las comparaciones entre secuencias iid y secuencias no iid, problemas de condensación de procesos puntuales , procesos "incómodos", algoritmos de selección , problemas de mochila , problemas de tipo Borel-Cantelli , el teorema de Bruss-Duerinckx y estrategias de mosaico en línea . ${\displaystyle N[n,s]}$

Referencias

Bruss FT y Robertson JB (1991) 'Lema de Wald' para sumas de estadísticas de orden de variables aleatorias iid , Adv. Appl. Probab., Vol. 23, 612-623.

Bruss FT y Duerinckx M. (2015), Procesos de ramificación dependientes de recursos y la envoltura de la sociedad , Ann. of Appl. Probab., Vol. 25 (1), 324-372.

Steele JM (2016), La desigualdad de Bruss-Robertson: elaboraciones, extensiones y aplicaciones , Math. Applicanda, vol. 44, n.º 1, 3-16.

Bruss FT (2021), La desigualdad BRS y sus aplicaciones , Probab. Surveys, vol. 18, 44-76.