

Bangalore Probability Seminar 2015
Venue: Indian Statistical Institute (auditorium) and Indian Institute of Science (Mathematics dept)
Organizers: Siva Athreya and Manjunath Krishnapur


201516 Ashok Maitra Memorial Lectures on Probability
Remco van der Hofstad
Metric convergence of critical scalefree random graphs
9 Nov, 2:003:00 and 3:104:00 at ISI, Bangalore
Empirical findings have shown that many realworld networks
are scalefree in the sense that there is a high variability in the
number of connections of the elements of the networks. Spurred by
these empirical findings, models have been proposed for such
networks. In this talk, we describe a particular class of random
graphs in which edges are present independently but with unequal edge
occupation probabilities that are moderated by appropriate vertex
weights. For such models, it is known precisely when there is a giant
component, meaning that a positive proportion of the vertices is
connected to one another. We discuss the scaling limit of the metric
structure of the largest connected components at criticality.
Our results show that, the critical behavior admits a transition when
the third moment of the degrees turns from finite to infinite. When
the third moment is finite, Bhamidi, Broutin, Sen and Wang show that
the largest clusters in a graph of n vertices have size n^{2/3} and
the metric scaling limit equals that on the homogeneous ErdoesRenyi
random graph apart from trivial rescalings. In particular, the
limiting metric space has Minkowski dimension 2.
When the third moment of the degrees is infinite and has tails that
are regularly varying with exponent (\tau1) with \tau in (3,4), the
largest clusters have size n^{(\tau2)/(\tau1)}, where
(\tau2)/(\tau1)\in (1/2,2/3). Further, the metric scaling limit is
rather different. For example, the Minkowski dimension equals
(\tau2)/(\tau3)>2, which can be arbitrarily large due to the
presence of 'hub' vertices with infinite degree.
[This is joint work with Shankar Bhamidi, Johan van Leeuwaarden and
Sanchayan Sen.]

26 Oct, IISc, 2:00 PM

On Risk Concentration

Marie Kratz, ESSEC Business School, CREAR (risk research
center)

We study the local behavior of (extreme) quantiles of the sum of
heavytailed random variables, to infer on risk concentration. Looking at
the literature, asymptotic (for high threshold) results have been obtained
when assuming (asymptotic) independence and second order regularly varying
conditions on the variables. Other asymptotic results have been obtained
in the dependent case when considering specific copula structures. Our
contribution is to investigate on one hand, the nonasymptotic case (i.e.
for any threshold), providing analytical results on the risk concentration
for copula models that are used in practice, and comparing them with
results obtained via MonteCarlo method. On the other hand, when looking
at extreme quantiles, we assume a multivariate second order regular
variation condition on the vectors and provide asymptotic risk
concentration results. We show that many models used in practice come
under the purview of such an assumption and provide a few examples.
Moreover this ties up related results available in the literature under a
broad umbrella. This presentation is based on two joint works, one with M.
Dacorogna and L. Elbahtouri (SCOR), the other with B. Das (SUTD).

12 Oct, ISI, 2:00 PM

Evolving phylogenies of traitdependent branching with mutation and
competition

Anita Winter (Universitat DuisburgEssen, Germany)

We propose a traitdependent branching model with mutation and
competition describing the phylogenies of a virus population. The
competition kernel depends for any two virus particles on the particles'
types, the total mass of the population as well as genetic information
available through the number of nucleotide substitutions separating the
virus particles. We rescale the evolving phylogenies of this individual
based model in the huge population, short reproduction time and frequent
mutation regime. We then characterize the limit through a wellposed
martingale problem. The solution is a strong Markov process with
continuous paths taking values in the space of marked metric measure
spaces. Due to heterogeneity in the natural branching rates, the
phylogenies are in general not ultrametric. We therefore develop new
techniques for verifying a compact containment condition. We also provide
a new functionvalued duality to establish uniqueness of the martingale
problem.
(joint work with Sandra Kliem)

12 Oct, ISI, 3:15 PM

Sequential decision making in stochastic environments

Aditya Gopalan (IISc, Bangalore)

Sequential decision making or online learning is concerned
with studying how an agent can learn to perform a task (read optimize a
metric) with repeated actions and ensuing feedback. An increasing number
of modernday automated systems are tasked with learning to make
sequential decisions by utilizing evolving data, e.g., Internet
recommendation engines, dynamic pricing algorithms, automated trading
systems, etc. We will discuss a widely employed model of decision making
under uncertainty called the MultiArmed Bandit, where a decision maker
repeatedly faces a choice of playing one of several "arms" or actions,
each with an unknown stochastic payoff. We will explore several
variants of the bandit model and popular algorithms for bandit
optimization. We will also present recent results toward understanding the
behaviour of a natural, Bayesianinspired algorithm  Thompson sampling or
posterior sampling  known to enjoy excellent empirical performance, often
with complex information structures and time dynamics such as those
encountered in reinforcement learning problems.
Joint work with Shie Mannor and Yishay Mansour.

21 Sep, IISc, 2:00 PM

RiskSensitive Ergodic Control of Continuous Time Markov Processes
With Denumerable State Space

Chandan Pal (IISc, Bangalore)

We study risksensitive control problem with controlled
continuous time Markov chain state dynamics. Using multiplicative dynamic
programming principle, we prove the existence and a characterization of
optimal risksensitive control under geometric ergodicity of the state
dynamics along with a smallness condition on the running cost.

21 Sep, IISc, 3:15 PM

Harnack inequality for nonlocal Schrödinger operators

Siva Athreya (ISI, Bangalore)

We show a Harnack inequality for bounded positive solutions of
the nonlocal Schrodinger operator. This is joint work with Koushik
Ramachandran. http://arxiv.org/abs/1507.07289

17 Aug, ISI, 2:00 PM

Entropy Minimality in Dynamical systems

Nishant Chandgotia

A topological dynamical system (X,T) is said to be entropy minimal if
all closed Tinvariant subsets of X have entropy strictly less than
(X,T). In this talk we will discuss the entropy minimality of a
class of topological dynamical systems which appear as the space of
graph homomorphisms from Z^d to graphs without four cycles; for
instance, we will see why the space of 3colourings of Z^d is entropy
minimal even though it does not have any of the nice topological
mixing properties. This talk should be accessible to the general audience.

3 Aug, TIFRCAM, 2:00 PM

A stochastic Kaczmarz algorithm for network tomography

Gugan Thoppe (ISI, Bangalore)

In this talk, we will see the stochastic approximation variant of the classical Kaczmarz algorithm that is incremental in nature and takes as input noisy real time data. We will prove that with probability one it mimics the behavior of the original scheme: starting from the same initial point, our algorithm and the corresponding deterministic Kaczmarz algorithm converge to precisely the same point. The motivation for this work comes from network tomography where network parameters are to be estimated based upon endtoend measurements. This is joint work with Vivek S. Borkar and D. Manjunath.

3 Aug, TIFRCAM, 3:15 PM

On monotonicity of the tendency towards convexity of Minkowski sums

Mokshay Madiman (University of Delaware)

Let us define, for a compact subset A of R^n, the sequence of compact sets
A(k)={(a_1 + a_2 + ... + a_k)/k : a_1,..., a_k are elements of A}.
In other words, A(k) is the Minkowski sum of k copies of A, scaled by 1/k. By a 1969 theorem of Shapley, Folkmann and Starr, A(k) approaches the convex hull of A in Hausdorff distance as k goes to infinity. The speaker
conjectured a few years ago that the volume (ndimensional Lebesgue measure) of A(k) is nondecreasing in k, or in other words, that when one has convergence in the ShapleyFolkmannStarr theorem in terms of a volume
deficit, then this convergence is actually monotone. This conjecture holds true in dimension 1 but we show that it fails in dimension 12 or greater. We also discuss some related inequalities for the volume of the
Minkowski sum of compact sets, showing that this is fractionally superadditive but not supermodular in general, but is indeed supermodular when the sets are convex. Then we consider whether one can have monotonicity in
the ShapleyFolkmannStarr theorem when measured using alternate measures of nonconvexity, including the Hausdorff distance, inner radius, and a nonconvexity index of Schneider. For these other measures, we present a
clutch of positive and negative results. Our main positive result
is that Schneider's index of nonconvexity of A(k) converges monotonically to 0 as k increases; even the convergence does not seem to have been known before. As a byproduct, we also obtain optimal rates of convergence.
Joint work with Matthieu Fradelizi, Arnaud Marsiglietti, and Artem Zvavitch.

27 July, IISc, 2:00 PM

Stable random fields indexed by trees

Sourav Sarkar (ISI, Kolkata)

We establish a connection between the length of memory
of stationary symmetric \alphastable random ﬁeld (0 < \alpha < 2) indexed by
free groups and the ergodic theoretic properties of the non singular group
actions. Partial maxima and point processes induced by stationary sym
metric \alphastable (S\alphaS) processes governed by dissipative and conserva
tive ﬂows were studied in relation to the length of memory. These re
sults have also been generalised to stable random ﬁelds on a lattice. In
this work, we try to investigate such behaviours induced by stationary
S\alphaS random ﬁelds indexed by nonamenable groups, especially, ﬁnitely
generated free groups. Such a random ﬁeld can be thought of as an S\alphaS
random ﬁeld on a regular tree of even degree by passing to the corre
sponding Cayley graph. When the underlying nonsingular action of the
free group is dissipative, the scaled point process sequence can be shown
to converge weakly to a cluster point process with a random thinning.
The convergence of the corresponding partial maxima is obtained as an
easy corollary. The results are signiﬁcantly different from those in the
case of a lattice. We also try to investigate the rate of convergence of
partial maxima when the group action is conservative. We believe that
the dichotomy between dissipative and conservative actions should exist
even in the case of ﬁnitely generated free groups. This dichotomy can be
used to indicate a phase transition from shorter to longer memory.

27 Apr, ISI, 2:00 PM

Remarks on absolute continuity in the context of free probability and
random matrices

Arijit Chakrabarty (ISI, Delhi)

In this talk, we show that the limiting spectral distribution of
symmetric random matrices with stationary entries is absolutely continuous under
some sufficient conditions. This result is applied to obtain sufficient
conditions on a probability measure for its free multiplicative convolution with
the semicircle law to be absolutely continuous. It is shown, in particular, that
if the support of a nonnegative probability measure is bounded away from zero,
then its free multiplicative convolution with the semicircle law has a
nontrivial semicircular component in the sense of free additive convolution.
This is a joint work with Rajat S. Hazra.

27 Apr, IISc, 3:15 PM

Estimation of Renyi Entropy

Himanshu Tyagi (IISc, Bangalore)

Estimation of randomness in data is an important problem that appears in many applications. A common approach is to assume that the data consists of independent and identically distributed samples from a
discrete distribution and use an estimate of Shannon entropy as a proxy for randomness in the data. However, to estimate the Shannon entropy of a discrete distribution over k symbols reliably, we require roughly order k
independent samples from it, which is close to the number of samples required to estimate the distribution itself (within small statistical distance). Renyi entropy is another fundamental notion of randomness and can
replace Shannon entropy as a measure of randomness in many applications. In fact, in many applications such as secrecy generation, Renyi entropy is a more relevant notion of randomness than Shannon entropy. Does
estimation of Renyi entropy of a given order still requires order k samples or is it easier to estimate Renyi entropy than Shannon entropy? We study this question and show that the answer depends on the order.
Specifically, estimating Renyi entropy of order less than 1 is even more difficult than estimating Shannon entropy, requiring order superlinear in k samples; estimating Renyi entropy of noninteger order greater than 1
still requires roughly order k samples; but estimating Renyi entropy of integer order a>1 requires sublinear, order k^{11/a} samples. This discontinuity in sample complexity of estimating Renyi entropy is perhaps
surprising in view of the continuity of Renyi entropy in its order. In this talk, we will a formal statement of these results and will provide a proof sketch for both the upper and the lower bound for sample complexity of
estimating Renyi entropy of different orders for a discrete k symbol distribution.
This is joint work with Jayadev Acharya, Alon Orlitsky, and Ananda Theertha Suresh.

6 Apr, IISc, 2:00 PM

Achieving positive information velocity in wireless networks

Srikanth Iyer (IISc, Bangalore)

In wireless networks, where each node transmits independently of
other nodes in the network (the ALOHA protocol), the expected delay
experienced by a packet until it is successfully received at any other
node is known to be infinite for signaltointerferenceplusnoiseratio
(SINR) model with node locations distributed according to a Poisson point
process. Consequently, the information velocity, defined as the limit of
the ratio of the distance to the destination and the time taken for a
packet to successfully reach the destination over multiple hops, is zero,
as the distance tends to infinity. A nearest neighbor distance based power
control policy is proposed to show that the expected delay required for a
packet to be successfully received at the nearest
neighbor can be made finite. Moreover, the information velocity is also
shown to be nonzero with the proposed power control policy. The condition
under which these results hold does not depend on the intensity of the
underlying Poisson point process.

6 Apr, IISc, 3:15 PM

Normal convergence of geometric functionals of clustering point processes

Yogeshwaran D (ISI, Bangalore)

I shall describe a central limit theorem for geometric functionals on point processes satisfying a "clustering condition". Examples of geometric functionals of interest are subgraph and component counts in a random geometric graph, intrinsic volumes of a Boolean model. Nontrivial examples of point process that satisfy our requirements are zeros of Gaussian analytic functions and determinantal point processes. In some particular cases, I shall describe variance asymptotics which are also necessary for the central limit theorem. This is a joint work with Joseph Yukich and Bartek Blaszczyszyn.

23 Mar, ISI, 2:00 PM

Correlation inequalities arising from 2D lattice models with pairwise
interactions

Navin Kashyap (IISc, Bangalore)

Consider an N x N square lattice (grid) with N^2 nodes (sites) and 2N(N1)
edges (bonds). Associated with each node i is a binaryvalued variable x_i. To
each edge e = {i,j} of the lattice, we associate a nonnegative function
\phi_e(x_i,x_j). Each configuration x = (x_i) \in {0,1}^{N^2} gets a probability
p(x) proportional to \prod_e \phi_e(x_i,x_j), the constant of proportionality
being the partition function Z of the model. The partition function is hard to
compute exactly in general, but it turns out that it is often possible to
approximate it extremely well using a generalized form of belief propagation.
The accuracy of the approximation is closely related to a certain conjectured
correlation inequality involving the probability p(x). In this talk, we will
give the form of the conjectured inequality, and report on the progress made
towards proving it.
Ongoing work with Eric Chan, Pascal Vontobel and Sidharth Jaggi, Chinese
University of Hong Kong.

23 Mar, ISI, 3:15 PM

Depth and the deepest point

Probal Chaudhuri (ISI, Kolkata)

A depth function is a statistical device for determining whether a
point is close to the centre of a probability distribution or away from it. The
concept of depth function was originally developed for probability distributions
in finite dimensional Euclidean spaces. Recently, there have been several
attempts to extend the concept of depth for probability distributions in
infinite dimensional Hilbert and Banach spaces. Certain depth functions behave
very differently in finite and infinite dimensional spaces while some others do
not. The median of a probability distribution, which can be defined as the
deepest point, also has interesting properties in infinite dimensional spaces.
There are important statistical consequences of such behavior of depth functions
and deepest points as will be demonstrated using data lying in infinite
dimensional spaces.

2 Feb, ISI, 2:00 PM

Quantum Gaussian states, their covariance matrices and structure

K.R. Parthasarathy (ISI, Delhi)

This is Lecture I of the short course. The Lectures II to V will be delivered from Feb 36th at 11:30am.

2 Feb, ISI, 3:15 PM

Point process convergence for branching random walks with
regularly varying steps

Parthanil Roy (ISI, Kolkata)

We consider the limiting behaviour of the point processes
associated with a branching random walk with supercritical branching
mechanism and balanced regularly varying step size. Assuming that the
underlying branching process satisfies KestenStigum condition, it is
shown that the point process sequence of properly scaled displacements
coming from the nth generation converges weakly to a Cox cluster
process. In particular, we establish that a conjecture of Brunet and
Derrida (2011) remains valid in this setup, investigate various other
issues mentioned in their paper and recover a slightly improved
version of a result of Durrett (1983) in our framework.
This talk is based on a joint work with Ayan Bhattacharya and Rajat
Subhra Hazra. The manuscript is available in http://arxiv.org/abs/1411.5646.

12 Jan, ISI, 2:00 PM

Approximation of the Fractional Stochastic Heat Equation by Interacting Diffusions

Mathew Joseph (University of Sheffield)

Consider a system of interacting diffusions on the integer lattice. We explain how this system converges to the solution of the fractional stochastic heat equation if we let the mesh size go to zero and use an appropriate scaling. We get a few consequences from this approximation, one of which is comparison inequalities for moments of the stochastic heat equation with different nonlinearities. This is based on joint works with Davar Khoshnevisan and Carl Mueller and with Mohammud Foondun.

12 Jan, ISI, 3:15 PM

On the trace of Loewner chains

Atul Shekhar (TU Berlin)

We discuss the problem of existence of trace for a Loewner chain. Motivated by construction of SLE_{κ,ρ}, we consider the Loewner chains driven by diffusions. With first approach, we prove that under appropriate conditions, trace exists. Examples include \log(1 + B_{t}^{2}). H\"older regularity and stability under approximation type results follows as corollary. Also this approach allows us to prove that deterministic CameronMartin paths yields \frac{1}{2}H\"older and bounded variation trace. We propose a second approach to the problem. Computations in this direction suggests that slow points of Brownian motion are responsible for the existence of trace. Content of the talk is based on an ongoing project with Peter Friz.

5 Jan, IISc, 2:00 PM

Lengths of Monotone Subsequences in a Mallows Permutation

Nayantara Bhatnagar (University of Delaware)

The longest increasing subsequence (LIS) of a uniformly random permutation
is a well studied problem. VershikKerov and LoganShepp first showed that
asymptotically the typical length of the LIS is 2sqrt(n). This line of
research culminated in the work of BaikDeiftJohansson who related this
length to the TracyWidom distribution.
We study the length of the LIS and LDS of random permutations drawn from the
Mallows measure, introduced by Mallows in connection with ranking problems
in statistics. Under this measure, the probability of a permutation p in S_n
is proportional to q^Inv(p) where q is a real parameter and Inv(p) is the
number of inversions in p. We determine the typical order of magnitude of
the LIS and LDS, large deviation bounds for these lengths and a law of large
numbers for the LIS for various regimes of the parameter q.
This is joint work with Ron Peled.

5 Jan, IISc, 3:15 PM

From Trees to Seeds  on the inference of the seed from large random
trees

Elchanan Mossel (University of Pennsylvania)

We study the influence of the seed in random trees grown according
to the uniform and preferential attachment models. The basic question is :
do different seeds lead to the same distributional limit? The talk will be
based on joint work with Bubeck and Racz, joint work with Bubeck, Eldan and
Racz and work by Curien, Duquesne, Kortchemski, and Manolescu.

