10.2.1: Aplicaciones de las Cadenas de Markov (Ejercicios)

Última actualización
Guardar como PDF

Page ID: 113848

$ \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}$

SECCIÓN 10.2 CONJUNTO DE PROBLEMAS: APLICACIONES DE CADENAS MARKOV

Las preguntas 1-2 se refieren a lo siguiente:

Referencia: Bart Sinclair, Modelo de Reparación de Maquinas. OpenStax CNX. Jun 9, 2005 Creative Commons Licencia de atribución 1.0. Descárgalo gratis en http://cnx.org/contents/56f1bed0-bd34-4c28-a2ec-4a3f9ded8e18@3. Este material ha sido modificado por Roberta Bloom, según lo permitido bajo dicha licencia.

Una cadena de Markov se puede utilizar para modelar el estado de los equipos, como una máquina utilizada en un proceso de fabricación. Supongamos que los estados posibles para la máquina son

Trabajo inactivo y en espera (I) Trabajo en un trabajo/tarea (W) Roto (B) En reparación (R)

La máquina es monitoreada a intervalos regulares para determinar su estado; para facilitar la interpretación en este problema, asumimos que el estado se monitorea cada hora. La matriz de transición se muestra a continuación:

$Sección10.5.2.png$

Utilice la matriz de transición para identificar las siguientes probabilidades con respecto al estado de la máquina dentro de una hora
1. Encuentra la probabilidad de que la máquina esté trabajando en un trabajo dentro de una hora si la máquina está inactiva ahora.
2. Encuentra la probabilidad de que la máquina esté inactiva dentro de una hora si la máquina está trabajando en un trabajo ahora.
3. Encuentra la probabilidad de que la máquina esté trabajando en un trabajo dentro de una hora si la máquina está siendo reparada ahora.
4. Encuentra la probabilidad de que la máquina esté siendo reparada en una hora si está rota ahora.

Realizar los cálculos apropiados utilizando la matriz de transición para encontrar las siguientes probabilidades respecto al estado de la máquina dentro de tres horas.
1. Encuentra la probabilidad de que la máquina esté trabajando en un trabajo dentro de tres horas si la máquina está inactiva ahora.
2. Encuentra la probabilidad de que la máquina esté inactiva dentro de tres horas si la máquina está trabajando en un trabajo ahora.
3. Encuentra la probabilidad de que la máquina esté trabajando en un trabajo dentro de tres horas si la máquina está siendo reparada ahora.
4. Encuentra la probabilidad de que la máquina esté siendo reparada en tres horas si está rota ahora.

Las preguntas 3-4 se refieren a la siguiente descripción de cómo se podría usar una cadena de Markov para “entrenar” una computadora para generar música.

Enseñar una teoría musical por computadora para que pueda crear música sería una tarea sumamente tediosa.
Tendrías que enseñar estructura de acordes, diferentes estilos musicales, y así sucesivamente. Y si pudieras darle al programa ejemplos de piezas que considerabas música y preguntarle, “escribe algo así para mí”. Así es esencialmente como funcionaría nuestra cadena Markov. El principio detrás de las cadenas de Markov en la música es generar una tabla de probabilidad para determinar qué nota debería venir después. Al alimentar al programa con una pieza musical de ejemplo, el programa puede analizar la pieza y crear una tabla de probabilidad para determinar qué notas son más probables que sigan una nota dada. Con la matriz de transición de probabilidad se pueden generar notas aleatorias que aún tienen alguna estructura musical. Al construir una matriz similar para ritmos o duraciones de notas, se puede completar un modelo de cadena de Markov para la generación de música.

Fuente: © Dic 18, 2008 Frank Chen. El contenido del libro de texto producido por Frank Chen está bajo una licencia Creative Commons Attribution License 2.0. Descárgalo gratis en http://cnx.org/contents/62219fba-96df-418a-b9aa-14fddd7c30fa@2.” Modificado por Roberta Bloom, según lo permitido bajo esta licencia.

La matriz de transición a continuación proporciona un ejemplo. Los estados son las notas A, A#, B, C, D, E, F, G, G#.
La matriz muestra la probabilidad de la siguiente nota (estado de columna), dada la nota actual (estado de fila).

Para generar música creada por computadora, un programa de computadora seleccionaría aleatoriamente la siguiente nota basada en la nota anterior y las probabilidades dadas en la matriz de transición.

$Sección10.5.2-3.png$

Encuentra la probabilidad para la siguiente nota, dada la nota actual
1. P (la siguiente nota es A | la nota actual es G) = ______
2. P (la siguiente nota es G | la nota actual es A) = ______
3. P (la siguiente nota es C | la nota actual es F) = ______
4. P (la siguiente nota es E | la nota actual es D) = ______

4a. Si la nota actual es A# (A-sharp) ¿qué nos dice la matriz de transición sobre la siguiente nota?

4b. Si la siguiente nota es F, qué sabemos de la nota actual.

La pregunta 5 se refiere a lo siguiente:

Las cadenas de Markov juegan un papel importante en la búsqueda en línea.

“PageRank es un algoritmo utilizado por Google Search para clasificar los sitios web en los resultados de sus motores de búsqueda. PageRank lleva el nombre de Larry Page, uno de los fundadores de Google. PageRank es una forma de medir la importancia de las páginas del sitio web”
Fuente: https://en.Wikipedia.org/wiki/PageRank bajo la Licencia Creative Commons Reconocimiento-CompartirIgual;

La teoría detrás de PageRank es que las páginas a las que se vinculan más a menudo son más importantes y útiles; identificar aquellas a las que se vinculan más a menudo sobre un tema ayuda a identificar las páginas que deben presentarse como más pertinentes en una búsqueda.

En la búsqueda del mundo real, hay miles o millones de páginas enlazando entre sí, lo que resulta en enormes matrices de transición. Debido al tamaño y otras propiedades de estas matrices, las matemáticas detrás de PageRank son más sofisticadas que el pequeño ejemplo que examinamos aquí con solo cuatro sitios web. Sin embargo, nuestro ejemplo es adecuado para transmitir el concepto principal de PageRank y su uso en algoritmos de búsqueda.

Cabe señalar que los algoritmos de búsqueda del mundo real, PageRank o esquemas similares de clasificación en cadena de Markov son solo uno de una variedad de métodos utilizados.

Supongamos que tenemos 4 páginas web que contienen enlaces entre sí. Llamamos a las páginas A, B, C, D.

De la página A, el 30% de las personas enlazan a la página B, el 50% enlazan a la página C y el 20% enlazan a la página D
De la página B, el 50% del popele enlaza a la página A y el 50% a la página D
De la página C, el 10% de las personas enlazan a la página B, el 70% a la página C y el 20% enlazan a la página D
De la página D, el 20% de las personas enlazan a la página A, el 40% a la página B, el 10% a la página C y el 30% enlazan a la página D

(En este ejemplo, cuando una página se vincula a sí misma, significa que una persona que ve la página se queda en esa página y no enlaza con otra página).

Escribir la matriz de transición T	Encuentra la probabilidad de que una persona que esté viendo la página C se vincule a la página D siguiente.
Encuentra la probabilidad de que una persona que ve la página C vea la página D después de dos enlaces	Encuentra la probabilidad de que una persona que ve la página C vea la página D después de tres enlaces
Encuentra la probabilidad de que una persona que esté viendo la página C se quede en la página C y no se vincule a ninguna otra página siguiente.	Encuentra la probabilidad de que una persona que ve la página C vea la página A siguiente

Search

Text Color

Text Size

Margin Size

Font Type