15.4: Procesos de Renovación Retrasada
- Page ID
- 152120
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Teoría Básica
Preliminares
Un proceso de renovación retrasada es igual que un proceso de renovación ordinario, excepto que se permite que la primera hora de llegada tenga una distribución diferente a las otras horas entre llegadas. Los procesos de renovación retardados surgen naturalmente en las aplicaciones y también se encuentran incrustados en otros procesos aleatorios. Por ejemplo, en una cadena de Markov (que estudiamos en el siguiente capítulo), las visitas a un estado fijo, comenzando en ese estado forman los tiempos aleatorios de un proceso ordinario de renovación. Pero las visitas a un estado fijo, iniciando en otro estado forman un proceso de renovación retrasado.
Supongamos que\( \bs{X} = (X_1, X_2, \ldots) \) es una secuencia de variables independientes que toman valores\( [0, \infty) \), con\( (X_2, X_3, \ldots) \) idéntica distribución. Supongamos también eso\( \P(X_i \gt 0) \gt 0 \) para\( i \in \N_+ \). El proceso estocástico con\( \bs{X} \) como secuencia de tiempos interllegados es un proceso de renovación retardada.
Como antes, los tiempos de llegada reales son las sumas parciales de\( \bs{X} \). Así vamos\[ T_n = \sum_{i=1}^n X_i \] así que eso\( T_0 = 0 \) y\( T_n \) es el momento de la\( n \) th llegada para\( n \in \{1, 2, \ldots\} \). También como antes,\( N_t \) es el número de llegadas en\( [0, t] \) (sin contar\( T_0 \)):\[ N_t = \sum_{n=1}^\infty \bs{1}(T_n \le t) = \max\{n \in \N: T_n \le t\} \] Si reiniciamos el reloj a la hora\( T_1 = X_1 \), tenemos un proceso de renovación ordinario con secuencia interarrival\( (X_2, X_3, \ldots) \). Utilizamos parte de la notación estándar desarrollada en la Introducción para este proceso de renovación. En particular,\( F \) denota la función de distribución común y\( \mu \) la media común de\( X_i \) for\( i \in \{2, 3, \ldots\} \). De igual manera\( F_n = F^{*n} \) denota la función de distribución de la suma de variables\( n \) independientes con función de distribución\( F \), y\( M \) denota la función de renovación:\[ M(t) = \sum_{n=1}^\infty F_n(t), \quad t \in [0, \infty) \] Por otro lado, dejaremos\( G \) denotar la función de distribución de\( X_1 \) (el especial tiempo interllegada, diferente del resto), y vamos a dejar\( G_n \) denotar la función de distribución de\( T_n \) for\( n \in \N_+ \). Como es habitual,\( F^c = 1 - F \) y\( G^c = 1 - G \) son las funciones de distribución de cola derecha correspondientes.
\( G_n = G * F_{n-1} = F_{n-1} * G\)para\( n \in \N_+ \).
Prueba
Lo que se desprende del hecho de que\( T_n \) es la suma de variables aleatorias\( n \) independientes; la primera tiene función de distribución\( G \) y las restantes\( n - 1 \) tienen función de distribución\( F \).
Por último, dejaremos\( U \) denotar la función de renovación para el proceso de renovación retrasada. Por lo tanto,\( U(t) = \E(N_t) \) es el número esperado de llegadas en\( [0, t] \) para\( t \in [0, \infty) \).
La función de renovación retardada satisface\[ U(t) = \sum_{n=1}^\infty G_n(t), \quad t \in [0, \infty) \]
Prueba
La prueba es igual que antes. \[ U(t) = \E(N_t) = \E\left(\sum_{n=1}^\infty \bs{1}(T_n \le t)\right) = \sum_{n=1}^\infty \P(T_n \le t) = \sum_{n=1}^\infty G_n(t) \]
La función de renovación retardada\( U \) satisface la ecuación\( U = G + M * G \); es decir,\[ U(t) = G(t) + \int_0^t M(t - s) \, dG(s), \quad t \in [0, \infty) \]
Prueba
El comprobante se desprende del condicionamiento a la hora de la primera llegada\( T_1 = X_1 \). Tenga en cuenta primero que\( \E(N_t \mid X_1 = s) = 0 \) si\( s \gt t \) y\( \E(N_t \mid X_1 = s) = 1 + M(t - s) \) si\( 0 \le s \le t \). De ahí
\[ U(t) = \int_0^\infty \E(N_t \mid X_1 = s) \, dG(s) = \int_0^t [1 + M(t - s)] \, dG(s) = G(t) + \int_0^t M(t - s) \, dG(s) \]La función de renovación retardada\( U \) satisface la ecuación de renovación\( U = G + U * F \); es decir,\[ U(t) = G(t) + \int_0^t U(t - s) \, dF(s), \quad t \in [0, \infty) \]
Prueba
Tenga en cuenta que\[ U = \sum_{n=1}^\infty G_n = G + \sum_{n=2}^\infty G_n = G + \sum_{n=2}^\infty ( G_{n-1} * F ) = G + \left(\sum_{n=1}^\infty G_n\right) * F = G + U * F \]
Comportamiento asintótico
En un proceso de renovación retrasada solo se cambia la primera hora de llegada. Así, no es sorprendente que el comportamiento asintótico de un proceso de renovación retrasada sea el mismo que el comportamiento asintótico del proceso de renovación regular correspondiente. Nuestro primer resultado es la fuerte ley de grandes números para el proceso de renovación retrasada.
\( N_t / t \to 1 / \mu \)como\( t \to \infty \) con probabilidad 1.
Prueba
Demostraremos que\( T_n / n \to \mu \) como\( n \to \infty \) con la probabilidad 1. Entonces, la prueba es exactamente como la prueba de la ley de grandes números para un proceso de renovación regular. Para\( n \in \{2, 3, \ldots \}\),\[ \frac{T_n}{n} = \frac{X_1}{n} + \frac{n - 1}{n} \frac{1}{n - 1} \sum_{i=2}^n X_i \] Pero\( \frac{X_1}{n} \to 0 \) como\( n \to \infty \) con probabilidad 1; por supuesto\( \frac{n}{n - 1} \to 1\) como\( n \to \infty \); y\( \frac{1}{n - 1} \sum_{i=2}^n X_i \to \mu\) como\( n \to \infty \) con probabilidad 1 por la ley fuerte ordinaria de grandes números.
Nuestro siguiente resultado es el teorema de renovación elemental para el proceso de renovación retrasada.
\( U(t) / t \to 1 / \mu \)como\( t \to \infty \).
A continuación tenemos el teorema de renovación para el proceso de renwal retrasado, también conocido como teorema de Blackwell, llamado así por David Blackwell.
Para\( h \gt 0 \),\( U(t, t + h] = U(t + h) - U(t) \to h / \mu \) como\( t \to \infty \) en cada uno de los siguientes casos:
- \( F \)no es aritmética
- \( F \)es aritmética con span\( d \in (0, \infty) \), y\( h \) es un múltiplo de\( d \).
Finalmente tenemos el teorema de renovación clave para el proceso de renovación retrasada.
Supongamos que el proceso de renovación no es aritmético y que\( g: [0, \infty) \to [0, \infty) \) es directamente integrable Riemann. Entonces\[ (g * U)(t) = \int_0^t g(t - s) \, dU(s) \to \frac{1}{\mu} \int_0^\infty g(x) \, dx \text{ as } t \to \infty \]
Procesos de Punto Estacionario
Recordemos que un proceso puntual es un proceso estocástico que modela un conjunto discreto de puntos aleatorios en un espacio de medida\( (S, \mathscr{S}, \lambda) \). Muchas veces, por supuesto,\( S \subseteq \R^n \) para algunos\( n \in \N_+ \) y\( \lambda \) es la medida Lebesgue\( n \) -dimensional correspondiente. Los casos especiales\( S = \N \) con medida de conteo y\( S = [0, \infty) \) con medida de longitud son de particular interés, en parte porque los procesos de renovación y renovación retrasada dan lugar a procesos puntuales en estos espacios.
Para un proceso general de puntos en\( S \), usamos nuestra notación estándar y denotamos el número de puntos aleatorios\( A \in \mathscr{S} \) por\( N(A) \). Hay un par de propiedades naturales que puede tener un proceso puntual. En particular, se dice que el proceso es estacionario si\( \lambda(A) = \lambda(B) \) implica eso\( N(A) \) y\( N(B) \) tienen la misma distribución para\( A, \; B \in \mathscr{S} \). En\( [0, \infty) \) el término incrementos estacionarios se suele utilizar, debido a que la propiedad de estacionariedad significa que para\( s, \, t \in [0, \infty) \), la distribución de\( N(s, s + t] = N_{s + t} - N_s \) depende sólo de\( t \).
Consideremos ahora un proceso de renovación regular. Anteriormente demostramos que las distribuciones asintóticas de la vida actual y de la vida restante son las mismas. Intuitivamente, después de un periodo de tiempo muy largo, el proceso de renovación se ve prácticamente igual hacia adelante en el tiempo o hacia atrás en el tiempo. Esto sugiere que si convertimos el proceso de renovación en un proceso de renovación retrasada al darle a la primera hora de llegada esta distribución asintótica, entonces el proceso puntual resultante será estacionario. Este es efectivamente el caso. Considerar la configuración y notación de la subsección preliminar anterior.
Para el proceso de renovación retardada, el proceso puntual\( \bs{N} \) es estacionario si y solo si la hora de llegada inicial tiene función de distribución\[ G(t) = \frac{1}{\mu} \int_0^t F^c(s) \, ds, \quad t \in [0, \infty) \] en cuyo caso la función de renovación es\( U(t) = t / \mu \) para\( t \in [0, \infty) \).
Prueba
Supongamos primero que\( \bs{N} \) tiene incrementos estacionarios. En particular, esto significa que los tiempos de llegada tienen distribuciones continuas. Para\( s, \, t \in [0, \infty) \),\[U(s + t) = \E(N_{s + t}) = \E[(N_{s + t} - N_t) + N_t] = \E(N_{s + t} - N_t) + \E(N_t) = U(s) + U(t) \] Un teorema del análisis establece que las únicas soluciones crecientes a tal ecuación funcional son las funciones lineales, y por lo tanto\( U(t) = c t \) para alguna constante positiva\( c \). Sustituir\( m_d \) en la ecuación de renovación anterior da\[ c t = G(t) + \int_0^t c (t - s) \, dF(s) = G(t) + c t \, F(t) - \int_0^t c s \, dF(s) \] Integrar por partes en la última integral y simplificar da\[ G(t) = c \int_0^t F^c(s) \, ds \] Finalmente, si dejamos\( t \to \infty \), el lado izquierdo converge a 1 y el lado derecho a\( c \mu \), entonces\( c = 1 / \mu \). Así\( G \) tiene la forma dada en el enunciado del teorema y\( U(t) = t / \mu \) para\( t \in [0, \infty) \).
Por el contrario, supongamos que\( G \) tiene la forma dada en el teorema. Tenga en cuenta que esta es una distribución continua con función de densidad\( t \mapsto F^c(t) \big/ \mu \). Sustituyendo en la ecuación de renovación anterior, se deduce que la densidad de renovación\( U^\prime \) satisface\[ U^\prime = \frac{1}{\mu} F^c + \frac{1}{\mu}F^c * \sum_{n=1}^\infty F_n = \frac{1}{\mu} \] De ahí\( U(t) = t / \mu \) para\( t \ge 0 \). A continuación, el proceso\( \bs{N} \) tiene incrementos estacionarios si y sólo si la vida restante\( R_t \) en el tiempo\( t \) tiene función de distribución\( G \) para cada uno\( t \). Argumentando así como en la Sección 2, tenemos\[ \P(R_t \gt y) = G^c(t + y) + \int_0^t F^c(t + y - s) \, d m_d(s), \quad y \ge 0 \] Pero\( G^c(t + y) = \frac{1}{\mu} \int_{t+y}^\infty F^c(u) \, du\) y\( dU(s) = \frac{1}{\mu} \, ds \), así sustituyendo en la última ecuación mostrada y usando una simple sustitución en la integral da\[ \P(R_t \gt y) = \frac{1}{\mu} \int_{t+y}^\infty F^c(u) \, du + \frac{1}{\mu} \int_y^{t+y} F^c(u) \, du = \frac{1}{\mu} \int_y^\infty F^c(u) \, du \]
Ejemplos y Aplicaciones
Patrones en Ensayos Multinomiales
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 secció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 ocurrencia repetida de una particular subcadena finita de letras (es decir, una palabra
o patrón
) en la secuencia infinita.
Entonces, arregle una palabra\( \bs a \) (nuevamente, una cadena finita de elementos de\( S \)), y considere los sucesivos números de prueba aleatorios\( (T_1, T_2, \ldots) \) donde\( \bs a \) se completa la palabra\( \bs{L} \). Dado que la secuencia\( \bs{L} \) es independiente e idéntica distribuida, parece razonable que estas variables sean los tiempos de llegada de un proceso de renovación. Sin embargo, hay una ligera complicación. Un ejemplo puede ayudar.
Supongamos que\( \bs{L} \) es una secuencia de ensayos de Bernoulli (so\( S = \{0, 1\} \)). Supongamos que el resultado de\( \bs{L} \) es\[ 101100101010001101000110\cdots \]
- Por la palabra\( \bs a = 001 \) señalar que\( T_1 = 7 \)\( T_2 = 15 \),\( T_3 = 22 \)
- Por la palabra\( \bs b = 010 \), señalar que\( T_1 = 8 \)\( T_2 = 10 \),\( T_3 = 12 \),\( T_4 =19 \)
En este ejemplo, probablemente notó una diferencia importante entre las dos palabras. For\( \bs b \), un sufijo de la palabra (una subcadena apropiada al final) también es un prefijo de la palabra (una subcadena apropiada al principio. Word\( \bs a \) no tiene esta propiedad. Entonces, una vez que llegamos
a\( \bs b \), hay formas de llegar de\( \bs b \) nuevo (aprovechando el sufijo-prefijo) que no existen a partir del inicio de las pruebas. Por otro lado, una vez que llegamos a\( \bs a \), llegar de\( \bs a \) nuevo es como con una nueva secuencia de ensayos. De esta manera nos llevan a la siguiente definición.
Supongamos que\( \bs a \) es una palabra finita del alfabeto\( S \). Si ningún sufijo apropiado de\( \bs a \) es también un prefijo, entonces\( \bs a \) es simple. De lo contrario,\( \bs a \) es compuesto.
Volviendo a la configuración general, let\( T_0 = 0 \) y luego let\( X_n = T_n - T_{n-1}\) for\( n \in \N_+ \). Para\( k \in \N \), vamos\( N_k = \sum_{n=1}^\infty \bs{1}(T_n \le k) \). Para ocurrencias de la palabra\( \bs a \),\( \bs{X} = (X_1, X_2, \ldots) \) es la secuencia de tiempos de interllegada,\( \bs{T} = (T_0, T_1, \ldots) \) es la secuencia de tiempos de llegada, y\( \bs{N} = \{N_k: k \in \N\} \) es el proceso de conteo. Si\( \bs a \) es simple, estos forman un proceso ordinario de renovación. Si\( \bs a \) es compuesto, forman un proceso de renovación retrasada, ya que\( X_1 \) tendrán una distribución diferente a la\( (X_2, X_3, \ldots) \). Dado que la estructura de un proceso de renovación retrasada subsume la de un proceso ordinario de renovación, trabajaremos con la notación anterior para el proceso retrasado. En particular, vamos a\( U \) denotar la función de renovación. Todo en este párrafo depende\( \bs a \) de la palabra claro, pero esto lo hemos suprimido en la notación.
Supongamos\( \bs a = a_1 a_2 \cdots a_k \), donde\( a_i \in S \) para cada uno\( i \in \{1, 2, \ldots, k\} \), así que esa\( \bs a \) es una palabra de longitud\( k \). Tenga en cuenta que\( X_1 \) toma valores en\( \{k, k + 1, \ldots\} \). Si\( \bs a \) es simple, esto se aplica también a los otros tiempos de interllegada. Si\( \bs a \) es compuesto, la situación es más complicada\( X_2, \, X_3, \ldots \) tendrá algún valor mínimo\( j \lt k \), pero los valores posibles son enteros positivos, claro, e incluyen\(\{k + 1, k + 2, \ldots\}\). En cualquier caso, el proceso de renovación es aritmético con span 1. Ampliando la definición de la función de densidad de probabilidad\( f \), let\[ f(\bs a) = \prod_{i=1}^k f(a_i) \] so that\( f(\bs a) \) is the probability of forming\( \bs a \) with\( k \) consecutive trials. Dejar\( \mu(\bs a) \) denotar la media común de\( X_n \) for\( n \in \{2, 3, \ldots\} \), así\( \mu(\bs a) \) es el número medio de ensayos entre ocurrencias de\( \bs a \). Dejar\( \nu(\bs a) = \E(X_1) \), así que ese\( \nu(\bs a) \) es el tiempo medio número de ensayos hasta que\( \bs a \) ocurra por primera vez. Nuestro primer resultado es una elegante conexión entre\( \mu(\bs a) \) y\( f(\bs a) \), que tiene una prueba maravillosamente simple de la teoría de la renovación.
Si\( \bs a \) es una palabra en\( S \) entonces\[ \mu(\bs a) = \frac{1}{f(\bs a)} \]
Prueba
Supongamos que\( \bs a \) tiene longitud\( k \), y considera el intervalo discreto\( (n, n + k] = \{n + 1, n + 2, \ldots, n + k\} \). Por el teorema de la renovación,\( U(n, n + k] \to 1 / \mu(\bs a) \) como\( n \to \infty \). Pero\( N(n, n + k] \), el número de veces que\( \bs a \) ocurre en el intervalo, es de 1 o 0. De ahí\( U(n, n + k] = f(\bs a) \) para cualquier\( n \).
Nuestro siguiente objetivo es calcular\( \nu(\bs a) \) en el caso que\( \bs a \) sea una palabra compuesta.
Supongamos que\( \bs a \) es una palabra compuesta, y esa\( \bs b \) es la palabra más grande que es un sufijo y prefijo adecuados de\( \bs a \). Entonces\[ \nu(\bs a) = \nu(\bs b) + \mu(\bs a) = \nu(\bs b) + \frac{1}{f(\bs a)} \]
Prueba
Dado que\( \bs b \) es el mayor prefijo-sufijo, el número esperado de juicios para pasar de\( \bs b \) a\( \bs a \) es el mismo que el número esperado de ensayos para pasar de\( \bs a \) a\( \bs a \), a saber\( \mu(\bs a) \). (Tenga en cuenta que los caminos de\( \bs b \) a\( \bs a \) son los mismos que los caminos de\( \bs a \) a\( \bs a \).) Pero para formar la palabra\( \bs a \) inicialmente, la palabra\( \bs b \) debe formarse primero, por lo que este resultado se desprende de la aditividad del valor esperado y del resultado anterior.
Mediante el uso repetido del último resultado, podemos calcular el número esperado de ensayos necesarios para formar cualquier palabra compuesta.
Considera los ensayos de Bernoulli con probabilidad de éxito\( p \in (0, 1) \), y deja\( q = 1 - p \). Para cada una de las siguientes cadenas, encuentre el número esperado de ensayos entre ocurrencias y el número esperado de ensayos hasta la primera ocurrencia.
- \( \bs a = 001 \)
- \( \bs b = 010 \)
- \( \bs c = 1011011\)
- \(\bs d = 11 \cdots 1 \)(\( k \)veces)
Contestar
- \( \mu(\bs a) = \nu(\bs a) = \frac{1}{p q^2} \)
- \( \mu(\bs b) = \frac{1}{p q^2} \),\( \nu(\bs b) = \frac{1}{q} + \frac{1}{p q^2} \)
- \( \mu(\bs c) = \frac{1}{p^5 q^2} \),\( \nu(\bs c) = \frac{1}{p} + \frac{1}{p^3 q} + \frac{1}{p^5 q^2} \)
- \( \mu(\bs d) = \frac{1}{p^k} \)\( \nu(\bs d) = \sum_{i=1}^k \frac{1}{p^i} \)
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 apostadores para hacer trampa.
Supongamos que se lanza repetidamente un dado plano ace-seis. Encuentra el número esperado de lanzamientos hasta que se produzca el patrón\( 6165616 \) por primera vez.
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:
- fue el mejor de los tiempos
- ser o no ser
Prueba
- \( 27^{24} \approx 2.258 \times 10^{34} \)
- \( 27^5 + 27^{18} \approx 5.815 \times 10^{25} \)