BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/254
DTSTAMP:20230914T125916Z
SUMMARY:Two Characterizations of General Ergodic Markov Chain Families with
  Small First Passage Time
DESCRIPTION:Speaker: Swagato  Sanyal\n\nAbstract: \nMarkov chain is a stoch
 astic process which has been found effective in modelling a wide variety o
 f situations and phenomena in computer science. In many such applications\
 , the first passage times of certain states of Markov chains become matter
 s of interest. One such example is randomized search heuristics for solvin
 g combinatorial optimization problems. The execution of many such heuristi
 cs can be modelled by a Markov chain where each state corresponds to a fea
 sible solution\, and the target state is the one corresponding to minimum 
 cost (for minimization problem). So the run time of such an algorithm is t
 he first passage time of the target state. Other examples include gamble a
 nd situations that can be modelled as gambles\, randomized routing algorit
 hms in computer networks\, etc. The thesis focusses on characterizing fami
 lies of ergodic Markov chains having small first passage time of some goal
  state. To appropriately define `small'\, we consider Markov chains parame
 trized by binary strings and define `short first passage time' to be at mo
 st a fixed polynomial in the size of the string that gives rise to the cha
 in. We introduce two notions of 'success' as we call it\, and show them to
  be equivalent. The thesis presents two characterizations of success. The 
 first one is that the ratio of the ergodic flow out of each set of states 
 not containing the goal state to the capacity of the state is at least som
 e inverse polynomial in the size of the string giving rise to the chain. T
 he second characterization\, which is easily seen to be a sufficient condi
 tion\, is that the family of Markov chains is rapidly mixing and the stati
 onary probability of the goal state is at least some inverse polynomial in
  the size of the generating string. Thus rapid mixing and first passage ti
 me turn out to be closely related. Finally we illustrate the applicability
  of our results by giving alternative proofs of some known results due to 
 Wegener on performance of the Metropolis algorithm on the minimum spanning
  tree problem for connecting triangles.\n
URL:https://www.tcs.tifr.res.in/web/events/254
DTSTART;TZID=Asia/Kolkata:20120229T140000
DTEND;TZID=Asia/Kolkata:20120229T153000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR