Bangalore Probability Seminar 2015



Venue: Indian Statistical Institute (auditorium) and Indian Institute of Science (Mathematics dept)

Organizers: Siva Athreya and Manjunath Krishnapur

Past lectures (2015)

Other years:
2014,
2013,
2012, 2011, 2010, 2009, Prior to 2009

Upcoming lectures

2015-16 Ashok Maitra Memorial Lectures on Probability

Remco van der Hofstad

Metric convergence of critical scale-free random graphs

9 Nov, 2:00-3:00 and 3:10-4:00 at ISI, Bangalore
Empirical findings have shown that many real-world networks are scale-free 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 Erdoes-Renyi 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 -(\tau-1) with \tau in (3,4), the largest clusters have size n^{(\tau-2)/(\tau-1)}, where (\tau-2)/(\tau-1)\in (1/2,2/3). Further, the metric scaling limit is rather different. For example, the Minkowski dimension equals (\tau-2)/(\tau-3)>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 heavy-tailed 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 non-asymptotic 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 Monte-Carlo 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 trait-dependent branching with mutation and competition Anita Winter (Universitat Duisburg-Essen, Germany)
We propose a trait-dependent 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 well-posed 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 ultra-metric. We therefore develop new techniques for verifying a compact containment condition. We also provide a new function-valued 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 modern-day 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 Multi-Armed 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, Bayesian-inspired 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 Risk-Sensitive Ergodic Control of Continuous Time Markov Processes With Denumerable State Space Chandan Pal (IISc, Bangalore)
We study risk-sensitive control problem with controlled continuous time Markov chain state dynamics. Using multiplicative dynamic programming principle, we prove the existence and a characterization of optimal risk-sensitive 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 non-local Schrödinger operators Siva Athreya (ISI, Bangalore)
We show a Harnack inequality for bounded positive solutions of the non-local 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 T-invariant 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 3-colourings 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, TIFR-CAM, 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 end-to-end measurements. This is joint work with Vivek S. Borkar and D. Manjunath.

3 Aug, TIFR-CAM, 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 (n-dimensional Lebesgue measure) of A(k) is non-decreasing in k, or in other words, that when one has convergence in the Shapley-Folkmann-Starr 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 Shapley-Folkmann-Starr theorem when measured using alternate measures of non-convexity, including the Hausdorff distance, inner radius, and a non-convexity 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 non-convexity of A(k) converges monotonically to 0 as k increases; even the convergence does not seem to have been known before. As a by-product, 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 \alpha-stable random field (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 \alpha-stable (S\alphaS) processes governed by dissipative and conserva- tive flows were studied in relation to the length of memory. These re- sults have also been generalised to stable random fields on a lattice. In this work, we try to investigate such behaviours induced by stationary S\alphaS random fields indexed by non-amenable groups, especially, finitely generated free groups. Such a random field can be thought of as an S\alphaS random field on a regular tree of even degree by passing to the corre- sponding Cayley graph. When the underlying non-singular 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 significantly 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 finitely 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 non-negative probability measure is bounded away from zero, then its free multiplicative convolution with the semicircle law has a non-trivial 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^{1-1/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 signal-to-interference-plus-noise-ratio (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 non-zero 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. Non-trivial 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 2-D lattice models with pairwise interactions Navin Kashyap (IISc, Bangalore)
Consider an N x N square lattice (grid) with N^2 nodes (sites) and 2N(N-1) edges (bonds). Associated with each node i is a binary-valued variable x_i. To each edge e = {i,j} of the lattice, we associate a non-negative 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 3-6th 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 Kesten-Stigum condition, it is shown that the point process sequence of properly scaled displacements coming from the n-th 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 + Bt2). H\"older regularity and stability under approximation type results follows as corollary. Also this approach allows us to prove that deterministic Cameron-Martin 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. Vershik-Kerov and Logan-Shepp first showed that asymptotically the typical length of the LIS is 2sqrt(n). This line of research culminated in the work of Baik-Deift-Johansson who related this length to the Tracy-Widom 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.