Bangalore Probability Seminar 2009

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

Organizers: Siva Athreya and Manjunath Krishnapur

Past lectures (2009)

Other years: Prior to 2009

Upcoming lectures

31 Dec, IISc, 3:30 PM Two philosophies for random graphs and networks: Local weak convergence and scaling limits. Shankar Bhamidi (University of North Carolina, Chapel Hill)

The last few years have witnessed an explosion in the number of mathematical models for random graphs and networks, as well as models for dynamics on these network models. In this context I would like to exhibit the power of two well known philosophies in attacking problems in random graphs and networks:
  1. Local weak convergence: The idea of local neighborhoods of probabilistic discrete structures (such as random graphs) converging to the local neighborhood of limiting infinite objects has been known for a long time in the probability community and has proved to be remarkably effective in proving convergence results in many different situations. Here we shall give a wide range of examples of the above methodology. In particular
    1. We shall show how the above methodology can be used to tackle problems of flows through random networks, where we have a random network with nodes communicating via least cost paths to other nodes. We shall show in some models on the completely connected network how the above methodology allows us to prove the convergence of the empirical distribution of edge flows, exhibiting how macroscopic order emerges from microscopic rules.
    2. We shall show how for a wide variety of random trees (uniform random trees, preferential attachment trees arising from a wide variety of attachment schemes, models of trees from Statistical Physics etc) the above methodology shows the convergence of the spectral distribution of the adjacency matrix of theses trees to a limiting non random distribution function.
  2. Scaling limits: For the analysis of critical random graphs, one often finds that properly associated walks corresponding to the exploration of the graph encode a wide array of information (including the size of the maximal components). In this context we shall extend work of Aldous on Erdös Renyi critical random graphs to the context of inhomogeneous random graph models. If time permits we shall describe the connection between these models and the multiplicative coalescent, arising from models of coagulation in the physical sciences.

07 Dec, ISI, 3:30 PM Random walks and Degenerate Random Environments. Tom Salisbury (York University, Toronto, Canada)

At each vertex of the planar square lattice, independently lay down pairs of arrows, heading either north and east (with probability p), or south and west (with probability 1-p). Then perform a simple random walk using the available ?arrows. This is one of a number of related RWRE models we'll consider. An example of the results obtained is that for p close to 1/2 there is an infinite cluster of points that communicate with each other, while for p close to 0 or 1 all such clusters are finite. This is joint work with Mark Holmes (Univ. of Auckland).

26 Oct, ISI, 2:00 PM Strong hydrodynamic limit for asymmetric particle systems on Z. K. Ravishankar (SUNY- New Platz)

We prove almost sure hydrodynamics for a large class of attractive particle systems on Z, when starting from (i) any shock profile (Riemann hydrodynamics), (ii) any general initial profile (Cauchy hydrodynamics). Our results generalize and extend earlier works by Seppalainen (1999) and Andjel et al. (2004). Our constructive approach for (ii) requires (i) for space-time shifted profiles. For this we introduce new ideas, as we can not use the subadditive ergodic theorem, a key tool in previous works.

26 Oct, ISI, 3:30 PM On the One Dimensional Critical "Learning from Neighbors" Model. Antar Bandhyopadyay (Indian Statistical Institute, Delhi)

We consider a model of a discrete time "interacting particle system" on the integer line where infinitely many changes are allowed at each instance of time. In this model each particle/agent can have two colors namely Red (R) or Blue (B). At each instance of time each particle performs an independent but identical coin toss experiment with probability $\alpha$ to decide whether to change its color or not. If the coin lands head then the particle retains its color (this is to be interpreted as a "success"), otherwise it observes the colors and coin tosses of its two nearest neighbors and changes its color only if, among its neighbors and including itself, the proportion of successes of the other color is larger than the proportion of successes of its own color. This produces a Markov chain with infinite state space $\left\{R, B\right\}^{\Zbold}$. This model was studied by Chatterjee and Xu (2004) in the context of diffusion of technologies in a set-up of myopic, memoryless agents. In their work they assume different success probabilities of coin tosses according to the color of the particles. In this work we consider the "critical" case where the success probability, $\alpha$, is the same irrespective of the color of the particle. We show that starting from any initial translation invariant distribution of colors the Markov chain converges to a limit of a single color, i.e., even at the critical case there is no "coexistence" of the two colors at the limit. As a corollary we also characterize the set of all translation invariant stationary laws of this Markov chain. Moreover we show that starting with an i.i.d. color distribution with density $p \in [0,1]$ of one color (say red), the limiting distribution is all red with probability $\pi\left(\alpha, p\right)$ which is continuous in $p$ and for $p$ "small", $\pi(p) > p$. The last result can be interpreted as the model favors the "underdog".

12 Oct, ISI, 3:30 PM Granger Causality for Point Processes. Nedungadi Aatira Gopalakrishnan (Indian Institute of Science, Bangalore)

Time series analysis of multivariate point process plays an important role in the study of multivariate neuronal spike train data. In particular, determining the directionality of neuronal interaction is of interest. For regular time series data, Granger causality has proven to be an effective method for this purpose. However, the basis for Granger causality estimation is autoregressive data modeling, which is not directly applicable to point processes. Various filtering options that have been used to get around this problem distort the properties of point processes. Here we propose a new nonparametric approach to estimate Granger causality directly from the Fourier transforms of realizations of point processes. We validate the method on synthetic spike trains generated by model networks of neurons with known connectivity patterns and then apply it to neurons simultaneously recorded from the thalamus and the primary somatosensory cortex of a squirrel monkey undergoing tactile stimulation.

07 Sep, ISI, 3:30 PM Aldous’s move on cladograms in the diffusion limit. Anita Winter (FAU Erlangen-Nürnberg)

A n-phylogenetic tree is a semi-labeled, unrooted and binary tree with n leaves labeled {1, 2, ..., n} and with n−2 unlabeled internal leaves and positive edge lengths repre- senting the time spans between common ancestors. In biological systematics n-phylogenetic trees are used to represent the revolutionary relationship between n species. If one does focus only on the kingship (that is taking all edge length of unit length), a more precise term is cladogram. In [Ald00] Aldous constructs a Markov chain on cladograms and gives bounds on their mixing time (see also [Sch02]). On the other hand, David Aldous gives in [Ald93] a notion of convergence of cladograms which shows that the uniform cladogram with N leaves and edge length re-scaled by a factor of 1/√N converges to the so-called Brownian continuum random tree (CRT) which is the tree “below” a standard Brownian excursion and can be thought of as the uniform compact real tree. These two results suggest that if we re-scale edge lengths by a factor of 1/√N and speeding up time by a factor of N3/2 the Aldous move on cladograms converges in some sense to a continuous tree-valued diffusion. The main emphasis of the talk is to give first precise statements towards that direction. To make life easier we ignore the labels on the leaves. This allows to code a cladogram with N-leaves as 0-hyperbolic metric spaces which are equipped with a probability measure (assigning mass 1/N to each point representing a leaf ) and use the Gromov-weak topology on spaces of metric measure spaces as introduced in [GPW06].

(Joint work with Leonid Mytnik (Technion, Haifa))

  • [Ald93] David Aldous. The continuum random tree III. Ann. Probab., 21:248–289, 1993.
  • [Ald00] David J. Aldous. Mixing time for a Markov chain on cladograms. Combin. Probab. Comput., 9(3):191–204, 2000.
  • [GPW06] Andreas Greven, Peter Pfaffelhuber, and Anita Winter. Convergence in distribu- tion of random metric measure spaces(the Lambda-coalescent measure tree). appears in PTRF 2009.
  • [Sch02] Jason Schweinsberg. An O(n2 ) bound for the relaxation time of a Markov chain on cladograms. Random Structures Algorithms, 20(1):59–70, 2002.

17 Aug, IISc, 2:30 PM The past of a Markov process given the present. Krishna B. Athreya (IISc, Bangalore and Iowa State University, Ames)

For any discrete state space discrete time irreducible, aperiodic, positive recurrent Markov chain it can be shown that given the present the past converges to a time homogeneous Markov chain? as the present moves forward. In this talk we prove this and discusss generalisations to null recurrent Markov chains,? general state spaces and continuous time. In particular we? show that? for standard Brownian motion conditioned on the present the past over any finite time segment converges to Brownian motion also.An application of this to level crossing will be given.

17 Aug, IISc, 4 PM A large deviations view of guessing and compression Rajesh Sundaresan (IISc, Bangalore)

I will describe the problem of guessing a random string. This arises in the analysis of the strength of secret-key cryptosystems against guessing attacks. The expected number of guesses needed before success grows exponentially with the length of the string. I will discuss this problem's relation to compression, and will then show how some elementary results from large deviations theory help identify the growth rate exponents.

4 Aug, IISc, 4 PM Interacting diffusion models and the effect of size Soumik Pal (University of Washington, Seattle)

Consider a multidimensional diffusion model where the drift and the diffusion coefficients for individual coordinates are functions of the relative sizes of their current value compared to the others. Two such models were introduced by Fernholz and Karatzas as models for equity markets to reflect some well-known empirically observed facts. In the first model, called 'Rank-based', the time-dynamics is determined by the ordering in which the coordinate values can be arranged at any point of time. In the other, named the 'Volatility-stabilized', the parameters are functions of the ratio of the current value to the total sum over all coordinates. We show some remarkable properties of these models, in particular, phase transitions and infinite divisibility. Relationships with existing models of queueing, dynamic spin glasses, and statistical genetics will be discussed. Part of the material is based on separate joint work with Sourav Chatterjee and Jim Pitman.

28 July, ISI, 4 PM Gaussian Minkowski functionals: an overview of infinite dimensional geometry in Wiener space Sreekar Vadlamani (ISI, Bangalore)

Gaussian Minkowski functionals (GMFs) for reasonably smooth subsets of Euclidean spaces, are defined as coefficients appearing in the the Gaussian-tube-formula in finite dimensional Euclidean spaces. The fact that the measure in consideration here is Gaussian, itself makes the whole analysis an infinite dimensional one. Therefore, one might want to generalize the definition of Gaussian Minkowski functionals to the subsets of Wiener space which arise from reasonably smooth (in Malliavin sense) Wiener functionals. As in the finite dimensional case, we shall identify the GMFs in the infinite dimensional case, as the coefficients appearing in the tube formula in Wiener space. Finally, we shall try to apply this infinite dimensional generalization to get results about the geometry of excursion sets of a reasonably large class of random fields defined on a "smooth" manifold.