Chaîne de Markov (absorption)
Je viens de commencer à apprendre la chaîne de Markov et je ne sais pas comment résoudre ce problème
Un homme roule un rocher sur une colline de 40 mètres de haut. Chaque minute, avec une probabilité de 1/3, il parvient à faire rouler le rocher d'un mètre, tandis qu'avec une probabilité de 2/3, le rocher roule d'un mètre vers le bas. Si l'homme est actuellement à mi-chemin vers le sommet, quelle est la probabilité qu'il atteigne le sommet avant de redescendre vers les contreforts?
Réponses
Il serait exagéré de résoudre ce problème en utilisant la théorie de la chaîne de Markov: mais les concepts sous - jacents vous aideront à le cadrer d'une manière qui admet une solution simple.
Formuler le problème
Le concept le plus fondamental est celui d'un état: on peut modéliser cette situation en termes de 41 positions distinctes, ou «états», situées à des intervalles d'un mètre de hauteur du bas (hauteur -40) au sommet (hauteur 0) de la colline. L'état actuel, à mi-hauteur de la colline, est une hauteur de -20.
Le deuxième concept fondamental est celui de l' indépendance vis-à-vis des événements passés: les chances de ce qui se passe ensuite ne dépendent que de l'État, et non des détails sur la manière dont l'homme est arrivé là-bas. Par conséquent, les chances d'atteindre le sommet ne dépendent que de l'État. En conséquence, si nous écrivons$s$ pour un Etat, la chance d'atteindre le sommet peut s'écrire simplement $p(s).$ On nous demande de trouver $p(-20).$
De n'importe quel état $s$ entre $-40$ et $0$ Il y a un $1/3$ chance que $s+1$ sera le prochain état et un $2/3$ chance que $s-1$sera le prochain état. Les lois les plus élémentaires de la probabilité conditionnelle impliquent alors
$$p(s) = (1/3)p(s+1) + (2/3)p(s-1) = \frac{p(s+1)+2p(s-1)}{3}.\tag{*}$$
La dernière étape de formulation du problème traite les points de terminaison, ou «états absorbants» $s=0$ et $s=-40.$ Il devrait être clair que
$$p(0)=1;\ p(-40)=0.\tag{**}$$
Une analyse
À ce stade, le travail peut sembler formidable: qui veut résoudre une séquence de 40 équations? Une belle méthode de résolution combine toutes les équations en un seul objet mathématique. Mais avant de continuer, permettez-moi de faire remarquer que vous n'avez pas besoin de suivre cette analyse: il suffira de vérifier que la formule finale (mise en évidence ci-dessous) satisfait toutes les conditions établies par le problème - et ce n'est qu'une question de algèbre simple.
À ce stade, il est utile de résoudre le problème général. Supposons qu'il y ait une séquence d'états$s=0,1,2,\ldots, n$ et que chaque état $s$ entre $1$ et $n-1$ transitions vers $s-1$ avec probabilité $p$ et à $s+1$ avec probabilité $1-p.$ Pour tous $s$ laisser $a_s$ être la chance d'arriver à l'état $0$ avant de frapper l'état $n.$ (J'ai laissé tomber le précédent "$p(-s)$"notation car elle conduit à trop de p et je suis passé de l'indexation des états avec des nombres négatifs à leur indexation avec des nombres positifs.)
Comme nous l'avons vu, $a_0=1,$ $a_n=0,$ et autrement $a_{s} = pa_{s-1} + (1-p)a_{s+1}$(la "relation de récurrence"). Cet ensemble d'équations est soigneusement codé par un polynôme
$$P(t) = a_0 + a_1 t + a_2 t^2 + \cdots + a_n t^n = a_0 + \sum_{s=1}^{n} a_s t^s.$$
Brancher la relation de récurrence puis collecter les pouvoirs communs de $t$ (l'écriture $a_{n+1}=0$ pour plus de commodité) donne
$$\begin{aligned} P(t) &= a_0 + \sum_{s=1}^n \left[pa_{s-1} + (1-p)a_{s+1}\right]t^s \\ &= a_0 + p\sum_{s=1}^n a_{s-1} t^s + (1-p)\sum_{s=1}^n a_{s+1}t^s\\ &= a_0 + pt\sum_{s=1}^n a_{s-1} t^{s-1} + \frac{1-p}{t}\sum_{s=1}^n a_{s+1}t^{s+1}\\ &= a_0 + pt\sum_{s=0}^{n-1} a_{s} t^{s} + \frac{1-p}{t}\sum_{s=2}^{n+1} a_{s}t^{s}\\ &= a_0 + pt(P(t) - a_nt^n) + \frac{1-p}{t}(P(t) - a_0 - a_1t) \end{aligned}$$
Ceci est une équation unique pour le polynôme$P$ (au moins jusqu'à $t^n;$ J'ignorerai tous les coefficients de $t^n$ou des puissances plus élevées qui pourraient être nécessaires pour que l'équation fonctionne exactement.) Simplifiez un peu cette équation en utilisant la condition initiale $a_0=1$ et résoudre pour $P$ obtenir
$$P(t) = \frac{(1-p) + (-1 + (1-p)a_1)t}{pt^2 - t + (1-p)}.$$
Maintenant, chaque coefficient de$P$ peut être exprimé en termes de nombre (encore inconnu) $a_1.$ La valeur de $a_1$ est déterminé par la condition finale $a_n=0.$
Une formule fermée est possible en développant le côté droit comme une fraction partielle. Cela revient à observer
$$\frac{1}{pt^2 - t + (1-p)} = \frac{1}{1-2p}\left(\frac{1}{1-t} - \frac{\lambda}{1 - \lambda t}\right)$$
et en développant les fractions comme des sommes de séries géométriques, toutes deux sous la forme
$$\frac{\rho}{1 - \rho t} = \rho + \rho^2 t + \rho^3 t^2 + \cdots$$
et en multipliant cela par le numérateur $(1-p) + (-1 + (1-p)a_1)t$ obtenir $P(t).$ Cela donne une formule fermée pour chaque terme de $P(t)$ en tant que fonction de $a_1.$
Pour $p\ne 1/2$ et l'écriture $\lambda = p/(1-p)$ cette approche donne le résultat général
$$a_s = \frac{\lambda^s - \lambda^n}{1 - \lambda^n}$$
pour $s=1, 2, \ldots, n$ (et cela fonctionne pour $s=0,$aussi). (Quand$p=1/2,$ $\lambda=1$rend cette formule indéfinie. Cependant, vous pouvez facilement trouver une formule simple en prenant la limite de$a_s$ comme $\lambda\to 1$ en utilisant une seule application de la Règle de L'Hôpital.)
A titre de vérification, il est clair que cette formule donne $a_0=1$ et $a_n=0.$ Il reste à vérifier qu'il satisfait la relation de récurrence, mais il s'agit de montrer
$$\frac{\lambda^s - \lambda^n}{1 - \lambda^n} = a_s = pa_{s-1} + (1-p)a_{s+1} = p\frac{\lambda^{s-1} - \lambda^n}{1 - \lambda^n} + (1-p)\frac{\lambda^{s+1} - \lambda^n}{1 - \lambda^n},$$
ce qui est simple.
Application
Dans le problème donné $n=40,$ $p=1/3,$ et on nous demande de trouver $a_{20}.$ par conséquent $\lambda = (1/3)\,/\,(1-1/3) = 1/2$ et
$$a_{20} = \frac{2^{-20} - 2^{-40}}{1 - 2^{-40}} = 2^{-20} - 2^{-40} + 2^{-60} - 2^{-80} + \cdots.$$
L'expansion sur le côté droit peut être terminée après les deux premiers termes lors du calcul en virgule flottante double précision (qui a une précision de $52$ places binaires), donnant
$$a_{20} \approx 2^{-20} - 2^{-40} \approx 9.53673406911546\times 10^{-7};$$
un peu moins d'un sur un million.
Imaginez que le voyage d'escalade se compose de 41 états, un pour chaque mètre possible, donc des états 0, 1, 3, ...., 40. La matrice de probabilité de transition devient alors une matrice 41x41, représentant les différentes probabilités de passer d'un état à un autre. Cela ressemble à ceci:
0 1 2 -- 40
0 0 1 0 -- 0
1 2/3 0 1/3 -- 0
2 0 2/3 0 -- 0
| | | | -- |
| | | | -- |
40 0 0 0 -- 0
Appelons cette matrice P. Si nous commençons à 20 mètres, avec d' autres mots à l' état 20, nous pouvons représenter cela comme un vecteur (41 éléments longs) avec les probabilités de départ dans chaque état, appelé u, u=[0,0, ... , 0, 1, 0 ... 0, 0]où la 1représentent une probabilité de 100% de à partir de 20 mètres .
La multiplication matricielle u*P,, devient alors les probabilités de se retrouver dans tous les autres états au pas de temps t +1. Si nous continuons à faire cette multiplication matricielle encore et encore, u*P^toù t va vers l'infini, nous atteindrons une matrice P * en régime permanent. Cette matrice d'état stationnaire représente les probabilités de se retrouver dans tous les autres états.
Donc, dans votre cas, vous feriez cette multiplication matricielle dans un langage de programmation de votre choix plusieurs fois (par exemple 100+), et vous chercheriez simplement P[20,40], ce qui vous donnerait la probabilité de commencer à 20 mètres et de faire tout le chemin au sommet de la colline!