estinzione di un Markovian Binary Tree
Candidato: Emiliano Morini
Relatori: pro. D. A. Bini, B. Meini
27 Giugno 2008 Consideriamo l'equazione
x − a −
Ψ(x ⊗ x) = 0,
(1) dovex
= (x
i
) ∈ R
n
,a
= (a
i
) ∈ R
n
,Ψ = (Ψ
i,jk
) ∈ R
n×n
2
,0 ≤ a
i
,
Ψ
i,jk
≤
1
perognii, j, k
= 1, . . . , n
, ee − a −
Ψ(e ⊗ e) = 0,
one
= (1, 1, . . . , 1)
T
.
Siamointeressatia al olarelasuasoluzione minimalenonnegativa, ioè
il vettore
q
tale heq − a −
Ψ(q ⊗ q) = 0
e
0 ≤ q ≤ y
perogni altra soluzioney
non negativadi (1), dove le disugua-glianzesonofatte omponenteper omponente. L'esistenzadiq
èdimostrata in [1℄.Questaequazione è stata studiata re entemente damoltiautori ([2℄, [5℄,
[6℄), inquantoèstrettamente ollegataadunparti olarepro essodi
dirama-zione, il Markovian Binary Tree (MBT), introdotto da N. Kontoleon ([6℄).
Talepro essosièrivelatoparti olarmenteadattoamodellizzarel'evoluzione
diunapopolazione he sioriginadaunsoloindividuo,ilqualepuò riprodursi
sdoppiandosi,dando luogo adun glio on lemedesime aratteristi he.
Il MBT è stato impiegato in molte ir ostanze, sia in ambito biologi o
([6℄), he in quello informati o (spe ialmente nello studio delle reti
peer-to-peer, ome fattoin[5℄).
Per molte appli azioni prati he, è parti olarmenteinteressante al olare
laprobabilità hel'interapopolazionesiestingua, sapendo hel'individuoda
relativi ai pro essi di diramazione ([1℄, [4℄), si può dimostrare he l'
i
-esima omponente delvettoreq
rappresenta proprioquesta probabilità.In letteratura sono stati presentati quattro metodi per al olare
q
: tre sono varianti di iterazioni funzionali sviluppate per risolvere un problemaderivante dalle atene di Markov di tipo QBD (si veda [3℄), mentre l'altro
algoritmo è il metodo di Newton, uno dei più onos iuti ed impiegati per
al olarenumeri amentegli zeri delle funzioni.
Ris rivendo inmanieraopportuna(1)rius iamoad introdurre una
fami-glia dinuovi metodiperapprossimare
q
dipendente daal uni parametri, di uifanno parte, ome asi parti olari,i quattroalgoritmigiànoti inlettera-tura. Per tutti i metodi appartenenti alla famiglia si ries ono a dimostrare
parti olariproprietà di onvergenza.
Unaltrorisultatonuovoriguardalostudiodella su essionegenerata
ap-pli ando a (1) una variante del metodo di Newton (proposta in [7℄). An he
inquesto aso rius iamoadare delle ondizioni su ientia n hé le
appros-simazioni al olatetendano a
q
, dimostrandoinmanieramoltosempli e he l'ordine di onvergenza è maggioredi quellodegli altrimetodi analizzati.Prin ipali riferimenti bibliogra i
[1℄ K.B. Athreya, P.E.Ney. Bran hing Pro esses.Springer-Verlag, 1972.
[2℄ N.G. Bean,N. Kontoleon,P.G.Taylor.Markovian trees: properties and
algorithms. Annals of OperationsResear h, volume 160,1:31-50, 2008.
[3℄ D.A. Bini, G. Latou he, B. Meini. Numeri al methods for stru tured
Markov hains. Numeri al Mathemati s and S ienti Computation,
Oxford University Press, 2005.
[4℄ T.E. Harris. TheTheory of Bran hingPro esses.Springer-Verlag,1963.
[5℄ S. Hautphenne, K. Leibnitz, M.A. Remi he. Extin tion probability in
Peer-to-Peer lediusion.SIGMETRICSPerform.Eval.Rev.34,2:3-4,
2006.
[6℄ N. Kontoleon. The Markovian Binary Tree: A Model of the
Ma- roevolutionary Pro ess. PhD thesis, The University of Adelaide,
2005.
[7℄ J.M. Ortega, W.C. Rheinboldt. Iterative Solution of Nonlinear
Equations in Several Variables. So iety for Industrial and Applied
