BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1053
DTSTAMP:20230914T125948Z
SUMMARY:The Propp-Wilson Perfect Sampling Algorithm
DESCRIPTION:Speaker: Sayantan Chakraborty (TIFR\, Mumbai)\n\nAbstract: \nAb
stract:*The problem of approximate sampling using Markov Chain Monte Carlo
has received considerable attention in the Theoretical Computer Science a
nd Physics communities. In this approach one typically takes a Markov Chai
n $M$ with a stationary distribution $\\Pi$ over a set $\\mathcal{S }$ and
runs it for a pre-specified amount of time $T$ from a fixed starting stat
e $s_0$. Using various techniques such as Coupling\, Spectral Gap\, etc.\,
the distribution of the output of the chain after $T$ steps\, say\, $s_T$
\, is shown to be close to the stationary distribution $\\Pi$ in total v
ariation distance . $T$ typically has a dependence on $\\log(1/\\eps)$ whe
re $\\eps$ is the desired upper bound on the TV distance between the distr
ibution of $s_T$ and $\\Pi$.* *However\, in this talk we will be intereste
d in producing a sample from $\\mathcal{S}$ that is distributed exactly ac
cording to $\\Pi$\, i.e\, we require $\\eps=0$. Notice\, that the above ap
proximate sampling approach cannot be used directly as we would require $T
$ to be $\\infty$ as it depends on $\\log(1/\\eps)$. To overcome the above
issues Propp and Wilson [1996] came up with a beautiful algorithm known a
s Coupling From The Past (CFTP). In this talk we will arrive at the algori
thm by taking various erroneous approaches and correcting them.*\n
URL:https://www.tcs.tifr.res.in/web/events/1053
DTSTART;TZID=Asia/Kolkata:20200214T140000
DTEND;TZID=Asia/Kolkata:20200214T150000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR