Saltar al contenido principal
LibreTexts Español

17.3: Tiempos de Parada

  • Page ID
    151834
  • \( \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}}\)

    \(\renewcommand{\P}{\mathbb{P}}\)\(\newcommand{\E}{\mathbb{E}}\)\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\Z}{\mathbb{Z}}\)\(\newcommand{\bs}{\boldsymbol}\)

    Teoría Básica

    Al igual que en la Introducción, comenzamos con un proceso estocástico\( \bs{X} = \{X_t: t \in T\} \) en un espacio de probabilidad subyacente\( (\Omega, \mathscr{F}, \P) \), teniendo espacio de estado\( \R \), y donde el conjunto de índices\( T \) (que representa el tiempo) es\( \N \) (tiempo discreto) o\( [0, \infty) \) (tiempo continuo). A continuación, tenemos una filtración\(\mathfrak{F} = \{\mathscr{F}_t: t \in T\} \), y asumimos que\( \bs{X} \) se adapta a\( \mathfrak{F} \). Así\( \mathfrak{F} \) es una familia creciente de sub\( \sigma \) -álgebras de\( \mathscr{F} \) y\( X_t \) es medible con respecto a\( \mathscr{F}_t \) for\( t \in T \). Pensamos en\( \mathscr{F}_t \) ello como la colección de eventos hasta el momento\( t \in T \). Suponemos que\( \E\left(\left|X_t\right|\right) \lt \infty \), para que la media de\( X_t \) exista como número real, para cada uno\( t \in T \). Finalmente, en tiempo continuo donde\( T = [0, \infty) \), hacemos la suposición estándar de que\( \bs X \) es correcto continuo y tiene límites izquierdos, y que la filtración\( \mathfrak F \) es correcta continua y completa.

    Nuestro objetivo general en esta sección es ver si algunas de las propiedades importantes de la martingala se conservan si el tiempo determinista\( t \in T \) es reemplazado por un tiempo de detención (aleatorio). Recordemos que un tiempo aleatorio\( \tau \) con valores adentro\( T \cup \{\infty\} \) es un tiempo de detención relativo a\( \mathfrak F \) if\( \{\tau \le t\} \in \mathscr{F}_t \) for\( t \in T \). Entonces un tiempo de parada es un tiempo aleatorio que no requiere que veamos hacia el futuro. Es decir, podemos decir si a\( \tau \le t \) partir de la información disponible en el momento\( t \). A continuación recordemos que la\( \sigma \) -álgebra asociada con el tiempo\( \tau \) de parada\( \mathscr{F}_\tau \) es So es la colección de eventos hasta el tiempo aleatorio\[ \mathscr{F}_\tau = \left\{A \in \mathscr{F}: A \cap \{\tau \le t\} \in \mathscr{F}_t \text{ for all } t \in T\right\} \]\( \tau \) así como lo\( \mathscr{F}_t \) es la colección de eventos hasta el tiempo determinista\( t \in T \). En términos de que un jugador juegue una secuencia de juegos, el tiempo que el jugador decida dejar de jugar debe ser un tiempo de parada, y de hecho esta interpretación es el origen del nombre. Es decir, el momento en que el jugador decide dejar de jugar sólo puede depender de la información que el jugador tenga hasta ese momento.

    Detención opcional

    La ecuación básica de martingala\( \E(X_t \mid \mathscr{F}_s) = X_s \) para\( s, \, t \in T \) con se\( s \le t \) puede generalizar reemplazando ambos\( s \) y\( t \) por tiempos de parada acotados. El resultado se conoce como el teorema de detención opcional de Doob y se nombra nuevamente por Joseph Doob. Supongamos que\( \bs X = \{X_t: t \in T\} \) satisface los supuestos básicos anteriores con respecto a la filtración\( \mathfrak F = \{\mathscr{F}_t: t \in T\} \)

    Supongamos que están delimitados los tiempos de detención relativos a\( \mathfrak F \) con\( \rho \le \tau \).

    1. Si\( \bs X \) es una martingala relativa a\( \mathfrak F \) entonces\( \E(X_\tau \mid \mathscr{F}_\rho) = X_\rho \).
    2. Si\( \bs X \) es una sub-martingala relativa a\( \mathfrak F \) entonces\( \E(X_\tau \mid \mathscr{F}_\rho) \ge X_\rho \).
    3. Si\( \bs X \) es una super-martingala relativa a\( \mathfrak F \) entonces\( \E(X_\tau \mid \mathscr{F}_\rho) \le X_\rho \).
    Prueba en tiempo discreto
    1. Supongamos que\( \tau \le k \) donde\( k \in \N_+ \) y vamos\( A \in \mathscr{F}_\tau \). Para\( j \in \N \) con\( j \le k \),\( A \cap \{\tau = j\} \in \mathscr{F}_j \). De ahí por la propiedad martingala,\[ \E(X_k ; A \cap \{\tau = j\}) = \E(X_j ; A \cap \{\tau = j\}) = \E(X_\tau ; A \cap \{\tau = j\})\] Dado que\( k \) es un límite superior en\( \tau \), los eventos\( A \cap \{\tau = j\} \) para la\( j = 0, 1, \ldots, k \) partición\( A \), por lo que sumando la ecuación mostrada sobre\( j \) da\( \E(X_k ; A) = \E(X_\tau ; A) \). Por definición de expectativa condicional,\( \E(X_k \mid \mathscr{F}_\tau) = X_\tau \). Pero ya que también\( k \) es un límite superior para\( \rho \) nosotros también tenemos\( \E(X_k \mid \mathscr{F}_\rho) = X_\rho \). Finalmente usando la propiedad de la torre tenemos\[ X_\rho = \E(X_k \mid \mathscr{F}_\rho) = \E[\E(X_k \mid \mathscr{F}_\rho) \mid \mathscr{F}_\tau] = \E[\E(X_k \mid \mathscr{F}_\tau) \mid \mathscr{F}_\rho] = \E(X_\tau \mid \mathscr{F}_\rho)\]
    2. Si\( \bs X \) es una sub-martingala, entonces por el teorema de descomposición de Doob,\( X_n = Y_n + Z_n \) para\( n \in \N \) donde\( \bs Y = \{Y_n: n \in \N\} \) es una martingala relativa a\( \mathfrak F \) y\( \bs Z = \{Z_n: n \in \N\} \) está aumentando y es predecible en relación con\( \mathfrak F \). Entonces\[ \E(X_\tau \mid \mathscr{F}_\rho) = \E(Y_\tau \mid \mathscr{F}_\rho) + \E(Z_\tau \mid \mathscr{F}_\rho)\] Pero\( \E(Y_\tau \mid \mathscr{F}_\rho) = Y_\rho \) por la parte (a) y desde que\( \bs Z \) va en aumento,\( \E(Z_\tau \mid \mathscr{F}_\rho) \ge \E(Z_\rho \mid \mathscr{F}_\rho) = Z_\rho \). De ahí\( \E(X_\tau \mid \mathscr{F}_\rho) \ge X_\rho \).
    3. La prueba cuando\( \bs X \) es una super-martingala es igual que (b), excepto que el proceso\( \bs Z \) está disminuyendo.
    Prueba en tiempo continuo

    Supongamos que\( \bs X \) es una martingala. Tenemos que demostrar eso\( \E(X_\tau; A) = \E(X_\rho; A) \) para cada uno\( A \in \mathscr{F}_\rho \). Dejar\( \rho_n = \lceil 2^n \rho \rceil / 2^n \) y\( \tau_n = \lceil 2^n \tau \rceil / 2^n \) para\( n \in \N \). Los tiempos de parada\( \rho_n \) y valores de\( \tau_n \) toma en un conjunto contable\( T_n \) para cada uno\( n \in \N \), y\( \rho_n \downarrow \rho \) y\( \tau_n \downarrow \tau \) como\( n \to \infty \). El proceso\( \{X_t: t \in T_n\} \) es una martingala de tiempo discreto para cada uno\( n \in \N \). Por la correcta continuidad de\( \bs X \),\[ X_{\rho_n} \to X_\rho, \; X_{\tau_n} \to X_\tau \text{ as } n \to \infty \] Supongamos siguiente que\( \tau \le c \) donde\( c \in (0, \infty) \) así que\( \rho \le c \) también. Entonces\( \rho_n \le c + 1 \) y\( \tau_n \le c + 1 \) para\( n \in \N \) así los tiempos de parada discretos se acoplan uniformemente. A partir de la versión discreta del teorema,\( X_{\rho_n} = \E\left(X_{c+1} \mid \mathscr{F}_{\rho_n}\right) \) y\( X_{\tau_n} = \E\left(X_{c+1} \mid \mathscr{F}_{\tau_n}\right) \) para\( n \in \N \). Se deduce entonces que las secuencias\( \left\{X_{\rho_n}: n \in \N\right\} \) y\( \left\{X_{\tau_n}: n \in \N\right\} \) son integrables uniformemente y por tanto\( X_{\rho_n} \to X_\rho \) y\( X_{\tau_n} \to X_\tau \) como\( n \to \infty \) en media así como con probabilidad 1. Ahora vamos\( A \in \mathscr{F}_\rho \). Desde\( \rho \le \rho_n \),\( \mathscr{F}_\rho \subseteq \mathscr{F}_{\rho_n} \) y así\( A \in \mathscr{F}_{\rho_n} \) para cada uno\( n \in \N \). Por el teorema en tiempo discreto,\[ \E\left(X_{\tau_n}; A\right) = \E\left(X_{\rho_n}: A\right), \quad n \in \N \] Dejar\( n \to \infty \) da\( \E(X_\tau; A) = \E(X_\rho; A) \). Las pruebas en las partes (b) y (c) son como en el tiempo discreto.

    El supuesto de que los tiempos de parada están acotados es crítico. A continuación se da un contraejemplo cuando esta suposición no se mantiene. Aquí hay un par de corolarios simples:

    Supongamos de nuevo eso\( \rho \) y\( \tau \) están delimitados los tiempos de detención relativos a\( \mathfrak F \) con\( \rho \le \tau \).

    1. Si\( \bs X \) es una martingala relativa a\( \mathfrak F \) entonces\( \E(X_\tau) = \E(X_\rho) \).
    2. Si\( \bs X \) es una sub-martingala relativa a\( \mathfrak F \) entonces\( \E(X_\tau) \ge \E(X_\rho) \).
    3. Si\( \bs X \) es una super-martingala relativa a\( \mathfrak F \) entonces\( \E(X_\tau) \le \E(X_\rho) \).
    Prueba

    Recordemos eso\( \E(X_\tau) = \E[\E(X_\tau \mid \mathscr{F}_\rho)] \), por lo que los resultados son inmediatos del teorema de detención opcional.

    Supongamos que\( \tau \) es un tiempo de detención limitado relativo a\( \mathfrak F \).

    1. Si\( \bs X \) es una martingala relativa a\( \mathfrak F \) entonces\( \E(X_\tau) = \E(X_0) \).
    2. Si\( \bs X \) es una sub-martingala relativa a\( \mathfrak F \) entonces\( \E(X_\tau) \ge \E(X_0) \).
    3. Si\( \bs X \) es una super-martingala relativa a\( \mathfrak F \) entonces\( \E(X_\tau) \le \E(X_0) \).

    La Martingala Parada

    Para nuestra próxima discusión, primero debemos recordar cómo detener un proceso estocástico en un momento de parada.

    Supongamos que\( \bs X \) satisface los supuestos anteriores y que\( \tau \) es un tiempo de parada relativo a la filtración\( \mathfrak F \). El proceso detenido\( X^\tau = \{X^\tau_t: t \in [0, \infty)\} \) se define por\[ X^\tau_t = X_{t \wedge \tau}, \quad t \in [0, \infty) \]

    Detalles

    En tiempo continuo, nuestros supuestos estándar aseguran que\( \bs{X}^\tau \) es un proceso estocástico válido y se adapta a\( \mathfrak F \). Es decir,\( X^\tau_t \) es mensurable con respecto a\( \mathscr{F}_t \) para cada uno\( t \in [0, \infty) \). Además, también\( \bs{X}^\tau \) es derecha continua y tiene límites izquierdos.

    Entonces\( X^\tau_t = X_t \) si\( t \lt \tau \) y\( X^\tau_t = X_\tau \) si\( t \ge \tau \). En particular, tenga en cuenta que\( X^\tau_0 = X_0 \). Si\( X_t \) es la fortuna de un jugador en el momento\( t \in T \), entonces\( X^\tau_t \) es la fortuna revisada en el\( t \) momento en\( \tau \) que es el tiempo de parada del jugador. Nuestro siguiente resultado, conocido como el teorema de detención elemental, es que una martingala detenida en un tiempo de parada sigue siendo una martingala.

    Supongamos nuevamente que\( \bs X \) satisface los supuestos anteriores, y que\( \tau \) es un tiempo de parada relativo a\( \mathfrak F \).

    1. Si\( \bs X \) es una martingala relativa a\( \mathfrak F \) entonces así es\( \bs{X}^\tau \).
    2. Si\( \bs X \) es una sub-martingala relativa a\( \mathfrak F \) entonces así es\( \bs{X}^\tau \).
    3. Si\( \bs X \) es una super-martingala relativa a\( \mathfrak F \) entonces así es\( \bs{X}^\tau \).
    Prueba general

    Si\( s, \, t \in T \) con\( s \le t \) entonces\( \tau \wedge s \) y\( \tau \wedge t \) están delimitados los tiempos de parada con\( \tau \wedge s \le \tau \wedge t \). Por lo que los resultados se deduce inmediatamente del teorema de detención opcional anterior.

    Prueba especial en tiempo discreto

    En tiempo discreto, hay una prueba directa simple usando la transformada martingala. Entonces supongamos que\( T = \N \) y definamos el proceso\( \bs Y = \{Y_n: n \in \N_+\} \)\[ Y_n = \bs{1}(\tau \ge n) = 1 - \bs{1}(\tau \le n - 1), \quad n \in \N_+ \] por Por definición de un tiempo de parada,\( \{\tau \le n - 1\} \in \mathscr{F}_{n-1} \) para\( n \in \N_+ \), así el proceso\( \bs Y \) es predecible. Por supuesto,\( \bs Y \) es un proceso acotado, no negativo también. La transformación de\( \bs X \) por\( \bs Y \) es\[ (\bs Y \cdot \bs X)_n = X_0 + \sum_{k=1}^n Y_k (X_k - X_{k-1}) = X_0 + \sum_{k=1}^n \bs{1}(\tau \ge k)(X_k - X_{k-1}), \quad n \in \N_+ \] Pero tenga en cuenta que\( X^\tau_k - X^\tau_{k-1} = X_k - X_{k-1} \) si\( \tau \ge k \) y\( X^\tau_k - X^\tau_{k-1} = X_\tau - X_\tau = 0 \) si\( \tau \lt k \). Es decir,\( X^\tau_k - X^\tau_{k-1} = \bs{1}(\tau \ge k)(X_k - X_{k-1}) \). De ahí\[ (\bs Y \cdot \bs X)_n = X_0 + \sum_{k=1}^n (X^\tau_k - X^\tau_{k-1}) = X_0 + X^\tau_n - X^\tau_0 = X^\tau_n, \quad n \in \N_+ \] Pero si\( \bs X \) es una martingala (sub-martingala) (super-martingala), entonces también lo es la transformación\( \bs Y \cdot \bs X = \bs{X}_\tau\).

    El teorema de detención elemental es una mala noticia para el jugador que juega una secuencia de juegos. Si los juegos son justos o desfavorables, entonces ningún tiempo de parada, independientemente de lo hábilmente diseñado, puede ayudar al jugador. Desde que una martingala detenida sigue siendo una martingala, la propiedad media tiene.

    Supongamos nuevamente que\( \bs X \) satisface los supuestos anteriores, y que\( \tau \) es un tiempo de parada relativo a\( \mathfrak F \). Vamos\( t \in T \).

    1. Si\( \bs X \) es una martingala relativa a\( \mathfrak F \) entonces\( \E(X_{t \wedge \tau}) = E(X_0) \)
    2. Si\( \bs X \) es una sub-martingala relativa a\( \mathfrak F \) entonces\( \E(X_{t \wedge \tau}) \ge E(X_0) \)
    3. Si\( \bs X \) es una super-martingala relativa a\( \mathfrak F \) entonces\( \E(X_{t \wedge \tau}) \le E(X_0) \)

    Detención opcional en tiempo discreto

    Un simple corolario del teorema de detención opcional es que si\( \bs X \) es una martingala y\( \tau \) un tiempo de parada acotado, entonces\( \E(X_\tau) = \E(X_0) \) (con las desigualdades apropiadas si\( \bs X \) es una sub-martingala o una super-martingala). Nuestra siguiente discusión se centra en otras condiciones que dan estos resultados en tiempo discreto. Supongamos que\( \bs X = \{X_n: n \in \N\} \) satisface los supuestos básicos anteriores con respecto a la filtración\( \mathfrak F = \{\mathscr{F}_n: n \in \N\} \), y que\( \tau \) es un tiempo de parada relativo a\( \mathfrak F \).

    Supongamos que\( \left|X_n\right| \) está acotado uniformemente en\( n \in \N \) y que\( \tau \) es finito.

    1. Si\( \bs X \) es una martingala entonces\( \E(X_\tau) = \E(X_0) \).
    2. Si\( \bs X \) es una sub-martingala entonces\( \E(X_\tau) \ge \E(X_0) \).
    3. Si\( \bs X \) es una super-martingala entonces\( \E(X_\tau) \le \E(X_0) \).
    Prueba

    Supongamos que\( \bs X \) es una super-martingala. Las pruebas para una sub-martingala son similares, y luego los resultados siguen de inmediato para una martingala. La herramienta principal es la propiedad media anterior para la súper martingala detenida:\[ \E(X_{\tau \wedge n}) \le \E(X_0), \quad n \in \N \] Ya que\( \tau \lt \infty \) con probabilidad 1,\( \tau \wedge n \to \tau \) como\( n \to \infty \), también con probabilidad 1. Ya que\( |X_n| \) está acotado en\( n \in T \), se deduce del teorema de convergencia acotada que\( \E(X_{\tau \wedge n}) \to \E(X_\tau) \) como\( n \to \infty \). Dejando\( n \to \infty \) entrar la ecuación mostrada da\( \E(X_\tau) \le \E(X_0) \).

    Supongamos que\( \left|X_{n+1} - X_n\right| \) está acotado uniformemente en\( n \in \N \) y eso\( \E(\tau) \lt \infty \).

    1. Si\( \bs X \) es una martingala entonces\( \E(X_\tau) = \E(X_0) \).
    2. Si\( \bs X \) es una sub-martingala entonces\( \E(X_\tau) \ge \E(X_0) \).
    3. Si\( \bs X \) es una super-martingala entonces\( \E(X_\tau) \le \E(X_0) \).
    Prueba

    Supongamos que\( \bs X \) es una super-martingala. Las pruebas para una sub-martingala son similares, y luego los resultados siguen inmediatamente para una martingala. La herramienta principal una vez más es la propiedad media anterior para la súper martingala detenida:\[ \E(X_{\tau \wedge n}) \le \E(X_0), \quad n \in \N \] Supongamos que\( |X_{n+1} - X_n| \le c \) donde\( c \in (0, \infty) \). Entonces\[ |X_{\tau \wedge n} - X_0| = \left|\sum_{k=1}^{\tau \wedge n} (X_k - X_{k-1})\right| \le \sum_{k=1}^{\tau \wedge n} |X_k - X_{k-1}| \le c (\tau \wedge n) \le c \tau \] De ahí\( |X_{\tau \wedge n}| \le c \tau + |X_0| \). Ya que\( \E(\tau) \lt \infty \) sabemos que\( \tau \lt \infty \) con probabilidad 1, así como antes,\( \tau \wedge n \to \tau \) como\( n \to \infty \). También\(\E(c \tau + |X_0|) \lt \infty\) así por el teorema de convergencia dominada,\( \E(X_{\tau \wedge n}) \to \E(X_\tau) \) como\( n \to \infty \). Así que de nuevo dejando\( n \to \infty \) entrar la ecuación mostrada da\( \E(X_\tau) \le \E(X_0) \).

    Volvamos a nuestra interpretación original de una martingala\( \bs{X} \) que representa la fortuna de un jugador jugando juegos justos. El jugador podría optar por dejar de fumar en un momento aleatorio\( \tau \), pero\( \tau \) tendría que ser un tiempo de parada, basado en la información del jugador codificada en la filtración\( \mathfrak{F} \). Bajo las condiciones del teorema, ningún esquema de este tipo puede ayudar al jugador en términos de valor esperado.

    Ejemplos y Aplicaciones

    El simple paseo aleatorio

    Supongamos que\( \bs{V} = (V_1, V_2, \ldots) \) es una secuencia si es independiente, se distribuyen idénticamente variables aleatorias con\( \P(V_i = 1) = p \) y\( \P(V_i = -1) = 1 - p \) para\( i \in \N_+ \), donde\( p \in (0, 1) \). Dejar\( \bs{X} = (X_0, X_1, X_2, \ldots)\) ser el proceso de suma parcial asociado con\( \bs{V} \) lo que\[ X_n = \sum_{i=1}^n V_i, \quad n \in \N \] Entonces\( \bs{X} \) es el simple paseo aleatorio con parámetro\( p \). En cuanto al juego, nuestro jugador juega una secuencia de juegos independientes e idénticos, y en cada juego, gana 1€ con probabilidad\( p \) y pierde 1€ con probabilidad\( 1 - p \). Así\( X_n \) es el total de ganancias netas del jugador después de\( n \) los juegos. Mostramos en la Introducción que\( \bs X \) es una martingala si\( p = \frac{1}{2} \) (el caso justo), una sub-martingala si\( p \gt \frac{1}{2} \) (el caso favorable), y una super-martingala si\( p \lt \frac{1}{2} \) (el caso injusto). Ahora, para\( c \in \Z \), vamos\[ \tau_c = \inf\{n \in \N: X_n = c\} \] donde como de costumbre,\( \inf(\emptyset) = \infty \). Así\( \tau_c \) es la primera vez que llega la fortuna del jugador\( c \). ¿Y si el jugador simplemente sigue jugando hasta que sus ganancias netas sean algún número positivo especificado (digamos €\(1\,000\,000 \))? ¿Es esa una estrategia viable?

    Supongamos eso\( p = \frac{1}{2} \) y aquello\( c \in \N_+ \).

    1. \( \P(\tau_c \lt \infty) = 1 \)
    2. \( \E\left(X_{\tau_c}\right) = c \ne 0 = \E(X_0) \)
    3. \( \E(\tau_c) = \infty \)
    Prueba

    Las partes (a) y (c) se mantienen ya que\( \bs X \) es una cadena recurrente nula de Markov. La parte b) se desprende de (a) ya que trivialmente\( X_{\tau_c} = c \) si\( \tau_c \lt \infty \).

    Tenga en cuenta que la parte (b) no contradice el teorema de detención opcional debido a la parte (c). La estrategia de esperar hasta que las ganancias netas alcancen un objetivo específico\( c \) es insostenible. Supongamos ahora que el jugador juega hasta que las ganancias netas o bien caen a un número negativo especificado (una pérdida que puede tolerar) o llegar a un número positivo especificado (un gol que espera alcanzar).

    Supongamos otra vez eso\( p = \frac{1}{2} \). Para\( a, \, b \in \N_+ \), vamos\( \tau = \tau_{-a} \wedge \tau_b \). Entonces

    1. \( \E(\tau) \lt \infty \)
    2. \( \E(X_\tau) = 0 \)
    3. \( \P(\tau_{-a} \lt \tau_b) = b / (a + b) \)
    Prueba
    1. Vamos a dejar\( X_0 \) tener un valor arbitrario en el conjunto\( \{-a, -a + 1, \ldots, b - 1, b\} \), para que podamos usar técnicas de cadena de Markov. Dejemos que\( m(x) = \E(\tau \mid X_0 = x) \)\( x \) en este set. Acondicionamiento en el primer estado y uso de la propiedad Markov que tenemos\[ m(x) = 1 + \frac{1}{2} m(x - 1) + \frac{1}{2} m(x + 1), \quad x \in \{-a + 1, \ldots, b - 1\} \] con condiciones de límite\( m(-a) = m(b) = 0 \). La relación lineal de recurrencia puede resolverse explícitamente, pero lo único que nos importa es el hecho de que la solución es finita.
    2. Se aplica el teorema de muestreo opcional, entonces\( \E(X_\tau) = \E(X_0) = 0 \).
    3. Dejemos\( q = \P(\tau_{-a} \lt \tau_b) \) que eso\( 1 - q = \P(\tau_b \lt \tau_{-a}) \). Por definición,\( X_\tau = -a \) si\( \tau_{-a} \lt \tau_b \) y\( X_\tau = b \) si\( \tau_b \lt \tau_{-a} \). Entonces de (b),\( q(-a) + (1 - q) b = 0 \) y por lo tanto\( q = b / (a + b) \).

    Entonces apostar hasta que las ganancias netas caigan\( -a \) o alcancen\( b \) es una estrategia viable, pero por desgracia ha esperado valor 0. Aquí hay otro ejemplo que muestra que la primera versión del teorema de muestreo opcional puede fallar si los tiempos de parada no están acotados.

    Supongamos otra vez eso\( p = \frac{1}{2} \). Déjalo\( a, \, b \in \N_+ \) con\( a \lt b \). Entonces\( \tau_a \lt \tau_b \lt \infty \) pero\[ b = \E\left(X_{\tau_b} \mid \mathscr{F}_{\tau_a} \right) \ne X_{\tau_a} = a \]

    Prueba

    Ya que\( X_0 = 0 \), el proceso\( \bs X \) debe llegar\( a \) antes de llegar\( b \). Como antes,\( \tau_b \lt \infty \) pero\( \E(\tau_b) = \infty \) ya que\( \bs X \) es una cadena recurrente nula de Markov.

    Este resultado no contradice el teorema de detención opcional ya que los tiempos de parada no están acotados.

    Ecuación de Wald

    La ecuación de Wald, llamada así por Abraham Wald, es una fórmula para el valor esperado de la suma de un número aleatorio de variables aleatorias independientes, distribuidas idénticamente. Esto lo hemos considerado antes, en nuestra discusión sobre el valor esperado condicional y nuestra discusión de muestras aleatorias, pero la teoría de la martingala lleva a una prueba particularmente simple y elegante.

    Supongamos que\( \bs X = (X_n: n \in \N_+) \) es una secuencia de variables independientes, distribuidas idénticamente con media común\( \mu \in \R \). Si\( N \) es un tiempo de parada para\( \bs X \) con\( \E(N) \lt \infty \) entonces\[ \E\left(\sum_{k=1}^N X_k\right) = \E(N) \mu \]

    Prueba

    Dejar\( \mathfrak F \) denotar la filtración natural asociada con\( \bs X \). Vamos\( c = \E(|X_n|)\), para que por suposición,\( c \lt \infty \). Por último, vamos\[ Y_n = \sum_{k=1}^n (X_k - \mu) \, \quad n \in \N_+ \] Entonces\( \bs Y = (Y_n: n \in \N_+) \) es una martingala relativa a\( \mathfrak F \), con media 0. Tenga en cuenta que\[ \E(|Y_{n+1} - Y_n|) = \E(|X_{n+1} - \mu|) \le c + |\mu|, \quad n \in \N_+ \] De ahí se aplica una versión discreta del teorema de detención opcional y tenemos\( \E(Y_N) = 0 \). Por lo tanto\[ 0 = \E(Y_N) = \E\left[\sum_{k=1}^N (X_k - \mu)\right] = \E\left(\sum_{k=1}^N X_k - N \mu\right) = \E\left(\sum_{k=1}^N X_k\right) - \E(N) \mu \]

    Patrones en Ensayos Multinomiales

    Los patrones en ensayos multinomiales se estudiaron en el capítulo de Procesos de Renovación. Como suele ser el caso, las martingales proporcionan una solución más elegante. Supongamos que\( \bs{L} = (L_1, L_2, \ldots) \) es una secuencia de variables aleatorias independientes, distribuidas idénticamente, tomando valores en un conjunto finito\( S \), de modo que\( \bs{L} \) es una secuencia de ensayos multinomiales. Dejar\( f \) denotar la función de densidad de probabilidad común para que para una variable de ensayo genérica\( L \), tenemos\( f(a) = \P(L = a) \) para\( a \in S \). Asumimos que todos los resultados en\( S \) son realmente posibles, así que\( f(a) \gt 0 \) para\( a \in S \).

    En esta discusión, interpretamos\( S \) como un alfabeto, y escribimos la secuencia de variables en forma de concatenación, en\(\bs{L} = L_1 L_2 \cdots\) lugar de forma de secuencia estándar. Así, la secuencia es una cadena infinita de letras de nuestro alfabeto\( S \). Nos interesa la primera aparición de una subcadena finita particular de letras (es decir, una palabra o patrón) en la secuencia infinita. La siguiente definición simplificará la notación.

    Si\( \bs a = a_1 a_2 \cdots a_k \) es una palabra de longitud\( k \in \N_+ \) del alfabeto\( S \), defina\[ f(\bs{a}) = \prod_{i=1}^k f(a_i) \] así\( f(\bs a) \) es la probabilidad de que ensayos\( k \) consecutivos produzcan palabra\( \bs a \).

    Entonces, fije una palabra larga\( \bs a = a_1 a_2 \cdots a_k \)\( k \in \N_+ \) del alfabeto\( S \), y considere el número de pruebas\( N_{\bs a} \) hasta que\( \bs a \) se complete. Nuestro objetivo es el cómputo\( \nu(\bs a) = \E\left(N_{\bs a}\right) \). Esto lo hacemos lanzando el problema en términos de una secuencia de jugadores jugando juegos justos y luego usando el teorema de detención opcional anterior. Entonces supongamos que si un jugador apuesta\( c \in (0, \infty) \) por una letra\( a \in S \) en un juicio, entonces el jugador gana\( c / f(a) \) si\( a \) ocurre en ese juicio y gana 0 de lo contrario. El valor esperado de esta apuesta es\[ f(a) \frac{c}{f(a)} - c = 0 \] y así la apuesta es justa. Considera ahora un jugador con una fortuna inicial 1. Cuando empieza a jugar, apuesta 1 por\( a_1 \). Si gana, apostó toda su fortuna\( 1 / f(a_1) \) en el próximo juicio el\( a_2 \). Ella continúa de esta manera: mientras gane, apuesta toda su fortuna en el próximo juicio en la siguiente letra de la palabra, hasta que pierda o complete la palabra\( \bs a \). Por último, consideramos una secuencia de jugadores independientes que juegan esta estrategia, con el jugador\( i \) comenzando en juicio\( i \) para cada uno\( i \in \N_+ \).

    Para una palabra finita\( \bs a \) del alfabeto\( S \),\( \nu(\bs a) \) es el total de ganancias por todos los jugadores a la vez\( N_{\bs a} \).

    Prueba

    Vamos a\( X_n \) denotar las fortunas totales de todos los jugadores después del juicio\( n \in \N_+ \). Ya que todas las apuestas son justas,\( \bs X = \{X_n: n \in \N_+\} \) es una martingala con media 0. Mostraremos que se mantienen las condiciones en la versión discreta del teorema de muestreo opcional. Primero, considere bloques disjuntos de ensayos de longitud\( k \), es decir\[ \left((L_1, L_2, \ldots, L_k), (L_{k+1}, L_{k+2}, \ldots, L_{2 k}), \ldots\right) \] Let\( M_{\bs a} \) denotar el índice del primer bloque de ese tipo que forma la letra\( \bs a \). Esta variable tiene la distribución geométrica en el parámetro\( \N_+ \) con éxito\( f(\bs a) \) y así en particular,\( \E(M_\bs{a}) = 1 / f(\bs a) \). Pero claramente\( N_{\bs a} \le k M_{\bs a} \) así\( \nu(\bs a) \lt k / f(\bs a) \lt \infty \). Siguiente nota que todos los jugadores han dejado de jugar por el tiempo\( N \), tan claramente\( |X_{n+1} - X_n| \le 1 / f(a) \) para\( n \in \N_+ \). Entonces se aplica el teorema de detención opcional, y por lo tanto\( \E\left(X_{N_a}\right) = 0 \). Pero tenga en cuenta que también se\( \nu(\bs a) \) puede interpretar como la cantidad esperada de dinero invertido por los jugadores (1 unidad en cada momento hasta que el juego termine en el momento\( N_{\bs a} \)), y de ahí que esta también debe ser la ganancia total en el momento\( N_{\bs a} \) (que es determinista).

    Dado\( \bs a \), podemos calcular las ganancias totales con precisión. Por definición, los juicios\( N - k + 1, \ldots, N \) forman la palabra\( \bs a \) por primera vez. De ahí para\( i \le N - k \), jugador\( i \) pierde en algún momento. También por definición, la jugadora\( N - k + 1 \) gana todas sus apuestas, completa palabra\( \bs a \) y así recoge\( 1 / f(\bs a) \). El factor que complica es que los jugadores\( N - k + 2, \ldots, N \) pueden o no haber ganado todas sus apuestas en el momento en que termina el juego. El siguiente ejercicio ilustra esto.

    Supongamos que\( \bs{L} \) es una secuencia de ensayos de Bernoulli (so\( S = \{0, 1\} \)) con probabilidad de éxito\( p \in (0, 1) \). Para cada una de las siguientes cadenas, encuentre el número esperado de pruebas necesarias para completar la cadena.

    1. 001
    2. 010
    Solución

    Vamos\( q = 1 - p \).

    1. Por la palabra 001, jugadora\( N - 2 \) gana\( \frac{1}{q^2 p} \) en sus tres apuestas. El jugador\( N - 2 \) hace dos apuestas, ganando la primera pero perdiendo la segunda. Gambler\( N \) pierde su primera (y única) apuesta. De ahí\( \nu(001) = \frac{1}{q^2 p} \)
    2. Para la palabra 010, jugadora\( N - 2 \) gana\( \frac{1}{q^2 p} \) en sus tres apuestas como antes. El jugador\( N - 1 \) pierde su primera apuesta. El jugador\( N \) gana\( 1 / q \) en su primera (y única) apuesta. Entonces\( \nu(010) = \frac{1}{q^2 p} + \frac{1}{q} \)

    La diferencia entre las dos palabras es que la palabra en (b) tiene un prefijo (una cadena apropiada al principio de la palabra) que también es un sufijo (una cadena apropiada al final de la palabra). La palabra no\( \bs a \) tiene dicho prefijo. Así nos llevan naturalmente a la siguiente dicotomía:

    Supongamos que\( \bs a \) es una palabra finita del alfabeto\( S \). Si ningún prefijo apropiado de\( \bs a \) es también un sufijo, entonces\( \bs a \) es simple. De lo contrario,\( \bs a \) es compuesto.

    Aquí está el resultado principal, que por supuesto es el mismo que cuando se resolvió el problema usando la teoría de la renovación.

    Supongamos que\( \bs a \) es una palabra finita en el alfabeto\( S \).

    1. Si\( \bs a \) es simple entonces\( \nu(\bs a) = 1 / f(\bs a) \).
    2. Si\( \bs a \) es compuesto, entonces\( \nu(\bs a) = 1 / f(\bs a) + \nu(\bs b) \) ¿dónde\( \bs b \) está la palabra más larga que es tanto un prefijo como un sufijo de\( \bs a \).
    Prueba

    Los ingredientes están en su lugar a partir de nuestra discusión anterior. Supongamos que\( \bs a \) tiene longitud\( k \in \N_+ \).

    1. Si\( \bs a \) es sencillo, solo\( N - k + 1 \) gana el jugador, y ella gana\( 1 / f(\bs a) \).
    2. Supongamos que\( \bs a \)\( \bs b \) es compuesto y es el mayor prefijo-sufijo apropiado. jugador\( N - k + 1 \) gana\( 1 / f(\bs a) \) como siempre. Las ganancias de los jugadores\( N - k + 2, \ldots, N \) son las mismas que las ganancias de una nueva secuencia de jugadores jugando una nueva secuencia de pruebas con el objetivo de llegar a la palabra\( \bs b \).

    Para una palabra compuesta, podemos usar (b) para reducir el cálculo a palabras simples.

    Considera los ensayos de Bernoulli con probabilidad de éxito\( p \in (0, 1) \). Encuentra el número esperado de ensayos hasta que se complete cada una de las siguientes cadenas.

    1. \( 1011011\)
    2. \(1 1 \cdots 1 \)(\( k \)veces)
    Soluciones

    Nuevamente, vamos\( q = 1 - p \).

    1. \( \nu(1011011) = \frac{1}{p^5 q^2} + \nu(1011) = \frac{1}{p^5 q^2} + \frac{1}{p^3 q} + \nu(1) = \frac{1}{p^5 q^2} + \frac{1}{p^3 q} + \frac{1}{p}\)
    2. Dejar\( \bs{1}_j \) denotar una cadena de\( j \) 1s para\( j \in \N_+ \). Si\( k \ge 2 \) entonces\( \nu(\bs{1}_k) = 1 / p^k + \nu(\bs{1}_{k-1}) \). De ahí\[ \nu(\bs{1}_k) = \sum_{j=1}^k \frac{1}{p^j} \]

    Recordemos que un troquel plano as-seis es un dado de seis lados para el cual las caras 1 y 6 tienen probabilidad\(\frac{1}{4}\) cada una mientras que las caras 2, 3, 4 y 5 tienen probabilidad\( \frac{1}{8} \) cada una. Los dados planos de Ace-seis a veces son utilizados por los jugadores para hacer trampa.

    Supongamos que se lanza repetidamente un dado plano ace-seis. Encuentra el número esperado de lanzamientos hasta que\( 6165616 \) se produzca el patrón.

    Solución

    De nuestro teorema principal,\ begin {align*}\ nu (6165616) & =\ frac {1} {f (6165616)} +\ nu (616) =\ frac {1} {f (6165616)} +\ frac {1} {f (616)} +\ nu (6)\\ & =\ frac {1} {f (6165656) 16)} +\ frac {1} {f (616)} +\ frac {1} {f (6)} =\ frac {1} {(1/4) ^6 (1/8)} +\ frac {1} {(1/4) ^3} +\ frac {1} {1/4} = 32\ ,836\ end {align*}

    Supongamos que un mono escribe aleatoriamente en un teclado que tiene las 26 teclas de letras minúsculas y la tecla de espacio (entonces 27 teclas). Encuentra el número esperado de pulsaciones de teclas hasta que el mono produzca cada una de las siguientes frases:

    1. fue el mejor de los tiempos
    2. ser o no ser
    Solución
    1. \( 27^{24} \approx 2.258 \times 10^{34} \)
    2. \( 27^5 + 27^{18} \approx 5.815 \times 10^{25} \)

    El problema del secretario

    El problema de la secretaria fue considerado en el capítulo sobre Modelos de Muestreo Finito. En esta discusión resolveremos una variación del problema utilizando martingales. Supongamos que hay\( n \in \N_+ \) candidatos para un trabajo, o tal vez posibles parejas matrimoniales. Los candidatos llegan secuencialmente en orden aleatorio y son entrevistados. Medimos la calidad de cada candidato por un número en el intervalo\( [0, 1] \). Nuestro objetivo es seleccionar a la mejor candidata, pero una vez rechazada una candidata, no puede ser recordada. Matemáticamente, nuestros supuestos son que la secuencia de variables candidatas\( \bs X = (X_1, X_2, \ldots, X_n) \) es independiente y que cada una se distribuye uniformemente en el intervalo\( [0, 1] \) (y también lo ha hecho la distribución uniforme estándar). Nuestro objetivo es seleccionar un tiempo de parada\( \tau \) con respecto a\( \bs X \) que maximice\( \E(X_\tau) \), el valor esperado del candidato elegido. La siguiente secuencia jugará un papel crítico como secuencia de umbrales.

    Definir la secuencia\( \bs a = (a_k: k \in \N) \) por\( a_0 = 0 \) y\( a_{k+1} = \frac{1}{2}(1 + a_k^2) \) para\( k \in \N \). Entonces

    1. \( a_k \lt 1 \)para\( k \in \N \).
    2. \( a_k \lt a_{k+1} \)para\( k \in \N \).
    3. \( a_k \to 1 \)como\( k \to \infty \).
    4. Si\( X \) se distribuye uniformemente\( [0, 1] \) entonces\( \E(X \vee a_k) = a_{k+1} \) para\( k \in \N \).
    Prueba
    1. Tenga en cuenta que\( a_1 = \frac{1}{2} \lt 1 \). Supongamos que\( a_k \lt 1 \) para algunos\( k \in \N_+ \). Entonces\(a_{k+1} = \frac{1}{2}(1 + a_k^2) \lt \frac{1}{2}(1 + 1) = 1 \)
    2. Tenga en cuenta que\( 0 = a_0 \lt a_1 = \frac{1}{2} \). Supongamos que\( a_k \gt a_{k-1} \) para algunos\( k \in \N_+ \). Entonces\( a_{k+1} = \frac{1}{2}(1 + a_k^2) \gt \frac{1}{2}(1 + a_{k-1}^2) = a_k \).
    3. Dado que la secuencia va en aumento y delimitada por encima,\( a_\infty = \lim_{k \to \infty} a_k \) existe. Tomando límites en la relación de recursión da\( a_\infty = \frac{1}{2}(1 + a_\infty^2) \) o equivalentemente\( (a_\infty - 1)^2 = 0 \).
    4. Para\( k \in \N \),\[ \E(X \vee a_k) = \int_0^1 (x \vee a_k) dx = \int_0^{a_k} a_k \, dx + \int_{a_k}^1 x \, dx = \frac{1}{2}(1 + a_k^2) = a_{k+1} \]

    Ya que\( a_0 = 0 \), todos los términos de la secuencia están en\( [0, 1) \) por (a). Aproximaciones de los primeros 10 términos son\[ (0, 0.5, 0.625, 0.695, 0.742, 0.775, 0.800, 0.820, 0.836, 0.850, 0.861, \ldots) \] Propiedad (d) da alguna indicación de por qué la secuencia es importante para el probelm secretario. En todo caso, el siguiente teorema da la solución. Para simplificar la notación, let\( \N_n = \{0, 1, \ldots, n\} \) y\( \N_n^+ = \{1, 2, \ldots, n\} \).

    El tiempo de parada\( \tau = \inf\left\{k \in \N_n^+: X_k \gt a_{n-k}\right\} \) es óptimo para el problema de secretario con\( n \) los candidatos. El valor óptimo es\( \E(X_\tau) = a_n \).

    Prueba

    \( \mathfrak F = \{\mathscr{F}_k: k \in \N_n^+\} \)Sea la filtración natural de\( \bs X \), y supongamos que\( \rho \) es un tiempo de parada para\( \mathfrak F \). Definir\( \bs Y = \{Y_k: k \in \N_n\} \) por\( Y_0 = 0 \) y\( Y_k = X_{\rho \wedge k} \vee a_{n-k} \) para\( k \in \N_n^+ \). Vamos a demostrar que\( \bs Y \) es una super-martingala con respecto a\( \mathfrak F \). Primero, sobre el evento\( \rho \le k - 1 \),\[ \E(Y_k \mid \mathscr{F}_{k-1}) = \E[(X_\rho \vee a_{n-k}) \mid \mathscr{F}_{k-1}] = X_\rho \vee a_{n-k} \le X_\rho \vee a_{n - k + 1} = Y_{k-1} \] donde hemos utilizado el hecho de que\( X_\rho \bs{1}(\rho \le k - 1) \) es medible con respecto\( \mathscr{F}_{k-1} \) y el hecho de que la secuencia\( \bs a \) va en aumento. Sobre el evento\( \rho \gt k - 1 \),\[ \E(Y_k \mid \mathscr{F}_{k-1}) = \E(X_k \vee a_{n-k} \mid \mathscr{F}_{k-1}) = \E(X_k \vee a_{n-k}) = a_{n - k + 1} \le Y_{k - 1} \] donde hemos utilizado el hecho de que\( X_k \) y\( \mathscr{F}_{k-1} \) son independientes, y parte (d) del resultado anterior. Dado que\( \bs Y \) es una super-martingala y\( \rho \) está acotada, se aplica el teorema de detención opcional y tenemos\[ \E(X_\rho) \le \E(X_\rho \vee a_{n - \rho}) = \E(Y_\rho) \le E(Y_0) = a_n \] así que\( a_n \) es un límite superior sobre el valor esperado del candidato elegido por el tiempo de parada\( \rho \).

    A continuación, mostraremos que en el caso especial que\( \rho = \tau \), el proceso\( \bs Y \) es una martingala. En el evento\( \tau \le k - 1 \) tenemos\(\E(Y_k \mid \mathscr{F}_{k-1}) = X_\tau \vee a_{n-k}\) como antes. Pero por definición,\( X_\tau \ge a_{n - \tau} \ge a_{n - k + 1} \ge a_{n - k} \) así en este evento,\[ \E(Y_k \mid \mathscr{F}_{k-1}) = X_\tau = X_\tau \vee a_{n - k + 1} = Y_{k-1} \] En el evento\( \tau \gt k - 1 \) tenemos\( \E(Y_k \mid \mathscr{F}_{k-1}) = a_{n-k+1}\) como antes. Pero en este evento,\(Y_{k-1} = a_{n-k+1} \). Ahora como\( \bs Y \) es una martingala y\( \tau \) está acotada, se aplica el teorema de detención opcional y tenemos\[ \E(X_\tau) = \E(X_\tau \vee a_{n-\tau}) = \E(Y_\tau) = \E(Y_0) = a_n \]

    Aquí hay un ejemplo específico:

    Pues\( n = 5 \), la regla de decisión es la siguiente:

    1. Seleccionar candidato 1 si\( X_1 \gt 0.742 \); de lo contrario,
    2. seleccionar candidato 2 si\( X_2 \gt 0.695 \); de lo contrario,
    3. seleccionar candidato 3 si\( X_3 \gt 0.625 \); de lo contrario,
    4. seleccionar candidato 4 si\( X_4 \gt 0.5 \); de lo contrario,
    5. seleccionar candidato 5.

    El valor esperado de nuestro candidato elegido es 0.775.

    En nuestra versión original del problema del secretario, solo podíamos observar los rangos relativos de los candidatos, y nuestro objetivo era maximizar la probabilidad de elegir al mejor candidato. Con\( n = 5 \), la estrategia óptima es dejar pasar a los dos primeros candidatos y luego elegir al primer candidato después de eso es mejor que todos los candidatos anteriores, si ella existe. Si ella no existe, por supuesto, debemos seleccionar candidata 5. La probabilidad de elegir al mejor candidato es 0.433


    This page titled 17.3: Tiempos de Parada is shared under a CC BY 2.0 license and was authored, remixed, and/or curated by Kyle Siegrist (Random Services) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.