L’ergodisme et la convergence des simulations de phénomènes aléatoires

L ' E R G O D I S M E ET LA C O N V E R G E N C E D E S S I M U L A T I O N S D E PH]~NOM]~NES AL]~,ATOIRES

p a r

Pierre LE GALL

Ing6nieur en chef des t61~communicatiens *

SOMMAIaE. - - On expose les propridtds de l'ergodisme, c'est-d-dire de la convergence des moyennes temporelles, lesqueUes permettent de rdgler la durde d'une simulation de phdnomdnes aldatoires. On s'al~ranchit, dans la mesure du possible, de l'hypothdse de stationnaritd et, en faisant dr plusieurs fois le processus d partir de conditions inltiales identiques (ce que ne permet pas l'observation des phdnom~nes rdels, oh le temps est irrdcerslble), on montre comment l'obsercation de la caleur probable des moyennes temporelles permet de conclure sur la convergence et sa raplditd, sans connaissance spdclales sur le processus simuld. On indlque comment cette caleur probable est fide au comportement asymptotique du proeessus et d sa fonction c( mdmolre )), c'est-d-dire d sa fonction de covariance traduisant la corrdlation entre les dvdnements successifs. On montre en outre que, pour avolr la concergence vers la loi normale, il est ndcessaire et suffisant que le proeessus se comporte asymptotiquement comme un processus markovien ou tout au moins v.markovien. Sans cette proprigtd, la durde de la simulation est nettement plus longue. On expose au chapitre ( IV, F) les r@les pratiques pour rdgler cette durde, et on termine par le eas des simulations de rdseaux

tdldphoniques.

P L A N . - �9 I. : In t roduc t ion . �9 l I . : Prdc i s ion d 'une o b s e r v a t i o n . �9 I I I . : O b s e r v a t i o n s rdpdtdes it un i n s t a n t donnd. �9 IV. O b s e r v a t i o n s de m o y e n n e s t e m p o r e l l e s (cas d'un seul passage sur calculateur) A) Convergence en moyenne quadratique; B) Convergence presque s~re; C) Rapiditd de la convergence; D) Les chaZnes homog~nes de Marker ; E) Dispersion suivant la loi normale ; F) Rdgles pour la durde des simulations. �9 V. : S i m u l a t i o n d 'un rgseau td ldphonique A) Cas d'un faisceau de circuits avec appels perdus ;

B) Cas des rdseaux. �9 VI. : Conclusion. �9 Bibliographic (12 rgf.).

I . I N T R O D U C T I O N .

Les m6thodes de simulation de processus al6a- toires sur calculateur 61ectronique fournissent un moyen d'investigation efficace pour 6tudier les cas les plus complexes, les moyens math6matiques 6rant trop souvent insuffisants dans l 'obtention de r6sul- tats chiffr6s, n6cessaires aux 6tudes de recherche op6rationnelle.

Toutefois, les ex6cutions de simulations 6rant souvent tr~s cofiteuses, il y a lieu de s'assurer non seulement que les r6sultats obtenus peuvent servir effectivement d'estimations pour les param~tres du processus h observer, mais aussi que la dur6e de la simulation a 6t6 bien r6gl6e pour obtenir la pr6cision d6sir6e.

Nous allons pr6senter quelques r~gles g6n6rales, permet tant de d6finir ces dur6es de simulation, dans le cas off nous n'avons que des informations som- maires sur les propri6t6s du processus h observer sur calculateur arithm6tique. Nous n'envisagerons que les processus h 6volution perp6tuelle. Pour le cas peu fr6quent de processus s 'arr~tant d'eux- mgmes, tel un duel se terminant faute de combat- rants, nous renvoyons h l '6tude de MM. Gafarian et Ancker [1].

Nous distinguerons l 'observation directe h u n instant donn6, h l 'aide de plusieurs passages, de l 'observation des moyennes temporelles sur un

seulpassage. Ces deux types d'observation condui- sent au mgme r6sultat tout au moins dans le cas de stationnarit6. C'est cette propri6t6 qui est d6- nomm6e g6n6ralement (( ergodisme )) ou c( ergodicit6 ~. Le deuxi~me mode d'exploitation, souvent plus 6conomique dans le cas stationnaire, vanous condui- re h des d6veloppements plus 6tendus, du fait de l'influence de la corr61ation entre des 6poques voi- sines. Nous en ferons l 'application ~ l '~tude de l'6cou- lement de trafic dans des r6seaux t616phoniques, oh les dur6es de simulation sent particuli~rement importantes.

Nous allons commencer par d6finir ce que nous entendons par precision d'une observation.

I I . P R ] ~ C I S I O N D ' U N E O B S E R V A T I O N .

Un r6sultat d 'une simulation est un nombre a, qui est en fait une des valeurs possibles que peut prendre la variable al6atoire Z qui sert (~ d'estimateur )) pour 6valuer le param~tre h observer, n6cessairement 6gal h E(Z) : esp6rance de Z. La simulation n 'est efficace que dans la mesure oh la dispersion des valeurs possibles prises par Z, autour de sa valeur probable, tend vers 0 quand la dur6e des simulations, ou leur nombre, crolt. Nous sommes amen6s h 6tudier la variance de cet est imateur :

(1) ~2 = E(Z 2) _ [E(Z)]~ = E t Z -- E(Z) I S, et ~ pr6ciser tout d 'abord deux types de convergence al6atoire assez diff6rents.

* D6tach~ h la Soci6t6 mlxte SOCOTEL : chef du service de Tdl6trafic & Recherche op6rationnelle,

- - 211 - -

2/18

1 o Convergence en m o y e n n e quadratique.

Nous disons que la variable al~atoire [Z - - E(Z)] tend vers 0 en moyenne quadratique si a ~ tend vers O, quand la durge de la simulation, ou le nombre de passages suivant le cas, cro~t ind~finiment. L'in6galit6 de Bienaym6 permet alors d'6crire,

c[uand E(Z) n'est pas nul :

p r I I Z - - E ( Z ) [ I (Y2 E(Z) >/ p ~ [pE(Z)] 2"

Si a z tend vers 0, nous pouvons dire que cette probabilit6 devient n6gligeable, m4me si pes t petit, a 4tant la valeur prise par Z et 6tant voisine de E(Z), nous 6crirons plut6t :

a G2

ou mieux :

(2) P, I 1~ - E(Z)! < ~ I < ~ - (~7"

Cette probabilit6 d6finit un certain coefficient de confiance pour que l'6cart de l 'estimation soit inf6rieur h une certaine valeur Aa = pa, appel6e intervaUe de confiance.

Si l ~ [cs/(Aa) ~] = 0,95, nous avons :

Aa = 6 V ~ "~ 4,5 a. L'in6galit6 de Bienaym6 permet done d'6noncer : Pour un intervolle de confianee Aa = 4,5 a, le

coefficient de confiance est au moins 6gal h 95 %. O U e n c o r e :

Pour un coefficient de eonfianee de 95 %, l'intervalle de eonfiance Aa est au plus @al it 6,5 a. Pour obtenir une valeur plus pr6cise de cet inter-

valle, il est n6cessaire de connaltre la loi r6gissant les dispersions. Nous reviendrons plus loin sur ce point.

Ce type de convergence en moyenne quadratique n'exclut pas l 'apparition toujours possible d'6carts importants, quoique tr6s peu fr6quents. Autrement dit, si les r6sultats d 'une simulation paraissent ~tre concluants, est-on stir qu'il en sera de m6me en recommenqant la simulation un certain nombre de fois, avec des suites de nombres pseudo-al6atoires diff6rentes, ou en la prolongeant beaucoup plus ? N'en trouvera-t-on pas une oh l'6cart des r6sultats sera net tement plus important ?

Pour ~tre prat iquement stir de ne pas trouver de tels cas d6favorables, il y a lieu de faire intervenir aussi un autre type de convergence al6atoire.

2 ~ Convergence presque sfire.

Nous disons que la variable aldatoire [Z - - E(Z)] tend presque s~trement vers O, quand la durde de la simulation, ou le nombre de passages, crolt inddfi- merit, s'il y a une probabilitd @ale it I pour que [Z - - E(Z)] tende vers 0 au sens de l'analyse. La variable Z e s t fonction d 'un param~tre discret

ou eontinu n caract6risant la dur6e de la simulation. ]~crivons :

(3) z,~ = z . - E(Z.).

P, LE G A L L [ANNALES DES T~L]~COMMUNICATIONS

La th6orie montre qu'il y a convergence presque sfire, s'il existe un hombre ~ > 0, tel que la somme :

Y~ E(IZ~,I ~')

reste born6e. En particulier, si la s6rie : oo oo

(4) Z E(Z~ 9")= Z ~

converge. L 'un de ces deux modes de convergence n'entralne

pas forc6ment l 'autre, et nous serons amen6s h les v@ifier tous les deux.

III . OBSERVATIONS R~.PI~T~.ES A U N I N S T A N T D O N N ~ .

Nous avons un processus quelconciue, pas [orcg- ment stationnaire. Nous voulons 6valuer la probabi- lit6 d'apparit ion d 'un certain 6v6nement it un instant donn6 de l '6volution du processus.

D6signons par Y~ une variable al6atoire, relative au ie passage de la simulation, prenant la valeur I si l '6v6nement arrive, et 0 dans le cas contraire. Nous effectuons N passages, o6 les donn6es initiales sent les mgmes, la suite des nombres pseudo-al6atoires utilisds 6tant diff6rente pour chaque passage.

Une estimation de la probabilit6 de l '6v6nement est donn6e par l 'estimateur :

I5) zN = ~ , . z{ v~.

Les variables Y~ 6tant indgpendantes, nous avons an fait un probl6me de (( pile ou face )), ou encore d 'al ternative r6p6t6e. Nous rappelons que la th6orie permet d'affirmer que Z N converge non seulement en moyenne quadratique (loi ordinaire des grands nombres), mais aussi presque sfirement (loi forte des grands nombres). La limite cherch6e, qui sert h 6valuer la probabilit6 de l '6v6nement observ6, est done la fr6quence moyenne des r6sultats des observations, faites sur un grand hombre de passage. Son 6cart avec la valeur th6orique p peut ~tre caract6ris6 par la variance des dispersions, cf. formule (l), qui vaut ici :

(6) ~ = E ( Z ~ ) _ p(~ - - p) N

Nous rappelons, en outre, que la fonetion de Z N - - p

r6partition de la variable al6atoire r6duite - - q N

tend vers la loi normale r6duite ou loi de Laplace, de sorte que la formule (2) peut gtre prgcis6e par la suivante, donnant le coefficient de eonfiance pour un intervalle de eonfiance relatif p donnd :

p, I [ Z N - - t! (7)

off :

(8) ~(x) -- V / ~ . . . . exp -- dx.

Nous d6duisons, dans ce eas, la r~gle pratique suivante :

2 i 2

t. 22, n os 7-8, 1967]

Pour un coefficient de 95 ~/o, l'intervaUe de confiance absolu Ap = p9 vaut :

(9) �9 Ap = 1,96~Iv ~ 2(~.

Compte tenu de l'expression (6) pour air, la formule prde4dente permet d'6valuer l'intercalle de confiance relatif Ap[p, en fonction du nombre de passages N :

Ap ~lv / i -- p - - ~ 2 - - = 2 p p ~ pN "

Appelons B = p N le nombre de fois que l'gvgne- ment ddslrg a gig observd. Nous avons :

(10) 5,pip ~, 2 V~(t -- p)IB.

Ap[p mesure en quelque sorte la pr6cision de l 'observation. G~n6ralement p e s t faible devant 1, d'ofi :

(1I) �9 Ap/p ~ 2Iv"B.

Pour une pr6cision de 20 %, nous devons avoir B -= 100. Si p = 0,1, il en r6sulte qu'il faut effeetuer N = B / p - = i 0 0 0 passages. Si p = t 0 -a, il est n6cessaire d'effectuer N = t0 ~ passages.

Ce dernier hombre conduit h se demander s'il ne vaudrai t pas mieux, pour les petites valeurs de p, d'effectuer un seul passage mais beaucoup plus long dans le cas des processus stationnaires au sens strict. Nous rappelons en effet que, dans ce cas, ]e th6o- r~me de Doob-Birkhov permet d'estimer la proba- bilit6 d 'apparit ion d 'un 6v6nement ~ un instant quelconque h l 'aide de fr6quence moyenne d'apparition dans le temps. Nous 6vitons ainsi les temps perdus au d6part de chaque passage de simulation, par suite de l'inscription des donn6es et surtout des d61ais n6cessaires pour atteindre la stationnarit6.

En outre, dans le cas de processus non stationnaires, il peut arriver que nous voulions justement noter des moyennes temporelles qui interviennent normalement dans les probl~mes de recherche op6rationnelle, surtout s'il s 'agit d'optimiser des cofits sur une dur6e donn6e.

IV . O B S E R V A T I O N S D E M O Y E N N E S T E M P O R E L L E S .

(Cas d 'un seul passage sur calculateur)

Nous observons en un seul passage un processus, stationnaire ou non, d6fini par la fonction al6atoire X(t), off t e s t un param~tre continu, par exemple le temps.

Comme il s'agit de simulation sur calculateur arithm6tique, ce processus est discontinu et born& Autrement dit, le syst~me envisag6 peut prendre des dtats distincts en hombre fini. I1 en est de rn~me de route fonction al6atoire Y(t) associ6e au processus et prenant la valeur rgelle y~ quand le syst~me est

l '6tat E~. I1 s'ensuit que les moments ElY(t)] ~ existent et

sont born6s. La fonction de eovarianee :

(12) P(t, t ' ) = E I Y(t).V(t')]

�9 Ce s igne typogJaph lque indique Ies t'o~mules encadr6es sur le manuscrit.

L'ERGODISME ET LA CONVERGENCE DES SIMULATIONS 3/i8

existe donc, car d'apr~s l'in6galit6 de Schwarz, nous avons :

E[Y(t). Y(t')l ~< v/ElY(t)] ~ . E[Y(t')] ~.

Cette fonction F(t, t') est importante, car elle traduit , en premiere approximation, la d @ e n d a n c e qui existe entre deux 6v6nements voisins ou non dans le temps. Nous la retrouverons tout au long de notre expos& Notons que :

(13) P(t, t ) = E[Y ~ (t)],

et d'apr~s l'indgalit6 prde4dente :

(14) IF(t, t')l ~< V'P(t, t).F(t, t').

Quand les 6poques t et t' sont tr~s distantes, les variables Y(t) et Y(t') sont g6n6ralemont pratique- ment ind6pendantes. Nous pouvons alors 6erire :

(15) r(t , t ' ) = E t Y(t).Y(t') f ~ EY(t).EY(t').

Nous nous int6ressons au comportement de la moyenne temporelle al6atoire :

(16) Z~, = ~ / T Y(t) dt.

Dans le cas de l 'observation d 'un proeessus stationnaire, l ' instant 0 des observations n'est pas forcgment le dObut de la s imulat ion; il y a lieu, en effet, d 'a t tendre un certain temps pour que le r6gime stationnaire soit atteint , d~lai g6n6ralement laiss6 a l 'appr6eiation de l 'utilisateur, par examen des r6sultats sortis h 6poques r6guli6rement espac6es Le d61ai d 'obtention de la stationnarit6 d6pend, en effet, beaucoup de la fr6quence d 'apparit ion de l '6v6nement observ6 et de la taille du syst6me simul6. Pour un mgme syst~me observ6, l'6poque 0 choisie pourra done gtre diff6rente selon qu'il s'agit de noter, par exemple, un trafic ou une probabilit6 d 'a t tente tr~s faible.

D'apr6s le th6or6me de Doob-Birkhov d6ja signal6, rexpression (16) tend presque s~rement vers une variable aldatoire limite A quand la dur~e de l'observation T cro~t inddfiniment si le processus est stat~onnaire au sens strict. (C'est-h-dire si la loi temporelle du processus est ind6pendante de toute translation dans le temps.)

En fait, si nous voulons qu'une simulation soit ex6cut6e en un seul passage sur le calculateur, il est n6cessaire de nous limiter au cas oft ~ se rdduit ?tun nombre certain A, pour que le r6sultat h obtenir ne soit pas masqu6 par les dispersions de ~.

En outre, il est n6eessaire de supposer que le choix de l'@oque 0, et l'histoire du syst~me jusqu'?t l'gpoque 0 comprise, n'influent pas sur la valeur du hombre limite A.

Cette quantit6 observde vaut done :

(t7) A = lira E(Zr), T h-or3

= lim ~ EY(t) dt.

En particulier, si Y(t) prend la valeur I quand le

- - 2 i 3 - -

4/~8

syst~me est h l '~tat Ej, et 0 dana le cas eontraire, nous d~duisons :

(18) A---- lim ~ Pj (t)dt, T-),Oo

o~t P~(t) est la probabilit6, pour le syst~me, d'6tre h l '6tat Ej h l ' instant t. A est la moyenne temporelle limite des apparitions de l'6,dnement considdrd, et [ournit finalement la moyenne temporelle limite de la probabilitd de production de cet d~,dnement.

Comme nous nous pla~ons actuellement dans le cas de la stationnarit6 au sens strict, PC(t) est ind6- pendant de t. (18) devient :

(19) A -= Pc.

Autrement dit, dans le cas de la stationnaritd au sens strict, A fournit la caleur de la probabilltd de production d'un dc, gnement h u n instant quelconque.

Ainsi, il est possible d 'observer une probabilit6 h un instant donn6, h l'aide d 'un seul passage, sur calculateur, de la simulation, t~videmment le pro- blame crucial est de d6terminer la dur6e de ce passage, en fonction de la prdcision d6sirde sur l 'estimation. Auparavant , nous allons consid6rer les cas oh il n 'y a pas de stationnarit6 au sens strict, et oh l 'existence de la quantit6 limite A peut encore nous int6resser et justifier l 'utilisation de la simulation.

A ) C o n v e r g e n e e en m o y e n n e quadrat ique .

Le processus n 'est pas stationnaire, mais on suppose que l'int~grale double

~o T / r F(t, t ').dt.dt ',

existe. I1 s'ensuit, d'apr6s la th6orie, que l 'expression (16) de Z r existe. C'est une int6grale de Riemann, convergeant en moyenne quadrat ique.

Nous pouvons alors 6erire :

r E ( Z ~ ) = ~ - ~ E I . ) ( ~ d ~ Y ( t ) Y ( t ' ) d t dt' I,

1 f r r )/C E 1 - - T ~ J o J o Y(t)Y(t') dt dt',

OU ; 1 - r / r

(20) E(Z~) = ~ ./o F(t, t') dt tit'.

Consid6rons maintenant l 'expression :

E(Zr - - A) ~ = E(Z~,) + A ~ - - 2AE(Zr).

Pour que Z r converge en moyenne quadrat ique vers A, il est n6cessaire et suffisant que l'expression pr6c6dente tende vers 0 quand T crolt ind6finiment. Nous d6duisons que si Z r converge, done E(ZT) aussi, il en est de mgme de E(Z~). Inversement, si E(Z~,) converge vers A ~, E(ZT) converge vers A. Ainsi, d'apr~s l 'expression (20).

Thdor~me I Pour que Z~ converge en moyenne quadratique

~,ers le nombre certain A, il est ndcessaire et suffisant que la limite suivante existe :

(21) Lira ~ P(t, t') dt d t ' = A ~.

- - 214 - -

P. LE G A L L [ANNALES DES T~Lf~COMMUNICATION$

Cette limite n'existe pas toujours en effet, bien que l 'expression du premier membre soit toujours bornde du fair que nous ne consid6rons qu'un syst6me limit6 en taille. Cette expression pourrait, par exemple, osciller quand T crolt ind6finiment.

Cas discret .

I1 arrive souvent que l'on ne s'int6resse qu'h des instants particuliers du processus. D'abord parce qu'il peut gtre jus tement demand6 d'observer ces ins tan ts : par exemple les instants d'arriv~e de visiteurs, en rue de l 'obtention de leur probabilit6 d 'a t tente ou de la longueur de la queue ~ leurs arriv6es, surtout si cette quantit6 r6agit sur le comportement des visiteurs. Mais il peut arriver aussi que l'on simplifie le processus en n 'observant que des instants bien choisis : instants de transition pour un processus de Markov, instants d'arriv6es de visiteurs quand le processus des arriv6es est r6g6nd- ratif et quelconque avec une loi exponentielle pour les dur6es de service. On a alors affaire h une chalne de Markov, malgr6 la g6n6ralit6 du processus des arrivdes. Pour des processus plus g6n6raux, il p e u t

aussi 6tre patrols possible d 'obtenir ainsi une chalne stationnaire du second ordre.

Si q, ts, . . . , t~, . . . consti tuent la suite de ces instants, posons : Y ( t n ) = Yn. Nous avons alors affaire h une chalne de r aldatoires Yn.

Au lieu de l 'est imateur Z r d6fini par (i6), nous consid6rons maintenant l 'cst imateur ZN d6fini par (5). La fonction de covariance (i2) devient :

(22) F(n, n') = E [ Y , . Y, , },

et la condition de convergence en moyenne quadratique (21) devient :

t N N (23) Lira E E F(n, n q = A 2.

N,--)-OO ~ nf f i l ~ ' = 1 "

Gas d' un processus asymptotiquement stationnaire du second ordre.

Nous supposons qu 'au bout d 'un temps plus ou moins long, la fonction al6atoire X(t) devient prati- quement stationnaire d 'ordre deux. Autrement dit, nous supposons que les limites suivantes existent :

t Lim E I X(t) }---- M, t ~

(24) Lim F(t, t § ~) = C(~-).

C(z) est appel6 la fonction de corrglation, et nous la supposerons continue pour z = 0.

Nous d6duisons de suite :

(25) Lim E ( Z r ) = M. T.--> ~

Pour que Z T converge en moyenne quadrat ique vers M, it faut et il sufflt que la limite (2t) existe. Or, cette expression a mgme convergence, d'apr6s (24), que :

i S r ~ 0 0 r T--- ~ C(t-- t') dt dt' 2

a0

t. 22, n ~ 7-8, 1967]

Nous pouvons 6noncer :

Thdorbme 2 Pour un processus asyrnptotiquement stationnaire

d'ordre deux, de [onction de corrdlation C(v), Z T eon~,erge en moyenne quadratique vers un nombre certain A si, et seulement si, la limite suit, ante existe :

Dans le cas discret, la limite "h consid@er a pour expression :

(27) Lira N 1 - - ~ C(n),

o~l compte tenu de (22) :

(28) C(n) = Lim ln(nl , n I + n). q$1 ,--><:x3

Remarque importante. Notons bien que nous ne parlons que de station-

narit6 limite, car c'est bien Ie eas dans les simulations, off nous n 'avons pas la stationnarit6 au dOpart. De plus, il s'agit de processus n 'exis tant pas avant le dObut de la simulation�9 I1 y a done une diseontinuitd au dObut de la simulation. Ceei nous emp@he de faire appel "~ la thforie, si fOconde, de l'analyse harmonique des fonction.s alOatoires, basOe sur un thOor~me fondamental de M. Logve [3], suivant lequel toute fonction alOatoire, s tat ionnaire ou non, peut ~tre repr6sentOe (avec une probabilit6 6gale h t) par l'intOgrale suivante (existant en moyenne quadratique) :

(29) X(t) = ~ + ~ e2~i~t dx(~),

oh x(v) est une fonction alOatoire du param~tre v continu ou non, cette fonction 6tant dOterminOe de fa~on unique. Nous aurions dOmontr6 alors aisOment non seulement la convergence en moyenne quadra- t ique dans t o u s l e s cas, mais aussl la convergence presque sore. En fait, cette thOorie suppose la continuitd de la fonction de covarlance F(t, t') dans toute l'Ochelle des temps ( - - c~, + c~). Au fond, elle impose des conditions de r6gularitO, mgme pour un pass6 tr~s lointain, incompatible avec le principe des simulations. C'est pourquoi, nous en resterons h notre thOorOme n ~ I pour la convergence en moyenne quadratlque. Abordons main tenant l'Otude de la convergence presque sore.

B) Convergence presque sore.

Nous savons que notre est imateur Z r converge en moyenne quadrat ique vers A. Posons :

(3o) z ~ = z T - A = ~ �9 [Y(t) .... AI at.

t Nous voulons maintenant savoir si Z r tend

presque sfirement vers 0 quand T crolt indOfiniment. La simulation effectuOe en un seul passage nous

montre bien, comme rOsultat, qu 'une valeur prlso

L'ERGODISME ET LA CONYERGE/qCE DES SIMULATIONS 5 / ~ 8

par Z r tend bien vers A. Si nous n 'avons aucune information sur le processus envisagO, il est toujours possible de recommencer la simulation un certain nombre de fois, avec des suites diffdrentes de nombres pseudo-alOatoires. Nous pouvons ainsi (au prix d 'un coot 6levO) suivre la convergence de E(Zr) et de E(Z;,), moyennes des rOsultats des divers passages. En fait, dans la pratique, nous nous conten- tons d 'un seul passage en admet t an t que la convergence des rOsultats recueillis donne une idOe approximat ive de la convergence de E(Z~,).

Nous supposerons qu'il a 6t6 possible de t rouver un nombre ~ (0 < ~ < ~ 1 ) , tel que, pour T suffisamment grand :

(31) T~.jEc (Z~)[ ~< H,

oh H est indOpendant de T et de c. L'indice c signifie que le syst~me est suppos6 avoir suivi un certain (c c h e m i n , e jusqu'h l'Opoque 0. E c (Z~) est une espOrance conditionnelle. Nous supposons done que l'inOgalit6 (31) est v6rifiOe quelle que soit l'Opoque prise pour origine des observations, durant la simulation. Cette inOgalit6 signifie qu'h par t i r d 'un certain moment oh l 'on constate un certain 6cart, les 6carts suivants sent toujours plus faibles en moyenne. L'hypoth~se (31) n'est, en fair, pas restrictive h par t i r du moment o/t l 'on constate effectivcment la convergence de Ec (Zr), et aussi du fait que la fonction alOatoire Y(t) est supposOe bornOe.

(30) nous permet d'Ocrire :

2 / " a' (32) E(Z~)2---- T-~ ' /0 E[Y(t)-- :t] dt X

t ~' Erc o [Y(t') - - A] dt',

ou encore, sous une forme plus directement appli- cable au cas discret :

l foe E(Zr) 2 = ~

2fo (a2') T~.

ElY(t)---A] 2 dt +

ElY(t) - A ] d t •

~t+ T E,(t) [Y(t') - - ] dt'. A 0

E~(t) est l'espOrance conditionnelle, 6tant suppos6 que Y(t) a pris la valeur y h l ' instant t. Cette expression peut encore s'Ocrire d 'une autre fa~on. D6si- gnons par Xj(t) la fonction al6atoire telle que :

l y - - t , si~tat Ej,

y = 0 dans le cas contrairc.

Posons :

(33) 7~j = Lira en m.q. Xj (t) dt.

7~ n'est autre que la limite de la moyenne temporelle des dtats Ej. Elle est supposge exister, puisque Xj(t) n 'est autre qu'une fonction Y(t) particuli~re attaehOe au processus.

- - 2 i5 - -

6/18 La premiere int6grale de (32') s'6erit done :

�9 ~-~], E[Y(t)-- A]' dt =

1 t ~o ' r ~ ( Y i - A) ~ ~ X s(t) dt.

Elle a pour limite, en moyenne quadrat ique :

(34) Lira en m.q. -~ E I Y ( t ) - A dt---- l'....~ao

off rq est donn~ par (33). Cette expression converge comme I [T.

Quant h la deuxi~me int6grale de (32'), d ie est born6e en module par l 'expression suivante, compte tenu de (31) :

2 X r H ~-~ IE[Y( t ) - A]I ( T - t) ( T - - t) ~ dt =

2H / ( " _ ( i _ ; ) ~ - a dt T=+~ j 0 r ]E[Y(t) A]I

2H i / ' r 2H < ~ 'F J o IE[Y(t ) - All dt ~ - ~ ~r:~ [y~ -- AJ.

En r6sum6 :

Thdorbme 3 E(Z'r) et E(Z'r)~ tendent vers 0 de la m~me

fafon. Si IT ~ E(Z~)] reste born& en module, quand T

crest inddfiniment, il enest de m~me de T ~ E(Z~) ~. Rappelons que nous avons : 0 < ~ ~< 1. I I n e faut pas s'attendre d avoir ~ > 1, car cola

signifierait que les deux int6grales de (32 ~) conver- geraient de la mgme far En fait, nous aurions alors une forte eorr61ation, on principe non al6atoire, entre Y(t) et Y(t').

Sachant clue T a E(Z~) 2 reste born6e, nous allons 6tendre au cas non stationnaire une m6thode due

A. Blanc-Lapierre et R. Brard [2]. Dans le cas stationnaire d 'ordre deux, le th6or~me fut pr6sent6 dans le cas permanent par A. Blanc-Lapierre et R. Ferre t [4, p. 468] et dans le cas discret par J.-L. Doob [5, p. 492].

Introduisons le plus petit entier positif p satis- faisant h la condition p " > 1. I1 existe une valeur n(T), et une seule, telle que :

[n(T)]v ~< T < [n(T) + l]v.

l~crivons :

Z~ = ,~ [Y(t) - - A] dt =

i s . o [ Y ( t ) - A] dt + ~ (r)l l~ [ Y ( t ) - A]dt.

T Quand T crolt ind~finiment, nous avons : [n(T)]~-->t.

D'oh , t / t n ( r ) ] ~

(35) ZT ~ In(T)], [V(t)-- A] dt +

' U [u A] at.

P. L E G A L L [ANNALES DES T~L]~COMMUNICA?IONS

La premiere expression a une variance te|le que :

E(Z~)~ ~ KIn~ .

Donc la s6rie ~ E(Z~v), off les n sent extraits fl

de la suite n(T) est convergente. En vertu de (4), eette premi6re expression converge presque sore- ment vers 0. Quant h la variance de la deuxi~me expression, d ie a pour valeur :

i f r f r E n ~--~ j ~v j n~ I [Y(t) - - A] [Y(t') - - A] } dt at',

laquelle est major6e en module p a r :

(36) t f,-+'," f , .+ ." n l--~ j.v J . v E [ ]Y(t) - - A] •

[Y( t ' ) - -Al l dt dt'.

Du falt que notre systkme est supposg borng et blen que le processus ne solt pas forcdment stationnaire, nous pouvons 6crire :

(37) E l Y ( t ) - A] 2 ~ L,

off L e s t une eonstante. L'in~galit6 de Schwarz permet de majorer (36) par :

f<.+,,, f<.+,,. - - L dt d t ' = L - - n 2~ j n~ o J n~ /2t ~

= L + n ' + "'" < [ n ~ '

off L' est une autre eonstante, choisie suffisamment plus grande que L. La s6rie de terme g6n6ral (36) est donc convergente, quand n crolt ind6finiment. Par suite, le deuxi~me terme de (35), et done Z~,, convergent presque sfirement vers 0.


Thdorkme 4 Si les rdsultats de la simulation nous permet.

tent de choislr un hombre ~ (0 < ~ ~< t) tel que T IE(Z )I este bornde qu nd T croU inddZniment, nous pouvons conclure ~t la convergence presque sore de Z~ vers O. Remarque D'apr~s la d6monstration qui vient d'gtre donn6e,

ot qui repose essentiellement sur l'in6galit6 (37), le th6or~me pout gtre 6tendu ~ toute fonction aldatoire d'ordre deux, stationnaire ou non, born6e ou non.

Dans le cas discret, los conclusions sent les mgmes, si nous constatons que N a IE(Z~)[ reste born6e, quand N erolt ind6finiment.

Conclusion.

Si nous constatons exp&imentalement la convergence de E(Z~) ou de E(Z~), nous pouvons conclure simultangment 5 la convergence en moyenne quadratique et h la convergence bpresque sore, parce que le systkme envisagd est limitd. Cette constatat ion exp6rimentale de la conver-

gence de E(Z~) ou de E(Z~v), est fondamentale. Elle nous permet de conclure aux diverses conver- gences, sans connaltre los propri6tds du processus envisage, surtout s'il n 'est pas stationnaire.

- - 2 1 6 - -

t. 22, n o~ 7-8, 1967] L~ERGODISME ET LA CONVERGENCE DES SIMULATIONS

Nous pouvons reposer ainsi sur des bases solides le prineipe m~me des simulations, qui deviennent un instrument trgs effieaee d 'observation du eomportement des syst~mes al6atoires.

I1 nous reste h ehiffrer eette convergence, et tout d 'abord h en d6terminer la rapidit&

C . R A P I D I T I ~ D E L A C O N V E R G E N C E .

Reprenons l'expression (32), pour T suffisamment grand, nous pouvons l'6crire sous la forme :

(38) E(Z~,) 2 ~ 2 Z Z ( y i - - A ) ( y j - - A ) •

T~ P~ (t) dt p(j, t'li , t) dr',

off P~(t) est la probabilitd a priori pour le syst~me d'6tre h l '6tat E~ h l ' instant t, et off p(j, t' I i, t) est la probabilitd conditionnelle pour le syst~me d'fitre h l '6tat E~ h l ' instant t', s'il a 6t6 h l '6tat E, h Fins- tant t.

Notons que nous no ehangeons rien, pour l '6tude do la convergence, en retranchant ~ la derni6re int6grale (simple) la quantit6 :

r P~ (t') dt'.

Nous avons en effet :

t 2 Z Z ( Y i - - A ) ( y ; - - A ) ~ •

fo (t/d, f ,j/t'l CE(Z tI' Cette quantit6 tend vers 0 plus rapidement que

E(Z~) et donc que E(Z~) 2. Posons :

(39) f~.~(t, T ) = / T [P(J, t'[i, t ) - P~(t')] &'.

Nous sommes ramen6s h 6tudier le comportement, pour T infiniment grand, de :

i f T (40) g~.~ ( r ) = ~ P~ (t) f~.~ (t, T) dt.

Nous retrouvons de suite, clue , s if i , ~(t, T) reste born6e, gid(T) tend vers 0. Pr~eisons plus, et introduisons une fonction F(T), sup posde positive et non ddcroissante pour T su~fisamment grand, de fagon que :

F(T) (41) Lim ~ - --> 0.

1',->oo

Si nous avons, pour T suffisamment grand :

Ih,; (t, T)I (42) O < C1 < F(T) < C2,

t 6tant quelconque, nous d6duisons :

F(T) I (43) [g~.~. (T)I < Co. T T •

/ T F(T). P~ (t) dt ~ C2.~ ~ T

E(Z~) 2 converge alors comme F(T)[T.

Int6grons par parties l'int6grale (40):

T (44) F ~ g~j (T)------

7/ 8

1

F(T) •

P~(O) dO ~dt f , . j (t, T).

Posons t P~ (0) dO ~ = K(t, T), ot consid6-

rons un hombre fixe To, tel que 0 < T O < T. I~erivons :

1 / T 1 F(T) K(t, T) dt f~.j (t, T) = F - ~ •

f .T fT~ K(t,T)dth.j ( t , r ) + F ( T ) J 0 K(t, T)dt h., (t, T).

En vertu des in6galit6s (42), le dernier terme du second membre est major6 on module par une quantitg de la forme C ( T o ) I T , off C est bornge.

Cette quantit6 tend vers 0. Dans la mesure off le premier membre reste fini non nul, quand T crolt ind6finiment, nous ne ehangeons done rien en int8grant seulement h partir d 'une certaine 6poque T o fixde telle que, pour t ~> To, nous ayons :

lfot ~- Pi (t) dt ~ ~ ,

(44) pout alors s'6erire, pour T suttisamment grand :

T T:~ s t F(T) gi'j (T) ~ F(T) . v ~ dt h.j (t, r) ,

ou en int6grant par parties :

T ~i I s (45) F ~ gi.~" (T) ~ F(T) T ~ f~.~ (t, T) dt.

Notons que l ' introduction de la fonetion F(T) et des in6galit6s (42) nous a servi essentiellement faeiliter notre expos6, qui suppose on fait seulement que E(Zs 2 tend vers 0. Ainsi, pour T suffisamment grand, l 'expression (38) pout s%crire finalement, si E(Z~) 2 tend vers 0 :

t (46) E(Z~,) 2 ~-, 2 Z Z r:i (yi-- A) (yj-- A) ~ •

T fi.J (t, T) dt.


Thdor~me 5 E(Z~) 2 tend vers O, quand T cro~t inddfiniment

de la m$me fafon que l'expression :

tfo* (47) T- ~ /~.~ (t, T) dt,

oh f~, ~(t, T) est donnde par (39). Cette expression caractdrise le comportement du

processus pour T croissant inddfiniment. Remarquons qu'h partir de l 'expression (38),

nous aurions pu aussi bien 6crire :

1 (48) E(Z~) ~ Z Z ( y i - d ) ( y j - A ) - ~ •

i t

/ r / T R,., (t, t') dt dt',

- - 2 1 7 - -

8/t8 avec

(49) 1R+.~ (t, t ' ) = E I IX, ( t ) - EX+ (t)] • [Xr ( t ' ) - EXi (t')]l.

Rappelons qua X+(t) prend la valeur 1, si le syst~me est h l '6tat E~ (h l ' instant t), et 0 dans le cas contraire.

Nous pouvons ajouter le corollaire suivant au th6or~me 5.

Corollaire Quand T cro~t inddfiniment, l'expression (47)

et la quantitd :

'S'J:" (50) T~ R+.~ (t, t') dt dt',

off R+.~(t, t') est donnfe par (49), tendent ~,ers 0 de la m~me fa~on. Ce corollaire pouvait se d6duire d'ailleurs directe-

ment du th6or~me 1, qui permet d'dcrire :

Lira ~h]lo / R(t, t') dt d t ' = 0, J 0

(51)

off

(52) R(t, t ' ) = E [ [X(t)-- EX(t)] [ X ( t ' ) - EX(t')] },

est la fonction de co~,ariance du processus centrd. Rassemblons maintenant tous ces r6sultats, en

tenant compte du th6or~me 3.

Thdor~me 6 o t 2

Les quantit~s E(Z2) , E(Z2) , (47), (50) et (51) tendent vers 0 de la m~me fa~on, quand T crott indgfiniment, en supposant qua :

(53) Lira ~ P~ (t) at = ~i.

En particulier, si le produit de l'une de ces expressions par la [onction TIF(T), cf. (41), tend ~,ers une limite, quand T croft inddfiniment, il en est de m~me pour les autres : Dans le cas off ces limites existent, posons :

1 1 X r (54) " r-~oLim F(T) T f+.~ (t, T) dt = S~,

l 'expression (46) s'6crit alors, pour T grand :

(55) l E(Z~.) z ~. k F(T)IT,

oh

(56) * X = 2 E Z = + S + + ( y ~ - - A ) ( y j - - A ) .

Le cas, qui correspond h la convergence la plus rapide en l I T , est en fait le plus fr6quent. Pour le volt, il suffit de se reporter h la convergence do l'expression (51), relative h la fonction de covariance du processus centr6, qui exprime quant i ta t ivement la fonction m4moire du processus.

C'est ainsi qua nous trouvons une convergence en l I T , dans les cas suivants :

a) R(t, t') '~ K . xlt--t'l (0 < x < 1, It - - t' I grand). C'est le cas des processus tendant asymptotique-

ment ~,ers un processus de Marker, off la mgmoire du syst~me dgcrott exponentiellement ;

P. LE GALL [ANN&t,ES DES T~J~CO~UNICATIONS

b) R(t, t') ,~ K(I t - - t 'O. I t - - t ' l . x l~- 'v l (0 < x < 1, [t - - t'] grand), off K( l t - - t ' l ) est bernie. [ci, la m6moire d6croit moins vite.

K( t t - - t ' i ) ( m > 1, I t - - t ' [ grand), c) R(t, t') Et_ t,L off K(lt ~ . t ' l ) est born6e. Ici, la m6moire d6crolt encore morns rapidement.

Par centre, il n 'en est plus de mgme si la fonction de covariance est de la forme :

K (57) R(t, t') ~, It-- t' t' (it-- t'] grand).

L'expression (51) tend alors cars 0 comma log e T[T .

Dans les formulas (54) et (75), nous devons donc poser :

(58) F(T) ~_ log T.

La convergence existe encore, mais ella est beaueoup plus lente, et la simulation devra ~tre beaucoup plus longue.

Remarque Du fair qua les expressions (51) et (47) convergent

de la mgme fa~on, la connaissance approximati~e de la dgpendance de phdnom~nes dloignds permet de ddduire la rapiditg a~,ec laquelle le processus tend ~,ers le processus limlte, et rgciproquement la connaissance de cette rapidit~ donne des informations sur carte c( fonction mdmoire )~ du processus.

Gas discrct.

Nous pouvons appliquer de mgme les r6sultats pr6c6dents au cas discret, h condition de partir de la formula (32') au lieu de (32). L'expression (39), d6finissant f+, r T) deviant maintenant :

27 t59) f+~ (n, N ) = Z [P(j, n']i, n ) - Pj (n')].

L'expression (47) ost ~ remplacer par la suivante :

I N--I (60) N ~ Z f+.s (n, N).

n--1

Les th6or~mes 5 et 6 s 'appliquent de la m6me fa~on.

La formula (54) deviant :

(61) t S+.~ = 27-~ooLim F(N) N . - I f+j (n, N).

Toutefois (46) a pour homologue, compte tenu de (32') et de (34) :

{ ECZ~)~ ~ N i, TM (y+ -- A)2 +

(62) F(N) 2 - ~ - E • 7:s S+j (U~- A) (y, - - A).

(55) s'6crit maintenant sous la forme :

(63) i E(Z~) ~ ~ k N

- - 2 1 8 - -

t. 22, n ~ 7-8, 19671

Si F(N) crolt ind6finiment (de fa~on que F(N) I N --> 0), nous avons pour homologuc de (56) :

(64) k = 2 E E r:~ Ss~ (y~ -- A) (yi - - A).

Si, au contraire, nous avons F(N) ~ 1, (62) nous donne :

(65) �9 X-----E~(y~ - A ) 2

2 E Y, ~ Ss~ ( y ~ - A) (yr A)

Compte tenu de remarques d6jh fakes duns le cas permanent , nous avons F(N) - - I si, pour In - - n' I grand, la fonction de covariance ccntr6e d6crolt plus vite que l ] ~ n - - n ' I. Par centre, si elle d6crolt comme l [ l n - - n ' l , nous avons F ( N ) ~ Iog, N.

D. L E S C H A I N E S H O M O G I ~ N E S D E M A R K O V .

L ERGODISME ET LA CONVERGENCE DES SIMULATIONS

De (39), nous ddduisons : ~ p �9 ! �9

~q~zfx,~ (t, T)------ [ " 3p(j, t l t , t) x d ' t ~t dt ' .

Ecrivons d o n c :

Ce cas est tr6s fr6quent dans les simulations ; il permet no tamment de ne simuler que les 6poques de changement d '6tat du systbme, appel6es encore @oques de transition. Au fond, mgme dans le cas permanent nous sommes ramen6s h 6tudier une chalne discrete : celle des 6poques de transition. Nous allons toutefois donner les formules de convergence en temps rdel.

1 o Cas des e h a i n e s h o m o g 6 n e s p e r m a n e n t e s .

Rappelons que la nature des transitions est d6finie en fr6quence, par des nombres q~; (t), tels que :

p(j, t + Atli, t) ~ qs, (t).At.

En fait, nous n'envisageons que le cas des chalnes homog~nes off les q~j sent ind6pendants du temps, pour ~tre stir de l 'existence du processus limite, lequel est alors n6cessairement stat ionnaire :

(66) Lira p(j, t'li, t) = ~ . t ' , - - ~ : ~

(53) est donc v6rifi6. En outre, la fonction de covariance centrde d6crolt exponentiel lement. Le th6or~me 6 s 'applique et nous avons la convergence en I [ T . Done F(T) = I.

Nous allons d6terminer les quantit6s s~ qui inter- v iennent duns l 'expression (56), d6finissant le facteur ~, in tervenant dans (55), cette derni~re relation devenant :

(67) * E(Z~) ~ ~ ?~lr.

(54) nous donne :

t ~ 0 0 "T (68) Sij = Lim f~ dt. T-->c~ T" (t, T)

Les (( 6c[uations du pass6 )) nous d'6crire :

Z q,x plj, t'lZ, t) -- ),

~, qix. P~ (t') = O. ).

permet ten t

3p(j, t'ti, t) bt '

9/18

I / "

/~T T " '" = - - - J o dt f 3p(j, t_'[t, t)

T f i t 5t dt',

J ~0 T t" " "" (it' / p(l, t t) = - - T . J o -37 dt,

- - r [p ( j , t '[i , 0) - - ~iJl dt ' ,

off: I ~j----t, si j = i ;

3 i j = 0 , si j # i .

Quand T croit ind6finiment, nous d6duisons :

(69) Y, q~x. Sx~" = 7:~- ~ .

Introduisons plut6t le nouveau coefficient suivant:

(70) P~ = Z S~ ( y j - A). t

Multiplions les deux membres de (69) par ( y j - - A ) , et sommons membre h membre les relations homo- logues pour les diverses valeurs de j. Nous t rouvons :

(71) * Z qix ?x = - - (yi - - A). X

(56) s%crit maintenant :

(72) * )~=2 ~] r z i (y~--A) p~. i

Les 9~ sent d6termin6s par les ~quations (71), pour les diverses valeurs de i. La d6termination est h une constante additive pros, car nous rappelons la relation :

E q~x= 0. A

Cela ne peut changer la valeur de ), ; nous avons en effet :

Y, ~i ( y ~ - A) = O.

Ainsi, la convergence de E(Zg) 2 est enti~rement d6termin6e par (67), (71) et (72), off nous poserons, par exemple, P1 = 0. Ces formules ont 6t~ donn6es h l 'origine par R. Ferre t [6], qui les avaient 6tablies l 'aide de fonctions caract6ristiques. Nous en avons fait l 'application aux processus de naissance et de mort , duns [7, pp. 19i-194].

2 ~ Cas des c h a i n e s h o m o g ~ n e s d i scr6tes .

La chalne est maintenant d6finie par les probabi- lit6s de passage :

(73) p(/, n + l[i, n ) = p~.

Nous avons les relations :

t ~ iA P(j, n'lX, n) ---- p(j, n'[i, n - - t),

po,. Pj(n') ---- Ps(n').

- - 2i9 - -

0/18 Cette derni6re &luation provenant du fait que :

(74) Z pa = l, x

(59) nous permet d'6crire :

(75) Zp,x.fxJ (n, N) = f,~- (n - - t, N) - - [pij-- Pj (n)]

Appliquons (61), en notan t que, comme pour les ehalnes permanentes, nous avons F(N) - - I. Nous t rouvons :

N

Ainsi, pour les chafnes rdguli&es, et aussi pour les cha~nes oscillantes, nous avons les 6quations :

(76) S~j - - ~] pix. Sxs = pij - - ~s. A

Notons, en outre, que : ~] fi~ (n, N) = 0, &off : J

(77) E S,~ = 0.

Les 6quations (76) et (77) ont 6t6 donn6es par M. Fr6ehet [8]. Ant6rieurement, yon Mises [9] avai t trait6 le cas non oscillant (de fagon assez compliqu6e), Markov lui-meme ayan t montr6 la convergence on J IN.

Par analogie avee le cas permanent , introduisons plutSt la quantit6 :

(78) p, = Y~ Si~ ( y ~ - A) + ( y , - A),

(76) devient :

(79) �9 p i - - ~ P i x p x = y i - - A . X

Nous avons donc, pour N grand, Z~, 6tant l 'esti-

matcur ~ Y~ ( Y ~ - - A) : 11--1

(80) �9 E ( Z ~ ) ~ ~-, ),IN,

off X, d6fini par (65), a pour expression, compte tenu de (78) :

(81) �9 ~ t=2ZTc~(y~- -A) o ~ - - Z ~ i ( y ~ - - A ) 2-

Notons que les 6quations (79) no d6finissent los pi qu'h une constante addit ive pr6s du fait de (74), ce qui no change pus l 'cxpression X, h cause de la relation :

Z 7:i (yi - - A) ---- 0. i

Rappelons, h toutes fins utiles, que Zz~ est l 'es t imateur :

, t .~ r Y e _ A ) = 1 ,82) Z= = ~, ~ 2-dx Yi - - A,

oh Y, prend la valeur y~, si le syst6me est h l '6tat E~ l '6poque i. Nous avons termin6 nos investigations sur la

rapidit6 de la convergence des moyennes temporelles. I1 nous reste maintenant h nous faire une id6e de la fonction de repart i t ion de Z~ ou do Z2~, ear la loi

P. LE GALL [ANNALES DES T~BI~COMMUNICATIONS

r6gissant les dispersions influe sur la d6termination des intervalles de confiance. Les variances E(Z~) z et E(Z~) ~ ne suffisent pas, en effet, pour cet te d6ter- ruination.

E. DISPEFtSION. S U I V A N T LA LOI N O R M A L E .

Au chapitre III, nous avons trouv6 un exemple off les dispersions de Z~ so r6partissaient pratique- ment suivant la loi normale, quand N 6tait suffisamment grand : cf. (7) et (8). Toutefois, duns (5) les Yi 6talent ind6pendants. Ils ne le sent plus maintenant . Mais il est permis de so demander si, tout do meme, cette loi normale ne pourrai t se re t rouver dans certains types de processus, 6tant donn6 qu'elle t radui t le d6sordre extreme.

Rappelons que, pour une variable al6atoire cen- tr6e Z (E(Z) = 0), la fonction caract6ristique de cette l o i e s t :

G 2

En d6veloppant en s6rie eette fonetion, nous trou- -cons que les moments d 'ordre impair sont nuls, et que les moments d 'ordre pair valent :

(83) rn2n = ~ : = (2n-- l) . . . 3 . l . (~l)~.

l~,tudions done, pour T grand, los divers moments o

do ZT, d6fini par (30). Commen0ons par le troisi6me moment, i o u s avons :

E(Zr) = Z Z Z (yi - - A) (Yi - - A) (Yk - - A) • i t k

<=') S'S'S" P(i, q , j , t 2 ; k, ta) dq dt z dt a,

off P(i, t x ; j , t 2 ; k, t3) est la probabilit6, pour le syst6me, d 'e t re sueeessivement h l '6tat Ei fi l ' instant ti, h l '6tat Es h l ' instant t 2 et h l '6tat Es h l ' instant t a. D6signons par p(k, tail, tx; j, t~) la probabilit6 conditionnelle, pour le syst6me, d 'e t re ~t l '6tat Ek h l ' ins tant t3, 6tant donn6 qu'il a 6t6 successivement h l '6tat i h l ' instant t 1 et h l '6tat j h l ' instant t 2. Dans l 'int6grale pr6c6dente, groupons les termes homo- logues en ordonnant les t~ de fa0on h avo i r : t x < t 2 < t a. (84) s'6erit maintenant :

E(Z~)S= 3t Y~ Y, Y, ( y , - - A ) ( y s - - A ) ( y k - - A ) •

(85) T a P(i, q, j, t2) dt 1 dt 2 X

X r p(k, tall , tl, j , t2) dt a.

Retranchons, dans la derni6re somme, la quantit6 P(k, ta). Nous retranchons ainsi, au total, une quantit6 qui v a u t :

3E(Z~) ~. E(Z&).

- - 2 2 0

t. 22 , n ~ 7-8, 1967]

(85) devient :

E(Z~,) 3 -- 3E(Z~,) 2. E(Z[,) =

3 ! Z Z Z ( y ~ - - A ) ( y ~ - . A ) ( y ~ - - A ) •

(86) ~ l Jo#r ,~r P(i, q) dq __ ! , p(j' t2[i' q) dt2 •

f t , r [p(k, t31i , q, j, t~) - P(k, ta)] odt,

De m~me, retranchons P(j, t2) sous la deuxi~me somme. Nous retranchons ainsi, h l'int6grale triple, la quantit6 :

Z~ P(i, t~). dt 1 P(j, t2) dt 2 •

r [p(k, qlii q, j , t 2 ) - P(k, t3)] .dr

D'aprgs le raisonnement qui nous a permis de passer de la relation (40) h la relation (45), l'int6grale pr6e6dente est 6quivalente h la suivante :

1 T ~.7~ ~-~ f dt~ ~ r dt2 X

~,t, r [p (k, tall, tx i, t2) - - (k, tz)] dta ; P

(86) devient :

(87) E(Z~) 3 - 3 E(Z~) 2 E ( Z ~ ) = Aa + B~,

avec :

I A a = 3! ~ ~ Y~ ~ ~ (y~--A) (y~--A) (y~--A) x

(88) t - r r f r / dq f dt 2 [p(k, tail , t 1 ; j , t2) T 3 ./o ./t~ / .

- - P(k, ta) ] dta, e t :

B , = 3 ! Z Z Z (Y~-- A) (yj-- A) (y* -- A), ' i t k

t t ~" r T~3foo P(i, tl) dq f t ' [P(j, t2ti, t ,)-P(j,t~)]dt~• (89)

~/ . ~ [p(k, t31i , q, j, t2)-- P(k, t3) ]d t 3

Avec l 'hypoth~se (42), A x converge comme F(T) [T , alors que B~ converge comme [F(T)IT] 2. En outre, le th6or~me (6) nous permet d'affirmer que la quantit6 E(Zg) 2. E(Z~) converge comme [F(T) IT] 2.

Nous avons done :

(90) E Z(~) 3 ~ A~.

De fa~on g6n6rale, nous trouvons, pour un processus quelconque :

(91)

' I118 L E R G O D I S M E E T L A C O N V E R G E N C E D E S S I M U L A T I O N S

Ainsi, les divers moments de Z~ convergent en g~ngral comme F(T ) [T , et il n 'y a pas tendance vers la loi normale.

Supposons maintenant que p(k, ta/i , tl, j , t2) soit ind6pendant de i, et done de q :

(92) p(k, t3[i , t 1 ; j , t2) ~ p(k, t3tj, t2).

En ver tu de la relation :

(93) Z ~ ( Y , - A) = 0,

A 1 s'annule. Par suite des remarques pr6c6dentes, E(Z~) 3 converge alors comme [F(T)[T] 2.

' 4 Consid6rons maintenant E(Zr) , toujours dans l 'hypoth~se (92). Avec le m~me raisonnement qui nous a amen6s h la relation (86), nous pouvons

6crire :

E Z ' 4 4E Z ' 3 E(Z~) = ( r)- (r) 4! E E ~, E (y i - -A) (y j - -A) (y~-- A) (yl--A) X

j , ~ ~ , ~ T (94) ~ ' L _ _ P(i' q) d q A p(j' t~[i, tl) dt 1

f rp(k, t3lJ, t2)dtz~tt)T[P( l, t4lkt3)--P(l, t4) ] d/4

Pour 6crire cette relation nous avons suppos6, en fait, une relation plus restrictive que (92), h savoir :

(95) p(/, t4li , t I ; j , t 2 ; k, t3) ~ p( l , t4l k, t3).

Retranchons maintenant P(j, te) sous la deuxi~me somme, ce qui revient h retrancher au deuxi~me membre de (94) :

I t 2 t 2 3.[E(ZT) ] .E(Z r) .

En outre, en utilisant h nouveau le raisonnement qui nous a permis de passer de l 'expression (40) h la relation (45), nous trouvons :

4E(ZT) . E(Zr) - - 3!E(Z~) 2. [E(Z~)] ~ E ( Z ~ ; ? - - ' ~ '

4! Z E Z E (Yi-- A) (Yi - - A) (Yk - - A) ( y , - A) X t it l T Z'T

(96) ~ S ~S dq~ t ' [p(j, tdi, q ) - - P(j,te)] dtz •

7~ dt a [p(/, q!k, t3) -- P(/, t4) ] dt 4.

= 3[E(Z~)Z] ~

En appliquant le th6or~me 6, nous trouvons que ' 4 les termes du premier membre, autres que E(Zr) ,

convergent comme [F(T)[T] 3. Le deuxi~me membre converge seulement comme [F(T) IT]L Done, compte tenu de l 'hypoth~se (95), nous trouvons :

(97) E(Z~) 4 ~ 3.1. [E(Z~)~] 2.

E(ZT)'~ ~ m! ~ . . . ~] ~q (Y~I-- A) . . . De fa~on plus g6n6rale, on trouverai t : Q im

r~,~_, (y,,~_~ - - A).(y,, , - - A), (98) E(Z~) 2~ = (2m-- 1) . . . 3.t. [E(Z~)21%

2 c'est-h-dire la relation (83), h condition de supposer : dtl . �9 �9 dtm--1 2 (99) p(izm, t2~l il, t 1 ; . . . ; i2m-1, t~,,-l)

/ ~ [p(im, tml ix , i ra-- l , t in--x) p(12m, t~mli2,n-1, t~rn-~). t l , 1

- - P(i,~, ~)] dtr~. Un processus v6rifiant cette condition est appel6

- - 2 2 1 -

T,~

t5

12/t8 P. LE

un processus (2m - - 2)-markovien. C'est un proccssus plus g6n6ral qu 'un processus de Markov, qui est en fair v-markovien, v 6tant aussi grand que l'on veut.

Enfin, nous pouvons v6rifier que E(ZT)2m+I converge comme [F(T)[T] 'n, c'est-h-dire comme E(Z~) ~'~, en supposant l 'hypoth6se (99).

Les moments de la variable r6duite Z'~/~/E(Z'~ ~) ont pour valeur :

E(Zr) I[v 'E(Zr)] .

Si m'~< 2m-4-1, la quantit6 pr6c6dente tend vers une limite positive pour m' pair, et nulle pour m' impair.

En outre, toujours avec l 'hypoth6se (99) les moments E(Z~,) '~' pour m' > 2m q- 1, convergent comme E(Z~,) ~+~, c'est-h-dire comme [F(T)/T]%

En vertu du th6or6me 5, il suffit que la condition (99) soit v6rifi6e pour le processus asymptotique.

R6sumons tout ce qui vient d'gtre dit dans les deux th6or~mes suivants.

G A L L [ANNALISS DES TI~LI~COMMUNIGATION$

processus ne tend pas asymptot iquement vers un processus de Markov.

I1 est possible d'en approcher prat iquement si le processus asymptotique est v-markovien, pour v 6gal h quelques unit6s.

Cette condition n6cessaire ne semble pas encore avoir 6t6 signal6e.

Nous avons termin6 avec la th6orie de l'ergodisme dans les processus stochastiques. Nous allons pouvoir pr6senter maintenant quelques r6gles pratiques pour r6gler la dur6e des simulations.

F. RI~GLES. P O U R L A D U R ] ~ E D E S S I M U L A T I O N S .

Nous sommes donc dans le cas d 'une simulation effectu6e en un seul passage, et nous observons les moyennes temporelles fournies par les estimateurs Z r (cf. (16) ou ZN(cf. (5-).

1 o) V6r i f i cat ion de la c o n v e r g e n c e .

Thdor~me 7 Les limites (53) ~tant supposdes exister, la

fonction de rgpartition de la variable algatoire

rgduite Z'~[v/E(Z'~) 2, of~ Z" T e s t restimateur (30) des moyennes temporelles centrdes, est telle que ses m premiers moments tendent vers ceux de la loi normale rgduite, quand T cro~t indgfiniment, pour les processus tendant asymptotiquement vers des provessus (m ~ 2 ) - m a r k o v i e n , et pour v e u x - llz s e u l e m e n t .

Les moments E(Z'r) 'n', pour m' > m, convergent alors comme :

E(Z~)%

Si nous rappelons qu 'un processus de Markov est v-markovien, pour v aussi grand que nous you- lons, nous pouvons d6duire le th6or6me suivant.

TMor~me 8 Les limites (53) dtant supposdes exister, la

[onction de r~partition de l'estimateur Z'~ des moyennes temporelles centrges tend, quand T crott ind~finiment, vers In loi n o r m a l e , pour les pro- r t e n d a n t a s y m p t o t i q u e m e n t vers des processus de M a r k o v , et p o u r veux-l~ seule- m e r i t . Les th6or6mes 7 et 8 s 'appliquent aussi bien h

l 'estimateur Z)r [el. (82)], darts Ie cas discret. La convergence vers la loi normale, pour les

chalnes de Markov homog6nes et discr6tes, a 6t6 4tudi6e par M. Fr6chet [8], off routes les r6f6rences sont donn6es concernant les divers t ravaux faits sur ce sujet avant t938.

Le cas des chalnes de Markov homog~nes et permanentes a 6t6 trait6 par R. Fortet [6], h l 'aide de la m6thode des fonctions caract6ristiques.

Nos th6or6mes 7 et 8 apportent une information suppl4mentaire, h savoir qu'il n'est pas possible d 'obtenir la convergence vers la loi normale, si le

Tout d'abord supposons que nous ayons quelques informations g6n6rales sur les caract6ristiques du processus h simuler.

Si nous savons qu'il tend asymptot iquement vers la stationnarit6, ou vers une chalne homog6ne de Markov, il y a convergence (meme dans le cas des chaines homog6nes discr6tes de Markov du type oscillant).

Dans les autres cas, nous pouvons peut-~tre avoir une id6e de la d6pendance entre deux 6poques quelconques mais 61oign6es, c'est-h-dire du comportement de la fonction de covariance, et appliquer les th~or~mes I ou 2.

Dans la pratique, si les modifications apport6es au syst6me, h une 6poque donn6e, ne peuvent provenir que d'6v6nements dont l'61oignemcnt est certainement limit6, nous pouvons affirmer la convergence dans le cas suivant.

Supposons que l'6volution du syst6me soit d6finie s @oques successives, et qu'il s'ensuive que l'6vo-

lution al6atoire du syst6me soit ainsi d6finie pour le futur, par des probabilit6s de passages p(i~+l, ts+ l ] is, ts ; - " ; il, q) en fait ind6pendantes des 6poques pr6cipit6es, nous avons encore une chatne homog~ne de Markov, mais d'ordre s. Au fond, s peut gtre grand, ce qui n'emp~che pas d'avoir la tendance asymptotique vers une chalne ordinaire homog6ne de Markov.

Si nous n 'avons pas suffisamment d ' information th6orique pour affirmer la convergence, nous pouvons, moyennant un cofit plus 61ev6, effectuer une simulation plus longue et constater la convergence de z~ ou z~, valeurs prises par Z~, ou Z~ au cours du temps. I1 y a tout lieu de penser qu'il c n e s t alors de m~me de E(Z~) ou E(Z~). Par prudence, il est toujours possible d'effectuer plusieurs passages avee des suites diff6rentes de hombres pseudo- al6atoires. La moyenne des r6sultats, aux m6mes 6poques, fournit une estimation de E(Z~,) ou E(Z)r

- - 222 - -

t. 2 2 , n ~ 7-8, 1967]

La convergence de E(Z~,), constat& expdrimenta- lement, entra~ne, d'aprJs les th&rkmes 3 et 6, les eonvergences presque s~tre et en moyenne quadratique.

2 o) Rapidit* de la convergence.

En ver tu des thdor&nes 5 et 6, la rapidit6 de cette convergence d6pend de l 'expression (47) t raduisant la rapidit6 de la tendance asymptot ique du proces- SUS.

Si nous savons que le processus tend asymptot i - quement vers une chMne homogbne de Marko% nous pouvons conclure h la convergence en 1IT ou I [N . D'apr~s une remarque prdc6dente, il e n e s t ainsi pour les chalnes homog~nes de Marker d'ordre s, off s est un entier quelconque mais fini.

Si nous avons une idge du compor tement de la fonctlon de co~,ariance centrde, pour des @oques t et t' (ou n e t n') 61oign6es, le thdor~me 6 nous a permis de montrer clue nous avions encore une conver- genre en l I T ou I [ N si cette fonction eonvergeait

1 1 plus rite que ~ - ~ ou ] n - n' l' suivant le cas.

(55) nous permet d'6crire, pour T grand :

I E(Z~)Z ~ )hiT' (too)

I E ( Z ~ ) 2 ~ X21N, off ?,~ et X2 sent des constantes diff6rentes et ind6- pendantes de T ou de N, suivant le cas.

Si la fonction de covariance centr6e converge moins r i t e que l [ ! t - t' 1 ou t / I n - n'l, et si nous nous sommes assur6s de l 'existence de la convergence (el. paragraphe t~ nous 6crirons :

E(Z~) ~ ~-, X~.F(T)/7', ( i o i ) . , ~

E(ZN) ~ Z~.F(N)/N.

F(T) et F(N) sont des fonctions positives non- d6croissantes et telles que :

F(T) Lira ~ --~- 0, T.--->oo

�9 F ( N )

Dans le cas de la convergence en l i l t - - t ' I ou l [ I n - n'[, nous averts :

F ( r ) -~ log~ T et F(N)=__log~iV.

Pour les proeessus homoggnes de Markov, nous averts 6crit les 6quations (7t), (72) d 'une part , et (79), (81) d 'autre part , pe rme t t an t de caleuler respeet ivement Xl et X~. En fair, pour les syst~mes complexes , e t a fortlori pour les proeessus plus g6n6- raux, nous ne savons pus ealculer X~ et X2. Nous verrons au ehapitre suivant, en d6erivant un exemple, comment les sorties r6guli~rement espae6es de la simulation permet ten t d'&aluer a posteriori ces constantes.

Si nous n 'avons aucune information th6orique suffisante pour d6terminer F(T) ou F(N), il est toujours possible, nmyennant un cofit dlevd, d'effectuer plusieurs passages de la simulation, et suffisam-

L ' E R G O D I S M E E T LA C O N V E R G E N C E DES SIM'ULA.TIONS 13]18

ment longtemps, pour appr6cier la convergence de E(Z~,), par exemple, laquelle converge de la m~me fa~on que E(Z~) ~, d'apr~s le th6or~me 6. Nous pouvons avoir ainsi une id6e de la fonction F(T), en ru e de l '6tablissement de la formule (101).

Finalement, nous eonnaissons E(Z~,) 2. I1 nous reste h d6terminer l ' intervalle de eonfiance relatif de l 'estimation qui d6finit la pr6cision de l 'observation.

3 o D~termination de l'intervalle de conflance.

D'apr~s les thdor~mes 7 et 8, si nous savons clue le processus tend asymptotic[uement vers un processus homogkne de Marker, ou tou t au moins vers un processus homoggne v-markovien, pour v 6gal h quelques unit6s, nous pouvons conclure h la convergence, ou h une convergence approximat ive dans le dernier cas, vers la loi normale.

Les formules (7), (8) et surtout (9) peuvent s'appliquer. Comme nous sommes en m~me temps dans le cas de la convergence en t IT (m~me pour les proeessus v-markoviens), les formules (100) nous donnent pour l ' intervalle de confiance relatif :

AA . / N AA (102) ~ - ~ 2 N A T ou ~ - ~ 2 T N '

en posant :

(t02bis) �9 X i ~ . A .

Notons que le nombre de fois B, que l '6v6nement consid6r6 a 6t6 observ6, est 6gal (en moyenne) h A T ou A N suivant le cas. La lettre B est souvent utilis6e duns les simulations de trafic t616phonique, od l 'on recueille des nombres d'appels (( bloqugs )). De m~me, rempla~ons plut6t A par la let tre 1 ), pour repr6senter la probabilit6 de product ion de l%v6nement consid@& (102) devient, en confondant le eas permanent et le eas discret :

- ~ - ~ 2

Duns les autres types de processus nous n 'avons pas la convergence vers la loi normale, et nous ne eonnaissons g6n6ralement pus la loi r6gissant les dispersions. Nous sommes oblig6s d'util iser Fin& galit6 de Bienaym6 qui nous a conduits h (2), et h un intervalle de confianee maximale de 4,5 ~. Nous nous bornerons h prendre un intervalle de eonfiance de 4e, sufllsant en g6n6ral. R6sumons tout, dans le th6or~me suivant.

Thdorgme 9 i) Pour un processus tendant asymptotiquement

~,ers un processus homog~ne markov ien ou v-markovien, l'intervolle relatif de confiance, pour un coefficient de confinnce de 95 %, a pour r :

(104) �9 A P I P ~ 2 V~X'I B,

ou B e s t le nombre observd de cas de production de l' &dnement consid&g.

- - 223 - -

I I18

2) Pour l e s a u t r e s p r o c e s s u s , ou nous a?ons gdngralement une convergence en l i T ou l I N , l'intervalle relatif de confiance peut ~tre prls dgal h :

(105) t A P I P "~ 4V~- ]B .

3) Dans le eas de syst~mes h c( mdmolre tr~s longue )), ou la fonction de covariance centrde ne converge pas plus rite que l/In - - n'l o~ t i i t - - t'l l' intervalle relatlf de con[lance vaut :

( 06) - -

sulvant le cas, F(T) ou F(N) pouvant dtre ddtermlnd par la thdorie ou l'obser?ation de la convergence de E(Z;) ou E(Z~).

Remarques a) Nous avons vu, dans le cas d 'observations

ind@endantes, que la formule (t04) s 'appliquait avec 9,' = t - - P ~ I : cf. (t0) et ( t t ) .

b) Dans le cas de syst~mes h ((m6moiro tr6s eourte ~), off la fonction de covariance centr6e d6crolt tr~s r i te (donc pour certaines chalnes de Markov), la relation (48) nous permet d'6crire, compte tenu de (t02 bis) :

( o7)

2 (o) A _

2 ~. Var Y(t),

ou 2 Var Y,

si la chalne est stationnaire d'ordre deux. Si les caract~ristiques du processus varient

lentement dans le temps, le syst~me 6tant toujours h ~( mdmoire tr~s courte ~), nous trouvons :

(108) ).' ~ ~-~ Var Y(t) dt,

2 ou A N ~ Var Yn.

c) La m~thode que nous indiquerons au chapitre suivant, pour 6valuer exp6rimentalement la constante k', ne s 'appliquera que dans le cas de la sta- tionnarit6, ou tout au moins de chalnes homog~nes dans le temps (pouvant comprendre des processus oscillant de fa0on p6riodique).

Si les caractdristiques du processus varient, au contraire, lentement dans le temps, le syst~mo n '6tant plus forc6ment h (( m6moire courte )), il est possible de d~terminer exp6rimentalement lo facteur X',

l 'aide de l'observation de diverses moyennes cumulges. Nous en avons fait la th6orie dans [7, ehapitre III, paragraphes t2 h t4]. Cette th6orie, t rop longue exposer ici, nous a conduits aux formules pratiques (III, t2, 17), (III , t2, t9) et sur tout (III, t2, 33).

d) Dans le cas 3 o) du th6or~me 9, rappelons clue si la fonction de covariance centr6e converge comme t i l t - - t'l ou t I]n - - n'], nous avons :

(t09) F(T)---- log~ T ou F ( N ) = log~ N.

Nous avons termin6 avec les r~gles pratiques qui

P. LE G A L L [ANNALrr$ DIES TI~LI~COMMUNICATIONS

permet tent de r6gler la dur6e d 'une simulation. Nous allons maintenant d6crire un exemple concret auquel nous sommes habitu6s : celui de la simulation de trafic dans un r6seau t61dphonique automatique, ou semi-automatique.

V. S I M U L A T I O N D ' U N RI~.SEAU TI~LI~PHONIQUE.

On d~finit la (( qualit~ d'~eoulement de trafic )~ d 'un r~seau t61dphonique par la probabilit6 de blocage entre un abonn6 demandeur et un abonn6 demand6. Dans le cas de l 'exploitation automatique, le syst~me fonctionne h (( appels perdus )). Autrement dit, un appel qui ne peut obtenir sa communication est refus6. On n'envisage pas le ph6nom~ne des appels r~p~t6s, car il est g~n6ralement suppos6 n6gligeable pour des probabilit6s de blocage inf~- rieures h 0,07 environ. Pour les r~seaux interurbains, on envisage des probabilit6s de blocage net tement inf6rieures h cette valeur, et m~me pour les r6seaux internes aux centraux, on envisage des valeurs comprises entre 10 -2 et 10 - a h c( l 'heure charg6e )). Elles sont donc tr~s faibles devant 1. Durant cette (( heure charg6e )), on suppose prat iquement la stationnarit4, de sorte que, en ver tu du th6or~me de Doob-Birkhov, la probabilit6 de blocage est ~gale h la proportion d'appels perdus, appel6e encore (r taux de perte )~, pour le (r courant de trafic )) consi- d~r~ entre deux nceuds du r~seau, g~n@alement constitu6s par deux abonn6s.

Nous avons d6jh d~crit dans [10] les m6thodes utilis~es pour cette cat6gorie de simulation. Nous n 'y reviendrons pas. Souvent, ]es r6seaux sont suffisamment complexes pour que les math6matiques soient insufflsantes pour ~valuer les (( taux de perte )). Nous rappellerons seulement les deux hypotheses habituellement envisag~es : arriv6es poissonniennes et dur6es des communications ob6issant h la loi exponentielle (dur6es comprenant le temps d'6ta- blissement des communications). Nous admettons donc que le syst~me 6volue h la Markov.

Nous ne nous int6ressons qu ' aux instants de production d'appels. Pour un (c type )) d'appels, correspondant par exemple h un ensemble d'abonn6s ayant une mgme probabilit6 de blocage, nous notons le hombre total N (r d'appels lances )) et ]e nombre total B d'appels bloqu6s et refuses. Le t aux de perte estim6 est donc P ~ B I N et, pour un coefficient de confiance de 95 %, la formule (I04) donne l'inter- vaUe relatif de confiance de l 'estimation de P :

(t10) A P I P ~ 2 V ' ~ .

Pour d6terminer exp@imentalement la constante k', qui d6pend du r6seau 6tudi6, nous proc6dons de la facon suivante, les observations 6tant suppos6es commencer seulement quand la stationnarit6 est prat iquement atteinte.

Tous les N 1 appels lanc6s (N1 = 10 000 par exemple), nous notons le hombre Bt d'appels refus6s

224

t . 2 2 , n ~ 7 - 8 , 1967] L E R G O D I S M E E T L A C O N V E R G E N C E D E S S I M U L A T I O N S

dans cette tranche. Nous estimons la variance des fluctuations de l 'estimateur Z~, par la formule :

E(Z~-,) n - i ~-1 - - \ N 1 / n ,

oh nest le nombre de tranches de N 1 appels lanc6s et N le nombre total d'appels lancds durant la station- narit6. Nous avons :

N = nN~,

B = ~ B~. ~ 1

La formule (110) correspond au cas off :

E(Z~,) ~' ~, XIN~,

~, N d'ofl l 'estimation de X' -- -- --

p X B :

(112) t k ' - - n I [ ~ (Bi)2] B

Le calculateur 61ectronique peut sortir ce r6sultat h la fin de la simulation. Pour avoir une bonne estimation, il est n6cessaire que le nombre de tranches soit suffisamment 61ev6 : n >~ 20 par exemple. Et il est important que les tranches soient suftisamment longues pour que les B~ ne fluctuent pas trop et aussi pour que la d6pendance qui existe entre la fin d 'une tranche et le d6but de la suivante ne perturbe qu'une faible proportion des appels refus6s par tranche. Nous pouvons, dans ces conditions, consid@er chaque tranche comme une simulation diff6rente. I1 ne faut pas omettre de remarquer qu'une bonne estimation du facteur X' entralne de prolonger la simulation, l 'estimation de P-----BIN 6tant plus ais6e. Cette estimation de X' ne se fera prat iquement que pour la premiere simulation de route une s6rie de m~mes caract6ristiques.

Dans la pratique, nous avons une id6e du facteur X'. Consid6rons tout d'abord, le cas simple d 'un seul faisceau.

Le cas de l 'estimation de la probabilit6 d'encom- brement h u n instant quelconque peut se d6duire des 6quations (71) et (72). Nous avons donn6 la formule explicite dans (7), formule (III, 10, 9).

En fait, ici nous nous int6ressons plutbt aux instants de production d'appel. Pour nous faire une idge, nous allons pr6senter la th6orie des estimations dans ce cas, th6orie qui ne semble avoir jamais 6t6 exposge encore sous sa forme exacte, avec les formules explicites qui vont suivre.

A) Cas d 'un faisceau de circuits avec appels perdus.

Nous avons L circuits, le processus des arriv6es 6rant r6g6n6ratif et la fonction de r6partition des intervalles d'arriv6es 6rant F(t). Nous rappelons que les du%es de communication suivent la loi exponentielle, de dur6e moyenne : l 'unit6 de temps. D6si- gnons par q0(z) la fonction caract6ristique :

(113) ~(z)---- F ~~ e~.dF(t), J o

15/t8

et posons :

V 0~(0) t,

(li4) ] ~(--i) ( i~ - i , 2, , L - - l ) . _ ~ ( i ) - i - ~ ( - i) . . . .

Ce mod~le permet de trailer le eas habituel des arriv6es poissonniennes (modUle d'Erlang) correspondant ~ :

(115) q0(z) = T I ( T - - z),

off T e s t le trafic offert ~valu6 en erlangs. ]l permet de traiter aussi le cas du trafic de d~bor-

dement issu d 'un faisceau primaire de L o circuits, recevant un trafic d'Erlang. Nous avons alors, d'apr~s les t ravaux de C. Palm, Cf. [7, formule III, 7, t5] :

t , x x--~ I

(116) ~(z) = ~.+1 1 '

CL,+I ~=o ( i - - z) k - 0 ~0

avec la convention :

),,--1 i zci~0 a o ( i + z ) - - t ' pour k = 0 .

La fonction ~o est ici relative au faisceau primaire. Du fait de la loi exponentielle pour les dur6es de

communication, les variables al6atoires donnant le nombre de communications en cours aux instants de production d'appel forment une chalne de Markov homog~ne et discrete, dont les probabilit6s de passage [Cf. (73)] ont pour expression [7, formules (III, 5, 1) et (IiI, 5, 2)3:

(tiT)

0 0

pi~ = ~+1 �9 e-r -- e-t)(~+ 1) - j dF(t),

s i j ~ < i + t,

s i j > i + 1, Pii ~ O,

p L j = PL----1.Y,

Les 6quations (79) nous donnent finalement les param6tres pt, avec Pc = O. Retranchons les deux derni~res 6quations (79), en tenant compte de la tier- nitre relation (1i7). Nous trouvons :

(tt8) ?~ = Pz-1 + ( y L - Yz---1).

Muhiplions les deux membres des 6quations (79), correspondant h i = 0, i , . . . , L - - 1, par la quan- tit6 Ci~+l.( - 1) ~+1. Sommons membre h membre toutes ces 6quations, pour i = 0, 1, . . . , v - - l et remarquons la relation :

Z 0,+~ ( - t)~+1.p~^= c ~ ( - t))` • i = O

Li - ),_1

c~, ( .... i) x / o o e - ~ ,tF(t).

- - 225 - -

i 6 / i 8

Ceci peut s'6crire finalement, compte tenu de (113) :

~--1 (1t9) Z C~ 4"I ( - - t ) i§ p i X = C ~ ( - - l ) k qO(--~J).

Posons :

~ = ~ c}. c- 1)~ ~, (120)

c, = Z c,~. ( - 1)~. (y~- A),

pour v = 1, . . . , L - - t , avec :

a o = 0 , C o = g o - - A -

L e s ~quations (79), retranch6es deux h deux, donnent finalement les 6quations suivantes pour v = 0 , t , . . . , L - - 2 :

(121) ~ [ - - ( v + 1)3 a~+t= [~(-- v) -- t] a~+ c~.

On d6duit ainsi, de proche en proche, tous les a~. Consid6rons, maintenant , l 'expression :

v ~ O v--0 X--0

= Z ~ ( - 1 ) ~ Z q ( - t ) ~ c ~ . A-O

Or :

( - 1)~ ,.Z, q ( - 1), c~ =

�9 / ~; ,c7=_I(_~)~_ ~ = o , si x < i ~-X = t , si X = i.

D'ofl, eompte tenu de la relation a 0 = 0 :

i (t22) ~, = Z Cl (-- t)~.a~,

V--1

pour i = l , 2, . . . , L - - I. (:[:[8) et (122) nous donnent donc tes valeurs des

pi-

Cas du blocage d'appel.

Nous avons :

Yo . . . . . YL--1 =" O, yL "= l ,

Compte tenu des expressions (114), les tions (121) nous donnent :

a o = O, P 1

(t23) a~ = (-- I ~. ) ~(-- v) ~(0) . . . ~ ( ~ - i)"

Puis, nous d~duiso.s de (122) et (118) :

(124)

En outre, les expressions des ~

A -= ~rL = P .

6qua-

pi = P ~ C~ 1 ,

(pour i = t, 2, . . . , L - - 1),

PL = pL--1 + t.

sont donn~es par

P. LE GALL [ANNALES DES T~LI~COMrCIUNICATIONS

les formules (III , 5, 8) dans [7], lesquelles peuvent s'6crire :

f L t

l ~ i = P ' 7 , C ~ . - X

(t25) ~ " L-~(0)" '" ~(~)

Z Q ( - 1)~-~ [~(o) . . . ~(x)], e t :

Les relations (81) et (102 bis) nous donnent finalement pour la eonstante X' in tervenant dans la formule ( t t0) :

L--1 (t27) X ' = ( I - - P ) ( I + 2p~--1)--2 • ~p~.

Les ealculs n6cessitent d 'e t re trait6s sur ealcula- teur 61eetronique.

Cas du traffc d'Erlang.

Les arriv6es sont poissonniennes. Ce cas plus simple a d6j~ 616 trait6, par des proc6d6s diff6rents clans [ i l l puis dans [12].

D'apr~s (It5), nous d6duisons :

(128) ~(i) = T l i .

(126) devient, pour i = l , 2, . . . , L - - i :

' [ ! ~ - l ) ! ~!] (129) 9~ = P v-iE CI~ [ ~T-Y + ~~j"

Quant aux expressions (125), elles se simplifient puisque nous avons main tenant les formules d 'Erlang, bien connues :

TI, IL ! (130) ~ r t + T [ i [ + . . . + TX, IL!

On t rouve que le facteur k' est un peu plus 61ev6 que dans le eas de l 'observat ion des encombrements h des instants quelconques, sauf toutefois pour des t a u x d 'occupat ion de circuits voisins de la satu- ration.

X' varie, en g6n6ral, entre 0,2 et 2.

B . C a s d e s r f i s e a u x .

I1 est pra t iquement impossible de calculer la constante X', dans le cas de r6seaux complexes. Nous avons montr6, plus haut, comment la d6duire des r6sultats de la simulation.

La valeur de cette constante est normalement plus 61ev6e que dans le cas d 'un faisceau isol6. Tout d 'abord, l 'appel emprunte plusieurs faisceaux successifs, ce qui augmente souvent la dispersion des r6sultats. Ensuite, la d6pendance al6atoire, qui s '6tablit entre t o u s l e s faisceaux, entralne un certain groupement des appels devant un faisceau d6termin6, d 'oh une nouvelle cause d 'augmenta t ion de la dispersion des r6suhats.

De routes les exp6riences que nous avons d6j~

- - 2 2 6 - -

t. 22, n as 7-8, 1967] L'ERGODISME ET LA CONVERGENCE DES SIMULATIONS

effectu6es, lesquelles sent au hombre de plusieurs centaines, nous avons toujours trouv6 X' compris entre I e t i5, dans le cas d 'exploitation normale.

Pour r6gler la dur6e d'une simulation, nous pre- nons, sans information suppl6mentaire, la valeur approximat ive: ) ~ ' = 5. La formule (t10) nous donne finalement la r~gle suivante, pour d6finir la (( prdcision )) d 'une simulation de r6seau, a priori :

(131) AP

Ainsi, dans le cas de l 'exploitation normale, pour ob~enir une (( prdcision )) de 20 ~ , nous devons observer 500 appels refusds environ.

Si le blocage h observer vaut 10 -2 environ, cela signifie que nous devons (( lancer )) 50 000 appels par ((types)) d'appels h observer. Un gdn6rateur aldatoire permet d'observer tout au plus une cen- taine de types d'appels, si nous voulons rester maitre du r6glage des trafics (ce qui conduit h faire des moyennes de blocage, si nous voulons aller au- delh). Nous sommes alors conduits h lancer 5.10 e appels en tout, sans compter les d61ais ndcessaires pour at teindre la stationnarit6, d61ais non n6gli- geables dans le cas de l '6tude de grands r6seaux.

De toute fa~on; le fair d'effectuer la simulation en un seul passage est plus 6conomique que d'observer la probabilit6 de blocage h un instant donnd, en effectuant un certain nombre de simulations. En effet, ]a formule (11), qui correspond h ;~' = l , conduit h effectuer t00 simulations pour obtenir la mgme pr6- cision. Pour les grands r6seaux, nous sommes amen6s h observer au moins 20 cas d'appels refus6s avant d'obtenir la stationnarit6, ce qui conduirait "h pro- duire en tout 2 000 appels refus6s au lieu de 500 par la m6thode pr6c6dente. Et ceci, sans compter le cofit du d6marrage des simulations.

l~videmment, il n 'est pas toujours n6cessaire d 'obtenir une pr6cision de 20 ~o qui entralne des simulations fort longues. De telles observations ne se produisent g6n6ralement que dans le cas d'ana- lyses pouss6es en rue de la justification de formules math6matiques approchdes, pour ~tre utilis6es ensuite quotidiennement, sans recourir aux simulations.

Notons toutefois le danger que peut pr6senter une mauvaise pr6cision. Supposons que nous nous contentions d 'un intervalle relatif de confiance de 100 % seulement, la formule (13t) nous conduit h l 'observation de 20 appels refus6s seulement par types d'appels. Comment affirmer, dans ce cas, que la stationnarit6 a 6t6 bien at teinte ? Pour l '6tude de grands r6seaux, nous risquons ainsi d'utiliser des r6sultats qui n 'ont aucun sens.

Dans le cas de r6seaux tr~s satur6s, utilisant des plans d 'acheminement non hi6rarchis6s, l'observation est plus facile car la stationnarit6 est plus r i te atteinte et le facteur k' peut 6tre plus faible, ce qui conduit h lancer moins d'appels durant la station- narit6.

17/ts

V I . C O N C L U S I O N .

Nous avons 6tudi6 la convergence de moyennes temporelles, pour la classe des fonctions aldatoires stationnaires ou non, utilis6es dans les simulations, h savoir celles dent l 'existence ne commence qu'h une certaine 6poque, d6but des simulations. Aussi, avons-nous dfi 61iminer la th6orie classique de l 'analyse harmonique.

Nous avons vu dans quelles conditions il est possible d'obtenir une limite, et nous averts indiqu6 la condition n6cessaire pour obtenir une convergence vers la loi normale, ce qui permet de r6duire la dur6e des simulations.

Enfin, nous avons pr6sent6 (paragraphe IV, F), des r~gles pratiques permet tant de r6gler la dur6e d'une simulation effectu6e en un seul passage par observation des moyennes temporelles.

Sur un plan beaucoup plus th6orique, nous avons montr6 comment l'ergodisme dtait li6 au comportement asymptotique du processus envisag6 et surtout h sa fonction de covariance, t raduisant la d6pen- dance entre deux 6poques, c'est-h-dire la (< m6moire )) du processus. La convergence est d ' au tan t plus rapide que cette m6moire est plus courte, et il est frappant de constater que, moyennant tr~s peu de conditions supp16mentaires, les moyennes tempo- re]les tendent vers des quantit6s ou des variables al6atoires bien d6finies, n ' ayan t plus gu~re de rap- port avec le processus d'origine. Ainsi, il est possible de fabriquer du certain h partir d'616ments al6a- toires tr~s g6n6raux, n ' ayan t que de vagues relations entre eux. Ou plutbt le certain se trouve dilu6 dans quelques caract6ristiques de l'al6atoire. C'est une d6couverte importante qu'ont faite les physiciens de ce si~cle-ci, h propos notamment de la thdorie de la mdcanique ondulatoire. Et d'ailleurs, plus nous voulons analyser la nature, plus nous nous sentons incapables de l'expliquer h l'aide de lois d6terministes, qui existent pourtant, mais qui sent cachdes derriere un support mouvant, difficilement saisissable.

L'exemple du m6canisme de la raison humaine, compar6 h celui des grands calculateurs 61ectro- niques, est un exemple significatif. Lots d 'une journ6e consacr6e aux simulations (*), off les bases de cette 6rude furent pr6sent6es, on s'6ton- nait que les calculateurs 61ectroniques ne soient pas encore capables de rivaliser avec l 'homme dans une partie d'6checs. Mais, quant h nous, nous avons m~me l'impression qu'il en sera toujours ainsi, t an t que les m6thodes de programmation res- teront aussi rigides qu'elles le sent actuellement. Dans le cerveau humain, les informations sent enregistrdes en g6n6ral avec beaucoup de redondances, et ne sent pas localisdes en un point particulier. Elles ne sent d'ailleurs pas enregistrdes de fagon

(*) Journde organis6e par l 'Association Fran~aise d ' Infor- mat ique et de Recherche Op6rationncllc (A.F.I.R.O.), le 10 novembre 1966.

227

a S / i S ~. LE

exacte, l 'homme eonservant seulement ce qui l 'a frapp6 le plus. Inconsciemment, il analyse ce qui lui paralt le plus int6ressant h conserver, et se d6barrasse du reste. I1 per~oit la nature h sa fagon, mais l 'ensemble des perceptions enregistr6es, se recouvrant abondamment , it en fait une synth~se correspondant h une r6alit6, avee une note person- nelle. L'exp6rience consistant h 6tablir un portrait- robot est assez amusante et tr~s significative dans cet ordre d'id6es. Chacun d6crit h sa fagon ce qu'il a retenu de la personne h d6erire. Les informations sont mgme parfois tr~s divergentes. Mais leur moyenne tend souvent vers une description tr~s pr6eise.

II est bien connu que les hommes dou6s d'une prodigieuse capacit6 de calcul mental ne font en g6n6ral pas de calcul, et n 'ont souvent pas les connaissances mathdmatiques n6cessaires, mais qu'ils op~rent par encadrements successifs de nombreuses informations en r6serve dans leur m6moire, encadrements convergeant r i te vers le r6sultat d6sir6.

C'est par un tel m6canisme de comparaisons sue- cessives d' informations raises en m6moire, mais ill- tr6es convenablement et redondantes d 'une certaine fagon, que l 'homme semble raisonner. S'il filtre peu, doric s'il n 'a pas le pouvoir d 'analyser rapidement, il ne peut agir que par raisonnements ddductifs : c'est l 'esprit de g6om6trie. Si au contraire il filtre beaucoup et mgme de diverses fagons, il a done un grand pouvoir d'analyse, et poss~de beaucoup d'informations redondantes. Si, en outre, il a une grande capacit6 de comparaison sur toutes ces informations nombreuses et disparates, son raisonne- merit subconscient, par approximations successives, peut converger vers cette intuition qui fait la sup6- riorit6 de l 'homme sur la machine et sur t o u s l e s autres 6tres vivants : c'est l 'esprit de finesse. Ce m6canisme de convergence, plus ou moins lent, entralne que la f6condit6 et la clart6 sent deux qua- lit6s inddpendantes.

On peut gtre f6cond et intuitif sans 6tre dou6 pour les raisonnements d6ductifs permet tant d'exposer clairement des id6es. Par centre, il est bien connu que la clart6 n 'entralne nullement la f6condit6 et l ' intuition.

En tout cas, cette diff6rence fondamentale entre le comportement de l'esprit humain et celui des grands calculateurs 61ectroniques actuels, explique pourquoi on ne peut, actuellement, simuler l 'homme que par l 'homme lui-mgme.

I1 est d'ailleurs int6ressant de constater que, dans de nombreux pays, les m6thodes cart6siennes de raisonnement n 'on t gu~re d'audience, l 'homme ayan t tendance h se tier davantage h son intuition.

G A L L [ANNALES DES TI~L]~COMMUNICATIONS

Les premiers physiciens, qui commenc~rent h devi- ner l'ergodisme, eurent d'ailleurs beaucoup de real h en trouver une formulation pr6cise, tellement ils s'61oignaient ainsi des r~gles cart6siennes tradition- nelles. I1 6tait difficile de comprendre que les lois relatives h t '6tat macroscopique du syst~me (gazeux par exemple), 6talent sans lien apparent avee celles relatives au syst~me h l '6tat microscopique.

Manuscrit re~u le i2 dgcembre i966.

RI~Ft~RENCES BIBLIOGRAPHIQUES

[l] GAFAaIAN (A. V.), A~rCKER (C. J.). Mean value estimation from digital computer simulation. (Estimation de la valeur probable par simulation sur calculateur num6rique.).Operations 11esearch. U.S.A. (janv. 1966), 14, n o 1, pp. 25-44.

[2] BLANc-LAPIERRE (A.), BRARD (R.). La loi forte des grands nombres pour les fonetions al6atoires stationnaires continues. C. 1l. Acad. Sci., Fr. (1945), 220, p. i34.

[3] Lo~.vE (M.). Analyse harmonique g4n6rale d'une fonction al6atoire. C. 11. Acad. Sci., Fr. (1945), 220, p. 380.

[4] BLAr~c-LAP~ERRE (A.), FORTET (R.). Th6orie des fonctions al6atoires. Masson, Paris (i953), 693 p., nombr, fig., bibl. (nombr. rdf.).

[5] Door (J. L.). Stochastic processes. (Processus al6atoires.) J. Wiley, New-York (1953), 654 p., bibl. (159 r6f.).

[6] FORTET (R.). Estimations et tests d'hypoth~ses concernant lc trafic t61~phonique. 2 e congr~s International de T616trafic, La Haye, 1958. P.T.T.-Bedrijf, Nederl. (mars t960), 9, n ~ 4, pp. 18i-182.

[7] Lp. GALL (P.): Les syst~mes avec ou sans attente et les processus stochastiques. Dunod, Paris (1962), 482 p,, nombr, fig., bibl. (nombr. r6f.).

[8] FaECH~T (M.). M6thode des fonctions arbitraires. Th6oric des 6v~nements en chalne dans le cas (~'un nombre fini d'4tats possibles. Gauthler- Villars, Paris (1938), 315 p., bibl. (nombr. r~f.).

[9] M1sEs (R. Vor~). Wahrscheinlichkeitsrechnung und ihre Anwendung in der Statistik und theoretis- chen Physik. (Calcul des probabilit6s et son application h la statistique et h la physique th6orique.) Deuticke, Wien (1931).

[10] L~ GALL (P.). Les m6thodes de simulations al6a- toires et leurs applications h l'~tude des pro- bl6mes de t~l~trafic. Commut. et Electron. Fr. (avril 1963), nO 4, pp. 44-58, 3 fig., 3 tabl., bibl. (13 r6f.).

f i l l KOSTEN (L.), MXNNINr (J. R.), GARwoon (F.). On the accuracy of measurements of probabilities of loss in telephone systems. (Sur la pr6eision des mesures de probabilit6s de pertes dans les syst~mes t61~phoniques.) J. 11. Statist. Soc. Ser. B, G.B., (1949), 11, pp. 54-67.

[12] DESCLOUX (A.). On the accuracy of loss estimates. (Sur la pr6cision des estimations des pertes.) Bell :Syst. tech. J., U.S.A. (juil.-aofit 1965), 44, nO 6, pp. it39-i164, 13 fig., bibl. (8 r6f.).

Le directeur de Ia publication : A. DUTILLI~UL.

Imprimerie TAFFIr~-LEFoRT, b, Lille (France). - - Published in France. D6pSt 16gal, 6diteur : 208 (t er trim. 1968). Commission paritaire, n ~ 29 685.

228

Documents

L’ergodisme et la convergence des simulations de phénomènes aléatoires