Saltar al contenido principal
LibreTexts Español

7.5: Umbrales, reglas de detención e identidad de Wald

  • Page ID
    86380
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    El siguiente lema muestra que una caminata aleatoria con un umbral tanto positivo como negativo, digamos\(\alpha > 0\) y\(\beta < 0\), finalmente cruza uno de los umbrales. La Figura 7.9 ilustra dos rutas de muestreo y cómo cruzan los umbrales. Más específicamente, la caminata aleatoria primero cruza un umbral en el juicio\(n\) si\(\beta < S_i < \alpha \) para\(1 \leq i < n\) y cualquiera\(S_n \geq \alpha \) o\(S_n \leq \beta \). Por ahora no hacemos suposiciones sobre la media o MGF de\(S_n\).

    El ensayo en el que se cruza por primera vez un umbral es un rv probablemente defectuoso\(J\). El suceso\(J = n \, (i.e.\), el hecho de que un umbral se cruza por primera vez en el juicio\(n)\), es una función de\(S_1, S_2, . . . , S_n\), y por lo tanto, en la notación de la Sección 4.5,\( J\) es un juicio de detención posiblemente defectuoso. El siguiente lema muestra que en realidad\(J\) es un juicio de detención, es decir, que la detención (cruce de umbral) eventualmente ocurre con probabilidad 1.

    clipboard_efec06dd132490be8aa62cc9b3f101b5b.png

      Figura 7.9: Dos caminos de muestreo de una caminata aleatoria con dos umbrales. En la primera, el umbral en\(\alpha \) se cruza en\(J = 5\). En el segundo, el umbral en\(\beta \) se cruza en\(J = 4\)  

    Lema 7.5.1. Que {\(X_i; i \geq 1\)} sean IID rv, no idénticamente 0. Para cada uno\(n \geq 1\), vamos\(S_n = X_1 +... + X_n\). Dejar\(\alpha > 0\) y\(\beta < 0\) ser arbitrario, y dejar\( J\) ser el más pequeño\( n\) para el cual cualquiera\(S_n \geq \alpha \) o\( S_n \leq \beta \). Entonces\( J\) es una variable aleatoria (i.e.,\( \lim_{m→\infty } \text{Pr}\{ J \geq m \} = 0\)) y tiene momentos finitos de todos los órdenes.

    Prueba: Como no\(X\) es idénticamente 0, hay algunos\(n\) para los cuales\(\text{Pr}\{ S_n \leq −\alpha + \beta\} > 0\) o para los cuales\(\text{Pr}\{ S_n \geq \alpha − \beta \} > 0\). Para cualquiera de tales\( n\), definir\(\epsilon \) por

    \[ \epsilon = \max [ \text{Pr} \{ S_n \leq -\alpha + \beta \}, \, \text{Pr}\{ S_n \geq \alpha - \beta \} ] \nonumber \]

    Para cualquier entero\(k ≥ 1\), dado que\(J > n(k − 1)\), y dado cualquier valor de\( S_{n(k−1)}\) in\((\beta , \alpha )\), un umbral será cruzado por el tiempo\(nk\) con probabilidad al menos\(\epsilon \). Por lo tanto,

    \[ \text{Pr} \{ J>nk|J>n(k-1)\} \leq 1-\epsilon \nonumber \]

    Iterando en\(k\),

    \[ \text{Pr} \{ J>nk \} \leq (1-\epsilon )^k \nonumber \]

    Esto demuestra que\(J\) es finito con probabilidad 1 y que\(\text{Pr}\{ J ≥ j\}\) va a 0 al menos geométricamente adentro\(j\). De ello se deduce que el momento que genera\(\mathsf{g}_J (r)\) la función de\(J\) es finita en una región alrededor\(r = 0\), y que\( J\) tiene momentos de todos los órdenes.

    \( \square \)

    La identidad de Wald para dos umbrales

    Teorema 7.5.1 (Identidad de Wald) Let {\(X_i; i ≥ 1\)} ser IID y dejar\(\gamma \ref{r} = \ln \{\mathsf{E} [e^{rX}]\}\) ser el MGF semi-invariante de cada uno\(X_i\). Supongamos que\(\gamma (r)\) es finito en el intervalo abierto\( (r_−, r_+)\) con\( r_− < 0 < r_+\). Para cada uno\( n ≥ 1\), vamos\( S_n = X_1 +... + X_n\). Dejar\(\alpha > 0\) y\(\beta < 0\) ser arbitrarios números reales, y dejar\(J\) ser el menor n para el cual cualquiera\( S_n ≥ \alpha \) o\(S_n ≤ \beta \). Entonces para todos\(r ∈ (r_−, r_+)\),

    \[ \mathsf{E} [\exp (rS_J-J \gamma (r))] = 1 \nonumber \]

    La siguiente prueba es una simple aplicación de las distribuciones de probabilidad inclinadas discutidas en la sección anterior.

    Prueba: Asumimos que\(X_i\) es discreto para cada uno\(i\) con el PMF\(\mathsf{p}_X (x)\). Para el caso arbitrario, los PMF deben ser sustituidos por funciones de distribución y las sumas por integrales de Stieltjes, complicando así los detalles técnicos pero no introduciendo nuevas ideas.

    Para cualquier dado\( r ∈ (r_−, r_+)\), utilizamos el PMF inclinado\(\mathsf{q}_{X,r}(x)\) dado en (7.4.4) como

    \[ \mathsf{q}_{X,r}(x) = \mathsf{p}_X(x) \exp [r-\gamma \ref{r} ]\nonumber \]

    Tomando como independiente en la medida de probabilidad inclinada, el PMF inclinado para la\(n\) -tupla\(\boldsymbol{X}^n = (X_1, X_2, . . . , X_n)\) viene dado por\( X_i\)

    \[ \mathsf{q}_{X^n,r} (\boldsymbol{x}^n) = \mathsf{p}_{\boldsymbol{X}^n}(\boldsymbol{x}^n) \exp [rs_n - n\gamma \ref{r} ] \qquad \text{where } s_n = \sum^n_{i=1}x_i \nonumber \]

    Ahora deja\(\mathcal{T}_n\) ser el conjunto de\(n\) -tuplas\(X_1, . . . , X_n\) tal que\(\beta < S_i < \alpha \) para\(1 ≤ i < n\) y o\(S_n ≥ \alpha\) o\(S_n ≤ \beta \). Es decir,\(\mathcal{T}_n\) es el conjunto\(\boldsymbol{x}^n\) para el que el ensayo de detención\(J\) tiene el valor muestral\(n\). El PMF para el juicio de detención\(J\) en la medida inclinada es entonces

    \[ \begin{align} \mathsf{q}_{J,r}(n) \quad &= \quad \sum_{\boldsymbol{x}^n\in \mathcal{T}_n} \mathsf{q}_{\boldsymbol{X}^n,r} (\boldsymbol{x}^n) = \sum_{\boldsymbol{x}^n\in \mathcal{T}_n} \mathsf{p}_{\boldsymbol{X}^n} (\boldsymbol{x}^n) \exp [rs_n - n\gamma \ref{r} ] \nonumber \\ &= \quad \mathsf{E} [\exp [rS_n-n\gamma \ref{r} |J=n] \, \text{Pr} \{J = n\} \end{align} \nonumber \]

    Lema 7.5.1 aplica al PMF inclinado en esta caminata aleatoria así como al PMF original, y así la suma de\(\mathsf{q}_J (n)\) más\( n\) es 1. También, la suma sobre\(n\) de la expresión de la derecha es\(\mathsf{E} [\exp [rS_J − J\gamma (r)]]\), completando así la prueba.

    \(\square \)

    Después de comprender los detalles de esta prueba, se ve que es esencialmente solo la afirmación la que\(J\) es una regla de detención no defectuosa en el espacio de probabilidad inclinado.

    A continuación damos una serie de ejemplos de cómo se puede utilizar la identidad de Wald.

    relación de la identidad de Wald con la igualdad de Wald

    El juicio\( J\) en el que se cruza un umbral en la identidad de Wald es un juicio de detención en la terminología del Capítulo 4. Si tomamos la derivada con respecto a r de ambos lados de (7.5.1), obtenemos

    \[ \mathsf{E} \left[ [ S_J - J\gamma' \ref{r} \right] \exp \{ rS_J - J\gamma \ref{r} \} = 0 \nonumber \]

    Estableciendo\( r = 0\) y recordando eso\(\gamma \ref{0} = 0\) y\(\gamma' \ref{0} = \overline{X}\), esto se convierte en la igualdad de Wald tal y como se establece en el Teorema

    \[ \mathsf{E} [S_J] = \mathsf{E} [J] \overline{X} \nonumber \]

    Tenga en cuenta que esta derivación de la igualdad de Wald se restringe 1 a una caminata aleatoria con dos umbrales (y esto automáticamente satisface la restricción en la igualdad de Wald que\(\mathsf{E} [J] < \infty )\). El resultado en el Capítulo 4 es más general, aplicándose a cualquier proceso que detenga tal manera que\(E [J] < \infty \).

    La segunda derivada de (7.5.1) con respecto a\(r\) es

    \[ \mathsf{E} [ [ (S_J - J\gamma' (r))^2- J\gamma''(r) ] ] \exp \{rS_J - J\gamma \ref{r} \} = 0 \nonumber \]

    En\(r=0\), esto es

    \[ \mathsf{E} \left[ S^2_J-2JS_J\overline{X} + J^2\overline{X}^2 \right] = \sigma^2_X \mathsf{E} [J] \nonumber \]

    Esta ecuación suele ser difícil de usar debido al término cruzado entre\( S_J\) y\(J\), pero su aplicación principal viene en el caso donde\(\overline{X} = 0\). En este caso, la igualdad de Wald no proporciona información sobre\(\mathsf{E}[J]\), pero (7.5.4) simplifica a

    \[ \mathsf{E} [S^2_J] = \sigma^2_X \mathsf{E} [J] \nonumber \]

    Caminatas aleatorias simples de media cero

    Como ejemplo de (7.5.5), considere el simple paseo aleatorio de la Sección 7.1.1 con\(\text{Pr}\{X=1\} = \text{Pr}\{X= − 1\} = 1/2\), y asuma que\(\alpha > 0\) y\(\beta < 0\) son enteros. Dado que\(S_n\) toma solo valores enteros y cambia solo por\(\pm 1\), toma el valor\(\alpha\) o\(\beta \) antes de superar cualquiera de estos valores. Así\( S_J = \alpha \) o\( S_J = \beta \). Vamos a\(q_{\alpha}\) denotar\(\text{Pr}\{S_J = \alpha \}\). El valor esperado de\(S_J\) es entonces\(\alpha q_{\alpha} + \beta (1 − q_{\alpha})\). De la igualdad de Wald,\(\mathsf{E} [S_J ] = 0\), so

    \[ q_{\alpha } = \dfrac{-\beta}{\alpha -\beta } ; \qquad 1-q_{\alpha} = \dfrac{\alpha}{\alpha-\beta } \nonumber \]

    Desde (7.5.5),

    \[ \sigma^2_X \mathsf{E} [J] = \mathsf{E}[S^2_J] = \alpha^2 q_{\alpha} + \beta^2 (1-q_{\alpha} ) \nonumber \]

    Utilizando el valor de\(q_{\alpha}\) from (7.5.6) y reconociendo que\(\sigma^2_X = 1\),

    \[ \mathsf{E} [J] = -\beta \alpha / \sigma^2_X = -\beta \alpha \nonumber \]

    Como comprobación de cordura, tenga en cuenta que si\(\alpha \) y cada uno\(\beta \) se multiplica por alguna constante grande\( k\), entonces\(\mathsf{E} [J]\) aumenta en\(k^2\). Ya que\(\sigma_{S_2}^2 = n\), esperaríamos\(S_n\) fluctuar con el incremento\( n\), con valores típicos creciendo como\(\sqrt{n}\), y así es razonable que el tiempo esperado para alcanzar un umbral aumente con el producto de las distancias a los umbrales.

    También notamos que si\(\beta \) se disminuye hacia\(−\infty \), mientras se mantiene\(\alpha\) constante, entonces\(q_{\alpha} \rightarrow 1\) y\( \mathsf{E} [J] \rightarrow \infty \). Esto ayuda a explicar el Ejemplo 4.5.2 donde uno juega un juego de lanzamiento de monedas, deteniéndose cuando finalmente se adelanta. Esto demuestra que si el lanzador de monedas tiene un capital finito\(b, \, i.e.\), se detiene ya sea al cruzar un umbral positivo en 1 o un umbral negativo en\( −b\), entonces el lanzador de monedas gana una pequeña cantidad con alta probabilidad y pierde una gran cantidad con poca probabilidad.

    Para caminatas aleatorias más generales con\(\overline{X} = 0\), suele haber un sobreimpulso cuando se cruza el umbral. Si las magnitudes de\(\alpha \) y\(\beta \) son grandes en relación con el rango de\(X\), sin embargo, a menudo es razonable ignorar los excesos, y entonces a menudo\(-\beta \alpha /\sigma^2_X\) es una buena aproximación a\(\mathsf{E} [J]\). Si se quiere incluir el sobreimpulso, entonces el efecto del sobreimpulso debe tenerse en cuenta tanto en (7.5.6) como en (7.5.7).

    Límite exponencial en la probabilidad de cruce de umbrales

    A continuación aplicamos la identidad de Wald para completar el análisis de cruzar un umbral en el\(\alpha > 0\)
    momento\(\overline{X} < 0\).

    Corolario 7.5.1. Bajo las condiciones del Teorema 7.5.1, asumir que\(\overline{X} < 0\) y que\(r^* > 0\) existe tal que\(\gamma (r^*) = 0\). Entonces

    \[\text{Pr} \{S_J \geq \alpha \}\leq \exp (-r^* \alpha) \nonumber \]

    Prueba: La identidad de Wald, con\(r = r^*\), se reduce a\(\mathsf{E} [\exp (r^*S_J )] = 1\). Podemos expresarlo como

    \[\text{Pr} \{S_J \geq \alpha\} \mathsf{E} [\exp (r^*S_J)|S_J\geq \alpha ]+\text{Pr}\{ S_J\leq \beta \} \mathsf{E} [ \exp (r^*S_J)|S_J \leq \beta] = 1 \nonumber \]

    Dado que el segundo término de la izquierda no es negativo,

    \[ \text{Pr} \{ S_J\geq \alpha \}\mathsf{E}[\exp(r^*S_J)|S_J\geq\alpha] \leq 1 \nonumber \]

    Dado eso\(S_J ≥ \alpha \), vemos eso\( \exp(r^*S_J ) ≥ \exp(r^*\alpha )\). Así

    \[ \text{Pr}\{ S_J \geq \alpha \} \exp (r^*\alpha)\leq 1 \nonumber \]

    que es equivalente a (7.5.9).

    Este límite es válido para todos\( \beta < 0\), y por lo tanto también es válido en el límite\(\beta → −\infty \) (ver Ejercicio 7.10 para una demostración más detallada de que (7.5.9) es válido sin un umbral inferior). Vemos a partir de esto que el caso de un solo umbral es realmente un caso especial del problema de los dos umbrales, pero como se ve en la caminata aleatoria simple de media cero, tener un segundo umbral suele ser valioso para comprender mejor el caso del umbral único. La ecuación (7.5.9) también es válida para el caso de la Figura 7.8, donde\(\gamma \ref{r} < 0\) para todos\(r ∈ (0, r_+]\) y\(r^* = r_+\).

    El límite exponencial en (7.4.14) muestra que\(\text{Pr}\{S_n ≥ \alpha \} ≤ \exp (−r^*\alpha)\) para cada uno\(n\); (7.5.9) es más fuerte que esto. Eso lo demuestra\(\text{Pr}\{\bigcup_n\{S_n ≥ \alpha\}\} ≤ \exp(−r^*\alpha )\). Esto también se mantiene en el límite\(\beta → −\infty \).

    Cuando se aplica el Corolario 7.5.1 a la cola G/G/1 en el Teorema 7.2.1, (7.5.9) es referido como el Kingman Bound.

    Corolario 7.5.2 (Kingman Bound). Sea {\(X_i; i ≥ 1\)} y {\(Y_i; i ≥ 0\)} los intervalos entre llegadas y los tiempos de servicio de una cola G/G/1 que está vacía en el momento 0 cuando llega el cliente 0. Dejar {\(U_i = Y_{i−1} − X_i; i ≥ 1\)}, y dejar\( \gamma \ref{r} = \ln\{\mathsf{E} [e^{U r}]\}\) ser el momento semi-invariante que genera la función de cada uno\(U_i\). Supongamos que\(\gamma (r)\) tiene una raíz en\(r^* > 0\). Entonces\(W_n\), el retraso en la cola de la\(n\) llegada, y\(W\), el retraso en la cola de estado estacionario, satisfacen

    \[ \text{Pr} \{W_n \geq \alpha \} \leq \text{Pr} \{W\geq\alpha\} \leq \exp (-r^*\alpha ) \quad ; \qquad for \, all \, \alpha>0 \nonumber \]

    En la mayoría de las aplicaciones, un cruce de umbral positivo para una caminata aleatoria con una deriva negativa corresponde a alguna circunstancia excepcional, y a menudo indeseable, (por ejemplo, un error en el problema de prueba de hipótesis o un desbordamiento en la cola G/G/1). Así, un límite superior como (7.5.9) proporciona una garantía de cierto nivel de rendimiento y a menudo es más útil que una aproximación o una expresión exacta que es muy difícil de evaluar. Dado que estos límites son exponencialmente estrechos, también sirven como aproximaciones aproximadas aproximadas.

    Para un paseo al azar con\(\overline{X} > 0\), la circunstancia excepcional es\(\text{Pr}\{S_J ≤ \beta \}\). Esto se puede analizar cambiando el signo de\( X\) y\(\beta\) y utilizando los resultados para un valor esperado negativo. Estos límites exponenciales no funcionan para\(\overline{X} = 0\), y no vamos a analizar ese caso aquí más que el resultado en (7.5.5).

    Obsérvese que el límite simple sobre la probabilidad de cruzar el umbral superior en (7.5.9) (y por lo tanto también el límite Kingman) es un límite superior (más que una igualdad) porque, primero, se eliminó el efecto del umbral inferior (véase (7.5.11)), y, segundo, el sobreimpulso se limitó por 0 (véase (7.5.12). El efecto del segundo umbral se puede tomar en cuenta al reconocerlo\(\text{Pr}\{S_J ≤ \beta \} = 1 − \text{Pr}\{S_J ≥ \alpha \}\). Entonces (7.5.10) se puede resolver, consiguiendo

    \[ \text{Pr}\{S_J \geq \alpha \} = \dfrac{1-\mathsf{E}[\exp (r^*S_J)|S_J \leq \beta ]}{\mathsf{E} [\exp (r^*S_J)|S_J \geq \alpha] - \mathsf{E} [\exp(r^*S_J)|S_J \leq \beta]} \nonumber \]

    Resolver los términos en el lado derecho de (7.5.14) generalmente requiere analizar el rebasamiento al cruzar una barrera, y esto suele ser difícil. Para el caso de la simple caminata aleatoria, no se producen rebasamientos, ya que la caminata aleatoria cambia solo en pasos unitarios. Así, para\(\alpha \) y\(\beta \) enteros, tenemos\(\mathsf{E} [\exp (r^*S_J ) | S_J ≤\beta ] = \exp(r^*\beta )\) y\(\mathsf{E} [\exp (r^*S_J ) | S_J ≥\alpha ] = \exp (r^*\alpha)\). Sustituir esto en (7.5.14) produce la solución exacta

    \[ \text{Pr}\{S_J \geq \alpha \} = \dfrac{\exp (-r^* \alpha)[1-\exp (r^*\beta)]}{1-\exp [-r^*(\alpha - \beta )]} \nonumber \]

    Resolviendo la ecuación\(\gamma (r^*) = 0\) para el simple paseo aleatorio con probabilidades\( p\) y\(q\) rendimientos\(r^∗ = \ln (q/p)\). Esto también es válido si\( X\) toma los tres valores −1, 0, y +1 con\(p = \text{ Pr}\{X = 1\}, \, q = \text{Pr}\{X = −1\}\), y\(1 − p − q = \text{Pr}\{X = 0\}\). Se puede ver que si\( \alpha \) y\(−\beta \) son grandes enteros positivos, entonces el límite simple de (7.5.9) es casi exacto para este ejemplo.

    La ecuación (7.5.15) se utiliza a veces como aproximación para (7.5.14). Desafortunadamente, para muchas aplicaciones, los rebasamientos son más significativos que el efecto del umbral opuesto. Así, (7.5.15) es sólo despreciable mejor que (7.5.9) como aproximación, y tiene la desventaja adicional de no ser un límite.

    Si realmente se\(\text{Pr} \{S_J ≥ \alpha\}\) debe calcular, entonces se deben tomar en cuenta los rebasamientos en (7.5.14). Véase el capítulo 12 de [8] para un tratamiento de sobrebrotes.

    Pruebas de hipótesis binarias con observaciones IID

    El objetivo de esta subsección y del siguiente es entender cómo tomar decisiones binarias a partir de un número variable de observaciones, eligiendo dejar de observar datos adicionales cuando se pueda tomar una decisión suficientemente buena. Esta subsección inicial sienta las bases para ello mediante el análisis de los aspectos de gran desviación de la detección binaria con un número grande pero fijo de observaciones IID.

    Considere el problema de prueba de hipótesis binaria de la Sección 7.3 en la que\( H \) se encuentra una hipótesis binaria con probabilidades apriori\(\mathsf{p}_H \ref{0} = p_0\) y\(\mathsf{p}_H \ref{1} = p_1\). La observación\(Y_1, Y_2, . . . ,\) condicional\(H = 0\), es una secuencia de IID rv con la densidad de probabilidad\(\mathsf{f}_{Y |H }(y | 0)\). Condicional\(H = 1\), las observaciones son IID con densidad\(\mathsf{f}_{Y |H} (y | 1)\). Para cualquier número dado de observaciones\(n\) de muestra\(y_1, . . . , y_n\), la razón de verosimilitud se definió como

    \[ \Lambda_n (\boldsymbol{y}) = \prod^n_{i=1} \dfrac{\mathsf{f}_{Y|H} (y_n |0)}{\mathsf{f}_{Y|H} (y_n|1)} \nonumber \]

    y la relación logarítmica se definió como

    \[ s_n = \sum^n_{i=1} z_n; \qquad \text{where } z_n = \ln \dfrac{\mathsf{f}_{Y|H}(y_n|0)}{\mathsf{f}_{Y|H}(y_n|1)} \nonumber \]

    La prueba MAP da la máxima probabilidad aposteriori de una decisión correcta basada en las n observaciones\((y_1, . . . , y_n)\). Se define como la siguiente prueba de umbral:

    \[ s_n = \left\{ \begin{array}{cc} >\ln (p_1/p_0) \quad ; \qquad \quad \text{select } \hat{h}=0 \\ \leq \ln (p_1/p_0) \quad ; \qquad \quad \text{select } \hat{h}=1 \end{array} \right. \nonumber \]

    Podemos usar el límite de Chernoff para obtener un límite exponencialmente ajustado sobre la probabilidad de error usando la prueba MAP y dado\( H = 1\) (y dado de manera similar\(H = 0\)). Es decir,\(\text{Pr}\{ e |H = 1\}\) es simplemente\(\text{Pr}\{S_n ≥ \ln (p_1/p_0) | H=1\}\) dónde\(S_n\) está el rv cuyo valor muestral viene dado por (7.5.16),\( i.e.,\, S_n = \sum^n_{i=1} Z_n\) donde\(Z_n = \ln [f_{Y |H} (Y | 0)/f_{Y |H} (Y | 1)]\). El MGF semiinvariante\(\gamma_1 (r)\) de\(Z\) dado\(H = 1\) es

    \[ \begin{align} \gamma_1(r) \quad &= \quad \ln\int_y\mathsf{f}_{Y|H}(y|1)\exp \left\{ r \left[ \ln \dfrac{\mathsf{f}_{Y|H}(y|0)}{\mathsf{f}_{Y|H}(y|1)} \right] \right\} dy \nonumber \\ &= \quad \ln \int_y [\mathsf{f}_{Y|H}(y|1)]^{1-r}[\mathsf{f}_{Y|H}(y|0)]^r dy \end{align} \nonumber \]

    Sorprendentemente, vemos eso\(\gamma_1(1) = \ln\int_y \mathsf{f}_{Y |H} (y | 0) dy = 0\), así que\(r∗ = 1\) para\(\gamma_1(r)\). Ya que\(\gamma_1(r)\) tiene una segunda derivada positiva, esto demuestra que\(\gamma_1'(0) < 0\) y\(\gamma_1'(1) > 0\). La Figura 7.10 ilustra el exponente optimizado en el límite de Chernoff,

    \[ \text{Pr}\{e|H=1\} \leq \exp \left\{n\left[\min_r\gamma_1(r)-ra \right] \right\} \qquad \text{where } a=\dfrac{1}{n} \ln(p_1/p_0) \nonumber \]

    clipboard_e622db8e17c27140dbe2724e2548bd5dd.png

      Figura 7.10: Descripción gráfica de los exponentes en los límites de Chernoff optimizados para\(\text{Pr}\{e | H=1\}≤ \exp \{ n[\gamma_1(r) − ra]\}\) y\(\text{Pr} \{e | H=0\}≤ \exp \{ n[\gamma_1(r) + (1 − r)a]\}\). La pendiente a es igual a\(\frac{1}{n} \ln(p_1/p_0)\). Para una prueba de umbral arbitrario con umbral\(\eta \), la pendiente\(a\) es\(\frac{1}{n} \ln η\).  

    Podemos encontrar al Chernoff con destino\(\text{Pr}\{e | H=0\}\) de la misma manera. El MGF semiinvariante para\(Z\) condicional\(H = 0\) es dado por

    \[ \gamma_0(r) = \ln \int_y [ \mathsf{f}_{Y|H}(y|1)]^{-r}[\mathsf{f}_{Y|H}(y|0)]^{1+r}dy = \gamma_1(r-1) \nonumber \]

    Podemos ver a partir de esto que la distribución de\(Z\) condicional\(H = 0\) es la distribución inclinada (at\(r = 1\)) de\(Z\) condicional on\(H = 1\). Ya que\(\gamma_0(r) = \gamma_1(r−1)\), el límite optimizado de Chernoff\(\text{Pr}\{e | H=0\}\) está dado por

    \[ \text{Pr}\{ e|H=0\} \leq \exp \left\{ n \left[ [ \min_r \gamma_1(r)+ (1-r)a \right] \right\} \qquad \text{where } a=\dfrac{1}{n} \ln (p_1/p_0) \nonumber \]

    En general, el umbral\(p_1/p_0\) puede ser reemplazado por un umbral arbitrario\(η\). Como se ilustra en la Figura 7.10, la pendiente\(\gamma_1'(r) = \frac{1}{n} \ln(η)\) a la que se produce el límite optimizado aumenta con\(η\), variando de\(\gamma'(0) = \mathsf{E} [Z | H=1]\) at\( r = 0\) a\(\gamma'(1) = \mathsf{E} [Z | H=0]\) at\( r = 1\). Se considera que el equilibrio entre los dos exponentes de error varía como los dos extremos de una sierra de cerco invertida. Uno podría en principio lograr una magnitud aún mayor de exponente para\(\text{Pr}\{(\} e | H=1)\) mediante el uso\(r > 1\), pero esto\(\text{Pr}\{e | H=0\}\) sería algo tonto ya que entonces estaría muy cerca de 1 y normalmente tendría más sentido simplemente decidir\(H = 1\) sin mirar los datos observados en absoluto.

    Podemos ver la compensación de los exponentes anteriores como una forma de gran desviación del criterio de Neyman-Pearson. Es decir, en lugar de fijar el valor permisible de\(\text{Pr}\{e | H=1\}\) y elegir una prueba para minimizar\(\text{Pr}\{e | H=0\}\), fijamos el exponente permisible para\(\text{Pr}\{e | H=1\}\) y luego optimizamos el exponente para\(\text{Pr}\{e | H=1\}\). Esto es esencialmente lo mismo que la prueba de Neyman-Pearson, y es una prueba umbral como antes, pero nos permite ignorar la solución exacta del problema de Neyman-Pearson y enfocarnos en los exponentes exponencialmente apretados.

    Decisiones secuenciales para hipótesis binarias

    El sentido común nos dice que debería ser valioso tener la capacidad de hacer observaciones adicionales cuando las observaciones actuales no conducen a una elección clara. Con tal habilidad, tenemos 3 opciones posibles al final de cada observación: elegir\( \hat{H} = 1\)\(\hat{H} =0\), elegir o continuar con observaciones adicionales. Es evidente que necesitamos un tiempo de parada\(J\) para decidir cuándo parar. Suponemos por el momento que la detención ocurre con probabilidad 1, tanto bajo hipótesis como\(H = 0\),\(H = 1\) y el indicador rv\(\mathbb{I}_{J=n}\) para cada uno\(n ≥ 1\) es función de\(Z_1, . . . , Z_n\).

    Dado\(H = 1\), la secuencia de LLR's {\(S_n; n ≥ 1\)} (donde\( S_n =\sum^n_{i=1} Z_i\)) es una caminata aleatoria. Supongamos por ahora que la regla de parada es detenerse cuando la caminata aleatoria cruza un umbral 2 en\(\alpha > 0\) o un umbral en\(β< 0\). Dado\(H = 0\), también\(S_n = \sum^n_{i=1} Z_n\) es una caminata aleatoria (con una medida de probabilidad diferente). Se debe utilizar la misma regla de detención, ya que la decisión de detenerse en\(n\) puede basarse únicamente en\(Z_1, . . . , Z_n\) y no en el conocimiento de\(H\). Vimos que la caminata aleatoria basada en\(H = 0\) usos probabilidades inclinadas de las basadas en\(H = 1\), hecho que aquí es interesante pero no necesario.

    Suponemos que cuando se produce la detención, la decisión\(\hat{h} = 0\) se toma si\( S_J ≥ α\) y\(\hat{h} = 1\) se toma si\(S_J ≤ β\). Dado eso\( H = 1\), entonces se hace un error si\(S_J ≥ α\). Así, usando la distribución de probabilidad para\(H = 1\), aplicamos (7.5.9), junto con\(r^∗ = 1\), para obtener

    \[ \text{Pr}\{ e|H=1\} \, = \, \text{Pr}\{ S_J \geq \alpha |H=1\} \, \leq \, \exp-\alpha \nonumber \]

    Del mismo modo, condicionalmente\(H = 0\), se comete un error si el umbral at\(β\) se cruza antes que en\(α\) y la probabilidad de error es

    \[\text{Pr} \{e|H=0\} \, = \, \text{Pr} \{S_J \leq \beta |H=0 \} \, \leq \, \exp \beta \nonumber \]

    Las probabilidades de error se pueden hacer tan pequeñas como se desee aumentando las magnitudes de\(α\) y\(β\), pero el costo de aumentar\(α\) es aumentar el número de observaciones requeridas cuando\(H = 0\). De la igualdad de Wald,

    \[ \mathsf{E} [J|H=0] \, = \, \dfrac{\mathsf{E}[S_J|H=0]}{\mathsf{E}[Z|H=0]} \,\approx\, \dfrac{\alpha+\mathsf{E}[\text{overshoot}]}{\mathsf{E}[Z|H=0]} \nonumber \]

    En la aproximación, hemos ignorado la posibilidad de\(S_J\) cruzar el umbral en\(β\) condicional\(H = 0\) puesto que se trata de un evento de probabilidad muy pequeña cuando\(α\) y\(β\) tienen grandes magnitudes. Así vemos que el número esperado de observaciones (dado\(H = 0\)) es esencialmente lineal en\(α\).

    A continuación nos preguntamos qué se ha ganado cuantitativamente utilizando aquí el procedimiento de decisión secuencial. Supongamos que usamos una prueba de longitud fija con\(n = α/\mathsf{E} [Z | H=0]\). Refiriéndose a la Figura 7.10, vemos que si elegimos la pendiente\(a = \gamma'(1)\), entonces el límite de Chernoff (exponencialmente apretado) viene dado por\(e^{−α}\), pero el exponente on\(\text{Pr}\{e | H=0\}\) es 0.\(\text{Pr}\{e | H=1\}\) En otras palabras, al usar una prueba secuencial como se describe aquí, obtenemos simultáneamente el exponente de error para\(H = 1\) eso proporcionaría una prueba fija si renunciamos por completo a un exponente de error para\(H = 0\), y viceversa. 3

    Una pregunta final que hay que hacer es si alguna mejora sustancial en este procedimiento de decisión secuencial resultaría de dejar que los umbrales fueran\(α\) y\(β\) variaran con el número de observaciones. Suponiendo que sólo nos preocupa el número esperado de observaciones, la respuesta es no. No vamos a llevar a cabo este argumento aquí, sino que consiste en utilizar el encuadernado de Chernoff en función del número de observaciones. Esto demuestra que existe un número típico de observaciones en las que ocurren la mayoría de los errores, y los cambios en los umbrales en otros lugares pueden aumentar la probabilidad de error, pero no disminuirla sustancialmente.

    Distribución conjunta del tiempo de cruce y barrera

    A continuación miramos\(\text{Pr}\{J ≥ n, \, S_J ≥ α\}\), donde nuevamente asumimos eso\(\overline{X} < 0\) y eso\(\gamma (^r∗) = 0\) para algunos\(r^∗ > 0\). Para cualquiera\(r\) en la región donde\(\gamma \ref{r} ≤ 0 \, (i.e., \, 0 ≤ r ≤ r^∗)\), tenemos\(−J\gamma \ref{r} ≥−n\gamma (r)\) para\(J ≥ n\). Así, desde la identidad de Wald, tenemos

    \[ \begin{align} &1 \geq \mathsf{E}[\exp [rS_J-J\gamma(r)]|J \geq n, \, S_J \geq \alpha ] \text{ Pr}\{ J \geq n, \, S_J \geq \alpha \} \\ &\qquad \geq\exp[r\alpha-n\gamma (r)] \text{Pr}\{J \geq n, \, S_J \geq \alpha \} \nonumber \\ &\text{Pr}\{ J \geq n, \, S_J \geq \alpha \} \leq \exp [-r\alpha+n\gamma (r)]; \qquad \text{for } r\in [0,r^*] \end{align} \nonumber \]

    Como esto es vago para todos\(r ∈ (0, r^∗]\), podemos obtener el límite más apretado de esta forma minimizando el lado derecho de (7.5.21). Esta es la misma minimización (a excepción de la restricción\(r ≤ r^∗\)) que en las Figuras 7.7. Supongamos que\(r^∗ < r_+\) (\(i.e.\), que la situación excepcional 4 de la Figura 7.8) no se da. Definir\(n^∗\) como\(α/\gamma'(r^∗)\). El resultado es entonces

    \[ \text{Pr} \{ J \geq n, S_J \geq \alpha \} \leq \left\{ \begin{array} \exp \exp [n\gamma (r_o) -r_o\alpha] \qquad \text{for } n>n^*, \, \alpha/n = \gamma' (r_o) \\ \\ \exp [-r^*\alpha ] \qquad \qquad n \leq n^* \end{array} \right. \nonumber \]

    La interpretación de (7.5.22) es que\(n^∗\) es una estimación del valor típico de\(J\) dado que\(α\) se cruza el umbral at. Para\(n\) mayor que este valor típico, (7.5.22) proporciona un límite más ajustado\(\text{Pr}\{J ≥ n, S_J ≥ α\}\) que el límite\(\text{Pr}\{S_J ≥ α\}\) en (7.5.9), mientras que (7.5.22) no proporciona nada nuevo para\(n ≤ n^∗\). En la Sección 7.8, derivaremos el resultado ligeramente más fuerte que también\(\text{Pr}\left\{ \bigcup_{i\geq n} [S_i ≥ α] \right\}\) está delimitado por la parte superior por el lado derecho de (7.5.22).

    Un límite superior casi idéntico a se\(\text{Pr}\{J ≤ n,\, S_J ≥ α\}\) puede encontrar (de nuevo asumiendo que\(r^∗ < r_+\)) usando la identidad de Wald para\(r > r^∗\). Aquí\(\gamma \ref{r} > 0\), así que\(−J\gamma \ref{r} ≥−n\gamma (r)\) para\(J ≤ n\). El resultado es

    \[ \text{Pr}\{J \leq n, S_J \geq \alpha \} \leq \left\{ \begin{array} \exp \exp[n\gamma (r_o)-r_o\alpha ] \quad \text{for } n<n^*, \, \alpha /n=\gamma' (r_o) \\ \quad \\ \exp [-r^*\alpha] \qquad \qquad n \geq n^* \end{array} \right. \nonumber \]

    Esto fortalece la interpretación de\(n^∗\) como el valor típico de\(J\) condicional a cruzar el umbral en\(α\). Es decir, (7.5.23) proporciona información sobre la cola inferior de la distribución de\(J\) (condicional\(S_J ≥ α\)), mientras que (7.5.22) proporciona información sobre la cola superior.

    ___________________________________

    1. Esta restricción es bastante artificial y se hace simplemente para posponer cualquier consideración de generalizaciones hasta discutir las martingales.
    2. Es lamentable que la palabra 'umbral' tenga un significado universalmente aceptado para caminatas aleatorias (\(i.e.\), el significado que estamos usando aquí), y la palabra 'prueba umbral' tenga un significado universalmente aceptado para la prueba de hipótesis. Detener cuando\(S_n\) cruza\(α\) o\(β\) puede ser visto como una extensión de una prueba de umbral de prueba de hipótesis en el sentido de que tanto el ensayo de detención como la decisión se basan únicamente en el LLR, y se basa en el cruce de LLR ya sea un umbral positivo o negativo, pero los resultados sobre las pruebas de umbral en la Sección 7.3 no son necesariamente válidas para esta extensión.
    3. En el contexto de la comunicación, se utilizan reglas de decisión para detectar datos transmitidos secuencialmente. El uso de una regla de decisión secuencial generalmente requiere retroalimentación de receptor a transmisor, y también requiere una velocidad de transmisión variable. Así, las reducciones sustanciales en la probabilidad de error van acompañadas de una complejidad sustancial del sistema.
    4. La situación excepcional donde\(\gamma (r)\) es negativa para\(r ≤ r_+\) y discontinua en\(r^∗ = r_+ ,\, i.e.\), la situación en la Figura 7.8, será tratada en los ejercicios, y es bastante diferente al caso aquí. En particular, como se puede ver en la figura, el límite Chernoff optimizado\(\text{Pr}\{ S_n ≥ α\}\) se optimiza en\(n = 1\).

    This page titled 7.5: Umbrales, reglas de detención e identidad de Wald is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Robert Gallager (MIT OpenCourseWare) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.