\title{Processus stochastique. Niveau 1.}
\language{fr}
\range{-5..5}
\author{Emeric Gioan}
\email{egioan@math.unice.fr}
\computeanswer{no}
\format{html}
\precision{100}

#############
#definition de la matrice de transition aleatoire
############

\integer{n=randint (2..4)}

\integer{connexe=0}

\while{\connexe=0}
{
\matrix{U=slib(matrix/givenrank \n,\n,0)}
\for{i=1 to \n}
	{
	\integer{q=randint (1..18-4*\n)}	
	\integer{r=\q}	
	\for{j=1 to \n-1}
		{
		\integer{p=randint (0..\r)}
		\matrix{U=pari(U=Mat([\U]);U[\j,\i]=\p/\q;U)}
		\integer{r=\r-\p}
		}
	\matrix{U=pari(U=Mat([\U]);U[\n,\i]=\r/\q;U)}
	}

#test de regularite de la matrice
#test de connexite forte du graphe de transition
#et d'existence d'une boucle

\matrix{Mn=pari(M=Mat([\U]);Mn=M;for(i=1,2*\n-1,Mn=Mn*M;);Mn)}
\integer{connexe=pari(Mn=Mat([\Mn]);c=1; for(i=1,\n,for(j=1,\n,if(Mn[i,j]==0,c=0);););c)}
\integer{boucle=pari(M=Mat([\U]);b=0; for(i=1,\n,if(M[i,i]>0,b=1););b)}
\if{\boucle=0}{\integer{connexe=0}}

}

############
#fin generation
##########""

#vecteur propre proba

\matrix{VP=pari(M=Mat([\U]);
for(i=1,\n,M[i,i]=M[i,i]-1);
N=matker(M);
s=0;
for(i=1,\n,s=s+N[i,1]);
N=N/s;
N
)}


#transposition

\matrix{Vsol=pari(VP=Mat([\VP]); 
V=matrix(1,\n);
for(i=1, \n, V[1,i]=VP[i,1];); V)}


#solution en numerique

\text{sol=}
\for{i=1 to \n}
{\real{a=pari(VP=Mat([\VP]);VP[\i,1])}
\if{\i>1}{\text{sol=\sol
,}}
\text{sol=\sol
\a}
}


#dessin graphe de transition

\matrix{Mtg=pari(M=Mat([\U]); Mt=Mat([\U]); 
for(i=1,\n, for(j=1,\n, if(M[i,j]<>0,Mt[j,i]=1,Mt[j,i]=0);););Mt)}
\text{dessin=slib(graph/draw [\Mtg],[red,blue])}

#################################

\statement{<U>Si vous ne savez pas répondre, vous pouvez consulter la solution illustrée en entrant une réponse quelconque</U>.<BR><BR>

La matrice suivante donne les probabilités de transition
des états de 1 à \n, <I>en colonnes</I>, <U>vers</U> les états de 1 à \n, <I>en lignes</I>.
<BR><BR>
<CENTER>
\([\U])</CENTER>
<BR><BR>

Calculer le vecteur de répartition limite des états, pour une répartition initiale quelconque.<BR>
<BR>
}


#VP=\([\VP])<BR>
#Mn=\([\Mn])<BR>
#sol=\sol<BR>
#Vsol=\Vsol<BR>

\hint{On demande
la limite de M<SUP>n</SUP>U pour n tendant vers l'infini,
où M est une matrice stochastique de transition, et pour un vecteur probabilités
U <I> quelconque</I>...}

\answer{vecteur répartition limite}{\Vsol}{type=vector}

\solution
{

<BR>

<U>Si une matrice stochastique M 
<! de taille r >
est régulière</U>,
c'est à dire si elle a une puissance dont tous les coefficients sont strictements positifs,
<! (ou de façon équivalente si M^r a tous ses coefficients strictement positifs), >
alors, pour tout vecteur probabilités U (vecteur dont les coefficients sont positifs de somme 1), 
M<SUP>n</SUP>U, pour n tendant vers l'infini,
tend vers l'unique <I>vecteur propre V de M pour la valeur propre 1</I> dont la somme de coefficients est égale à 1. On est alors ramené à résoudre le système MV=V.<BR>
<BR>

<U>Pour tester si la matrice M est régulière</U>, il suffit de tester si la matrice d'incidence N du graphe de transition G associé vérifie N<SUP>n</SUP>
à partir d'un certain n
<! N^r r=taille >
a tous ses coefficeients strictement positifs. Cette propriété implique que G est fortement connexe. 
Mais la propriété que G soit fortement connexe n'est pas suffisante (par exemple un cycle donne une matrice de permutation non régulière). <BR>
<BR>

<U>On peut parfois utiliser le graphe de transition</U> pour éviter de calculer les puissances successives de M ou de N. On a en effet la condition suffisante (mais non nécessaire) suivante :
si G est fortement connexe
et possède une boucle alors la matrice est régulière. <BR>
<BR>

<B> ICI :</B> <U>le graphe de transition est fortement connexe et possède une boucle</U>,
comme le montre le dessin suivant <FONT SIZE=2>(si, sur ce dessin, les arêtes sont dessinées sans flêches, c'est parceque toutes les arêtes sont doubles, une dans chaque sens)</FONT>,
<U>donc la matrice est régulière</U>.<BR>

<CENTER>
\draw{300, 300}{\dessin}
</CENTER>
<BR>

<B> ICI :</B> <U>donc on résoud MV=V</U>, et on trouve comme vecteur limite V=\([\Vsol]), c'est à dire en décimal (éventuellement approché) V=( \sol ).<BR>
<BR>
<BR>
} \title{Processus stochastique. Niveau 1.}
\language{fr}
\range{-5..5}
\author{Emeric Gioan}
\email{egioan@math.unice.fr}
\computeanswer{no}
\format{html}
\precision{100}

#############
#definition de la matrice de transition aleatoire
############

\integer{n=randint (2..4)}

\integer{connexe=0}

\while{\connexe=0}
{
\matrix{U=slib(matrix/givenrank \n,\n,0)}
\for{i=1 to \n}
	{
	\integer{q=randint (1..18-4*\n)}	
	\integer{r=\q}	
	\for{j=1 to \n-1}
		{
		\integer{p=randint (0..\r)}
		\matrix{U=pari(U=Mat([\U]);U[\j,\i]=\p/\q;U)}
		\integer{r=\r-\p}
		}
	\matrix{U=pari(U=Mat([\U]);U[\n,\i]=\r/\q;U)}
	}

#test de regularite de la matrice
#test de connexite forte du graphe de transition
#et d'existence d'une boucle

\matrix{Mn=pari(M=Mat([\U]);Mn=M;for(i=1,\n-1,Mn=Mn*M;);Mn)}
\integer{connexe=pari(Mn=Mat([\Mn]);c=1; for(i=1,\n,for(j=1,\n,if(Mn[i,j]==0,c=0);););c)}
\integer{boucle=pari(M=Mat([\U]);b=0; for(i=1,\n,if(M[i,i]>0,b=1););b)}
\if{\boucle=0}{\integer{connexe=0}}

}

############
#fin generation
##########""

#vecteur propre proba

\matrix{VP=pari(M=Mat([\U]);
for(i=1,\n,M[i,i]=M[i,i]-1);
N=matker(M);
s=0;
for(i=1,\n,s=s+N[i,1]);
N=N/s;
N
)}


#transposition

\matrix{Vsol=pari(VP=Mat([\VP]); 
V=matrix(1,\n);
for(i=1, \n, V[1,i]=VP[i,1];); V)}


#solution en numerique

\text{sol=}
\for{i=1 to \n}
{\real{a=pari(VP=Mat([\VP]);VP[\i,1])}
\if{\i>1}{\text{sol=\sol
,}}
\text{sol=\sol
\a}
}


#dessin graphe de transition

\matrix{Mtg=pari(M=Mat([\U]); Mt=Mat([\U]); 
for(i=1,\n, for(j=1,\n, if(M[i,j]<>0,Mt[j,i]=1,Mt[j,i]=0);););Mt)}
\text{dessin=slib(graph/draw [\Mtg],[red,blue])}

#################################

\statement{<U>Si vous ne savez pas répondre, vous pouvez consulter la solution illustrée en entrant une réponse quelconque</U>.<BR><BR>

La matrice suivante donne les probabilités de transition
des états de 1 à \n, <I>en colonnes</I>, <U>vers</U> les états de 1 à \n, <I>en lignes</I>.
<BR><BR>
<CENTER>
\([\U])</CENTER>
<BR><BR>

Calculer le vecteur de répartition limite des états, pour une répartition initiale quelconque.<BR>
<BR>
}


#VP=\([\VP])<BR>
#Mn=\([\Mn])<BR>
#sol=\sol<BR>
#Vsol=\Vsol<BR>

\hint{On demande
la limite de M<SUP>n</SUP>U pour n tendant vers l'infini,
où M est une matrice stochastique de transition, et pour un vecteur probabilités
U <I> quelconque</I>...}

\answer{vecteur répartition limite}{\Vsol}{type=vector}

\solution
{

<BR>

<U>Si une matrice stochastique M 
<! de taille r >
est régulière</U>,
c'est à dire si elle a une puissance dont tous les coefficients sont strictements positifs,
<! (ou de façon équivalente si M^r a tous ses coefficients strictement positifs), >
alors, pour tout vecteur probabilités U (vecteur dont les coefficients sont positifs de somme 1), 
M<SUP>n</SUP>U, pour n tendant vers l'infini,
tend vers l'unique <I>vecteur propre V de M pour la valeur propre 1</I> dont la somme de coefficients est égale à 1. On est alors ramené à résoudre le système MV=V.<BR>
<BR>

<U>Pour tester si la matrice M est régulière</U>, il suffit de tester si la matrice d'incidence N du graphe de transition G associé vérifie N<SUP>n</SUP>
à partir d'un certain n
<! N^r r=taille >
a tous ses coefficeients strictement positifs. Cette propriété implique que G est fortement connexe. 
Mais la propriété que G soit fortement connexe n'est pas suffisante (par exemple un cycle donne une matrice de permutation non régulière). <BR>
<BR>

<U>On peut parfois utiliser le graphe de transition</U> pour éviter de calculer les puissances successives de M ou de N. On a en effet la condition suffisante (mais non nécessaire) suivante :
si G est fortement connexe
et possède une boucle alors la matrice est régulière. <BR>
<BR>

<B> ICI :</B> <U>le graphe de transition est fortement connexe et possède une boucle</U>,
comme le montre le dessin suivant <FONT SIZE=2>(si, sur ce dessin, les arêtes sont dessinées sans flêches, c'est parceque toutes les arêtes sont doubles, une dans chaque sens)</FONT>,
<U>donc la matrice est régulière</U>.<BR>

<CENTER>
\draw{300, 300}{\dessin}
</CENTER>
<BR>

<B> ICI :</B> <U>donc on résoud MV=V</U>, et on trouve comme vecteur limite V=\([\Vsol]), c'est à dire en décimal (éventuellement approché) V=( \sol ).<BR>
<BR>
<BR>
} \title{Processus stochastique. Niveau 1.}
\language{fr}
\range{-5..5}
\author{Emeric Gioan}
\email{egioan@math.unice.fr}
\computeanswer{no}
\format{html}
\precision{100}

#############
#definition de la matrice de transition aleatoire
############

\integer{n=randint (2..4)}

\integer{connexe=0}

\while{\connexe=0}
{
\matrix{U=slib(matrix/givenrank \n,\n,0)}
\for{i=1 to \n}
	{
	\integer{q=randint (1..18-4*\n)}	
	\integer{r=\q}	
	\for{j=1 to \n-1}
		{
		\integer{p=randint (0..\r)}
		\matrix{U=pari(U=Mat([\U]);U[\j,\i]=\p/\q;U)}
		\integer{r=\r-\p}
		}
	\matrix{U=pari(U=Mat([\U]);U[\n,\i]=\r/\q;U)}
	}

#test de regularite de la matrice
#test de connexite forte du graphe de transition
#et d'existence d'une boucle

\matrix{Mn=pari(M=Mat([\U]);Mn=M;for(i=1,\n-1,Mn=Mn*M;);Mn)}
\integer{connexe=pari(Mn=Mat([\Mn]);c=1; for(i=1,\n,for(j=1,\n,if(Mn[i,j]==0,c=0);););c)}
\integer{boucle=pari(M=Mat([\U]);b=0; for(i=1,\n,if(M[i,i]>0,b=1););b)}
\if{\boucle=0}{\integer{connexe=0}}

}

############
#fin generation
##########""

#vecteur propre proba

\matrix{VP=pari(M=Mat([\U]);
for(i=1,\n,M[i,i]=M[i,i]-1);
N=matker(M);
s=0;
for(i=1,\n,s=s+N[i,1]);
N=N/s;
N
)}


#transposition

\matrix{Vsol=pari(VP=Mat([\VP]); 
V=matrix(1,\n);
for(i=1, \n, V[1,i]=VP[i,1];); V)}


#solution en numerique

\text{sol=}
\for{i=1 to \n}
{\real{a=pari(VP=Mat([\VP]);VP[\i,1])}
\if{\i>1}{\text{sol=\sol
,}}
\text{sol=\sol
\a}
}


#dessin graphe de transition

\matrix{Mtg=pari(M=Mat([\U]); Mt=Mat([\U]); 
for(i=1,\n, for(j=1,\n, if(M[i,j]<>0,Mt[j,i]=1,Mt[j,i]=0);););Mt)}
\text{dessin=slib(graph/draw [\Mtg],[red,blue])}

#################################

\statement{<U>Si vous ne savez pas répondre, vous pouvez consulter la solution illustrée en entrant une réponse quelconque</U>.<BR><BR>

La matrice suivante donne les probabilités de transition
des états de 1 à \n, <I>en colonnes</I>, <U>vers</U> les états de 1 à \n, <I>en lignes</I>.
<BR><BR>
<CENTER>
\([\U])</CENTER>
<BR><BR>

Calculer le vecteur de répartition limite des états, pour une répartition initiale quelconque.<BR>
<BR>
}


#VP=\([\VP])<BR>
#Mn=\([\Mn])<BR>
#sol=\sol<BR>
#Vsol=\Vsol<BR>

\hint{On demande
la limite de M<SUP>n</SUP>U pour n tendant vers l'infini,
où M est une matrice stochastique de transition, et pour un vecteur probabilités
U <I> quelconque</I>...}

\answer{vecteur répartition limite}{\Vsol}{type=vector}

\solution
{

<BR>

<U>Si une matrice stochastique M 
<! de taille r >
est régulière</U>,
c'est à dire si elle a une puissance dont tous les coefficients sont strictements positifs,
<! (ou de façon équivalente si M^r a tous ses coefficients strictement positifs), >
alors, pour tout vecteur probabilités U (vecteur dont les coefficients sont positifs de somme 1), 
M<SUP>n</SUP>U, pour n tendant vers l'infini,
tend vers l'unique <I>vecteur propre V de M pour la valeur propre 1</I> dont la somme de coefficients est égale à 1. On est alors ramené à résoudre le système MV=V.<BR>
<BR>

<U>Pour tester si la matrice M est régulière</U>, il suffit de tester si la matrice d'incidence N du graphe de transition G associé vérifie N<SUP>n</SUP>
à partir d'un certain n
<! N^r r=taille >
a tous ses coefficeients strictement positifs. Cette propriété implique que G est fortement connexe. 
Mais la propriété que G soit fortement connexe n'est pas suffisante (par exemple un cycle donne une matrice de permutation non régulière). <BR>
<BR>

<U>On peut parfois utiliser le graphe de transition</U> pour éviter de calculer les puissances successives de M ou de N. On a en effet la condition suffisante (mais non nécessaire) suivante :
si G est fortement connexe
et possède une boucle alors la matrice est régulière. <BR>
<BR>

<B> ICI :</B> <U>le graphe de transition est fortement connexe et possède une boucle</U>,
comme le montre le dessin suivant <FONT SIZE=2>(si, sur ce dessin, les arêtes sont dessinées sans flêches, c'est parceque toutes les arêtes sont doubles, une dans chaque sens)</FONT>,
<U>donc la matrice est régulière</U>.<BR>

<CENTER>
\draw{300, 300}{\dessin}
</CENTER>
<BR>

<B> ICI :</B> <U>donc on résoud MV=V</U>, et on trouve comme vecteur limite V=\([\Vsol]), c'est à dire en décimal (éventuellement approché) V=( \sol ).<BR>
<BR>
<BR>
} 