Subversion Repositories wimsdev

Rev

Rev 15373 | Rev 15495 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 15373 Rev 15462
Line 9... Line 9...
9 
:
 9 
:
10 
<div class="wims_defn">
 10 
<div class="wims_defn">
11 
    <h4>Définitions</h4>
 11 
    <h4>Définitions</h4>
12 
  <ul>
 12 
  <ul>
13 
    <li>
 13 
    <li>
- 
 
 14 
      Un <strong>graphe probabiliste</strong> est un graphe orienté pondéré dans
14 
      Un <strong>graphe probabiliste</strong> est un graphe orienté pondéré dans lequel la somme des poids des arêtes issues de chaque sommet est égale à 1.
 15 
      lequel la somme des poids des arêtes issues de chaque sommet est égale à 1.
15 
    </li><li>
 16 
    </li><li>
- 
 
 17 
      La <strong>matrice de transition</strong> associée à un graphe probabiliste
- 
 
 18 
      d'ordre \(n\) est la matrice carrée \(M =(a_{i,j})\) d'ordre \(n\) telle
- 
 
 19 
      que, pour tous entiers \(i\) et \(j\) vérifiant \(1\leqslant i\leqslant n\)
- 
 
 20 
      et <span style="white-space:nowrap">\(1\leqslant j\leqslant n\),</span>
- 
 
 21 
      \(a_{i,j}\) est égal au poids de l'arête orientée d'origine le sommet \(i\)
16 
      La <strong>matrice de transition</strong> associée à un graphe probabiliste d'ordre \(n\) est la matrice carrée \(M =(a_{i,j})\) d'ordre \(n\) telle que, pour tous entiers \(i\) et \(j\) vérifiant \(1\leqslant i\leqslant n\) et \(1\leqslant j\leqslant n\!,\) \(a_{i,j}\) est égal au poids de l'arête orientée d'origine le sommet \(i\) et d'extrémité le sommet \(j\) si cette arête existe, et est égal à \(0\) sinon.
 22 
      et d'extrémité le sommet \(j\) si cette arête existe, et est égal à \(0\)
- 
 
 23 
      sinon.
17 
      <br/>
 24 
      <br/>
18 
      Cette matrice décrit le passage d'un état au suivant.
 25 
      Cette matrice décrit le passage d'un état au suivant.
19 
    </li><li>
 26 
    </li><li>
20 
      Un <strong>état probabiliste</strong> est une loi de probabilité sur l'ensemble des états possibles.
 27 
      Un <strong>état probabiliste</strong> est une loi de probabilité sur
- 
 
 28 
      l'ensemble des états possibles.
21 
      <br/>
 29 
      <br/>
22 
      Cette loi est représentée par une matrice ligne.
 30 
      Cette loi est représentée par une matrice ligne.
23 
    </li>
 31 
    </li>
24 
  </ul>
 32 
  </ul>
25 
</div>
 33 
</div>
26 
 
 34 
 
27 
<div class="wims_thm">
 35 
<div class="wims_thm">
28 
    <h4>Théorème 1</h4>
 36 
    <h4>Théorème 1</h4>
- 
 
 37 
  Soit \(M\) la matrice de transition d'un graphe probabiliste, \(P_0\) la
29 
  Soit \(M\) la matrice de transition d'un graphe probabiliste, \(P_0\) la matrice ligne décrivant l'état initial et \(P_n\) l'état probabiliste à l'étape \(n\), où \(\n \in \NN\!.\)
 38 
  matrice ligne décrivant l'état initial et \(P_n\) l'état probabiliste à l'étape
- 
 
 39 
  \(n\), où <span style="white-space:nowrap">\(\n \in \NN\).</span>
30 
  <br/>
 40 
  <br/>
31 
  Pour tout \(n\in \NN\!,\) \(P_n=P_0 . M^n \!.\)
 41 
  Pour tout \(n\in \NN\), \(P_n=P_0 . M^n\).
32 
</div>
 42 
</div>
33 
<div class="wims_thm">
 43 
<div class="wims_thm">
34 
  <h4>Théorème 2</h4>
 44 
  <h4>Théorème 2</h4>
- 
 
 45 
  Pour tout graphe probabiliste d'ordre 2 dont la matrice de transition \(M\) ne
- 
 
 46 
  comporte pas de <span style="white-space:nowrap">\(0\),</span> l'état \(P_n\)
35 
  Pour tout graphe probabiliste d'ordre 2 dont la matrice de transition \(M\) ne comporte pas de \(0\!,\) l'état \(P_n\) converge vers un état \(P\) indépendant de l'état initial \(P_0\) et \(P\) est l'unique solution de l'équation \(X=X . M\) où \(X=[x,y]\), \(x\in [ 0;1]\), \(y\in [ 0;1]\), et \(x + y = 1\!.\)
 47 
  converge vers un état \(P\) indépendant de l'état initial \(P_0\) et \(P\) est
- 
 
 48 
  l'unique solution de l'équation \(X=X . M\) où
- 
 
 49 
  <span style="white-space:nowrap">\(X=[x,y]\),</span>
- 
 
 50 
  <span style="white-space:nowrap">\(x\in [ 0;1]\),</span>
- 
 
 51 
  <span style="white-space:nowrap"> \(y\in [ 0;1]\),</span> et
- 
 
 52 
  <span style="white-space:nowrap">\(x + y = 1\).</span>
36 
</div>
 53 
</div>