11.2: Cadenas de Markov Absorbentes

El tema de las cadenas de Markov se estudia mejor considerando tipos especiales de cadenas de Markov. El primer tipo que estudiaremos se llama

Un estado\(s_i\) de una cadena de Markov se llama si es imposible dejarla (es decir,\(p_{ii} = 1\)). Una cadena de Markov es si tiene al menos un estado absorbente, y si de cada estado es posible pasar a un estado absorbente (no necesariamente en un solo paso).

En una cadena absorbente de Markov, un estado que no es absorbente se llama

Caminata de Borracho

[examen 11.2.1] Un hombre camina por un tramo de cuatro cuadras de Park Avenue (ver Figura [fig 11.3]). Si está en la esquina 1, 2 o 3, entonces camina hacia la izquierda o hacia la derecha con igual probabilidad. Continúa hasta llegar a la esquina 4, que es un bar, o esquina 0, que es su casa. Si llega a casa o al bar, se queda ahí.

Formamos una cadena de Markov con estados 0, 1, 2, 3 y 4. Los estados 0 y 4 son estados absorbentes. La matriz de transición es entonces

\[\mat{P} =\begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 0 & 1 & 2 & 3 & 4 \cr 0 & 1 & 0 & 0 & 0 & 0 \cr 1 & 1/2 & 0 & 1/2 & 0 & 0 \cr 2 & 0 & 1/2 & 0 & 1/2 & 0 \cr 3 & 0 & 0 & 1/2 & 0 & 1/2 \cr 4 & 0 & 0 & 0 & 0 & 1 \cr\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .\]Los estados 1, 2 y 3 son estados transitorios, y de cualquiera de estos es posible alcanzar los estados absorbentes 0 y 4. De ahí que la cadena sea una cadena absorbente. Cuando un proceso alcanza un estado absorbente, diremos que lo es.

La pregunta más obvia que se puede hacer sobre una cadena de este tipo es: ¿Cuál es la probabilidad de que el proceso llegue finalmente a un estado absorbente? Otras preguntas interesantes son: a) ¿Cuál es la probabilidad de que el proceso termine en un determinado estado absorbente? b) En promedio, ¿cuánto tiempo tardará en absorberse el proceso? c) En promedio, ¿cuántas veces estará el proceso en cada estado transitorio? Las respuestas a todas estas preguntas dependen, en general, del estado a partir del cual se inicia el proceso así como de las probabilidades de transición.

Forma canónica

Considera una cadena de Markov que absorbe arbitrariamente. Renumérense los estados para que los estados transitorios sean lo primero. Si hay estados\(r\) absorbentes y\(t\) transitorios, la matriz de transición tendrá lo siguiente

\[\offinterlineskip \mat{P}\;= \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% &\hbox{TR.}&\omit\hfil&\hbox{ABS.}\cr \hbox{TR.}\relax\ifmmode\copy\bigstrutbox\else\unhcopy\bigstrutbox\fi&\mat{Q} &\omit\kern.5em\vrule\kern-.5em&\mat{R} \cr \noalign{\kern-\snellbaselineskip\kern\snellskip} &\multispan 1\strut\hrulefill &\omit\hbox to.5em{\hrulefill}\vrule height \snellskip\kern-.5em&\multispan 1\hrulefill\cr \hbox{ABS.}\relax\ifmmode\copy\bigstrutbox\else\unhcopy\bigstrutbox\fi&\mat{0} &\omit\kern.5em\vrule\kern-.5em&\mat{I}\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\]

Aquí\(\mat{I}\) hay una matriz de\(r\) identificación\(r\) -por-,\(\mat{0}\) es una matriz\(r\) -por-\(t\) cero,\(\mat{R}\) es una matriz\(t\) -por-\(r\) distinta de cero, y\(\mat{Q}\) es una\(t\) matriz\(t\) -by-. Los primeros\(t\) estados son transitorios y los últimos\(r\) estados son absorbentes.

En la Sección 1.1, vimos que la entrada\(p_{ij}^{(n)}\) de la matriz\(\mat{P}^n\) es la probabilidad de estar en el estado\(s_j\) después de\(n\) los pasos, cuando la cadena se inicia en estado\(s_i\). Un argumento de álgebra de matriz estándar muestra que\(\mat{P}^n\) es de la forma\[\offinterlineskip \mat{P}^n\;= \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% &\hbox{TR.}&\omit\hfil&\hbox{ABS.}\cr \hbox{TR.}\relax\ifmmode\copy\bigstrutbox\else\unhcopy\bigstrutbox\fi&\mat{Q}^n &\omit\kern.5em\vrule\kern-.5em&\ast \cr \noalign{\kern-\snellbaselineskip\kern\snellskip} &\multispan 1\strut\hrulefill &\omit\hbox to.5em{\hrulefill}\vrule height \snellskip\kern-.5em&\multispan 1\hrulefill\cr \hbox{ABS.}\relax\ifmmode\copy\bigstrutbox\else\unhcopy\bigstrutbox\fi&\mat{0} &\omit\kern.5em\vrule\kern-.5em&\mat{I}\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\] donde el asterisco\(*\) representa la\(r\) matriz\(t\) -by- en la esquina superior derecha de\(\mat{P}^n.\) (Esta submatriz se puede escribir en términos de\(\mat{Q}\) y\(\mat{R}\), pero la expresión es complicado y no es necesario en este momento.) La forma de\(\mat{P}^n\) muestra que las entradas de\(\mat{Q}^n\) dan las probabilidades de estar en cada uno de los estados transitorios después de\(n\) pasos para cada posible estado de inicio transitorio. Para nuestro primer teorema probamos que la probabilidad de estar en los estados transitorios después de\(n\) pasos se acerca a cero. Así, cada entrada de\(\mat{ Q}^n\) debe acercarse a cero a medida que\(n\) se acerca al infinito (es decir,\(\mat{Q}^n \to \mat{ 0}\)).

Probabilidad de Absorción

[thm 11.2.1] En una cadena absorbente de Markov, la probabilidad de que el proceso sea absorbido es 1 (es decir,\(\mat{Q}^n \to \mat{0}\) as\(n \to \infty\)).

Desde cada estado no absorbente\(s_j\) es posible alcanzar un estado absorbente. Dejar\(m_j\) ser el número mínimo de pasos requeridos para alcanzar un estado absorbente, a partir de\(s_j\). \(p_j\)Sea la probabilidad de que, a partir de\(s_j\), el proceso no llegue a un estado absorbente en\(m_j\) pasos. Entonces\(p_j <1\). Let\(m\) be the largest of the\(m_j\) and let\(p\) be the largest of\(p_j\). La probabilidad de no ser absorbida en\(m\) pasos es menor o igual a\(p\), en\(2m\) pasos menores o iguales a\(p^2\), etc. ya que\(p<1\) estas probabilidades tienden a 0. Dado que la probabilidad de no ser absorbida en\(n\) pasos es monótona decreciente, estas probabilidades también tienden a 0, de ahí\(\lim_{n \rightarrow \infty } \mat{Q}^n = 0.\)

La Matriz Fundamental

[thm 11.2.2] Para una cadena de Markov absorbente la matriz\(\mat{I} - \mat{Q}\) tiene una inversa\(\mat{N}\) y\(\mat{N} =\mat{I} + \mat{Q} + \mat{Q}^{2} + \cdots\\). El\(ij\) -ingreso\(n_{ij}\) de la matriz\(\mat{N}\) es el número esperado de veces que la cadena está en estado\(s_j\), dado que inicia en estado\(s_i\). El estado inicial se cuenta si\(i = j\).

\((\mat{I} - \mat{Q})\mat{x}~=~0;\)Que sea\(\mat{x}~=~\mat{Q}\mat{x}.\) Entonces, iterando esto vemos que\(\mat{x}~=~\mat{Q}^{n}\mat x.\) Desde\(\mat{Q}^{n} \rightarrow \mat{0}\), tenemos\(\mat{Q}^n\mat{x} \rightarrow \mat{0}\), así\(\mat{x}~=~\mat{0}\). Así\((\mat{I} - \mat{Q})^{-1}~=~\mat{N}\) existe. Nota siguiente que multiplicando\[(\mat{I} - \mat{Q}) (\mat{I} + \mat{Q} + \mat{Q}^2 + \cdots + \mat{Q}^n) = \mat{I} - \mat{Q}^{n + 1}\ .\] así ambos lados por\(\mat{N}\) da\[\mat{I} + \mat{Q} + \mat{Q}^2 + \cdots + \mat{Q}^n = \mat{N} (\mat{I} - \mat{Q}^{n + 1})\ .\] Dejar\(n\) tender al infinito tenemos\[\mat{N} = \mat{I} + \mat{Q} + \mat{Q}^2 + \cdots\ .\]

Dejar\(s_i\) y\(s_j\) ser dos estados transitorios, y asumir a lo largo del resto de la prueba que\(i\) y\(j\) son fijos. Let\(X^{(k)}\) Ser una variable aleatoria que es igual a 1 si la cadena está en estado\(s_j\) después de\(k\) los pasos, y es igual a 0 de lo contrario. Para cada uno\(k\), esta variable aleatoria depende de ambos\(i\) y\(j\); elegimos no mostrar explícitamente esta dependencia en aras de la claridad. Tenemos\[P(X^{(k)} = 1) = q_{ij}^{(k)}\ ,\] y\[P(X^{(k)} = 0) = 1 - q_{ij}^{(k)}\ ,\] donde\(q_{ij}^{(k)}\) esta la entrada\(ij\) th de\(\mat{Q}^k\). Estas ecuaciones se mantienen\(k = 0\) desde entonces\(\mat{Q}^0 = \mat{I}\). Por lo tanto, dado que\(X^{(k)}\) es una variable aleatoria 0-1,\(E(X^{(k)}) = q_{ij}^{(k)}\).

El número esperado de veces que la cadena está en estado\(s_j\) en los primeros\(n\) pasos, dado que inicia en estado\(s_i\), es claramente\[E\Bigl(X^{(0)} + X^{(1)} + \cdots + X^{(n)} \Bigr) = q_{ij}^{(0)} + q_{ij}^{(1)} + \cdots + q_{ij}^{(n)}\ .\] Dejando\(n\) tender al infinito que tenemos\[E\Bigl(X^{(0)} + X^{(1)} + \cdots \Bigr) = q_{ij}^{(0)} + q_{ij}^{(1)} + \cdots = n_{ij} \ .\]

Para una cadena de Markov absorbente\(\mat{P}\), la matriz\(\mat{N} = (\mat{I} - \mat{Q})^{-1}\) se llama la para\(\mat{P}\). La entrada\(n_{ij}\) de\(\mat{N}\) da el número esperado de veces que el proceso está en el estado transitorio\(s_j\) si se inicia en el estado transitorio\(s_i\).

[examen 11.2.2] (Ejemplo [examen 11.2.1] continuado) En el ejemplo del Paseo del Borracho, la matriz de transición en forma canónica es\[\offinterlineskip \mat{P}\;= \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & \hbox{1} &\hbox{2}&\hbox{3}&\omit\hfil&\hbox{0}&\hbox{4}\cr \hbox{1}\strut & 0 &1/2 & 0 & \omit\kern.5em\vrule\kern-.5em& 1/2 & 0 \cr \hbox{2}\strut &1/2 & 0 &1/2 & \omit\kern.5em\vrule\kern-.5em& 0 & 0 \cr \hbox{3}\strut & 0 &1/2 & 0 & \omit\kern.5em\vrule\kern-.5em& 0 & 1/2\cr \noalign{\kern-\snellbaselineskip\kern\snellskip} &\multispan 3\strut\hrulefill &\omit\hbox to.5em{\hrulefill}\vrule height \snellskip\kern-.5em&\multispan 2\hrulefill\cr \hbox{0}\strut & 0 & 0 & 0 & \omit\kern.5em\vrule\kern-.5em& 1 & 0 \cr \hbox{4}\strut & 0 & 0 & 0 & \omit\kern.5em\vrule\kern-.5em& 0 & 1\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .\] A partir de esto vemos que la matriz\(\mat{Q}\) es\[\mat{Q} = \pmatrix{ 0 & 1/2 & 0 \cr 1/2 & 0 & 1/2 \cr 0 & 1/2 & 0 \cr}\ ,\] y\[\mat{I} - \mat{Q} = \pmatrix{ 1 & -1/2 & 0 \cr -1/2 & 1 & -1/2 \cr 0 & -1/2 & 1 \cr}\ .\] Computación\((\mat{I} - \mat{Q})^{-1}\), encontramos\[\vspace{7pt}\hbox{$\mat{N} = (\mat{I} - \mat{Q})^{-1} = {}$} \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 1 & 2 & 3 \cr 1 & 3/2 & 1 & 1/2 \cr 2 & 1 & 2 & 1 \cr 3 & 1/2 & 1 & 3/2 \cr\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .\] De la fila media de\(\mat{N}\), vemos que si empezamos en el estado 2, entonces el número esperado de veces en los estados 1, 2 y 3 antes de ser absorbidos son 1, 2 y 1.

Tiempo de Absorción

Consideramos ahora la pregunta: Dado que la cadena inicia en estado\(s_i\), ¿cuál es el número esperado de pasos antes de que se absorba la cadena? La respuesta se da en el siguiente teorema.

[thm 11.2.2.5] Dejar\(t_i\) ser el número esperado de pasos antes de que se absorba la cadena, dado que la cadena inicia en estado\(s_i\), y deja\(\mat{t}\) ser el vector de columna cuya entrada es\(i\) th\(t_i\). Entonces\[\mat{t} = \mat{N}\mat{c}\ ,\] donde\(\mat{c}\) está un vector de columna cuyas entradas son 1.

Si sumamos todas las entradas en la fila\(i\) th de\(\mat{N}\), tendremos el número esperado de veces en cualquiera de los estados transitorios para un estado de inicio dado\(s_i\), es decir, el tiempo esperado requerido antes de ser absorbidos. Así,\(t_i\) es la suma de las entradas en la fila\(i\) th de\(\mat{N}\). Si escribimos esta afirmación en forma de matriz, obtenemos el teorema.

Probabilidades de Absorción

[thm 11.2.3]\(b_{ij}\) Sea la probabilidad de que una cadena absorbente sea absorbida en el estado absorbente\(s_j\) si inicia en el estado transitorio\(s_i\). Dejar\(\mat{B}\) ser la matriz con entradas\(b_{ij}\). Entonces\(\mat{B}\) es una\(r\) matriz\(t\) -by-, y\[\mat{B} = \mat{N} \mat{R}\ ,\] donde\(\mat{N}\) está la matriz fundamental y\(\mat{R}\) es como en la forma canónica. Tenemos\[\begin{aligned} \mat{B}_{ij} &=& \sum_n\sum_k q_{ik}^{(n)} r_{kj} \\ &=& \sum_k \sum_n q_{ik}^{(n)} r_{kj} \\ &=& \sum_k n_{ik}r_{kj} \\ &=& (\mat{N}\mat{R})_{ij}\ .\end{aligned}\] Esto completa la prueba.

Otra prueba de ello se da en Ejercicio [exer 11.2.33].

[examen 11.2.3] (Ejemplo [examen 11.2.2] continuado) En el ejemplo de la Caminata del Borracho, encontramos que\[\vspace{7pt}\hbox{$\mat{N} = {}$} \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 1 & 2 & 3 \cr 1 & 3/2 & 1 & 1/2 \cr 2 & 1 & 2 & 1 \cr 3 & 1/2 & 1 & 3/2 \cr\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .\] De ahí,\[\begin{aligned} \mat{t} = \mat{N}\mat{c} &=& \pmatrix{ 3/2 & 1 & 1/2 \cr 1 & 2 & 1 \cr 1/2 & 1 & 3/2 \cr } \pmatrix{ 1 \cr 1 \cr 1 \cr } \\ &=& \pmatrix{ 3 \cr 4 \cr 3 \cr }\ .\end{aligned}\] Así, comenzando en los estados 1, 2 y 3, los tiempos esperados para la absorción son 3, 4 y 3, respectivamente.

Desde la forma canónica,\[\vspace{7pt}\hbox{$\mat{ R} = {}$} \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 0 & 4 \cr 1 & 1/2 & 0 \cr 2 & 0 & 0 \cr 3 & 0 & 1/2 \cr\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .\] Por lo tanto,\[\begin{aligned} \mat{B} = \mat{N} \mat{R} &=& \pmatrix{ 3/2 & 1 & 1/2 \cr 1 & 2 & 1 \cr 1/2 & 1 & 3/2 \cr} \cdot \pmatrix{ 1/2 & 0 \cr 0 & 0 \cr 0 & 1/2 \cr} \cr \cr \cr &=& \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 0 & 4 \cr 1 & 3/4 & 1/4 \cr 2 & 1/2 & 1/2 \cr 3 & 1/4 & 3/4 \cr\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .\end{aligned}\]

Aquí la primera fila nos dice que, a partir del estado\(1\), hay probabilidad 3/4 de absorción en estado\(0\) y 1/4 de absorción en estado\(4\).

Computación

El hecho de que hayamos podido obtener estas tres cantidades descriptivas en forma de matriz hace que sea muy fácil escribir un programa de computadora que determine estas cantidades para una matriz de cadena absorbente dada.

El programa AbsorbingChain calcula las cantidades descriptivas básicas de una cadena absorbente de Markov.

Hemos corrido el programa AbsorbingChain para el ejemplo de la caminata del borracho (Ejemplo [examen 11.2.1]) con 5 cuadras. Los resultados son los siguientes:

\[\mat{Q} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 1 & 2 & 3 & 4 \cr 1 & .00 & .50 & .00 & .00\cr 2 & .50 & .00 & .50 & .00\cr 3 & .00 & .50 & .00 & .50\cr 4 & .00 & .00 & .50 & .00\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ ;\]

\[\mat{R} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 0 & 5 \cr 1 & .50 & .00 \cr 2 & .00 & .00 \cr 3 & .00 & .00 \cr 4 & .00 & .50 \crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ ;\]

\[\mat{N} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 1 & 2 & 3 & 4 \cr 1 & 1.60 & 1.20 & .80 & .40 \cr 2 & 1.20 & 2.40 & 1.60 & .80 \cr 3 & .80 & 1.60 & 2.40 & 1.20\cr 4 & .40 & .80 & 1.20 & 1.60\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ ;\]

\[\mat{t} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & \cr 1 & 4.00 \cr 2 & 6.00 \cr 3 & 6.00 \cr 4 & 4.00\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ ;\]

\[\mat{B} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 0 & 5 \cr 1 & .80 & .20 \cr 2 & .60 & .40 \cr 3 & .40 & .60 \cr 4 & .20 & .80 \crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .\]

Obsérvese que la probabilidad de llegar a la barra antes de llegar a casa\(x\), comenzando en, es\(x/5\) (es decir, proporcional a la distancia del hogar desde el punto de partida). (Ver Ejercicio [exer 11.2.23].)

i [exer 11.2.1] En Ejemplo [examen 11.1.2], ¿para qué valores de\(a\) y\(b\) obtenemos una cadena de Markov absorbente?

i [exer 11.2.2] Mostrar que Ejemplo [examen 11.1.5] es una cadena de Markov absorbente.

i [exer 11.2.3] ¿Cuál de los ejemplos genéticos (Ejemplos [examen 11.1.7], [examen 11.1.8] y [examen 11.1.9]) son absorbentes?

i [exer 11.2.4] Encuentra la matriz fundamental\(\mat{N}\) para Ejemplo [examen 11.1.8].

i [exer 11.2.5] Por ejemplo [examen 11.1.9], verificar que la siguiente matriz es la inversa de\(\mat{I} - \mat{Q}\) y por lo tanto es la matriz fundamental\(\mat{N}\). \[\mat{N} = \pmatrix{ 8/3 & 1/6 & 4/3 & 2/3 \cr 4/3 & 4/3 & 8/3 & 4/3 \cr 4/3 & 1/3 & 8/3 & 4/3 \cr 2/3 & 1/6 & 4/3 & 8/3 \cr}\ .\]Encontrar\(\mat{N} \mat{c}\) y\(\mat{N} \mat{R}\). Interpretar los resultados.

i [exer 11.2.6] En el ejemplo Tierra de Oz (Ejemplo [examen 11.1.1]), cambiar la matriz de transición haciendo de R un estado absorbente. Esto le da a\[\mat{P} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & \mbox{R} & \mbox{N} & \mbox{S} \cr \mbox{R} & 1 & 0 & 0 \cr \mbox{N} & 1/2 & 0 & 1/2 \cr \mbox{S} & 1/4 & 1/4 & 1/2\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .\] Find la matriz fundamental\(\mat{N}\), y también\(\mat{Nc}\) y\(\mat{NR}\). Interpretar los resultados.

i [exer 11.2.7] En Ejemplo [examen 11.1.6], convertir los estados 0 y 4 en estados absorbentes. Encuentra la matriz fundamental\(\mat{N}\), y también\(\mat{Nc}\) y\(\mat{NR}\), para la cadena absorbente resultante. Interpretar los resultados.

i [exer 11.2.8] En Ejemplo [examen 11.2.1] (Paseo del borracho) de esta sección, supongamos que la probabilidad de un paso a la derecha es 2/3, y un paso a la izquierda es 1/3. Encontrar\(\mat{N},~\mat{N}\mat{c}\), y\(\mat{N}\mat{R}\). Compárelos con los resultados de Ejemplo [examen 11.2.3].

i [exer 11.2.9] Un proceso se mueve sobre los enteros 1, 2, 3, 4 y 5. Comienza en 1 y, en cada paso sucesivo, se mueve a un entero mayor que su posición actual, moviéndose con igual probabilidad a cada uno de los enteros mayores restantes. El estado cinco es un estado absorbente. Encuentra el número esperado de pasos para llegar al estado cinco.

i [exer 11.2.10] Usando el resultado de Ejercicio [exer 11.2.9], hacer una conjetura para la forma de la matriz fundamental si el proceso se mueve como en ese ejercicio, excepto que ahora se mueve sobre los enteros de 1 a\(n\). Pon a prueba tu conjetura para varios valores diferentes de\(n\). ¿Se puede conjeturar una estimación del número esperado de pasos para llegar al estado\(n\), para grandes\(n\)? (Ver Ejercicio [exer 11.2.10.5] para un método para determinar este número esperado de pasos.)

[exer 11.2.10.5] Dejar\(b_k\) denotar el número esperado de pasos a alcanzar\(n\) desde\(n-k\), en el proceso descrito en Ejercicio [exer 11.2.9].

1. Definir\(b_0 = 0\). Demostrar que para\(k > 0\), tenemos\[b_k = 1 + \frac 1k \bigl(b_{k-1} + b_{k-2} + \cdots + b_0\bigr)\ .\]

2. Dejar\[f(x) = b_0 + b_1 x + b_2 x^2 + \cdots\ .\] Usando la recursión en la parte (a), muestra que\(f(x)\) satisface la ecuación diferencial\[(1-x)^2 y' - (1-x) y - 1 = 0\ .\]

3. Mostrar que la solución general de la ecuación diferencial en la parte (b) es\[y = \frac{-\log(1-x)}{1-x} + \frac c{1-x}\ ,\] donde\(c\) es una constante.

4. Utilice la parte (c) para mostrar que\[b_k = 1 + \frac 12 + \frac 13 + \cdots + \frac 1k\ .\]

i [exer 11.2.11] Tres tanques pelean un duelo de tres vías. El tanque A tiene probabilidad 1/2 de destruir el tanque al que dispara, el tanque B tiene probabilidad 1/3 de destruir el tanque al que dispara, y el tanque C tiene probabilidad 1/6 de destruir el tanque al que dispara. Los tanques disparan juntos y cada tanque dispara al oponente más fuerte aún no destruido. Formar una cadena de Markov tomando como estados los subconjuntos del conjunto de tanques. Encuentra\(\mat{N},~\mat{N}\mat{c}\), e\(\mat{N}\mat{R}\), e interpreta tus resultados.: Toma como estados ABC, AC, BC, A, B, C, y ninguno, indicando los tanques que podrían sobrevivir comenzando en el estado ABC. Se puede omitir AB porque no se puede llegar a este estado desde ABC.

i [exer 11.2.12] Smith está en la cárcel y tiene 3 dólares; puede salir bajo fianza si tiene 8 dólares. Un guardia acepta hacer una serie de apuestas con él. Si Smith apuesta\(A\) dólares, gana\(A\) dólares con probabilidad .4 y pierde\(A\) dólares con probabilidad .6. Encuentra la probabilidad de que gane 8 dólares antes de perder todo su dinero si

1. apuesta 1 dólar cada vez (estrategia tímida).

2. apuesta, cada vez, tanto como sea posible pero no más de lo necesario para llevar su fortuna hasta 8 dólares (estrategia audaz).

3. ¿Qué estrategia le da a Smith la mejor oportunidad de salir de la cárcel?

i [exer 11.2.13] Con la situación en Ejercicio [exer 11.2.12], considera la estrategia tal que para\(i < 4\), Smith apuesta\(\min(i,4 - i)\), y para\(i \geq 4\), apuesta según la estrategia audaz, donde\(i\) está su fortuna actual. Encuentra la probabilidad de que salga de la cárcel usando esta estrategia. ¿Cómo se compara esta probabilidad con la obtenida para la estrategia audaz?

i [exer 11.2.14] Considera el juego de tenis cuando se alcanza. Si un jugador gana el siguiente punto, tiene En el siguiente punto, o gana el juego o el juego vuelve a Asumir que para cualquier punto, el jugador A tiene probabilidad .6 de ganar el punto y el jugador B tiene probabilidad .4 de ganar el punto.

1. Configurar esto como una cadena de Markov con estado 1: A gana; 2: B gana; 3: ventaja A; 4: deuce; 5: ventaja B.

2. Encuentra las probabilidades de absorción.

3. En deuce, encuentra la duración esperada del juego y la probabilidad de que B gane.

Los ejercicios [exer 11.2.15] y [exer 11.2.16] se refieren a la herencia del daltonismo, que es una característica ligada al sexo. Hay un par de genes, g y G, de los cuales el primero tiende a producir daltonismo, el segundo visión normal. El gen G es dominante. Pero un hombre sólo tiene un gen, y si esto es g, es daltónico. Un hombre hereda uno de los dos genes de su madre, mientras que una mujer hereda un gen de cada progenitor. Así, un hombre puede ser de tipo G o g, mientras que una mujer puede ser tipo GG o Gg o gg. Estudiaremos un proceso de endogamia similar al del Ejemplo [examen 11.1.9] mediante la construcción de una cadena de Markov.

i [exer 11.2.15] Enumerar los estados de la cadena.: Hay seis. Computar las probabilidades de transición. Encuentra la matriz fundamental\(\mat{N}\),\(\mat{N}\mat{c}\), y\(\mat{N}\mat{R}\).

i [exer 11.2.16] Mostrar que tanto en el Ejemplo [examen 11.1.9] como en el ejemplo que se acaba de dar, la probabilidad de absorción en un estado que tiene genes de un tipo particular es igual a la proporción de genes de ese tipo en el estado inicial. Demuestre que esto puede explicarse por el hecho de que un juego en el que tu fortuna es el número de genes de un tipo particular en el estado de la cadena Markov es un juego limpio. ⁵

i [exer 11.2.17] Supongamos que un estudiante que va a una determinada escuela de medicina de cuatro años en el norte\(q\) de Nueva Inglaterra tiene, cada año, una probabilidad\(r\) de reprobar, una probabilidad de tener que repetir el año y una probabilidad\(p\) de pasar al siguiente año (en el cuarto año , seguir adelante significa graduarse).

1. Formar una matriz de transición para este proceso tomando como estados F, 1, 2, 3, 4 y G donde F significa reprobar y G para graduarse, y los demás estados representan el año de estudio.

2. Para el caso\(q = .1\),\(r = .2\), y\(p = .7\) encontrar el tiempo que un estudiante principiante puede esperar estar en el segundo año. ¿Cuánto tiempo debe esperar este estudiante estar en la escuela de medicina?

3. Encuentra la probabilidad de que este estudiante principiante se gradúe.

i [exer 11.2.18] (E. Brown ⁶) Mary y John están jugando el siguiente juego: Tienen un mazo de tres cartas marcado con los números 1, 2 y 3 y un spinner con los números 1, 2 y 3 en él. El juego comienza repartir las cartas para que el crupier obtenga una carta y la otra persona obtenga dos. Un movimiento en el juego consiste en un giro del spinner. La persona que tiene la tarjeta con el número que aparece en el spinner le entrega esa tarjeta a la otra persona. El juego termina cuando alguien tiene todas las cartas.

1. Configura la matriz de transición para esta cadena absorbente de Markov, donde los estados corresponden al número de cartas que Mary tiene.

2. Encuentra la matriz fundamental.

3. En promedio, ¿cuántos movimientos durará el juego?

4. Si Mary trata, ¿cuál es la probabilidad de que John gane el juego?

i [exer 11.2.19] Supongamos que un experimento tiene resultados\(m\) igualmente probables. Demostrar que el número esperado de ensayos independientes antes de la primera ocurrencia de ocurrencias\(k\) consecutivas de uno de estos resultados es\((m^k - 1)/(m - 1)\).: Formar una cadena absorbente de Markov con estados 1, 2,...,\(k\) con estado\(i\) representando la longitud de la corrida actual. El tiempo esperado hasta una ejecución de\(k\) es 1 más que el tiempo esperado hasta que la absorción para la cadena comenzó en el estado 1. Se ha encontrado que, en la expansión decimal de pi, comenzando con el dígito 24 , 658, 601, hay una racha de nueve 7's ¿Cuál diría su resultado sobre el número esperado de dígitos necesarios para encontrar tal corrida si los dígitos se producen aleatoriamente?

i [exer 11.2.20] (Roberts ⁷) Una ciudad se divide en 3 áreas 1, 2 y 3. Se estima que cada día se emiten cantidades\(u_1\)\(u_2\),, y\(u_3\) de contaminación desde estas tres zonas. Una fracción\(q_{ij}\) de la contaminación de la región\(i\) termina al día siguiente en la región\(j\). Una fracción\(q_i = 1 - \sum_j q_{ij} > 0\) entra en la atmósfera y escapa. Dejar\(w_i^{(n)}\) ser la cantidad de contaminación en la zona\(i\) después de\(n\) días.

1. \(\mat{w}^{(n)} = \mat{u} + \mat{u} \mat{Q} +\cdots + \mat{u}\mat{Q}^{n - 1}\)Demuéstralo.

2. Mostrar eso\(\mat{w}^{(n)} \to \mat{w}\), y mostrar cómo calcular a partir de.

3. El gobierno quiere limitar los niveles de contaminación a un nivel prescrito prescribiendo\(\mat{w}.\) Mostrar cómo determinar los niveles de contaminación\(\mat{u}\) que resultarían en un valor limitante prescrito\(\mat{w}\).

i [exer 11.2.21] En el modelo económico Leontief, ⁸ hay\(n\) industrias 1, 2,...,\(n\). La\(i\) industria requiere una cantidad\(0 \leq q_{ij} \leq 1\) de bienes (en valor en dólares) de la compañía\(j\) para producir bienes por valor de 1 dólar. La demanda externa de las industrias, en valor en dólares, viene dada por el vector\(\mat{d} = (d_1,d_2,\ldots,d_n)\). Dejar\(\mat{Q}\) ser la matriz con entradas\(q_{ij}\).

1. Demostrar que si las industrias producen cantidades totales dadas por el vector\(\mat{x} = (x_1,x_2,\ldots,x_n)\) entonces las cantidades de bienes de cada tipo que las industrias necesitarán sólo para satisfacer sus demandas internas viene dada por el vector\(\mat{x} \mat{Q}\).

2. Demostrar que para satisfacer la demanda externa\(\mat{d}\) y las demandas internas las industrias deben producir cantidades totales dadas por un vector\(\mat{x} = (x_1,x_2,\ldots,x_n)\) que satisfaga la ecuación\(\mat{x} = \mat{x} \mat{Q} + \mat{d}\).

3. Demostrar que si\(\mat{Q}\) es la\(\mat{Q}\) -matriz para una cadena absorbente de Markov, entonces es posible satisfacer cualquier demanda externa\(\mat{d}\).

4. Supongamos que las sumas de fila de\(\mat{Q}\) son menores o iguales a 1. Dar una interpretación económica de esta condición. Formar una cadena de Markov tomando a los estados como las industrias y las probabilidades de transición a ser las\(q_{ij}\). Agregar un estado absorbente 0. Definir\[q_{i0} = 1 - \sum_j q_{ij}\ .\] Mostrar que esta cadena va a ser absorbente si cada empresa está obteniendo ganancias o en última instancia depende de una empresa con fines de lucro.

5. \(\mat{x} \mat{c}\)Definir como el producto nacional bruto. Encontrar una expresión para el producto nacional bruto en términos del vector de demanda\(\mat{d}\) y el vector\(\mat{t}\) dando el tiempo esperado para la absorción.

i [exer 11.2.22] Un jugador juega un juego en el que en cada jugada gana un dólar con probabilidad\(p\) y pierde un dólar con probabilidad\(q = 1 - p\). El es el problema de encontrar la probabilidad\(w_x\) de ganar una cantidad\(T\) antes de perderlo todo, comenzando por el estado\(x\). Demostrar que este problema puede ser considerado como una cadena de Markov absorbente con estados 0, 1, 2,...,\(T\) con 0 y estados\(T\) absorbentes. Supongamos que un jugador tiene probabilidad\(p = .48\) de ganar en cada jugada. Supongamos, además, que el jugador empieza con 50 dólares y esos\(T = 100\) dólares. Simula este juego 100 veces y ve con qué frecuencia se arruina el jugador. Esto estima\(w_{50}\).

i [exer 11.2.23] Demostrar que\(w_x\) de Ejercicio [exer 11.2.22] satisface las siguientes condiciones:

1. \(w_x = pw_{x + 1} + qw_{x - 1}\)para\(x = 1\), 2,...,\(T - 1\).

2. \(w_0 = 0\).

3. \(w_T = 1\).

Demostrar que estas condiciones determinan\(w_x\). Demostrar que\(p = q = 1/2\), si, entonces\[w_x = \frac xT\] satisface (a), (b), y (c) y de ahí es la solución. Si\(p \ne q\), muestra que\[w_x = \frac{(q/p)^x - 1}{(q/p)^T - 1}\] satisface estas condiciones y por lo tanto da la probabilidad de que el jugador gane.

i [exer 11.2.24] Escribir un programa para calcular la probabilidad\(w_x\) de Ejercicio [exer 11.2.23] para valores dados de\(x\),\(p\), y\(T\). Estudia la probabilidad de que el jugador arruine el banco en un juego que sólo es ligeramente desfavorable\(p = .49\), digamos, si el banco tiene significativamente más dinero que el jugador.

[exer 11.2.25] Consideramos los dos ejemplos de la Caminata del Borracho correspondientes a los casos\(n = 4\) y\(n = 5\) bloques (ver Ejemplo [examen 11.2.1]). Verificar que en estos dos ejemplos el tiempo esperado para la absorción, a partir de\(x\), sea igual a\(x(n - x)\). A ver si puedes probar que esto es cierto en general.: Demuestre que si\(f(x)\) es el tiempo esperado para la absorción entonces\(f(0) = f(n) = 0\) y\[f(x) = (1/2)f(x - 1) + (1/2)f(x + 1) + 1\] para\(0 < x < n\). Demostrar que si\(f_1(x)\) y\(f_2(x)\) son dos soluciones, entonces su diferencia\(g(x)\) es una solución de la ecuación\[g(x) = (1/2)g(x - 1) + (1/2)g(x + 1)\ .\] También,\(g(0) = g(n) = 0\). Demostrar que no es posible\(g(x)\) tener un máximo estricto o un mínimo estricto en el punto\(i\), donde\(1 \le i \le n-1\). Usa esto para demostrar que\(g(i) = 0\) para todos i. Esto demuestra que hay como mucho una solución. Después verificar que la función\(f(x) = x(n-x)\) sea una solución.

i [exer 11.2.29] Considera una cadena de Markov absorbente con espacio estatal\(S\). Dejar\(f\) ser una función definida en\(S\) con la propiedad que\[f(i) = \sum_{j \in S} p_{ij} f(j)\ ,\] o en forma vectorial\[\mat{f} = \mat{Pf}\ .\] Entonces\(f\) se llama a for\(\mat{P}\). Si imaginas un juego en el que tu fortuna es\(f(i)\) cuando estás en estado\(i\), entonces la condición armónica significa que el juego está en el sentido de que tu fortuna esperada después de un paso es la misma que antes del paso.

1. Demuéstralo para\(f\) armónicos\[\mat{f} = \mat{P}^n{\mat{f}}\] para todos\(n\).

2. Mostrar, usando (a), que para\(f\) armónicos\[\mat{f} = \mat{P}^\infty \mat{f}\ ,\] donde\[\mat{P}^\infty = \lim_{n \to \infty} \mat{P}^n = \pmatrix{\]

   \[\cr}\ .\]

3. Usando (b), demuestre que cuando comienzas en un estado transitorio\(i\) tu fortuna final esperada\[\sum_k b_{ik} f(k)\] es igual a tu fortuna inicial\(f(i)\). En otras palabras, un juego limpio en un espacio estatal finito sigue siendo justo hasta el final. (Los juegos justos en general se llaman Juegos justos en espacios estatales infinitos no necesitan ser justos con un número ilimitado de jugadas permitidas. Por ejemplo, considera el juego de Heads or Tails (ver Ejemplo [examen 1.3]). Que Peter empiece con 1 centavo y juegue hasta que tenga 2. Entonces Peter se asegurará de terminar 1 centavo por delante.)

i [exer 11.2.26] Una moneda es arrojada repetidamente. Nos interesa encontrar el número esperado de lanzados hasta que se produzca por primera vez un patrón particular, digamos B = HTH. Si, por ejemplo, los resultados de los lanzados son HHTTHTH decimos que el patrón B ha ocurrido por primera vez después de 7 tiradas. \(T^B\)Sea el momento de obtener el patrón B por primera vez. Li ⁹ da el siguiente método para determinar\(E(T^B)\).

Estamos en un casino y, antes de cada lanzamiento de la moneda, entra un jugador, paga 1 dólar para jugar, y apuesta a que el patrón B = HTH ocurrirá en los siguientes tres tiradas. Si se produce H, gana 2 dólares y apuesta esta cantidad a que el siguiente resultado será T. Si gana, gana 4 dólares y apuesta esta cantidad que H va a subir la próxima vez. Si gana gana gana 8 dólares y se ha dado el patrón. Si en algún momento pierde, se va sin ganancias.

Que A y B sean dos patrones. Que AB sea la cantidad que ganen los jugadores que lleguen mientras se produce el patrón A y apueste a que se producirá B. Por ejemplo, si A = HT y B = HTH entonces AB = 2 + 4 = 6 ya que el primer jugador apostó por H y ganó 2 dólares y luego apostó por T y ganó 4 dólares más. El segundo jugador apostó por H y perdió. Si A = HH y B = HTH, entonces AB = 2 ya que el primer jugador apostó por H y ganó pero luego apostó por T y perdió y el segundo jugador apostó por H y ganó. Si A = B = HTH entonces AB = BB = 8 + 2 = 10.

Ahora por cada jugador que entra, el casino toma 1 dólar. Así el casino toma en\(T^B\) dólares. ¿Cuánto paga? Los únicos jugadores que se van con algún dinero son los que llegan durante el tiempo que ocurre el patrón B y ganan la cantidad BB. Pero como todas las apuestas realizadas son apuestas perfectamente justas, parece bastante intuitivo que la cantidad esperada que recibe el casino debe ser igual a la cantidad esperada que paga. Es decir,\(E(T^B)\) = BB.

Ya que hemos visto que para B = HTH, BB = 10, el tiempo esperado para alcanzar el patrón HTH por primera vez es 10. Si hubiéramos estado tratando de obtener el patrón B = HHH, entonces BB\(= 8 + 4 + 2 = 14\) ya que los tres últimos jugadores están pagados en este caso. Así, el tiempo esperado para obtener el patrón HHH es de 14. Para justificar este argumento, Li utilizó un teorema de la teoría de las martingales (juegos justos).

Podemos obtener estas expectativas considerando una cadena de Markov cuyos estados son los posibles segmentos iniciales de la secuencia HTH; estos estados son HTH, HT, H y\(\emptyset\), donde\(\emptyset\) está el conjunto vacío. Entonces, para este ejemplo, la matriz de transición es\[\begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% &\mbox{HTH} & \mbox{HT} & \mbox{H} & \emptyset \cr \mbox{HTH} & 1 & 0 & 0 & 0 \cr \mbox{HT} & .5 & 0 & 0 & .5 \cr \mbox{H} & 0 & .5 & .5 & 0 \cr \emptyset & 0 & 0 & .5 & .5 \crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ ,\] y si B = HTH,\(E(T^B)\) es el tiempo esperado de absorción para esta cadena iniciada en estado\(\emptyset\).

Mostrar, utilizando la cadena asociada de Markov, que los valores\(E(T^B)\) = 10 y\(E(T^B)\) = 14 son correctos para el tiempo esperado para alcanzar los patrones HTH y HHH, respectivamente.

i [exer 11.2.27] Podemos usar la interpretación de juego dada en el Ejercicio [exer 11.2.26] para encontrar el número esperado de tiradas requeridas para alcanzar el patrón B cuando comenzamos con el patrón A. Para ser un problema significativo, asumimos que el patrón A no tiene patrón B como subpatrón. \(E_A(T^B)\)Sea el tiempo esperado para alcanzar el patrón B comenzando con el patrón A. Utilizamos nuestro esquema de juego y asumimos que los primeros k tirados de monedas produjeron el patrón A. Durante este tiempo, los jugadores hicieron una cantidad AB. El monto total que los jugadores habrán hecho cuando se produzca el patrón B es BB. Así, la cantidad que hicieron los jugadores después de que se haya producido el patrón A es BB - AB. Nuevamente por el argumento del juego justo,\(E_A(T^B)\) = BB-AB.

Por ejemplo, supongamos que empezamos con el patrón A = HT y estamos tratando de obtener el patrón B = HTH. Entonces vimos en Ejercicio [exer 11.2.26] que AB = 4 y BB = 10 así\(E_A(T ^B)\) = BB-AB= 6.

Verifique que esta interpretación del juego lleve a la respuesta correcta para todos los estados iniciales en los ejemplos en los que trabajó en Ejercicio [exer 11.2.26].

i [exer 11.2.28] Aquí hay un método elegante debido a Guibas y Odlyzko ¹⁰ para obtener el tiempo esperado para alcanzar un patrón, digamos HTH, por primera vez. \(f(n)\)Sea el número de secuencias de longitud\(n\) que no tienen el patrón HTH. \(f_p(n)\)Sea el número de secuencias que tienen el patrón por primera vez después de\(n\) los lanzamientos. A cada elemento de\(f(n)\), agregue el patrón HTH. Luego divida las secuencias resultantes en tres subconjuntos: el conjunto donde se produce HTH por primera vez en el momento\(n + 1\) (para esto, la secuencia original debe haber terminado con HT); el conjunto donde se produce HTH por primera vez en el momento\(n + 2\) (no puede suceder para este patrón); y el conjunto donde la secuencia HTH ocurre por primera vez en el momento\(n + 3\) (la secuencia original terminó con cualquier cosa excepto HT). Haciendo esto, tenemos\[f(n) = f_p(n + 1) + f_p(n + 3)\ .\] Así,\[\frac{f(n)}{2^n} = \frac{2f_p(n + 1)}{2^{n + 1}} + \frac{2^3f_p(n + 3)}{2^{n + 3}}\ .\] Si\(T\) es el momento en que se produce el patrón por primera vez, esta igualdad establece que\[P(T > n) = 2P(T = n + 1) + 8P(T = n + 3)\ .\] Mostrar que si suma esta igualdad sobre todo\(n\) lo que obtiene\[\sum_{n = 0}^\infty P(T > n) = 2 + 8 = 10\ .\] Mostrar que para cualquier variable aleatoria de valor entero\[E(T) = \sum_{n = 0}^\infty P(T > n)\ ,\] y concluir que\(E(T) = 10\). Tenga en cuenta que este método de prueba deja muy claro que\(E(T)\) es, en general, igual a la cantidad esperada que paga el casino y evita el teorema del sistema martingala utilizado por Li.

i [exer 11.2.30] En Ejemplo [examen 11.1.9],\(f(i)\) definir como la proporción de genes G en estado\(i\). Mostrar que\(f\) es una función armónica (ver Ejercicio [exer 11.2.29]). ¿Por qué esto demuestra que la probabilidad de ser absorbido en estado\((\mbox{GG},\mbox{GG})\) es igual a la proporción de genes G en el estado inicial? (Ver Ejercicio [exer 11.2.16].)

i [exer 11.2.31] Demostrar que el modelo de escalón (Ejemplo [examen 11.1.10]) es una cadena de Markov absorbente. Supongamos que estás jugando un juego con cuadrados rojos y verdes, en el que tu fortuna en cualquier momento es igual a la proporción de cuadrados rojos en ese momento. Da un argumento para demostrar que este es un juego limpio en el sentido de que tu ganancia esperada después de cada paso es justo lo que era antes de este paso.: Demuestre que por cada resultado posible en el que tu fortuna disminuya en uno hay otro resultado de exactamente la misma probabilidad donde aumentará en uno.

Usa este hecho y los resultados de Ejercicio [exer 11.2.29] para mostrar que la probabilidad de que un color en particular gane es igual a la proporción de cuadrados que son inicialmente de este color.

i [exer 11.2.32] Considera un andador aleatorio que se mueve sobre los enteros 0, 1,...\(N\), moviendo un paso a la derecha con probabilidad\(p\) y un paso a la izquierda con probabilidad\(q = 1 - p\). Si el andador alguna vez llega a 0 o\(N\) se queda ahí. (Este es el problema de la ruina del jugador del ejercicio [exer 11.2.22].) Si\(p = q\) muestra que la función\[f(i) = i\] es una función armónica (ver Ejercicio [exer 11.2.29]), y si\(p \ne q\) entonces\[f(i) = \biggl(\frac {q}{p}\biggr)^i\] es una función armónica. Usa esto y el resultado del Ejercicio [exer 11.2.29] para mostrar que la probabilidad\(b_{iN}\) de ser absorbido en estado\(N\) comenzando en estado\(i\) es\[b_{iN} = \left \{ \matrix{ \frac iN, &\mbox{if}\,\, p = q, \cr \frac{({q \over p})^i - 1}{({q \over p})^{N} - 1}, & \mbox{if}\,\,p \ne q.\cr}\right.\] Para una derivación alternativa de estos resultados ver Ejercicio [exer 11.2.23].

i [exer 11.2.33] Completar la siguiente prueba alterna del Teorema [thm 11.2.3]. Dejar\(s_i\) ser un estado transitorio y\(s_j\) ser un estado absorbente. Si calculamos\(b_{ij}\) en términos de las posibilidades sobre el resultado del primer paso, entonces tenemos la ecuación\[b_{ij} = p_{ij} + \sum_k p_{ik} b_{kj}\ ,\] donde se realiza la suma sobre todos los estados transitorios\(s_k\). Escribe esto en forma de matriz, y deriva de esta ecuación la declaración\[\mat{B} = \mat{N}\mat{R}\ .\]

i [exer 11.2.34] En la ruleta Monte Carlo (ver Ejemplo [examen 6.1.5]), en la opción (c), hay seis estados (\(S\)\(W\),\(L\),\(E\),\(P_1\), y\(P_2\)). Se hace referencia al lector a la Figura [fig 6.1.5], que contiene un árbol para esta opción. Forma una cadena de Markov para esta opción, y usa el programa AbsorbingChain para encontrar las probabilidades de que ganes, pierdas o rompas para una apuesta de 1 franco en rojo. Usando estas probabilidades, encuentra las ganancias esperadas para esta apuesta. Para una discusión más general de las cadenas de Markov aplicadas a la ruleta, véase el artículo de H. Sagan al que se hace referencia en Ejemplo [examen 6.7].

i [exer 11.5.26] Consideramos a continuación un juego llamado por su inventor W. Penney. ¹¹ Hay dos jugadores; el primer jugador elige un patrón A de H y T, y luego el segundo jugador, sabiendo la elección del primer jugador, elige un patrón diferente B. Suponemos que ninguno de los patrones es un subpatrón del otro patrón. Una moneda se lanza una secuencia de veces, y el jugador cuyo patrón aparece primero es el ganador. Para analizar el juego, necesitamos encontrar la probabilidad de\(p_A\) que el patrón A ocurra antes del patrón B y la probabilidad de\(p_B = 1- p_A\) que el patrón B ocurra antes del patrón A. Para determinar estas probabilidades utilizamos los resultados de Ejercicios [exer 11.2.26] y [exer 11.2.27]. Aquí se le pidió que demostrara que, el tiempo esperado para alcanzar un patrón B por primera vez es,\[E(T^B) = BB\ ,\] y, comenzando con el patrón A, el tiempo esperado para alcanzar el patrón B es\[E_A(T^B) = BB - AB\ .\]

1. Demuestre que las probabilidades de que gane el primer jugador están dadas por la fórmula ¹² de John Conway:\[\frac{p_A}{1-p_A} = \frac{p_A}{p_B} = \frac{BB - BA}{AA - AB}\ .\]: Explique por qué\[E(T^B) = E(T^{A\ {\rm or}\ B}) + p_A E_A(T^B)\]

   y así\[BB = E(T^{A\ {\rm or}\ B}) + p_A (BB - AB)\ .\] Intercambiar A y B para encontrar una ecuación similar que involucre el\(p_B\). Por último, tenga en cuenta que\[p_A + p_B = 1\ .\] Utilice estas ecuaciones para resolver para\(p_A\) y\(p_B\).

2. Supongamos que ambos jugadores eligen un patrón de la misma longitud k Demostrar que\(k = 2\), si, este es un juego limpio, pero, si\(k = 3\), el segundo jugador tiene una ventaja sin importar la elección que haga el primer jugador. (Se ha demostrado que, para\(k \geq 3\), si el primer jugador elige\(a_1\),\(a_2\),...\(a_k\), entonces la estrategia óptima para el segundo jugador es de la forma\(b\),\(a_1\),...,\(a_{k - 1}\) donde\(b\) está la mejor de las dos elecciones H o T. ¹³)