Bangalore Probability Seminar 2009

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

Organizers: Siva Athreya and Manjunath Krishnapur

Past lectures (2010)

Other years: 2009, Prior to 2009

Upcoming lectures

20 Dec, IISc, 2:45 PM Coalescing systems of non-Brownian particles Arnab Sen (Statistical Laboratory, University of Cambridge)

A well-known result of Arratia shows that one can make rigorous the notion of starting an independent Brownian motion at every point of an arbitrary closed subset of the real line and then buildi\ ng a set-valued process by requiring particles to coalesce when they collide. Arratia noted that the value of this process will be almost surely a locally finite set at all positive times, and a \ finite set almost surely if the starting set is compact. We investigate whether such instantaneous coalescence still occurs for coalescing systems of particles where either the state space of the\ individual particles is not locally homeomorphic to an interval or the sample paths of the individual particles are discontinuous. We show that Arratia's conclusion is valid for Brownian motions\ on the Sierpinski gasket and for stable processes on the real line with stable index greater than one. Joint work with Steve Evans and Ben Morris.

20 Dec, ISI, 4:00 PM Spectrum of non-hermitian heavy-tailed random matrices Charles Bordenave (Universite de Toulouse)

This is a joint work with Pietro Caputo (Roma 3) and Djalil Chafaï (Paris Est). Consider an n x n random matrix whose entries are i.i.d. complex random variables in the domain of attraction of an alpha-stable law, with 0< alpha <2. We establish a heavy tailed counterpart of the circular law. Namely, as n goes to infinity, we prove that, properly rescaled, the empirical distribution of the eigenvalues converges almost surely to a limiting measure. In contrast with the Hermitian case, we find that this limiting measure is not heavy tailed. Our proof combines Aldous' objective method with Tao and Vu's approach to Girko's Hermitization using logarithmic potentials.

16 Dec, ISI, 2:00 PM Reconstructing population pedigrees Bhalchandra Thatte (University of Oxford, U.K.)

A pedigree of a population of individuals is a finite directed acyclic graph in which each vertex has indegree 0 or 2. The sink vertices in a pedigree are living individuals and sources are the founders of the population. Can we construct pedigrees from observations on living individuals? I will give an overview of a broad range of theoretical questions in my attempts to adapt phylogenetic methods to study the above question. In particular, I would like to introduce many combinatorial questions closely related to enumeration, graph reconstruction from subgraphs, line graphs of graphs and permutation groups, and statistical identifiability and consistency questions for simple models of recombination and mutation.

16 Dec, ISI, 3:15 PM Experiments with the site frequency spectrum Raazesh Sainuddin (University of Canterbury, New Zealand and Indian Statistical Institute, Bangalore)

Evaluating the likelihood function of parameters in highly-structured population genetic models from extant deoxyribonucleic acid (DNA) sequences is computationally prohibitive. In such cases, one may approximately infer the parameters from summary statistics of the data such as the site-frequency-spectrum (SFS) or its linear combinations. Such methods are known as approximate likelihood or Bayesian computations. Using a controlled lumped Markov chain and computational commutative algebraic methods we compute the exact likelihood of the SFS and many classical linear combinations of it at a non-recombining locus that is neutrally evolving under the infinitely- many-sites mutation model. Using a partially ordered graph of coalescent experiments around the SFS we provide a decision-theoretic framework for approximate sufficiency. We also extend a family of classical hypothesis tests of standard neutrality at a non- recombining locus based on the SFS to a more powerful version that conditions on the topological information provided by the SFS. Keywords: controlled lumped Markov chain, unlabelled coalescent, random integer partition sequences, partially ordered experiments, population genomic inference population genetic Markov bases, approximate Bayesian computation done exactly Link to the preprint of the accepted paper in Bulletin of Mathematical Biology, Algebraic Biology Special Edition:

13 July, IISc, 4:00 PM Do Financial Returns Have Finite or Infinite Variance? A Paradox and an Explanation Michael Grabchak (Cornell)

One of the major points of contention in studying and modeling financial returns is whether or not the variance of the returns is finite or not. A common model is to assume that returns have regularly varying tails with tail index α. This parameter controls which moments are finite. Since returns over a certain time horizon correspond to the aggregation of returns over smaller time horizons, the parameter α should be the same for all aggregation levels. Paradoxically, empirically estimated values of α tend to increaseas the time horizon gets larger. This suggests that the tails are actually lighter than the model assumes. Never-the-less, the fact that the data appears to be heavy tailed suggests that the true distribution has tails that seem to be heavy up to a point, but are eventually lighter. We shall call such distributions tempered heavy tailed.

Although these models are in the domain of attraction of the Gaussian, they may have stable-like behavior at certain aggregation levels. Building on the prelimit theorems of Klebanov et al. (1999, 2000), we show that, in fact, even if a tempered heavy tailed distribution looks nothing like a stable, it may, at larger aggregation levels, look more and more stable-like, before ultimately converging to a Gaussian. Important examples demonstrate the existence of a natural scale associated with the model, at which the apparent shift in the tails occurs.

Joint work with G. Samorodnitsky.

10 May, ISI, 2:00 PM Limit of characteristic polynomials of a random matrix. Manjunath Krishnapur (Mathematics, IISc)

We show that the characteristic polynomials of n x n Gaussian matrices, appropriately normalized, converges to a random analytic function. The limit random analytic function turns out to be a Gaussian analytic function with respect to a random covariance kernel. We show this by proving a version of Polya's urn scheme for Hilbert space valued random variables. This is joint work with Bálint Virág.

10 May, ISI, 3:15 PM On the changing patterns of Indian monsoon rainfall V. Venugopal (C.A.O.S , IISc)

The talk will focus on changes in several attributes of the Indian monsoon rainfall over the past 50-100 years.

26 Apr, IISc, 2:30 PM A multidimensional ruin problem. S. Ramasubramanian (Indian Statistical Institute, Bangalore)

It is known that the joint dynamics of insurance companies operating under a risk reducing treaty can be modelled in terms of Skorokhod problem. In this talk we give an account of ongoing work on the associated ruin problem.

26 Apr, IISc, 3:45 PM Risk sensitive control of diffusions with bounded cost Anup Biswas (TIFR, Bangalore)

Infinite horizon risk-sensitive control of diffusions will be analyzed under a stability condition coupled with a bound on the running cost. Two types of cost functions will be considered: "near monotone cost" and "small cost". It will be shown that the corresponding Hamilton-Jacobi-Bellman equation has a solution. This also leads to an existence result for optimal controls.

12 Apr, ISI, 2:15 PM Hill estimator for truncated data. Arijit Chakrabarty (Indian Institute of Science, Bangalore)

We analyze the behavior of the Hill statistic applied to data coming from a truncated power law, assuming that the truncating threshold goes to infinity along with the sample size. It turns out that if the growth rate of the threshold is sufficiently slow, then a priori choosing a 'k' so that the Hill statistic is consistent is a problem. To overcome this, we suggest a sample based (and hence random) choice of 'k'. In this talk, we shall show that this choice of 'k' leads to a consistent estimator of the inverse of the tail exponent, and also show that under some further assumptions, the Hill statistic is asymptotically normal. This is a joint work with Gennady Samorodnitsky.

12 Apr, ISI, 3:30 PM Extended Random Signal-to-Interference-and-Noise-Ratio Graphs with Fading. Srikanth Iyer (Indian Institute of Science, Bangalore)

The asymptotic properties of a random geometric graph (SINR-F) on uniform points in which a directed link exists between two nodes if the signal-to-interference-noise-ratio is above a certain threshold will be discussed. The first step is to study such a graph in the presence of fading effects alone (RGG-F). For this graph an almost sure limit for the critical power required to ensure that the graph does not possess isolated nodes and a criterion under which the number of isolated nodes converges in distribution to a Poisson distribution is proved. A sufficient condition under which the graph will be connected with high probability will be presented as well as almost sure bounds on the maximum and minimum vertex degrees. Finally an almost sure upper bound on the maximum received interference is obtained. This enables one to choose an asymptotic spread parameter so as to bound the maximum received interference. With this choice of spread parameter the results obtained for RGG-F can be extended to SINR-F.

22 Mar, IISc, 3:00 PM SDE's with coefficients in S' : Uniqueness B. Rajeev (Indian Statistical Institute, Bangalore)

In this talk we will discuss the (pathwise) uniqueness of solutions to SDE's ; these solutions are processes taking values in $S'$, the space of tempered distributions ; they maybe viewed as generalisations of finite dimensional diffusions .

22 Mar, IISc, 4:10 PM Brownian motion or R-trees. Siva Athreya (Indian Statistical Institute, Bangalore)

22 Feb, ISI, 2:15 PM Diffusion limits and the optimal control of large networks. Adam Shwartz (EE, Technion, Israel)

We shall survey the field of diffusion limits of networks in its classical form, where time and space are scaled as in the functional central limit theorem. This will motivate the new "many server limits", called Halfin-Whitt limits, which we shall describe. Then we formulate control problems for the pre-limit and limiting diffusions. I shall present two original results: one on the optimality of a blind policy, which is unusual in that the amount of information it uses is, in some sense, negligible. A second result concerns the issue of "server fairness", which is again treated through Halfin-Whitt limits.

(joint work with Rami Atar, Technion)

22 Feb, ISI, 3:30 PM Strong laws for urn models. Amites Dasgupta (Indian Statistical Institute, Kolkata)

19 Feb, IISc, 3:00 PM Hard-core Model on Random Graphs. Antar Bandyopadhyay (Indian Statistical Institute, New Delhi Centre)

In this talk we will consider the hard-core model (also known as random independent set) on a general Galton-Watson branching process tree. Given an activity parameter λ > 0 and a progeny distribution N, we will characterize the phase transition phenomenon in terms of unique solution of a recursive distributional equation (RDE). This will be a generalization of earlier work of Kelly (1985), who looked at the same model on regular trees. Moreover we will show that in the uniqueness domain the long range independence property holds. This will enable us to deduce that the size of a random independent set distributed according to a hard-core model on a sparse random graph (Erdos-Renyi random graph or random regular graph) scales with its size, provided the parameters are such that the associated limiting Galton-Watson tree model is in the uniqueness domain. We will also show that the limiting constant can be (explicitly) computed in terms of the unique solution of the associated RDE.

[The talk will be self contained and no prior knowledge about hard-core model or recursive distributional equations will be assumed.]

18 Jan, IISc, 3:00 PM Role of Randomness in analysis and design of Block Ciphers. Rajeeva Karandikar (Cranes Software International Limited)

After a brief introduction to Cryotplogy including Block ciphers, we will discuss the essential role played by the notion of Randomness in analysis of Block ciphers. We will also show how randomness tests can be developed as a tool to test appropriateness of a block cipher design and also to contruct new algorithms.

18 Jan, IISc, 4:10 PM Limit of isoperimetry. Amit Deshpande (Microsoft research, Bangalore)

Among all curves of the same perimeter, circle encloses the maximum area. Among all bodies of the same surface area, sphere encloses the maximum volume. These are special cases of a common underlying principle known as the ``isoperimetric inequality''. In this talk, we will define a hierarchy of density functions (called s-concave) and investigate the isoperimetric inequality for convex bodies with such densities. We will characterize the limitations of isoperimetry for this hierarchy. Our isoperimetric inequalities imply that a geometric random walk (called ball walk) mixes rapidly, which has applications in sampling and optimization algorithms. This extends a result of Lovasz and Vempala on sampling from log-concave densities to heavy-tailed densities beyond log-concave.

06 Jan, ISI, 2:00 PM Asymptotic free independence of Wigner Matrices. B.V. Rao (Chennai Mathematical Institute)

After setting up the language of free probability we discuss the following discovery of Voiculescu. Consider two sequences of self adjoint random matrices (A_n) and (B_n). Entries of A_n , as well as B_n are `independent' centered Gaussian with variance 1/n each. If for each n, A_n and B_n are independent in the classical sense, then the sequences are asymptotically indepedent in the sense of free probahlity.

06 Jan, ISI, 3:30 PM Flows, first passage percolation and random disorder in networks. Shankar Bhamidi (University of North Carolina, Chapel Hill)

Consider a connected network and suppose each edge in the network has a random positive edge weight. Understanding the structure and weight of the shortest path between nodes in the network is one of the most fundamental problems studied in modern probability theory and goes under the name first passage percolation. It arises as a fundamental building block in many interacting particle system models such as the spread of epidemics on networks. To a large extent such problems have been only studied in the context of the n-dimensional lattice. In the modern context these problems take on an additional significance with the minimal weight measuring the cost of sending information while the number of edges on the optimal path (hopcount) representing the actual time for messages to get between vertices in the network. Given general models of random graphs with random edge costs, can one develop techniques to analyze asymptotics of functionals of interest which are robust to the model formulation? The aim of this talk is to describe a heuristic based on continuous time branching processes which gives very easily, a wide array of asymptotic results for random network models in terms of the Malthusian rate of growth and the stable age distribution of associated branching process. These techniques allow us to solve not only first passage percolation problems rigorously but also understand functionals such as the degree distribution of shortest path trees, congestion across edges as well as asymptotics for ``betweeness centrality'' a concept of crucial interest in social networks, in terms of Cox processes and extreme value distributions. These techniques also allow one to exactly solve models of ``weak disorder'' in the context of the stochastic mean field model of distance, a model of great interest in probabilistic combinatorial optimization.