Champs de Markov - Introduction

Introduction

Definition
Statistiques: comptage et representation de donnees

Definition
Probabilite: phenomene dont on extrait un modele

Optimisation combinatoire

On a une grille, on veut la remplir pour que ca devienne un echequier via un algorithme

Est-ce que notre algo est deterministe ?
Oui, car on a toujours le meme resultat avec la meme entree.

Si la couleur d'une case est aleatoire, l'algo n'est plus deterministe.

Definition
Un algo est stochastique si a l'interieur il y a de l'aleatoire

# algo
rand()
#algo

L'aleatoire provient de l'entree

Il existe des programmes stochastisques et deterministes.

rand() est-il deterministe ?

Oui. C'est dingue, hein ?

$$\begin{gathered} \mathrm{\Omega }=\{A,B,C,D\} \\ \{\begin{array}{l}P(A)\in [0,1],\text{idem pour }B,C\text{ et }D\\ P(A)+P(B)+P(C)+P(D)=1\end{array} \end{gathered}$$

Exemple

Nous sommes une population, on mesure la probabilite d'avoir 20 ans.

$$\underset{P(A)}{\underbrace{P(20)}}=0.36$$

Maintenant avec la meteo:

$$\begin{gathered} \mathrm{\Omega }=\{\text{beau},\text{pluie},\text{couvert}\} \\ \{\begin{array}{l}P(\text{beau})=0.51\\ P(\text{pluie})=0.01\\ P(\text{couvert})=1-0.21-0.01\end{array} \end{gathered}$$

Faire action avec la proba

$P$

$$P(\varnothing )=P(1)=P(2)=...=\frac{1}{\text{RANDMAX}}$$

Retour sur la meteo:

$$\{\begin{array}{l}P(\text{beau})=0.3\\ P(\text{pluie})=0.5\\ P(\text{couvert})=0.2\end{array}$$

Le probleme: certaines variables aleatoires ne sont pas independante (salaire, categorie pro, etc.)

SUDOKU

On doit ecrire un programme qui resout le sudoku

	1
		2
		3
2			$◻$

On a

$$4^{12}=16,7M$$ de valeur possibles.

On va bruteforce, cad visiter plein de chemins possibles pour remplir. Les

$16$ millions de possibilites de remplissage vont baisser mais vont rester elevees.

La resolution prend du temps :(

Mais, au lieu de faire un algo bete, on fait quoi ?

On rentre dans un probleme d'optimisation combinatoire.

On enumerait les nombres de remplissage possible

Mais pourquoi un probleme d'optimisation ?

On obtient un espace a 12 axes, la solution est quelque part dans l'espace

On cherche le minimum ou le maximum de la fonction

$$x_{\text{sol}}={\text{arg min}}_{x}f(x)$$

Ah et evidemment pas moyen que ce soit une fonction convexe.

Pour les gens du fond:

Resolution de Sudoku

.	.	.	.
.	2	3	.
1	.	.	.
.	.	.	4

$$\begin{gathered} P(\begin{array}{cc}\left|\begin{array}{cc}3& 1\\ 4& 2\end{array}\right|& \left|\begin{array}{cc}4& 2\\ 3& 1\end{array}\right|\\ \left|\begin{array}{cc}1& 4\\ 2& 3\end{array}\right|& \left|\begin{array}{cc}2& 3\\ 1& 4\end{array}\right|\end{array})=\frac{1}{4^{12}} \\ P(\begin{array}{cc}\left|\begin{array}{cc}1& 1\\ 1& 2\end{array}\right|& \left|\begin{array}{cc}1& 1\\ 1& 1\end{array}\right|\\ \left|\begin{array}{cc}1& 1\\ 1& 1\end{array}\right|& \left|\begin{array}{cc}1& 1\\ 1& 4\end{array}\right|\end{array})=\frac{1}{4^{12}} \end{gathered}$$

Quand on ne sait pas, on fait de l'equiprobable

Mais on sait, c'est un sudoku:

$$\begin{gathered} P(\begin{array}{cc}\left|\begin{array}{cc}3& 1\\ 4& 2\end{array}\right|& \left|\begin{array}{cc}4& 2\\ 3& 1\end{array}\right|\\ \left|\begin{array}{cc}1& 4\\ 2& 3\end{array}\right|& \left|\begin{array}{cc}2& 3\\ 1& 4\end{array}\right|\end{array})=1 \\ P(\begin{array}{cc}\left|\begin{array}{cc}1& 1\\ 1& 2\end{array}\right|& \left|\begin{array}{cc}1& 1\\ 1& 1\end{array}\right|\\ \left|\begin{array}{cc}1& 1\\ 1& 1\end{array}\right|& \left|\begin{array}{cc}1& 1\\ 1& 4\end{array}\right|\end{array})=\varnothing \end{gathered}$$

$$\begin{gathered} P(x_{\text{sol}})=1 \\ \mathrm{\forall }x\ne x_{\text{sol}},P(x)=0 \end{gathered}$$

On peut pas juste ecrire notre solution comme ca…

:::

"Certaines solutions sont plus vraies que d'autres"
Le camarade qui a dit un truc important

Par "vrai", on veut dire proche de la solution

$\equiv$ peu d'erreur

$$\begin{gathered} P(\begin{array}{cc}\left|\begin{array}{cc}3& 1\\ 4& 2\end{array}\right|& \left|\begin{array}{cc}4& 2\\ 3& 1\end{array}\right|\\ \left|\begin{array}{cc}1& 4\\ 2& 3\end{array}\right|& \left|\begin{array}{cc}2& 3\\ 1& 4\end{array}\right|\end{array})=0.00001 \\ P(\begin{array}{cc}\left|\begin{array}{cc}1& 1\\ 1& 2\end{array}\right|& \left|\begin{array}{cc}1& 1\\ 1& 1\end{array}\right|\\ \left|\begin{array}{cc}1& 1\\ 1& 1\end{array}\right|& \left|\begin{array}{cc}1& 1\\ 1& 4\end{array}\right|\end{array})=0.0\dots 01 \end{gathered}$$

La prob est plus elevees que le reste

La meteo de Gulli

$$\begin{array}{ccc}P(A& \cap & B)\\ \text{beau}& & \text{Londres}\\ \text{temps}=\{\text{pourri, ...}\}& & \text{lieu}=\{\text{Londres, Paris, ...}\}\end{array}$$

• $T$ VA pour rpz le temps
• $P(T=\text{beau})=0.6$,
  $P(T=\text{pourri})=0.1$, …

$$\boxed{{\displaystyle P(T=t)}}$$

• $V$ vecteur aleatoire,
  $$V=(V_1,...,V_n)$$,
  $$V_i$$ var aleatoire

$$P(T=t\underset{\text{et}}{\underbrace{,}}L=l)\equiv f(t,l)\in ]\varnothing ,1]\{\begin{array}{l}t\in \{\text{beau, pourri,}\dots \}\\ l\in \{\text{Londres, Paris,}\dots \}\end{array}$$

$$\begin{gathered} P(A\cap B)=P(A)+P(B)-P(A\cup B) \\ \overline{A}+\cap +\cap +\overline{B}-\overline{A}-\cap -\overline{B} \end{gathered}$$

Exemple

$W$ weather,

$L$ location,

$N$ thune de Xavier NIEL.

$P(W=w,L=l)\equiv$ proba qu'il fasse

$$\underset{\text{beau a Londres}}{\underbrace{\boxed{{\displaystyle \text{w a l}}}}}$$

$$\begin{array}{rl}P(A\cap B)& =P(A|B).P(B)\\ =P(B\cap A)& =P(B|A).P(A)\\ & \Rightarrow P(A|B)=\frac{P(A\cap B)}{P(B)}\end{array}$$

$$\begin{gathered} \begin{array}{rl}{x}_{\text{sol}}={\text{arg max}}_{x}P(X=x& |Y=y)\\ & \downarrow \end{array} \\ \frac{\stackrel{f(x,y)}{\overbrace{P(Y=y|X=x)}}.P(X=x)}{\underset{\text{terme constant}}{\underbrace{P(Y=y)}}} \\ \underset{\text{VRAISEMBLANCE}}{\underbrace{L(X=x|Y=y)}}.\underset{\text{A PRIORI}}{\underbrace{P(X=x)}}) \end{gathered}$$

Retour au SUDOKU

$$\begin{gathered} y=\begin{array}{cc}\left|\begin{array}{cc}{y}_1& \\ & 1\end{array}\right|& \left|\begin{array}{cc}& \\ 2& x_p\end{array}\right|\\ \left|\begin{array}{cc}3& \\ & \end{array}\right|& \left|\begin{array}{cc}& \\ & 4\end{array}\right|\end{array} \\ y=(0,0,0,0,0,1,2,0,3,0,0,0,0,0,0,4) \\ y=(y_1,...,y_{15}) \\ {y}_6=1 \\ x=(x_1,x_2,x_3,x_4,x_6,0,0,x_p,0,\dots ) \\ {x}^{\prime }=(1,1,1,1,1,0,0,1,0,\dots ) \end{gathered}$$

En solution:

$$\begin{gathered} P(x^{\prime })=\begin{array}{cc}\left|\begin{array}{cc}1& 1\\ 1& 0\end{array}\right|& \left|\begin{array}{cc}1& 1\\ 0& 1\end{array}\right|\\ \left|\begin{array}{cc}0& 1\\ 1& 1\end{array}\right|& \left|\begin{array}{cc}1& 1\\ 0& 1\end{array}\right|\end{array}=? \\ P(x^{″})=\begin{array}{cc}\left|\begin{array}{cc}1& 2\\ 3& 0\end{array}\right|& \left|\begin{array}{cc}3& 4\\ 0& 1\end{array}\right|\\ \left|\begin{array}{cc}0& 1\\ 4& 3\end{array}\right|& \left|\begin{array}{cc}4& 3\\ 2& 0\end{array}\right|\end{array}=? \end{gathered}$$

Recap

$$\begin{gathered} P_T(X=x)=\frac{1}{Z}{e}^{\frac{-U(x)}{T}}(z=\sum _x{e}^{-U(x)}) \\ {P}_T(X=x_{\text{sol}})>P_T(X=x)\mathrm{\forall }x\ne x_{\text{sol}} \\ P(X=x_{\text{sol}})=0.000001\text{ECHANTILLONEUR }\bullet \to x\text{ suivant }P(x) \\ \underset{T\to 0^{+}}{lim}{P}_T=\{\begin{array}{l}{P}_0(X=x_{\text{sol}})=1\\ P_0(X=x_{\text{sol}})=\varnothing & \text{sinon}\end{array} \end{gathered}$$