Problème reconnaissance de loi

MJ_Addict

Bonsoir tout le monde

J'ai actuellement un projet de proba/stats à réaliser avec mon binôme, sauf que nous bloquons dès la première question, impossible de se débloquer et le professeur sensé nous superviser, ne nous aide pas vraiment. C'est pourquoi je fais appel à vous, ne serait-ce que pour m'éclairer.Voici le début du sujet :
Une ligne de réseau de communication est composée de C circuits. Des appels arrivent sur la ligne. L'intervalle entre deux appels successifs est indépendant des autres intervalles et suite une loi exponentielle de paramètre lambda. Un appel est traité s'il y a au moins un circuit de libre. L'appel occupe alors le circuit un temps de loi exponentielle de paramètre mu (on pourra poser mu=1 pour la suite). Pour t appartenant à [0;+l'infini[, on note Xt, le nombre de circuits occupés à l'instant t, Xt appartenant à {0,1,...,C}.

1) Simuler l'évolution sur un certain temps de la ligne (= tracer des trajectoires possibles de Xt, c'est-à-dire des courbes aléatoires représentant la fonction t->Xt). On pourra faire varier X0, lambda et C (On pourra commencer par C = +l'infini : un appel est directement traité).
Donc notre problème est que nous n'arrivons pas à identifier la fonction recherchée dans la première question, on sait que la loi ou fonction dépend de X0, lambda, et C mais impossible de la déterminer !
Ne sachant pas répondre à cette question, nous bloquons pour la suite du problème..
Si quelqu'un pouvait m'éclairer un peu pour que je puisse démarrer ça serait super cool.
Bonne soirée

afk

Bonsoir,

ton problème est-il
- d'ordre mathématique? Dans ce cas, tu devrais préciser tes connaissances sur le sujet (processus de naissance et de mort, processus de sauts markoviens, files d'attentes).
- d'ordre informatique (comment simuler le processus)? Dans ce cas, tu devrais préciser le langage de programmation que tu utilises.

MJ_Addict

Bonsoir

Il me semble que la simulation doit être faite sous Maple ! Le problème est que je trouve ce sujet d'un niveau un peu trop élevé par rapport au mien et il nous est difficile de reconnaitre f(Xt) !

afk

Encore une fois, que sais-tu sur les processus de sauts? Es-tu capable de décrire la loi suivie par les durées $T_{n+1}-T_n$ entre deux sauts (arrivée d'un appel ou fin de traitement d'un appel)?

MJ_Addict

Absolument rien, j'ignorais que le sujet traitait du processus des sauts etant donné qu'on ne nous l'a pas enseigné ! Je vais faire quelques recherches sur le sujet, je reviendrai si j'ai des soucis de compréhension !

Merci

Steven Neutral

Je ne te comprends pas trop : tu n'as rien besoin de calculer, on te demande de modéliser ce bazar avec un prog informatique. Tu peux commencer par dessiner une "trajectoire" d'un circuit au cours du temps $t$, par exemple tu mets $0$ quand le circuit est libre et $1$ quand il est occupé. Donc tu obtiens comme dessin un truc qui commence en $0$ ou en $1$ (les deux "états" possibles) puis qui ne bouge pas jusqu'au prochain changement d'état, etc. La loi des durées entre deux changement d'états est donnée dans ton énoncé : exponentielle de paramètre $\mu$ ou $\lambda$. Saurais-tu modéliser ça en langage informatique ?

afk

Tout ce que tu as besoin de connaitre c'est le lemme dit des 2 réveils: Si $T_0$ et $T_1$ suivent des lois exponentielles de parametres respectifs $\mu$ et $\lambda$ (temps avant que le réveil sonne), alors le minimum $T$ de $T_0$ et $T_1$ suit une loi exponentielle de paramètre $\lambda + \mu$. De plus si on note $N$ le numero du reveil qui sonne en premier, i.e. $N = i$ si $T= T_i$, alors $N$ est indépendant de $T$ et $P(N=0) = \frac{\mu}{\lambda+\mu}$ $P(N=1) = \frac{\lambda}{\lambda+\mu}$.

Donc comme l'a dit Steven, pour ton processus, si tu as $k$ circuits occupés, tu simules une loi exponentielle de paramètre $\lambda + k\mu$, temps durant lequel ta fonction reste constante égale à $k$. Puis tu simules une variable de Bernouilli [Bernoulli] de paramètre $\frac{\lambda}{\lambda+k\mu}$. Si elle vaut $1$, alors ta fonction augmente de $1$ sinon elle baisse de $1$ et puis tu recommences...

Il reste juste à distinguer les cas où la fonction atteint les bornes $k=0$ et $k=C$, elle y reste alors pendant un temps suivant une loi exponentielle de paramètre $\lambda$ et $C\mu$ respectivement au lieu de $\lambda + k\mu$ et au bout de ce temps, elle va automatiquement augmenter de $1$ resp. diminuer de $1$.

[Bernoulli ne prend pas de 'i' devant les deux 'l' (pas de nouille dans Bernoulli). AD]

MJ_Addict

Merci pour vos réponses.

J'ai compris ce que vous m'avez dit au sujet du changement d'état & du lemme des 2 réveils. Cependant j'ai toujours du mal à comprendre :

On me demande de traçer des courbes représentant la fonction qui à t associe Xt, le nombre de circuits occupés à l'instant t. Je dois donc trouver cette fameuse fonction ( qui devrait dépendre de Xo, lambda et C d'apres l'énoncé) pour pouvoir la modéliser non ?

Dois-je avoir des connaissances au sujet du processus de Poisson ou des lois de Markov pour pouvoir y arriver ?

Mes questions peuvent paraitre un peu bete mais je trouve ce projet d'un niveau bien supérieur au mien

afk

Tu devrais préciser ton niveau et le cadre de ton projet: Prépa? Ecole d'ingé? Licence? M1? Et tu devrais poser des questions au professeur chargé de t'encadrer.

Sur le plan mathématique, tu n'as pas besoin d'en savoir plus sur les processus que ce qu'il y a dans mon message précédent.

Pour la programmation, le message de Steven et le mien te donnent essentiellement l'algorithme.

MJ_Addict

Je suis en école d'ingé !
Donc si je suis bien :

=> On suppose un circuit occupé, elle reste constante pendant un temps qui suit une loi exponentielle de paramètre λ+ µ ( minimum de deux lois exponentielles suit une loi exponentielle). S'en suit une loi de Bernoulli qui détermine si le circuit est occupé où non, si il l'est on reste à 0, sinon on remonte à 1 et on re-simule une loi exponentielle.

C'est ça ? Si c'est le cas je comprends à peu près le fonctionnement d'un circuit mais je vois pas comment modéliser toute la ligne, en prenant en compte tous les circuits cette fois !

EDIT :

En réfléchissant un peu j'arrive à une forme d'algo comme ça :

Debut
-> Entrer le nombre de circuits occupés à l'instant t=0, X0

Xtot=X0
Pour (i=0;i=C;i++) Faire
   Ti suit une loi exponentielle de para  λ+ µ
   Xi suit une loi binomiale de para  λ/ λ+1
       Si Xi=1 Alors
           Xtot = Xtot-1
       Sinon
           Xtot=Xtot+1
       FinSi
FinPour
Fin

Bon j'imagine que c'est faux, maintenant il s'agit de comprendre où et pourquoi !

afk

Je me suis plante dans les parametres des lois oubliant de prendre en compte le nombre de circuits occupes. Je corrigerai en rentrant.

Dans ta boucle pour ne doit pas etre sur le nombre de circuit mais le nombre de sauts.

MJ_Addict

Donc je dois fixer un nombre maximum d'appel c'est ca ( qui correspond au nombre de sauts max ) ?

Comment je fais dans mon algo pour traiter chacun des circuits ?

afk

J'ai corrigé les paramètres.

La fonction que tu representes est le nombre de serveurs occupés à l'instant $t$. Si tu as $k$ serveurs occupés, le temps avant le prochain saut est le minimum d'une $\mathcal{E}(\lambda)$ (arrivée d'un nouvel appel) et de $k$ lois $\mathcal{E}(\mu)$ (fin de traitement d'un appel). Il suit donc une loi $\mathcal{E}(\lambda+k\mu)$.

Pour l'algo, tu peux te fixer un nombre maximal de sauts (= arrivée d'un appel ou fin de traitement d'un appel) ou tu peux te fixer un temps maximal (ce que tu peux traiter avec une boucle while au lieu d'une boucle for).

MJ_Addict

Ah oui je vois mieux merci

Donc on aurait qqchose de la forme suivante :

Debut
-> Entrer le nombre de circuits occupés à l'instant t=0, X0
-> Entrer le nombre maximum de sauts
Xtot=X0

while(ns<MAX)                 //J'ai pris le nombre de sauts
T suit une loi exponentielle de paramètre &#955;+ Xtot*µ
         ------------------------------------------

// Exprimer la loi de Bernoulli suivie par chacun des circuits


         --------------------------------------------

Si
Alors Xtot = Xtot+1;
Sinon
Xtot = Xtot - 1;
FinSi

ns=ns+1;
Fin

Je dois utiliser une autre boucle pour traiter tous les circuits de la ligne ?

afk

Non pas besoin d'une autre boucle. Avec probabilité $\lambda/(\lambda + X_t \mu)$ c'est un nouvel appel qui arrive et avec probabilité $ X_t \mu/(\lambda + X_t \mu)$ c'est l'un des $X_t$ appels en cours dont le traitement prend fin. C'est tout.

sadfub0

Bonsoir,

cet exercice m'intéresse (de point de vue simulation) et j'ai une question : avec $X0=0$, $C=+\infty$ , $\lambda$ et $\mu$ donnés
si t est donné , est ce qu 'il faut simuler une trajectoire dans $[0,t]$ c'est à dire une fonction en escalier de$ [0,t] $dans$ \N$

sadfub0

Bonjour,
le cas où la fonction atteint $k=C$, elle y reste alors pendant un temps suivant une loi exponentielle de paramètre$C\mu$ ou $\mu$ ?

afk

Cmu puique c est le minimum de C variables independantes de loi exponentelle de parametre mu.

sadfub0

Bonjour,
MJ_ addict >voilà mon programme sous scilab:(je voudrais voir le votre) et la suite du problème
Afk > pourriez vous me corriger (je suis débutant sur scilab)

function  pp=traj(t,X0,C,lambda,mu)
   X=X0;
   TT(1)=0;
   XX(1)=X0;
   T=0;
   i=1;
   while (T<t)
      i=i+1;
      r=rand();
      X=X+(1*(r<lambda/(lambda+X*mu))-1*(r>=lambda/(lambda+X*mu)))*( 0<X)*(X<C)+1*(X==0)-1*(X==C);
      T=T+(grand(1,1,'exp',1/lambda))*( 0<X)*(X<C)+(grand(1,1,'exp',1/lambda))*(X==0)+(X==C)*grand(1,1,'exp',1/(C*mu));
      XX(i)=X;
      TT(i)=T;
   end
   n=length(XX);
   pp=plot2d2(TT(1:n-1) ,XX(1:n-1));
endfunction

sadfub0

Enfin

$function $ $pp=traj(t,X0,C,\lambda,\mu)$
$ X=X0$
$TT(1)=0;$
$ XX(1)=X0;$
$T=0$
$i=1$
$while (T < t)$
$ i=i+1;$
$ r=rand();$
$ X=X+(1*(r <\lambda/(\lambda+X*\mu))-1*(r>=\lambda/(\lambda+X*\mu)))*( 0<X)*(X<C)+1*(X==0)-1*(X==C);$
$T=T+(grand(1,1,'exp',1/\lambda))*( 0<X)*(X<C)+$
$(grand(1,1,'exp',1/\lambda))*(X==0)+(X==C)*grand(1,1,'exp',1/(C*\mu));$

$XX(i)=X;$
$ TT(i)=T$
$ end$
$n=length(XX);$
$pp=plot2d2(TT(1:n-1) ,XX(1:n-1));$
$endfunction$

MJ_Addict

Bonsoir,

Merci encore une fois pour vos réponses !

Je ne m'y suis pas penché aujourd'hui, j'avais un autre projet à finir en parallèle :P

sadfub, je vous envoie le sujet demain si vous le désirez et j'essayerai de faire un algo correct, demain ou après demain.

sadfub

Ok et merci

MJ_Addict

Dans votre algorithme sadfub, ce ne serait pas 1/lambda+Xmu dans la fonction grand ?

sadfub

Exactement bien vu : mais seulement dans le cas où ( 0< X< C)
on a (grand(1,1,'exp',1/(lambda+X*mu)))

Sinon j'aimerais bien que afk nous corrige éventuellement.

MJ_Addict

Pouvez vous m'expliquer simplement pourquoi lorsque le r< λ/(λ+ X*µ) X augmente de 1 et lorsque r>=λ/(λ+ X*µ) elle descend de 1 ?

Je sais que c'est au niveau de la binomiale et que si r< λ/(λ+ X*µ) alors cela signifie qu'un appel arrive et que r>=λ/(λ+ X*µ) un appel part mais que représente concretement le rapport λ/(λ+ X*µ) ?

Merci d'avance

sadfub

d'après le lemme de reveil

MJ_Addict

Comment avez vous déterminé le paramètre de la loi binomiale ?

sadfub

Car $\min(x,y_1,\ldots,y_n)=\min(x,\min(y_1,\ldots,y_n))$ ce qui permet de confondre $n$ réveils en attente à un seul réveil pour appliquer le lemme des deux réveils.

sadfub

ok
Si $T_0$ et X $T_i$ suivent des lois exponentielles de parametres respectifs $\lambda$ et $\mu$ (temps avant que le réveil sonne), alors le minimum $T$ de $T_0$ et des X $T_i$ suit une loi exponentielle de paramètre $\lambda +X \mu$. De plus si on note $N$ le numero du reveil qui sonne en premier, alors $P(N=0) = \frac{\lambda}{\lambda+X\mu}$

Pour le montrer il suffit de remarquer que $P(N=0) =P(T_0<Min(T_i))$