BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/557
DTSTAMP:20230914T125929Z
SUMMARY:Rare events in Heavy-tailed Stochastic Systems: Algorithms and Anal
ysis
DESCRIPTION:Speaker: Karthyek Rajhaa A M\n\nAbstract: \nAbstract: Events th
at occur with low probability are called rare events. In the design of pro
babilistic models\, it is important to ensure that certain undesirable eve
nts\, for example\, bankruptcy of financial institutions (or) data loss in
communication networks\, do not happen (or) if at all they happen\, they
happen with low probability. Conventional theory of large deviations\, whi
ch is usually used to explain the behaviour of such rare events\, is inapp
licable when the random variables involved are heavy-tailed. We call a ran
dom variable to be heavy-tailed if its tail probabilities decay slowly at
some polynomial rate. Simulation of rare events\, in particular\, has been
traditionally considered difficult when heavy-tailed random variables are
involved. In this work\, we analyse asymptotic behaviour of certain rare
events involving heavy-tailed random variables and develop simulation algo
rithms that are provably efficient. To be specific\, we discuss the follow
ing contributions in the talk:\n \n1) Based on the "big jump principle"\,
we develop an entirely new methodology for the estimation of various larg
e deviations and level crossing probabilities that arise in the context of
heavy-tailed sums. Our key contribution has been to question the prevaili
ng view that one needs to resort to state-dependent methods when a large n
umber of heavy-tailed random variables are involved. The algorithms we dev
elop are provably efficient\, follow a general template\, and are easy to
generalize\, as we shall see\, to settings more general than sums of indep
endent random variables. In addition to simulation involving finite sums\,
we tackle the problem of estimating tail probabilities of sums of infinit
e sums\, where bias is generally a problem. Apart from eliminating bias\,
our algorithm computes tail probabilities with uniformly bounded computati
onal effort.\n \n2) Building up on the theory of rare events in heavy-tai
led sums\, we attempt to explain how large delays in service happen in mul
ti-server queues when incoming jobs are heavy-tailed (in size) and traffic
intensity is an integer. In the current literature\, characterizations of
steady-state delay exist only when the traffic intensity is not an intege
r. There are qualitative reasons\, as we shall see\, that makes the intege
r case more delicate to analyse. Our main contribution is that we develop
the first known tail asymptotic for steady-state delay in multi-server que
ues when the traffic intensity is an integer. Specifically\, we consider a
two-server queue and identify interesting transitions in the tail behavio
ur of steady-state delay via a careful analysis that is not typical in the
analysis of queuing systems.\n
URL:https://www.tcs.tifr.res.in/web/events/557
DTSTART;TZID=Asia/Kolkata:20141216T143000
DTEND;TZID=Asia/Kolkata:20141216T160000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR