{"id":6426,"date":"2018-06-21T10:04:30","date_gmt":"2018-06-21T09:04:30","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6426"},"modified":"2022-12-03T23:00:45","modified_gmt":"2022-12-03T22:00:45","slug":"probabilite-datteinte-dun-etat","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/markov-process\/probability-of-a-state\/","title":{"rendered":"Probability of reaching a condition"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6426\" class=\"elementor elementor-6426\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e495dc9 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e495dc9\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-c71b333\" data-id=\"c71b333\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8162b8a elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"8162b8a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Markov process<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-adb322b\" data-id=\"adb322b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7cbc121 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"7cbc121\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-105809b\" data-id=\"105809b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ac99760 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"ac99760\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Cha%C3%AEne_de_Markov\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-846efe8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"846efe8\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e97b97f\" data-id=\"e97b97f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-20d133b elementor-widget elementor-widget-progress\" data-id=\"20d133b\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"progress.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t<span class=\"elementor-title\" id=\"elementor-progress-bar-20d133b\">\n\t\t\t\tDifficulty\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-20d133b\" class=\"elementor-progress-wrapper\" role=\"progressbar\" aria-valuemin=\"0\" aria-valuemax=\"100\" aria-valuenow=\"50\" aria-valuetext=\"50% (Moyen)\">\n\t\t\t<div class=\"elementor-progress-bar\" data-max=\"50\">\n\t\t\t\t<span class=\"elementor-progress-text\">Average<\/span>\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-progress-percentage\">50%<\/span>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-26ace78d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"26ace78d\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7fcb9f7d\" data-id=\"7fcb9f7d\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-108da3df elementor-widget elementor-widget-text-editor\" data-id=\"108da3df\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/probability-of-a-state\/#Probabilite-datteinte-dun-etat\" >Probability of reaching a condition<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/probability-of-a-state\/#Exemple-de-probabilite-datteinte-dun-etat\" >Example of probability of reaching a state<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/probability-of-a-state\/#Temps-moyen-datteinte-a-partir-dune-configuration\" >Average time to reach from a configuration<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/probability-of-a-state\/#Exemple-de-temps-moyen-datteinte\" >Example of average time to reach<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Probabilite-datteinte-dun-etat\"><\/span>Probability of reaching a condition<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The probability of reaching a state and by extension the time to reaching a state refers to the number of times before reaching a state in the Markov chain.<\/p>\n<p>(X<sub>not<\/sub>)<sub>not<\/sub> means a <a href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/discrete-time-markov-chains\/\">markov chain<\/a> homogeneous of finite or countable state space X of transition matrix Q: we can interpret X<sub>not<\/sub> as modeling the state of a system at time n.<\/p>\n<p><\/p>\n<p>The initial chain law (X<sub>not<\/sub>) having been fixed, only the states likely to be reached intervene in the study of the evolution of the chain. We put X<sub>To<\/sub> = {x \u2208 X, there exists n \u2265 0, P (X<sub>not<\/sub> = x)&gt; 0}.<\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>For a state e \u2208 X<sub>To<\/sub>, we will denote by T<sup>(not)<\/sup><sub>e<\/sub> the time it takes for the chain to reach state e strictly after time n:<\/p>\n<ul>\n<li>T<sup>(not)<\/sup><sub>e<\/sub> therefore denote the smallest integer k&gt; 0 such that X<sub>n + k<\/sub> = e if the chain passes through e after time n<\/li>\n<li>T<sup>(not)<\/sup><sub>e<\/sub> = + \u221e if the chain does not pass through the state e after time n.<\/li>\n<li>To simplify the notations T<sup>(0)<\/sup><sub>e<\/sub> will also be denoted simply T<sub>e<\/sub>.<\/li>\n<\/ul>\n<\/div>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>Let i, e \u2208 X<sub>To<\/sub>.<\/p>\n<ul>\n<li>For all n \u2208 N and k \u2208 N<sup>\u2217<\/sup> , the probability of reaching state e at time n + k for the first time after time n knowing that X<sub>not<\/sub> = i does not depend on n, we will denote it f<sub>ie<\/sub>(k) = P (T<sup>(not)<\/sup><sub>e<\/sub> = k | X<sub>not<\/sub> = i). It satisfies the following equation: f<sub>ie<\/sub>(1) = Q (i, e) and f<sub>ie<\/sub>(k) = \u2211<sub>j\u2208X \\ {e}<\/sub> Q (i, j) f<sub>I<\/sub>(k - 1) for all k \u2265 2.<\/li>\n<\/ul>\n<p>The equation for f<sub>ie<\/sub>(k) simply translates the fact that to arrive for the first time in state e in k steps, starting from state i, it is necessary to go from state i to state j \u2260 e, then starting from j , arrive for the first time in e in k - 1 step.<\/p>\n<ul>\n<li>The probability of reaching a state e after time n, knowing that X<sub>not<\/sub> = i does not depend on n, we will denote it f<sub>ie<\/sub> : f<sub>ie<\/sub> = P (T<sup>(not)<\/sup><sub>e<\/sub> &lt;+ \u221e | X<sub>not<\/sub> = i). She checks: f<sub>ie<\/sub> = Q (ie) + \u2211<sub>j\u2208X \\ {e}<\/sub> Q (i, j) f<sub>I<\/sub>.<\/li>\n<\/ul>\n<p>The equation for f<sub>ie<\/sub> reflects the fact that the chain reaches e from a state i either directly, or passes from state i to a state j \u2260 e then reaches e from state j.<\/p>\n<\/div>\n<p><\/p>\n<p>Note that f<sub>ie<\/sub>= 1 if and only if f<sub>I<\/sub>= 1 for any state j \u2260 e such that Q (i, j)&gt; 0.<\/p>\n<p><\/p>\n<p>When the string is <a href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/invariant-law-and-asymptotic-behavior\/\">ergodic<\/a>, it is possible to calculate the time to return to a state by calculating the inverse of the stationary probability. For that it is necessary that all the states are positive recurrent, that is to say that its expectation is positive and not infinite:<\/p>\n<p><\/p>\n<figure><img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/proba30.png\" alt=\"probability of reaching a condition\" width=\"459\" height=\"82\" title=\"\"><\/figure>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple-de-probabilite-datteinte-dun-etat\"><\/span>Example of probability of reaching a state<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>In order to show how to calculate the probability of reaching a state, we will take the following example.<\/p>\n<p>Suppose the player has 1 euro and plays a game of chance where the stake is 1 euro until he has reached the sum of 3 euro or until he is ruined.<\/p>\n<p><\/p>\n<p>Recall that p denotes the probability that he wins a game and therefore wins 1 euro and 1 \u2212 p is the probability that he loses the game and therefore loses 1 euro.<\/p>\n<p><\/p>\n<p>We are looking for the probability that he will thus succeed in having 3 euros, that is to say f<sub>1,3<\/sub>. The equation with i = 1 and e = 3 is written f<sub>1,3<\/sub> = pf<sub>2,3<\/sub> + (1 - p) f<sub>0,3<\/sub>. We af<sub>0,3<\/sub> = 0 since the player cannot play if he has no money initially (0 is an absorbing state). It remains to write the equation for f<sub>2,3<\/sub> which is the probability that a player manages to get 3 euros if he initially has 2 euros. We get: f<sub>2,3<\/sub> = 1 - p + (1 - p) f<sub>1,3<\/sub>. We therefore have to solve a system of 2 equations with 2 unknowns: {f<sub>1,3<\/sub> = pf<sub>2,3<\/sub>; f<sub>2,3<\/sub> = p + (1 - p) f<sub>1,3<\/sub>}.<\/p>\n<p><\/p>\n<p>This system has only one solution which is f<sub>2,3<\/sub> = p \/ (1 \u2212 p (1 \u2212 p) and f<sub>1,3<\/sub> = p\u00b2 \/ 1 \u2212 p (1 \u2212 p).<\/p>\n<p><\/p>\n<p>In particular, if the game is fair, i.e. if p = 1\/2, we have<sub>1,3<\/sub> = 1\/3 which means that if the player initially has 1 euro, he has a one in three chance of getting 3 euros. The probability that the game will stop because the player is ruined is calculated in a similar way by writing the equations satisfied by f<sub>1,0<\/sub>, f<sub>2,0<\/sub> and F<sub>3,0<\/sub> and by solving the obtained system. This calculation shows that f<sub>1,0<\/sub> + f<sub>1,3<\/sub> = 1, which means that the player necessarily stops at the end of a finite number of games, either because he has managed to obtain 3 euros, or because he is ruined.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Temps-moyen-datteinte-a-partir-dune-configuration\"><\/span>Average time to reach from a configuration<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div>In addition to the probability of reaching a state, it is possible to calculate the average time to reach this state.<\/div>\n<p><\/p>\n<p>The mean time to reach is the smallest positive solution in the system:<\/p>\n<p><\/p>\n<figure><img fetchpriority=\"high\" decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/proba22.png\" alt=\"probability of reaching a condition\" width=\"772\" height=\"82\" title=\"\"><\/figure>\n<p><\/p>\n<p>where the absorbent class designates the states in which the system begins. Indeed, since we start from these states, the average time to reach them is 0 movement.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple-de-temps-moyen-datteinte\"><\/span>Example of average time to reach<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div>Here the probability of reaching a state is not calculated. In fact, the probability of reaching a state and the average time to reaching states must be studied together.<\/div>\n<p><\/p>\n<p>A chip jumps over a triangle, with a probability 2\/3 clockwise, and 1\/3 counterclockwise.<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>The vertices are numbered: 1,2,3.<\/li>\n<li>Let&#039;s take a look at the hit times. We start from summit 1. We have<br \/>for i = 1: x<sub>1<\/sub>=0<\/li>\n<li>For i = 2, 3, we have to solve the following systems:\n<ul>\n<li>x<sub>2<\/sub>= 1 + 1\/3 x<sub>1<\/sub>\u00a0+ 0 x<sub>2<\/sub>+ 2\/3 x<sub>3<\/sub><\/li>\n<li>x<sub>3<\/sub>= 1 + 2 \/ 3x<sub>1<\/sub>+ 1\/3 x<sub>2<\/sub>+ 0 x<sub>3<\/sub><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p><\/p>\n<p>Which gives for solution the vector (0, 15\/7, 12\/7)<\/p>\n<p><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Markov process Home page Wiki Difficulty Average 50% Probability of reaching a state The probability of reaching a state and by extension the time to reach a \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":5007,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-6426","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6426","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=6426"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6426\/revisions"}],"predecessor-version":[{"id":18625,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6426\/revisions\/18625"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/5007"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=6426"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}