Matemàtiques i Internet : 101 anys de teoria de cues

Butlletí de la Societat Catalana de Matemàtiques Vol. 25, núm. 2, 2010. Pàg. 109–144. DOI: 10.2436/20.2002.01.29 Matemàtiques i Internet: 101 anys de teoria de cues* Rosario Delgado La red mundial de Internet nos permite a hombres y mujeres llegar a los rincones más desconocidos y comunicarnos. Es como llegar con la luz del sol a los lugares donde todo parece noche. Hebe de Bonafini, presidenta de la Asociación Madres de Plaza de Mayo Imagine a world in which every single person on the planet has free access to the sum of all human knowledge. Jimmy Wales, fundador de Wikipedia I think there is a world market for maybe five computers. Atribuïda a Thomas J. Watson, fundador i president d’IBM, el 1943 Resum Sense precedents en el seu creixement, sense paral.lelismes en la seva heterogeneïtat i imprevisible o, fins i tot, caòtica en el seu comportament, «Internet és una revolució en si mateixa».1En aquest article farem un cop d’ull a com i per què el trànsit d’informació a través d’Internet difereix en aspectes fonamentals del trànsit de veu a través de les xarxes de comunicació convencionals (telefonia fixa) i presentarem un model matemàtic que ha suposat una fita en l’enginyeria del teletrànsit. *Aquest article ha guanyat el Premi Albert Dou 2010 de la Societat Catalana de Matemàtiques. Aquest premi distingeix els treballs «que contribueixin a fer visible la importància de la matemàtica en el nostre món, a transmetre el coneixement matemàtic a un públic més ampli que els mateixos especialistes, i a promoure tot el que pugui ajudar a l’extensió del prestigi de la matemàtica a la nostra societat». 1 En paraules d’Anthony-Michael Rutkowski, nomenat director executiu de la Internet Society l’any 1994, després d’haver contribuït a la seva creació el 1991 i haver-ne estat vicepresident durant dos anys. Actualment està considerat una de les veus més importants sobre el desenvolupament present i futur d’Internet. La Internet Society té com a objectiu promoure les activitats i la coordinació necessàries per al creixement, desenvolupament i expansió d’Internet a tot el món. 110 Rosario Delgado Paraules clau: Internet, teletrànsit, fractal, teoria de cues, procés de Poisson, autosimilitud, memòria llarga, cues pesades, moviment brownià fraccionari. Classificació MSC2010: 60-03 (01A60, 01A65, 01A67, 01A70), 60F05, 60G07, 60G15, 60G18, 60G22, 60J65, 60K25, 90B15. 1 Introducció Ens podríem preguntar qui i quan va dir això: «It will be possible for a business man in New York to dictate instructions, and have them instantly appear in type at his office in London or elsewhere. He will be able to call up, from his desk, and talk to any telephone subscriber on the globe... An inexpensive instrument, not bigger than a watch, will enable its bearer to hear anywhere, on sea or land, music or song, the speech of a political leader, the address of an eminent man of science, or the sermon of an eloquent clergyman, delivered in some other place, however distant. In the same manner any picture, character, drawing, or pint can be transferred from one to another place.»2 Aquestes paraules a tots ens fan pensar en Internet; per això resulta sorprenent descobrir que les va dir el físic, matemàtic i enginyer elèctric Nikola Tesla (1856–1943) l’any 1908, ara fa més d’un segle. I és que Internet és la manifestació d’un gran nombre de desenvolupaments tecnològics i el vòrtex al voltant del qual s’està produint una onada de canvis i millores, no només en infraestructures, sinó també en aplicacions, innovacions i serveis. Internet lidera el camí cap a la societat de la informació del segle xxi. Ha penetrat les nostres institucions i ha canviat en gran mesura la nostra conducta i les nostres actituds. Més de mil milions de persones usen Internet avui dia. La generació més jove no pot concebre un món en què no puguin compartir les seves fotografies, parlar amb els amics, mirar vídeos o anar a comprar, tot des del seu ordinador, sense moure’s. Mai no podrem fer marxa enrere per tornar al món tal com era abans de l’arribada d’Internet. Ara que ens estem submergint a velocitat vertiginosa en aquest univers de persones, dispositius, aplicacions i serveis sempre interconnectats, sembla interessant fer un cop d’ull al passat per entendre algunes de les raons i conèixer alguns dels pioners que van ajudar que sobrevinguessin aquestes meravelles. Internet és un nou món. Un món on les exigències de l’enginyeria demanen noves solucions matemàtiques, nous models. En concret, en aquest 2«Serà possible que un home de negocis dicti instruccions a Nova York, i que apareguin escrites instantàniament a l’oficina de Londres o a qualsevol altre lloc. Podrà trucar des del seu despatx i parlar amb qualsevol altre telèfon abonat del món... Un instrument de baix cost, no més gran que un rellotge, permetrà al seu portador escoltar des de qualsevol lloc, dins el mar o a terra, música o cançons, el discurs d’un líder polític, la conferència d’un eminent home de ciència o el sermó d’un capellà eloqüent, fet en un altre lloc, a qualsevol distància. De la mateixa manera, qualsevol imatge, caràcter, dibuix o pintura pot ser transferida d’un lloc a un altre.» Matemàtiques i Internet 111 article volem explorar en quin sentit Internet difereix de manera fonamental de les xarxes de comunicació de veu tradicionals. Des del seu origen, les telecomunicacions van provocar el naixement i desenvolupament d’una teoria matemàtica, coneguda com teoria del teletrànsit (teletraffic theory, en anglès) en la seva vessant més propera a les telecomunicacions, o teoria de cues (queueing theory) en general. Veurem com va sorgir aquesta teoria de la mà del naixement de la telefonia i com va anar evolucionant, i acabarem amb la introducció d’un model matemàtic recent que es fa servir per a modelar el trànsit d’informació a través d’Internet i que va suposar la superació d’un repte en la teoria del teletrànsit. El naixement de la teoria del teletrànsit «Although several points within the field of Telephony give rise to problems, the solution of which belongs under the theory of probabilities, the latter has not been utilized much in this domain, so far as can be seen. In this respect the Telephone Company of Copenhagen constitutes an exception as its managing director, Mr. F. Johannsen, through several years has applied the methods of the theory of probabilities to the solution of various problems of practical importance; also, he has incited others to work on investigations of similar character. As it is my belief that some point or other from this work may be of interest, and as a special knowledge of telephonic problems is not at all necessary for the understanding thereof, I shall give an account of it below.»3 Aquesta és la introducció de l’article que el matemàtic danès Agner Krarup Erlang (1878–1929) va publicar l’any 1909 i que és considerat el punt de partida de la teoria de cues.4Per tant, l’any 2010 celebrem el 101 aniversari d’aquesta teoria. La teoria de cues és un camp de la matemàtica aplicada relativament independent, que està a cavall de la teoria de la probabilitat i de la investigació operativa i que s’ocupa de les necessitats pràctiques de l’anàlisi de sistemes que proporcionen cert servei als clients i en els quals es poden produir endarreriments. La introducció de l’article d’Erlang no pot ser més clara en relacionar la seva recerca amb la resolució, mitjançant l’aplicació de mètodes probabilístics, de problemes d’aquesta índole apareguts en el camp de la telefonia. 3«Encara que diversos punts en el camp de la telefonia donen lloc a problemes, la solució dels quals correspon a la teoria de la probabilitat, aquesta no ha estat gaire utilitzada en aquest àmbit, fins a on es pot veure. En aquest sentit, la Telephone Company de Copenhaguen constitueix una excepció, i el seu director general, el senyor F. Johannsen, al llarg de diversos anys, ha aplicat els mètodes de la teoria de la probabilitat a la resolució de diversos problemes d’importància pràctica; també ha incitat d’altres a treballar en investigacions de caràcter similar. Com que crec que alguns punts d’aquest treball poden ser d’interès, i com que no és en absolut necessari tenir un especial coneixement dels problemes telefònics per a la seva comprensió, passo a explicar-los a continuació.» 4L’article es titula «The theory of probabilities and telephone conversations», publicat originàriament en danès l’any 1909 a Nyt Tidsskrift for Matematik, B, v. 20, p. 33. La seva traducció a l’anglès es pot trobar a [1], juntament amb altres treballs i una biografia molt documentada de l’autor. 112 Rosario Delgado Figura 1:Agner Krarup Erlang (1878–1929). En aquest treball Erlang estableix que el nombre de trucades que arriben a una centraleta telefònica manual durant un interval de temps determinat segueix una llei de Poisson, i mostra com a partir d’aquest fet es troba l’expressió per calcular el temps d’espera de les trucades fent cua per ser ateses si totes les trucades tenen la mateixa longitud fixada. El que fa realment remarcable aquest article és el fet que reconeix clarament el problema de la congestió dels sistemes telefònics com a fenomen estocàstic que pot (ha de) ser analitzat fent servir raonaments probabilístics. Figura 2:Antiga centraleta telefònica manual, 1927. Erlang mateix va analitzar situacions més complicades en articles posteriors: en el de l’any 1917,5considerat el més important dels que va publicar, apareixen les seves famoses fórmules Erlang B iErlang C. Aquesta darrera dóna la 5«Solution of some problems in the Theory of Probabilities of significance in automatic telephone exchanges», publicat originàriament en danès a Elektroteknikeren, vol. 13 (1917), p. 5. La seva traducció a l’anglès també es pot trobar a [1]. Matemàtiques i Internet 113 probabilitat que una trucada que arriba a una centraleta telefònica manual amb un cert nombre d’operadors (hauríem de dir «operadores»?) i sistema de trucada en espera hagi d’esperar i formi una «cua». La fórmula Erlang B dóna la probabilitat que, si la centraleta no disposa del sistema de trucada en espera, es produeixi una pèrdua, és a dir, arribi una trucada que trobi tots els operadors ocupats. Els resultats d’Erlang van ser utilitzats per altres investigadors que treballaven en allò que s’acabaria coneixent com a teoria del teletrànsit, la vessant aplicada a les telecomunicacions de la teoria de cues, principalment a diferents empreses relacionades amb la incipient indústria telefònica, com la Bell Telephone Company als Estats Units, els laboratoris de la qual donaven feina a enginyers i matemàtics que aviat van conèixer i utilitzar els treballs d’Erlang. Així, doncs, els problemes associats a l’estudi de la qualitat del servei de les xarxes analògiques telefòniques amb centraleta es troben a l’origen i desenvolupament de la teoria de cues. Però molts altres problemes apareguts a molts diversos camps científics poden ser formulats en termes d’aquesta teoria i resolts mitjançant els seus mètodes. Per citar-ne només alguns: la informàtica i les comunicacions, la biologia, l’organització industrial, el transport, la logística o l’atenció sanitària pública. I avui dia segueixen apareixent noves aplicacions d’aquesta teoria tan versàtil, que va néixer ara fa un segle. En paraules del matemàtic rus Boris Vladimirovitx Gnedenko (1912–1995), molt interessat en la interrelació entre les matemàtiques i els seus camps d’aplicació, «[. . . ] és més fàcil assenyalar les situacions en les quals la teoria de cues no pot ser utilitzada, que fer una llista de totes les àrees en què es pot aplicar». Figura 3:Persones formant una cua. El treball embrionari d’Erlang va ser continuat per diversos investigadors durant la primera meitat del segle xx, tant a Europa com als Estats Units. Entre ells, E. C. Molina, de la Bell Telephone Company, que va ser el primer de proposar, en el treball [17] de l’any 1922, la llei exponencial com a model per al temps de servei o durada de les trucades a un sistema telefònic. Tampoc no podem oblidar la contribució de Felix Pollaczek (1892–1981): l’any 1923 114 Rosario Delgado aquest jove austrofrancès es va incorporar al Servei de Correus de Berlín. Havia estudiat matemàtiques i enginyeria elèctrica abans de fer el seu doctorat en teoria de nombres a Berlín, i aquesta formació li va permetre aplicar tècniques clàssiques de les matemàtiques als problemes del teletrànsit. El seu primer treball en aquest sentit és de l’any 1930. És important remarcar que ni Erlang ni Pollaczek tenien a la seva disposició la teoria dels processos estocàstics que es desenvoluparia posteriorment, a partir del treball dels grans matemàtics russos Andrei Andreievitx Markov (1856–1922) i Andrei Nikolaievitx Kolmogorov (1903–1987). No podem deixar de mencionar la contribució del matemàtic Harld Crámer (1893–1985), que cooperava activament amb la Ericsson Company i que durant els anys previs a la Segona Guerra Mundial i, fins i tot, durant la Guerra dirigia un seminari de probabilitats i estadística a Estocolm en el qual van participar molts dels investigadors en la teoria del teletrànsit. Entre ells, Conrad «Conny» Palm (1907–1951), enginyer elèctric i estadístic suec conegut per la seva contribució a la teoria del teletrànsit, que l’any 1943 va presentar al seminari la seva tesi doctoral [18], en la qual estudiava les fluctuacions del trànsit telefònic. Al llarg de tota la seva vida Pollaczek va tractar problemes de cues sense fer servir els mètodes probabilístics. Els seus treballs resultaven de difícil lectura i, potser per aquest motiu, no van tenir la difusió i el reconeixement que es mereixien. Afortunadament, sí que van arribar a un altre gran matemàtic rus, Aleksandr Iakovlevitx Khintxin (1894–1959), que coneixia els treballs de Markov i estava en contacte amb el jove Kolmogorov. Va ser Khintxin qui va reescriure, l’any 1932, el treball sobre cues de Pollaczek de l’any 1930 en termes probabilístics més senzills. Però no va ser sinó un cop ja acabada la Segona Guerra Mundial que la teoria de cues es va convertir en un tema molt actiu d’interès per als membres de la comunitat matemàtica en general, entre ells, David George Kendall (1918–2007). La Segona Guerra Mundial i la teoria de cues Kendall era un matemàtic britànic interessat a treballar en temes astronòmics que, com tants altres, va canviar la seva línia de recerca per les exigències bèl.liques. L’any 1945 Stalin va assetjar Berlín Occidental, i Kendall va quedar fascinat pel fet que gràcies al transport aeri els alemanys van aconseguir mantenir les comunicacions i els subministraments de la ciutat assetjada. Kendall es va plantejar si el problema d’evitar o reduir la congestió del trànsit aeri podia ser abordat amb mètodes matemàtics. A les biblioteques d’Oxford, on era professor, va trobar la resposta gràcies als treballs d’Erlang, Khintxin i altres, els quals va decidir recopilar en un únic article que pogués ser presentat a les reunions de Londres de la Royal Statistical Society. Aquest article es va publicar l’any 1951 amb alguns comentaris [6], va tenir molt ressò i aconseguí arribar a molts investigadors que altrament no haurien conegut aquests treballs. Matemàtiques i Internet 115 Figura 4:Soldats russos amb la seva bandera sobre Berlín en flames. A partir de la dècada dels cinquanta hi va haver un creixement considerable de la recerca en aquests temes aplicats. Però ben aviat es va produir el fenomen de la segregació entre els enginyers que treballaven en el teletrànsit, d’una banda, i els matemàtics que treballaven en la teoria de cues, de l’altra. Aquest fet ja va quedar de manifest al Fourth International Teletraffic Congress, celebrat l’any 1964 a Londres: mentre els enginyers del teletrànsit continuaven treballant en problemes aplicats derivats del món de la telefonia, els matemàtics van anar desenvolupant la teoria de cues com una branca autònoma de la probabilitat aplicada, amb poca relació amb els seus orígens telefònics. L’era de la informàtica i les telecomunicacions Els primers ordinadors, dissenyats pel matemàtic britànic Alan Turing (1912– 1954), que treballava per als serveis d’intel.ligència del seu país durant la Segona Guerra Mundial, amb l’objectiu de descodificar els codis de la màquina alemanya de criptografia naval Enigma, van ser construïts per enginyers de la Post Office britànica. Això ens fa pensar que devia existir una certa analogia entre la tecnologia dels primers ordinadors i la de les centraletes telefòniques. I així era. A mesura que les xarxes telefòniques es feien més globals, i els ordinadors estaven cada vegada més integrats en xarxes, les dues tecnologies ràpidament van convergir fins a ser, actualment, quasi indistingibles: en cert sentit, avui dia «Internet és la gran centraleta telefònica mundial». Sembla clar que juntament amb altres àrees d’aplicació també molt importants, com l’estudi del trànsit de vehicles o la gestió de les llistes de pacients del sistema sanitari, l’anàlisi de la congestió en xarxes complexes de telecomunicacions, incloent-hi Internet, serà un dels principals components del desenvolupament de la teoria de cues al llarg del segle xxi. Però l’estudi 116 Rosario Delgado Figura 5:Alan Turing amb el Colossus, un dels primers ordinadors. del trànsit a través d’Internet ja ha plantejat, a hores d’ara, nous reptes per a aquesta teoria: els seus models clàssics no són adequats per a estudiar-lo, i ha estat necessari cercar-ne de nous. La comprensió i la modelització del trànsit d’informació a través de les xarxes de telecomunicacions, tan diferent en el seu comportament del de veu, ha estat un repte per als investigadors. A la construcció d’aquests models, s’hi ha arribat gràcies al treball coordinat de les comunitats d’enginyers en teletrànsit i de matemàtics, que han tornat a treballar conjuntament amb un objectiu comú. El present article vol explicar la història de com s’ha afrontat aquest repte, i de la seva superació. El procés de Poisson: un model clàssic La teoria del teletrànsit clàssica, que comprèn les eines matemàtiques aplicables al disseny, control i gestió de les xarxes de telefonia fixa, ha estat una de les aplicacions amb més èxit de les matemàtiques a la indústria al llarg de tota la història, ja que ha permès el desenvolupament d’una xarxa de telecomunicacions de telefonia fixa molt fiable i pràcticament universal. Quines són les característiques del trànsit de veu que han facilitat aquest èxit? El seu caràcter marcadament estàtic i una limitada variabilitat, trets distintius dels sistemes homogenis en els quals es pot parlar d’un usuari típic i d’un comportament genèric. També hi ha contribuït el fet que els models utilitzats pel trànsit de veu han resultat ser molt atractius per a la comunitat d’enginyers que els havien de fer servir, a causa del seu caràcter intuïtiu i la seva simplicitat, ja que necessiten un conjunt molt petit de paràmetres que poden ser estimats amb facilitat. Aquest caràcter estàtic ha contribuït a la creença popular en l’existència de «lleis universals» que governen les xarxes de telecomunicacions per a la Matemàtiques i Internet 117 transmissió de veu. Potser la més coneguda d’aquestes lleis és la que diu que les trucades a una centraleta telefònica arriben segons un procés de Poisson.6 Això és equivalent a dir que els temps entre arribades són variables aleatòries exponencials independents. Una altra d’aquestes lleis universals diu que els temps de servei dels clients també es distribueixen segons exponencials independents. O dit d’una altra manera, el procés de sortides del sistema, sempre que hi hagi clients, també és un procés de Poisson, que és el que havia proposat Molina l’any 1922. A partir del treball d’Erlang, el procés de Poisson s’ha fet servir com a model bàsic de la teoria del teletrànsit durant més de mig segle. Naturalment, en els seus inicis aquesta teoria es basava en estudis empírics en els quals es prenien mesures del trànsit telefònic (Erlang prenia laboriosament aquestes mesures personalment per a la Copenhagen Telephone Company, on treballava), però aviat la creença en la universalitat del procés de Poisson com a model va fer que decaigués l’interès de prendre més mesures i, en canvi, va potenciar el desenvolupament de la teoria i dels mètodes analítics basats en el procés esmentat, que són una part molt important de la teoria de cues. Però l’aplicabilitat a les noves tecnologies dels principis que sustenten aquesta teoria va començar a ser qüestionada, no fa encara ni trenta anys, a partir de l’aparició de tres nous avenços tecnològics: el fax, que va aparèixer a la dècada dels vuitanta, el telèfon mòbil de darrera generació, que permet enviar i rebre informació a més de mantenir una conversa, i, sobretot, Internet. Transmissió d’informació versus transmissió de veu Internet és una xarxa global de telecomunicacions en què els encaminadors (routers) interconnecten xarxes i subxarxes per tal de transmetre i intercanviar informació. La primera versió d’Internet porta el nom d’ARPANET, va ser construïda l’any 1968 i estava formada per quatre ordinadors (servidors o nodes), situats a diferents universitats nord-americanes. Leonard Kleinrock és un dels principals investigadors en teoria de cues en aquella època i va establir les bases que van fer possible el desenvolupament d’ARPANET; un article molt interessant sobre els aspectes històrics d’aquesta recerca i sobre el desenvolupament d’Internet escrit per ell mateix és [7]. Durant la dècada dels setanta aquesta xarxa d’ordinadors, que va ser desenvolupada com una manera de tenir en contacte persones i sistemes que treballaven en diferents projectes de ciència de la computació i d’investigació militar, no va parar de créixer. Però no va ser fins a mitjan dècada següent que 6El procés de Poisson modela bé les arribades de clients o trucades al sistema «completament a l’atzar», és a dir, aquelles que es produeixen de manera que el nombre d’arribades en intervals disjunts de temps són independents. És precisament l’article d’Erlang de l’any 1909, el primer en el qual es justifica aquest fet, com ja hem comentat, i és per això que se’l considera com el que marca el naixement de la teoria de cues. Una introducció breu i elemental a aquests models clàssics es pot trobar a [3], i a la seva bibliografia apareixen alguns manuals de referència que són ja clàssics per a iniciar-se en el seu estudi. La definició formal d’aquest procés la donarem a la secció 3. 124 Rosario Delgado El procés de Poisson i el procés de moviment brownià Hi ha moltes situacions reals en les quals podem observar fenòmens aleatoris que evolucionen en el temps. Per exemple, la quantitat de vehicles que passen per un determinat punt d’una autovia, des d’un moment considerat com l’inici del temps, que serà 0 per conveni, fins a un instant de temps t, va evolucionant com a funció de t. És un fenomen aleatori ja que aquesta funció del temps depèn de molts factors i no es pot saber a priori com serà exactament. De fet, encara que observem una determinada funció del temps, sabem que en podríem observar altres, ja que no és determinista. Malgrat que per a un temps tfixat no sabem exactament quin valor prendrà la funció, sí que pot ser que suposem un model matemàtic (aleatori) pels possibles valors que pren, que serà una variable aleatòria (una variable aleatòria és el model matemàtic per a una quantitat aleatòria). Informalment, quan parlem de llei (o llei de probabilitat) d’una variable aleatòria ens referim a la manera com aquest model matemàtic ens diu quins són els valors que pren aquesta quantitat aleatòria i amb quines probabilitats es prenen. Dues lleis han estat i són fonamentals tant des del punt de vista del desenvolupament de la teoria de la probabilitat i de l’estadística, com des d’un punt de vista aplicat: la de Poisson i la normal o gaussiana. 1 Definició Una variable aleatòria Nes diu que segueix una llei de Poisson de paràmetre λ > 0 i s’escriu N∼Pois(λ), si pren com a possibles valors N∪{0}={0,1,2, . . .}amb aquestes probabilitats: la probabilitat que la variable Nsigui igual a kés: P(N =k) =e−λλk k!on k!=k(k −1)(k −2)···1. 2 Definició Una variable aleatòria Xes diu que segueix una llei normal o gaussiana de paràmetres µ∈Riσ2>0 i s’escriu X∼N(µ, σ2), si pren com a possibles valors tots els nombres reals, i la probabilitat que prengui valors a un interval (a, b), amb −∞ ≤ a<b≤ +∞, és la integral següent: PX∈(a, b)=Zb a 1 √2π σ2e−1 2σ2(x−µ)2dx . Aquesta integral no es pot tractar analíticament i s’ha de calcular per mètodes numèrics (o fent servir taules). A més, la probabilitat que la variable Xprengui un valor concret és 0 (ja que pren valors sobre un continu). El paràmetre µés l’esperança matemàtica o valor mitjà de la llei de X, i això ho denotem per E(X) =µ(és el valor al voltant del qual es distribueixen els valors que pren la variable). Si µ=0 es diu que la variable és centrada. Una propietat molt important de l’esperança matemàtica és que és lineal, és a dir, que commuta amb la suma i amb el producte per nombres reals. El paràmetre σ2és la variància de la llei de X, una mesura de la variabilitat o dispersió dels valors que pren la variable al voltant del seu valor mitjà o esperança. Si a Matemàtiques i Internet 125 més de ser centrada, la variància de la variable és 1, es diu que la normal és estàndard. La definició de la variància de Xés: var(X) =E(X −E(X))2i es pot calcular equivalentment com var(X) =E(X2)−(E(X))2. La idea és que la variància es calcula com el valor mitjà de les desviacions entre els valors que pren la variable Xi el seu valor mitjà (al quadrat per a evitar cancel.lacions entre desviacions per sobre i per sota). La variància no commuta amb el producte per nombres reals: les constants multiplicatives surten fora de la variància al quadrat. Una altra propietat de la variància és que no commuta en general amb la suma, però sí que ho fa si les variables són independents:7si tenim en compte la definició de variància i la linealitat de l’esperança, var(X +Y) =E(X +Y)2−E(X +Y)2 =EX2+Y2+2X Y−E(X)2−E(Y)2−2E(X) E(Y) =var(X) +var(Y) +2E(X Y) −E(X) E(Y ) i, per tant, var(X +Y) =var(X) +var(Y) si i només si E(X Y) =E(X) E(Y), i això es compleix si XiYsón variables aleatòries independents. Si les variables tenen llei normal, el recíproc també és cert, és a dir, si es compleix E(X Y) = E(X) E(Y ), llavors les variables són independents. Pel que acabem de dir, el model matemàtic per a l’evolució d’un fenomen aleatori en el temps serà una família de variables aleatòries Y·= {Yt, t ≥ 0}de manera que a l’instant de temps t≥0 la variable Ytindica el valor que pren la quantitat aleatòria que estem observant precisament en aquest instant de temps. D’això se’n diu procés estocàstic. Cada funció del temps que podríem observar rep el nom de trajectòria del procés. Encara que, de fet, només observarem una de les trajectòries, necessitem conèixer el model (procés estocàstic), és a dir, les lleis de les variables aleatòries del procés i les seves propietats, per tal de poder extreure conclusions fiables sobre el fenomen aleatori a partir de la trajectòria. 3 Definició Un procés N·= {Nt, t ≥0}es diu que és un procés de Poisson d’intensitat λ > 0 si compleix les propietats següents: a)N0=0 (parteix de l’origen, excepte potser per a un conjunt de trajectòries de probabilitat 0). b)Els increments del procés en intervals disjunts de temps són independents. És a dir, si 0 ≤s < t ≤u<v, tenim que Nt−NsiNv−Nusón variables aleatòries independents. c)Per a tot 0 ≤s < t, l’increment del procés Nt−Nsés una variable aleatòria amb llei de Poisson de paràmetre proporcional a la longitud de l’interval, amb constant de proporcionalitat λ. És a dir, Nt−Ns∼Poisλ (t −s). 7Intuïtivament, dues variables aleatòries XiYsón independents si el fet de tenir informació sobre el valor que ha pres una d’aquestes no afecta en res els possibles valors que pren l’altra ni les probabilitats amb què els pren. 126 Rosario Delgado Anomenem distribucions en dimensió finita d’un procés Y·= {Yt, t ≥0}les lleis de qualsevol conjunt finit de variables del procés (Yt1, . . . , Ytn), per a n≥1 it1, . . . , tn≥0 arbitraris. La llei d’un conjunt de variables del procés es defineix de manera anàloga a la llei d’una sola variable aleatòria: és el model matemàtic pels possibles valors que prenen les variables del conjunt i les probabilitats amb què ho fan, però no entrarem en els detalls tècnics d’aquesta definició. Si {Yn ·}n≥1és una successió de processos estocàstics, més endavant farem servir la notació següent: ˜ lim n→+∞Yn ·=Y· per indicar que les distribucions en dimensió finita dels processos Yn ·convergeixen cap a les distribucions en dimensió finita del procés Y·quan n→ +∞. Això vol dir que per a tot m≥1 i t1, . . . , tm≥0, si denotem per Fn(x1, . . . , xm)la probabilitat de l’esdeveniment {Yn t1≤x1, . . . , Yn tm≤xm}i per F(x1, .. . , xm) la probabilitat de l’esdeveniment {Yt1≤x1, . . . , Ytm≤xm}, tenim que lim n→+∞Fn(x1, . . . , xm)=F(x1, . . . , xm) per a x1, . . . , xm∈Rqualssevol (punts de continuïtat de F). 4 Definició Es diu que un procés Y·= {Yt, t ≥0}és un procés gaussià si donats n≥1, t1, . . . , tn≥0 i a1, . . . , anarbitraris, n P i=1 aiYtisegueix una llei normal (això és equivalent a dir que les distribucions en dimensió finita són normals). Els processos gaussians queden caracteritzats per l’esperança matemàtica de les seves variables, i pel que anomenem funció de covariàncies, que engloba la informació relativa a les variàncies de les variables, però també la que ens diu quin tipus de relació hi ha entre les variables (si són independents o no, i si no ho són, quin tipus de dependència hi ha entre aquestes). Si totes les variables del procés són centrades es diu que el procés ho és. La funció de covariàncies es defineix així: per a cada 0 < s, t , la covariància entre les variables YtiYsés: Cov(Yt, Ys)=E(Yt−E(Yt)) (Ys−E(Ys)) =E(YtYs)si E(Yt)=E(Ys)=0. Observem que, amb s=t,Cov(Yt, Yt)=var(Yt), així que la funció de covariàncies ens dóna les variàncies de les variables del procés, i també ens dóna una mesura de la relació que hi ha entre aquestes (quan s6= t). D’entre tots els processos gaussians, destaca per la seva importància l’anomenat procés de moviment brownià oprocés de Wiener. L’estudi d’aquest procés es va originar en un intent per explicar el fenomen físic del moviment irregular i ràpid observable al microscopi d’una partícula petita suspesa en un fluid. Aquest moviment caòtic es coneix com a moviment brownià en honor de Robert Brown (1773–1858), botànic anglès que va ser el primer que el va Matemàtiques i Internet 127 observar l’any 1828, i és a causa del bombardeig intensiu de la partícula per part de les molècules del fluid, com va deixar establert el Premi Nobel de Física Albert Einstein (1879–1955) l’any 1905 (el mateix any que va publicar els seus famosos treballs sobre l’efecte fotoelèctric que li valdrien el Premi Nobel l’any 1923, i el de la teoria de la relativitat). Figura 12:Moviment irregular d’una partícula en un fluid. Norbert Wiener (1894–1964), un dels científics més brillants i influents del segle xx i fundador de la cibernètica, va fer una contribució fonamental a la construcció i l’estudi des d’un punt de vista matemàtic del moviment brownià, com es pot veure recollit en una sèrie de cinc articles publicats entre 1920 i 1924, per la qual cosa aquest procés també porta el seu nom. A continuació donem la seva definició, semblant a la del procés de Poisson (definició 3) però canviant la llei de Poisson per la normal. 5 Definició Un procés B·= {Bt, t ≥0}es diu que és un procés de moviment brownià (de variància σ2>0) si compleix les propietats següents: a)B0=0 (parteix de l’origen, excepte potser per a un conjunt de trajectòries de probabilitat 0). b)Els increments del procés en intervals disjunts de temps són independents. És a dir, si 0 ≤s < t ≤u < v, tenim que Bt−BsiBv−Busón variables aleatòries independents. c)Per a tot 0 ≤s < t, l’increment del procés Bt−Bsés una variable aleatòria amb llei normal centrada i amb variància proporcional a la longitud de l’interval, amb paràmetre de proporcionalitat σ2. És a dir, Bt−Bs∼N0, σ2(t −s). Si σ2=1 es diu que és un procés de moviment brownià estàndard. 6 Proposició La definició 5 és equivalent a dir que B·és un procés gaussià, centrat i amb funció de covariàncies: Cov(Bt, Bs)=E(BtBs)=σ2min(s, t) . (1) 128 Rosario Delgado Justificació En efecte, si suposem per fixar idees que 0 ≤s≤t, per la linealitat de l’esperança, pel fet que els increments són independents i que Bt−Bs∼N(0, σ2(t−s)), tenim a partir de la definició 5 que, si B·= {Bt, t ≥0} és un procés de moviment brownià (de variància σ2>0), llavors Cov(Bt, Bs)=E(BtBs)=E(Bt−Bs)Bs+E(B2 s) =E(Bt−Bs) E(Bs)+E(B2 s)=0+σ2s=σ2min(s, t) , és a dir, obtenim (1). I recíprocament, fent servir que el procés és gaussià i centrat, i l’expressió (1), tenim que var(Bt)=E(B2 t)=σ2t; així que, si t=0, var(B0)=0, cosa que vol dir que B0és constant i obtenim a) de la definició 5. La independència dels increments de l’apartat b) es deriva del fet de ser variables amb llei normal tals que l’esperança del producte és producte d’esperances, cosa que és fàcil de veure ja que, si 0 ≤s < t ≤u < v, E(Bt−Bs)(Bv−Bu)=E(BtBv)−E(BtBu)−E(BsBv)+E(BsBu) =σ2min(t, v) −min(t, u) −min(s, v) +min(s, u) =σ2(t −t−s+s) =0 iE(Bt−Bs)=E(Bv−Bu)=0. Finalment, per obtenir c) només cal veure que var(Bt−Bs)=σ2(t −s) si 0 ≤s < t, i això es dedueix de var(Bt−Bs)=E(Bt−Bs)2=EB2 t+B2 s−2BtBs =E(B2 t)+E(B2 s)−2E(BtBs)=σ2t+s−2 min(s, t) =σ2(t +s−2s) =σ2(t −s) . 2 Una propietat dels processos estocàstics de gran importància en modelització és la que tractarem a continuació. Autosimilitud 7 Definició Direm que el procés estocàstic Y·= {Yt, t ≥0}és autosimilar d’índex H∈(0,1)si per a tota constant a > 0 el procés canviat d’escala {a−HYa t, t ≥0}té les mateixes distribucions en dimensió finita que el procés original. Ho denotem per Y· d =a−HYa· Dit d’una altra manera, l’autosimilitud implica que un canvi a l’escala del temps que consisteix a multiplicar el temps tper una constant a > 0 és equivalent al canvi a l’escala de l’espai d’estats que consisteix a multiplicar l’estat del procés per aH(llavors, Yat té la mateixa llei que aHYt). En les aplicacions, són molt importants els processos autosimilars que compleixen a més la propietat de la definició següent: Matemàtiques i Internet 129 8 Definició Direm que el procés estocàstic Y·= {Yt, t ≥0}té els increments estacionaris si Y·+h−Yhd =Y·−Y0per a tota h > 0, on Y·+hdenota el procés {Yt+h, t ≥0}. 9 Proposició Sigui Y·= {Yt, t ≥0}un procés autosimilar d’índex H∈(0,1), amb increments estacionaris, i tal que, per a tot t≥0,E(Y 2 t) < +∞. Llavors, es compleixen les propietats següents: a)Y0=0(parteix de l’origen, excepte potser per a un conjunt de trajectòries de probabilitat 0). Això és conseqüència que per a tot a > 0, com que a0=0, per l’autosimilitud tenim que Y0=Ya0té la mateixa llei que aHY0. b) El procés és centrat, és a dir, E(Yt)=0per a tot t≥0. Això és molt fàcil de justificar, ja que per l’estacionarietat dels increments i per a), E(Y2t)=E(Y2t−Yt)+Yt=E(Y2t−Yt)+E(Yt)=E(Yt−Y0)+E(Yt)=2E(Yt). D’altra banda, per la propietat d’autosimilitud, Y2tté la mateixa llei que 2HYti, com a conseqüència, E(Y2t)=2HE(Yt), així; obtenim que 2E(Yt)=2HE(Yt)per a tot t≥0, cosa que implica necessàriament la propietat ja que H∈(0,1). c)E(Y2 t)=t2Hσ2si σ2denota E(Y2 1). Això és a causa de l’autosimilitud, ja que pel fet que t=1t, tenim que Ytté la mateixa llei que tHY1i, per tant, E(Y2 t)=E(tHY1)2=t2HE(Y2 1)=t2Hσ2. d) La funció de covariàncies del procés és ΓH(s, t) =σ2 2t2H+s2H−|t−s|2H.(2) En efecte, com que el procés és centrat, usant a b =1 2(a2+b2−(a −b)2), la funció de covariàncies és Cov(Yt, Ys)=E(YtYs)=1 2E(Y2 t)+E(Y2 s)−E(Yt−Ys)2 =1 2E(Y2 t)+E(Y2 s)−E(Y2 |t−s|)=σ2 2t2H+s2H−|t−s|2H, on hem fet servir l’estacionarietat dels increments i l’apartat c). La proposició anterior ens diu quines propietats compleixen els processos autosimilars i amb increments estacionaris però... estem segurs de l’existència d’aquests processos? El resultat següent ens assegura que sí que existeixen. 130 Rosario Delgado El moviment brownià fraccionari 10 Proposició Sigui H∈(0,1)iσ2>0. La funció definida per (2), és a dir, ΓH(s, t) =σ2 2t2H+s2H−|t−s|2Hs, t ≥0 és definida no negativa.8 La demostració de la proposició, molt elegant, es pot trobar a [19]. La seva importància rau en el fet que el caràcter de definida no negativa de la funció ΓHfa que pugui ser realment la funció de covariàncies d’un procés. En efecte, resultats clàssics de probabilitat ens asseguren que existeix un procés estocàstic, que denotem per BH ·= {BH t, t ≥0}, gaussià, centrat i amb funció de covariàncies CovBH t, BH s=ΓH(s, t). Notem que amb s=ta l’expressió de la funció de covariàncies CovBH t, BH t=varBH t=EBH t2=σ2t2H<+∞. A més, com que un procés gaussià i centrat queda caracteritzat per la seva funció de covariàncies, com ja hem comentat just després de la definició 4, donat 0 < H < 1, per la proposició 9 tenim que tots els processos gaussians, centrats, autosimilars d’índex Hi increments estacionaris, són el mateix procés (llevat de constants multiplicatives). Per això podem donar la definició següent: 11 Definició Un procés BH ·= {BH t, t ≥0}gaussià, centrat, autosimilar d’índex H∈(0,1), amb increments estacionaris i E(BH 1)2=σ2>0, rep el nom de moviment brownià fraccionari (mbf) (de variància σ2). Es diu que el procés és estàndard si σ2=1. La funció de covariàncies d’aquest procés, com hem vist, serà CovBH t, BH s=ΓH(s, t) =σ2 2t2H+s2H−|t−s|2H. Observació Quan H=1/2 aquest procés coincideix amb el procés de moviment brownià clàssic, que hem introduït a la definició 5, ja que ΓH=1/2=σ2 2( t +s−|t−s|)=σ2min(s, t), que coincideix amb (1). L’índex Hs’anomena índex de Hurst en honor a H. E. Hurst, que en els seus estudis hidrològics al riu Nil va trobar empíricament que el model adequat per a les dades que havia obtingut era un procés autosimilar d’índex H0,7 en lloc 8Una funció de dues variables fés definida no negativa si, per a tot n≥1, t1, . . . , tn≥0 i a1, . . . , an∈R, es compleix que Pn i=1Pn j=1f(ti, tj) aiaj≥0. Matemàtiques i Internet 131 de H=0,5, corresponent al cas del moviment brownià clàssic, com en principi havia esperat (vegeu [5]). Existeixen processos autosimilars i amb increments estacionaris que no són gaussians, encara que cap d’aquests ha tingut la importància del moviment brownià fraccionari, que ha estat utilitzat amb molt d’èxit en modelització. A partir del que hem vist tenim els resultats següents: 12 Proposició Sigui Y·= {Yt, t ≥0}un procés estocàstic tal que: a)és un procés gaussià, centrat, i amb Y0=0(parteix del 0excepte potser per a un conjunt de trajectòries de probabilitat 0), b)existeixen σ2>0i0< H < 1tals que, per a tot t≥0,E(Y 2 t)=t2Hσ2, c)té increments estacionaris; llavors, el procés Y·és un mbf d’índex Hi variància σ2. 13 Proposició Siguin Y·= {Yt, t ≥0}un procés estocàstic i σ2=E(Y2 1) > 0. Fixat H∈(0,1), les afirmacions següents són equivalents: a)Yés un procés gaussià, autosimilar d’índex Hi amb increments estacionaris. b)Yés un mbf d’índex Hi variància σ2. c)Yés un procés gaussià, centrat i amb funció de covariàncies donada per Cov(Yt, Ys)=ΓH(s, t) =σ2 2t2H+s2H−|t−s|2H, s, t ≥0. Què podem dir de les trajectòries del procés mbf? Per a qualsevol 0 < H < 1, les trajectòries del mbf d’índex Hsón contínues però no són diferenciables en cap punt. És a dir, que, tot i ser contínues, les trajectòries són molt irregulars (fan ziga-zaga), encara que són menys irregulars com més gran és H. Més concretament, podem considerar la covariància entre dos increments del procés en intervals (s1, s2]i(t1, t2]qualssevol, CovYt2−Yt1, Ys2−Ys1=EYt2−Yt1Ys2−Ys1 =σ2 2−|t2−s2|2H+|t2−s1|2H+|t1−s2|2H−|t1−s1|2H.(3) Si prenem ara 0 ≤s1< s2≤t1< t2(és a dir, els intervals disjunts) tenim que en el cas H=1/2, que correspon al moviment brownià clàssic, la covariància és zero, és a dir, els increments en intervals disjunts són variables aleatòries independents, mentre que si 0 < H < 1/2 la covariància és negativa (els increments tendeixen a tenir signes oposats, la qual cosa es tradueix en un efecte ziga-zaga més gran) i si 1/2< H < 1, és positiva (els increments tendeixen a tenir el mateix signe i disminueix l’efecte ziga-zaga; d’això últim, se’n diu efecte Josep pels set anys seguits de vaques grasses i els set anys seguits de vaques magres de l’episodi bíblic). La justificació del signe de la covariància per al cas H=1/2 és immediata, i si H6= 1/2 es basa en el fet que, si definim per a t≥0 132 Rosario Delgado la funció g(t) =t2H, resulta que gés estrictament convexa si 1/2< H < 1 i estrictament còncava si 0 < H < 1/2. Per tant, si 1/2< H < 1 tenim que g(t2−s2) < s2−s1 (t2−t1)+(s2−s1)g(t1−s2)+t2−t1 (t2−t1)+(s2−s1)g(t2−s1) g(t1−s1) < t2−t1 (t2−t1)+(s2−s1)g(t1−s2)+s2−s1 (t2−t1)+(s2−s1)g(t2−s1) i sumant dóna: g(t2−s2)+g(t1−s1) < g(t1−s2)+g(t2−s1), amb la qual cosa queda provat que (3) és >0. El cas 0 < H < 1/2 es faria anàlogament. Autosimilitud i memòria llarga Sigui Y·= {Yt, t ≥0}un procés amb increments estacionaris i autosimilar d’índex H, amb 0 < H < 1. Podem considerar el procés d’increments associat definit així: X·= {Xk, k ≥1},amb Xk=Yk+1−Yk,per a tot k∈N. 14 Definició Si Y·és un mbf de variància σ2, llavors el procés d’increments associat que acabem de definir, X·, rep el nom de soroll gaussià fraccionari (de variància σ2). Aquestes són les propietats fonamentals del soroll gaussià fraccionari: 15 Proposició El soroll gaussià fraccionari X·= {Xk, k ≥1}(de variància σ2) compleix les propietats següents: a)les variables Xktenen totes la mateixa llei (obvi, ja que el procés Y·té els increments estacionaris), b) és centrat (per ser-ho el procés Y·), c) la variància de Xkés var(Xk)=EX2 k=E(Yk+1−Yk)2=σ2 2−02H+12H+12H−02H=σ2 per la fórmula (3) amb s1=t1=kis2=t2=k+1 (o bé, directament, ja que, per l’estacionaritat dels increments, E(Yk+1−Yk)2=E(Y1)2=σ2). d) la funció d’autocovariàncies del procés X, definida per: ρ(`) =Cov(Xk, Xk+`)per a `≥1, és: ρ(`) =EXkXk+`=σ2 2(` +1)2H+(` −1)2H−2`2H, Matemàtiques i Internet 133 fent servir de nou (3) als intervals (k, k +1]i(k +`, k +`+1], i tenim que ρ(`)        <0 si 0 < H < 1/2, =0 si H=1/2, >0 si 1/2< H < 1. e) Si H6= 1/2, tenim que ρ(`) es comporta com σ2H(2H−1) `2(H−1)quan `→ +∞. Aquest comportament és conseqüència immediata de d), ja que ρ(`) =σ2 2(` +1)2H+(` −1)2H−2`2H =σ2 2`2(H−1)`2(1+1 `)2H+(1−1 `)2H−2 | {z } tendeix a 2H(2H−1)quan `→+∞ . Per la propietat e) veiem que lim `→+∞ρ(`) =0 com una potència, però quan 1/2< H < 1 ho fa tan lentament que la sèrie P `≥1 ρ(`) divergeix. Llavors diem que el procés X·té memòria llarga, a diferència del que passa quan 0 < H < 1/2, cas en què la sèrie convergeix. En general, podem donar la definició següent: 16 Definició Donada una successió de variables aleatòries, totes amb la mateixa llei, centrades i amb variància finita, X·= {Xk, k ≥1}, direm que X·té memòria llarga si es compleix que ρ(`)=EXkXk+`es comporta com `−βL(`) quan `→ +∞ amb 0 <β<1 i Luna funció de variació lenta a l’infinit9(en aquest cas la sèrie P `≥1 ρ(`) divergeix). La divergència d’aquesta sèrie captura la intuïció que hi ha darrere de la memòria llarga: encara que les autocorrelacions ρ(`) amb `gran (és a dir, en un interval llarg) són petites individualment considerades, el seu efecte acumulat resulta ser important i dóna lloc a un comportament marcadament diferent del que tenen els processos amb memòria curta. Pel que hem vist, el soroll gaussià fraccionari amb 1/2< H < 1 és una successió que té memòria llarga, amb β=2(1−H) ∈(0,1)iLconstant i igual aσ2H (2H−1). 9Una funció Les diu que és de variació lenta a l’infinit si és acotada a cada interval finit i per a tot a > 0, limx→+∞ L(a x) L(x) =1 . Les constants i els logaritmes en són exemples. 140 Rosario Delgado (MANET), ja han generat i encara generaran nous problemes a la teoria del teletrànsit. Ara que tot just encetem el segon centenari de la teoria de cues, una de les seves tasques per al futur és precisament el desenvolupament de les eines matemàtiques per solucionar aquests problemes. Apèndix: sobre la demostració del teorema Donarem en aquest apèndix les idees més importants de la demostració del teorema 17, sense entrar a fons en els detalls tècnics complicats (la demostració dels quals es pot trobar a [21]). Primer pas: El primer pas de la demostració consisteix a adonar-se que, pel teorema central del límit habitual, ˜ lim N→+∞ 1 √N N X n=1U(n) ·−EU(n) ·=G·(5) amb G·= {Gu, u ≥0}un procés gaussià i estacionari15 (això a causa que, per a cada n,U(n) ·= {U(n) u, u ≥0}és un procés estacionari), que és un procés centrat i amb funció d’autocovariàncies {ρ(u), u ≥0}, la mateixa que U(n) ·, per a qualsevol n, és a dir, ρ(u) =EGuG0=EU(n) uU(n) 0−E(U(n) 0)2. Segon pas: Ara ens fixem que, per (5), l’expressió de (4) es pot reescriure com ˜ lim N→+∞ ˆ AT,N ·=RT· 0Gudu THpL(T),(6) on hem fet servir la notació RT· 0Gudu TH√L(T) per al procés nRTt 0Gudu TH√L(T) , t ≥0o.Això és a causa que, per a tot n=1, . . . , N, Zt 0E(U(n) u) du =tµ1 µ1+µ2. Per tant, per demostrar el teorema, fem servir (6) i el que hem de provar és que ˜ lim T→+∞ RT· 0Gudu THpL(T) =BH ·.(7) I això serà conseqüència del teorema clàssic de l’any 1962, degut a John W. Lamperti [9], en què es veu com apareixen els processos autosimilars a partir 15 Un procés X·= {Xt, t ≥0}és estacionari si les seves distribucions en dimensió finita no canvien en fer una translació en el temps, és a dir, si per a tot n≥1, ` > 0, t1, . . . , tn≥0 i x1, . . . , xn∈Res compleix que P(Xt1≤x1, . . . , Xtn≤xn)=P(Xt1+`≤x1, . . . , Xtn+`≤xn). Matemàtiques i Internet 141 de cert tipus de límit. Lamperti va ser el primer a observar aquest resultat fonamental, que presentem en una versió lleugerament simplificada, tal com es pot trobar en el capítol 2 del llibre [4] (llevat que a (9) elevem La 1/2 per fer una aplicació directa del teorema). 18 Teorema (Lamperti) Sigui Y·= {Yt, t ≥0}un procés tal que existeixen una funció fpositiva que compleix lim ξ→+∞f(ξ) = +∞ i un procés X·= {Xt, t ≥0}, de manera que ˜ lim ξ→+∞ Xξ· f(ξ) =Y·(8) on Xξ·denota el procés {Xξt, t ≥0}. Llavors, a) el procés Y·és autosimilar d’índex Hper a certa H∈(0,1), i b) per a certa funció Lde variació lenta a l’infinit, f(ξ) =ξHL1/2(ξ) . (9) Recíprocament, tot procés Y·autosimilar d’índex H∈(0,1)resulta ser un límit del tipus (8) per a cert procés X·i certa funció fque compleix (9). (Aquesta darrera afirmació, si agafem X·=Y·if(ξ) =ξH, és trivial.) Tercer pas: Ara apliquem aquest teorema al procés X·donat per Xt=Rt 0Gudu, tenint en compte que {Gu, u ≥0}és un procés gaussià, centrat, estacionari i amb funció d’autocovariàncies ρ(u) tal que compleix Zt 0Zv 0ρ(u) dudv es comporta com σ2t2HL(t) 2quan t→ +∞,(10) amb σ2>0, H∈(0,1)iLuna funció de variació lenta a l’infinit. La justificació de (10) és un detall tècnic però és el que porta més feina de la demostració i, per això, no la donarem aquí, i adrecem el lector interessat a l’article original [21, p. 13–15]. Llavors, amb ξ=T→ +∞ if(T) =THL1/2(T), tenim que ˜ lim T→+∞ RT· 0Gudu THL1/2(T) =BH · amb BH ·un mbf amb variància σ2. La justificació d’aquest límit és que el procés límit a (8) en aquest cas és gaussià, centrat, parteix de l’origen i té increments estacionaris, ja que la integral de G·ho compleix, i a més el teorema ens diu que és un procés autosimilar d’índex H. D’altra banda, VarZt 0Gudu=EZt 0G(v) dv2=2Zt 0Zv 0E(G(v) G(r )) drdv =2Zt 0Zv 0ρ(v −r) dr dv =2Zt 0Zv 0ρ(u) dudv . 142 Rosario Delgado Per tant, fent servir (10) tenim que VarZTt 0Gudues comporta com σ2(Tt)2HL(Tt) quan T→ +∞, així que VarRTt 0Gudu THL1/2(T)es comporta com σ2t2Hquan T→ +∞, i aquestes propietats caracteritzen el procés de moviment brownià fraccionari amb variància σ2, per la proposició 12.  Agraïments L’autora voldria agrair al revisor anònim la seva acurada lectura d’una versió prèvia de l’article i els seus comentaris, que han estat molt pertinents i han permès redactar aquesta versió final millorada. Aquest treball està subvencionat pel projecte de recerca del Ministeri de Ciència i Innovació amb referència MTM2009-08869. Referències [1] Brockmeyer, E.; Halstrom, H. L.; Jensen, A. The life and works of A. K. Erlang. The Copenhagen Telephone Company, 1848. (Transactions of the Danish Academy of Technical Sciences, 2). [http://oldwww.com.dtu.dk/teletraffic/Erlang.htm]. [2] Crovella, M. E.; Bestavros, A. «Self-similarity in World Wide Web traffic: evidence and possible causes». IEEE/ACM Trans. Networking, 5 (6) (1997), 835–846. 160–169. [3] Delgado, R. «Recordando a Erlang: Un breve paseo (sin esperas) por la Teoría de Colas». Materials Matemàtics, 5 (2009). Accessible lliurement a: http://www.mat.uab.cat/matmat/PDFv2009/v2009n05.pdf [4] Embrechts, P.; Maejima, M. Selfsimilar processes. Princeton: Princeton Univ. Press, 2002. (Princeton Ser. Appl. Math.) [5] Hurst, H. E. «Long-term storage capacity of reservoirs». Trans. Amer. Soc. Civ. Eng., 116 (1951), 770–808. [6] Kendall, D. G. «Some problems in the theory of queues». J. R. Stat. Soc. B, 13 (1951), 151–173 (discussió: 173–185). [7] Kleinrock, L. «History of the Internet and its flexible future». IEEE Wireless Communications, (2008), 8–18. [8] Kolmogorov, A. N. «Wienersche Spiralen und einige andere interessante Kurven im Hilbertschen raum». Comptes Rendus (Doklady) de l’Académie des Sciences de l’URSS (N. S.), 26 (1940), 115–118. Matemàtiques i Internet 143 [9] Lamperti, J. «Semi-stable stochastic processes». Trans. Amer. Math. Soc., 104 (1) (1962), 62–78. [10] Leland, W.; Taqqu, M.; Willinger, W.; Wilson, D. V. «On the self-similar nature of the Ethernet traffic». Proceedings of SIGCOMM’93, San Francisco, California, (1993), 183–193. [11] Leland, W.; Taqqu, M.; Willinger, W.; Wilson, D. V. «On the selfsimilar nature of the Ethernet traffic (extended version)». IEEE/ACM Trans. Networking, 2 (1) (1994), 1–15. [12] Mandelbrot, B. B. «Une classe de processus stochastiques homothetiques a soi; application a loi climatologique de H. E. Hurst». C. R. Acad. Sci. Paris, 240 (1965), 3274–3277. [13] Mandelbrot, B. B. «Long-Run linearity, locally Gaussian processes, H-Spectra and Infinite Variances». Internat. Econom. Rev., 10 (1969), 82– 113. [14] Mandelbrot, B. B. The fractal geometry of nature. Nova York: W. H. Freeman and Co., 1982. [15] Mandelbrot, B. B.; Van Ness, J. W. «Fractional Brownian motions, fractional noises and applications». SIAM Rev., v. 10, (1968), 422–437. [16] Mikosch, T.; Resnick, S.; Rootzén, H.; Stegeman, A. «Is network traffic approximated by stable Lévy motion or fractional Brownian motion?» Ann. Appl. Probab., 12 (2002), 23–68. [17] Molina, E. C. «The theory of probabilities applied in telephone trunking problems». Bell Syst. Tech. J., 1 (1922), 69–81. [18] Palm, C. «Intensity fluctuations in telephone traffic». Ericsson Technics, v. 44 (1943), 1–189. [19] Taqqu, M. S. «Fractional Brownian motion and long-range dependence». A: Doukhan, P.; Oppenheim, G.; Taqqu, M. S. [ed.]. Theory and applications of long-range dependence. Boston: Birkhäuser, 2003. [20] Taqqu, M. S.; Levy, J. «Using renewal processes to generate long-range dependence and high variability». A: Eberlein, E.; Taqqu, M. S. [ed.]. Dependence in Probability and Statistics. Birkhäuser, 1986. [21] Taqqu, M. S.; Willinger, W.; Sherman, R. «Proof of a fundamental result in self-similar traffic modeling». Comput. Commu. Rev., 27 (2) (1997), 5–23. [22] Willinger, W.; Paxon, V. «Where mathematics meets the Internet». Notices Amer. Math. Soc., (setembre 1998). [23] Willinger, W.; Taqqu, M. S.; Erramilli, A. «A bibliographical guide to self-similar traffic and performance modeling for modern high-speed networks». A: Kelly, F. P.; Zachary, S.; Ziedins, I. [ed.]. Stochastic networks: Theory and applications. Oxford Sci. Publ., 1996. (Royal Statistical Society. Lecture Note Series, 4.) 144 Rosario Delgado [24] Willinger, W.; Taqqu, M. S.; Sherman, R.; Wilson, D. V. «Self-similarity through high-variability: Statistical analysis of Ethernets LAN traffic at the source level». IEEE/ACM Trans. Networking, 5 (1) (1997). Departament de Matemàtiques Universitat Autònoma de Barcelona Edifici C, Campus de la UAB 08193 Bellaterra (Cerdanyola del Vallès) [email protected]