\title{Graphe de transition plus général}
\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, tests pour qu'elle convienne, calculs associes
############

\integer{n=randint (3..8)}
\if{\n<6}{\integer{dec=1}}{\integer{dec=2}}

\integer{test=0}

\while{\test=0}
	{

#generation d'une matrice stochastique aleatoire

	\matrix{U=slib(matrix/givenrank \n,\n,0)}
	\for{i=1 to \n}
		{
		\integer{q=randint (2..10)}	
		\integer{r=\q}	
		\for{j=1 to \n-1}
			{
			\integer{p=randint (0..(\dec)*\r)}
			\if{\p>\r}{\integer{p=0}}
			\if{\p=q}{\integer{p=randint (\q-1..\q)}}
			\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)}
		}

#teste qu'il existe boucle dans le graphe (pour pouvoir tester la connexite forte par une puissane 2^n)
			
	\integer{existeboucle=0}
	\for{i=1 to \n}
		{
		\integer{boucle=pari(
			M=Mat([\U]);
			if(M[\i,\i]>0,t=1,t=0);
			t)
			}
		\if{\boucle=1}{\integer{existeboucle=1}}
		}
	\if{\existeboucle=0}{\integer{test=0}}
	{
#test de non connexite forte du graphe de transition


	\matrix{Mg=pari(M=Mat([\U]); 
		for(i=1,\n, for(j=1,\n, if(M[i,j]<>0,M[i,j]=1);););M)}

	\matrix{Mn=pari(M=Mat([\Mg]);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)}

#test qu'il y a une seule composante fortement connexe sans arete sortante

	\if{\connexe=0}
		{
		\matrix{Mgdel=pari(
			Mn=Mat([\Mn]); 
			Mgdel=Mat([\Mg]); 
			for(i=1,\n,
				existezero=0;
				for(j=1, \n,
					if(Mn[i,j]==0, existezero=1););
					if(existezero==1, for(j=1, \n, Mgdel[i,j]=0);
					);
				);
			Mgdel)
			}
		\matrix{Mdeln=pari(
			Mn=Mat([\Mn]); 
			Mdeln=Mat([\Mn]); 
			for(i=1,\n,
				existezero=0;
				for(j=1, \n,
					if(Mn[i,j]==0, existezero=1););
					if(existezero==1, for(j=1, \n, Mdeln[i,j]=0);
					);
				);
			Mdeln)
			}
		\matrix
			{
			Mgdeln=pari(M=Mat([\Mgdel]);Mn=M;for(i=1,2*\n-1,Mn=Mn*M;);Mn)
			}
		\integer{test=pari(
			Mdeln=Mat([\Mdeln]); 
			Mgdeln=Mat([\Mgdeln]); 
			if(Mdeln=Mgdeln, t=1);
			t)
			}

#calcul du nombre de sommets de la composante fortement connexe

		\integer{nonzeros=pari(M=Mat([\Mdeln]);nb=0; for(i=1,\n,
			if(M[i,1]>0,nb=nb+1););nb)
			}

#restriction au cas ou le graphe extrait a au plus 4 sommets

		\if{\nonzeros>4}{\integer{test=0}}
			{

#calcul liste de ces sommets nonzeros

			\text{liste=}
\integer{nb=0}
			\for{i=1 to \n}
				{\integer{a=pari(M=Mat([\Mdeln]);
					if(M[\i,1]>0,a=1,a=0);a)
					}
				\if{\a=1}{\text{liste=\liste
						\i
						}
\integer{nb=\nb+1}
\if{\nb<\nonzeros}{\text{liste=\liste
						,
						}
}
					}
				}


#teste qu'il existe boucle dans le graphe extrait
			
			\integer{existeboucleext=0}
			\for{i=1 to \nonzeros}
				{
				\integer{a=item(\i,\liste)}
				\integer{boucle=pari(
					M=Mat([\Mg]);
					if(M[\a,\a]==1,t=1,t=0);
					t)
					}
				\if{\boucle=1}{\integer{existeboucleext=1}}
				}
			\if{\existeboucleext=0}{\integer{test=0}}

#teste que (1,1) ne vaut pas 1 (trop frequent dans cette construcion aleatoire)

\integer{val11=pari(U=Mat([\U]);U[1,1])}
\if{\val11=1}{\integer{test=0}}

			}   #fin du else du if(nonzeros>4)

		} #fin du if(connexe=0)
	} #fin du if(existeboucle=0)
	} #fin du while(test=0)


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


#calcul matrice extraite 

\matrix{Mext=pari(matrix(\nonzeros,\nonzeros))}
\for{i=1 to \nonzeros}
	{
	\for{j=1 to \nonzeros}
		{
		\integer{a=item(\i,\liste)}
		\integer{b=item(\j,\liste)}
\matrix{Mtemp=pari(M=Mat([\Mext]);M)}
		\matrix{Mext=pari(M=Mat([\Mtemp]);
			U=Mat([\U]);
			M[\i,\j]=U[\a,\b];
			M)
			}
		}
	}

#calcul aretes extraites pour dessin

\text{couleurs=}
\for{i=1 to \nonzeros}
{
\integer{a=item(\i,\liste)}
\for{j=1 to \nonzeros}
{
\integer{b=item(\j,\liste)}
\text{couleurs=\couleurs
\a,\b,red;}
}
}



#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],blue,black,,[\couleurs])}

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

\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>

<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>
}

#matrice de transiton U=\([\U])<BR>
#matrice d'incidence u graphe Mg=\([\Mg])<BR>
#Mg puissance n Mn=\([\Mn])<BR>
#on supprimme les acycliques Mgdel=\([\Mgdel])<BR>
#on supprime les acyclique pour comparer puissance n Mgdeln=\([\Mgdeln])<BR>
#on supprime les acyclique pour comparer puissance n  Mdeln=\([\Mdeln])<BR>
#nombre de non acyclique nonzeros=\nonzeros<BR>
#liste de non acycliques nonzeros=\liste<BR>
#matrice extraite Mext=\([\Mext])<BR>
#nonce des aretes a colorier couleurs=\couleurs<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
{
\if{\nonzeros=1}
{<BR><BR><B>ICI : </B><U>l'état \liste est un <I>état absorbant</I></U>. En effet, tout état émet vers cet état (avec des intermédiaires), mais cet état n'émet vers aucun autre. Donc à la limite, seul cet état a une valeur de répartition non nulle. Le dessin ci-dessous montre le graphe de transition du processus.<BR><BR>

 <B>Vous avez eu de la chance de tomber sur ce cas. Réessayez l'exercice !</B><BR><BR>

<CENTER>
\draw{400, 400}{\dessin}
</CENTER>
<BR>
}
{<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>
<I>Remarque</I> : pour tester si la matrice M est régulière, il suffit de tester si la matrice d'incidence N du graphe de transition G associé vérifie que N<SUP>n</SUP>
a tous ses coefficeients strictement positifs
 à partir d'un certain n. <BR>
<BR>
<U>Si la matrice  est régulière</U>,
alors le graphe de transition 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>

<B> ICI :</B> <U>la matrice n'est pas régulière</U> car le graphe de transition n'est pas fortement connexe, comme le montre le dessin suivant. <BR>

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

<U>On cherche donc le plus grand sous graphe H dont toutes les composantes connexes fortement connexes</U> du graphe de transition G. <I>Remarque</I> : ce graphe a pour ensemble d'arête l'union des cycles orientés, il s'obtient aussi en supprimant toutes les coupes orientées. <I>Attention</I> : ce sous graphe n'est pas forcément connexe. On appelle <U>composantes fortement connexes</U>
de G les graphes formés des composantes connexes de H.
<BR>
<BR>

<U>Si une unique composante fortement connexe n'a pas d'arête sortante vers les autres sommets,</U> (c'est à dire si le graphe acyclique 
dont les sommets les composantes fortement connexes de G a un unique puits),  alors
on sait que tous les états qui ne sont pas des 
sommets de cette composante seront dans une proportion nulle à la limite. <I>En effet</I> : la répartition `diparaît' progressivement de tous les états qui donnent sans recevoir, et elle 'disparaît' aussi des composantes fortement connexes qui émettent vers l'extérieur.
<BR><BR>

<B> ICI :</B> <U>une unique composante fortement connexe n'a pas d'arête sortante vers les autres sommets</U>, formée par le sous graphe aux <FONT COLOR=red> ARETES ROUGES</FONT>.
<BR><BR>

<U>On est donc ramené à étudier un processus stochastique extrait</U>
car on s'intéresse seulement à la limite de répartition.
<BR><BR>

<B> ICI :</B> <U>les états qui ne disparaîtront pas à la limite</U> sont les sommets des arêtes rouges, soit l'ensemble<BR>
<CENTER>\liste</CENTER>
<BR><BR>

<B>ICI :</B> <U>la matrice de transition pour ce sous processus</U>
est la matrice stochastique correspondante extraite Mext de la matrice de départ M, soit la matrice
<CENTER>\([\Mext])</CENTER>
<BR><BR>


<B> ICI :</B> <U>cette matrice extraite est régulière</U>
car le graphe de transition de ce sous-processus est fortement connexe et possède une boucle (condition suffisante mais non nécessaire).<BR>
<BR>

<B> ICI :</B> <U>on trouve donc la répartition limite</U>
en résolvant MextVext=Vext et en donnant la valeur 0 aux états suprimés,
soit finalement V=\([\Vsol]), c'est à dire en décimal (éventuellement approché) V=( \sol ).<BR>
<BR>
<BR>
<B> Remarque et mise en garde : ici,</B> comme lorsque la matrice de départ est régulière, la répartition limite ne dépend pas de la répartition initiale, <U>MAIS</U> si le graphe acyclique des composantes fortement connexes n'a pas un seul puits, alors la répartition entre les différents sous-processus formés par ces composantes puits se fait progressivement et d'une façon qui dépend bien sûr de la répartition initiale.<BR>
<BR>
}

} 