ISI logo

Lectures on Probability and Stochastic Processes X

Indian Institute of Science
December 13 - 16, 2015

IISc logo

Short talks:

13 Dec Slotted Aloha on a sensor field Amitabha Bagchi
We consider a set of sensors placed on integer points of a $\sqrt{n} \times \sqrt{n}$ torus. Time is discrete. At each time instant each sensor receives a new data item from the environment with probability $\lambda$. At each time instant each sensor whose buffer is non-empty transmits, with probability p, the packet at the head of the buffer into the environment where it is collected by a data mule that traverses the entire field in one time unit. However the transmission is considered failed if one of the 4 neighbors of the sensor also transmits in the same time slot. This process forms a Markov Chain, but the question of what the stationary distribution of this Markov Chain is leads to the question of how close this stationary distribution is to a product distribution. Answering the latter question allows us to use what we know about site percolation to study this scenario.

13 Dec Limit theorems for two color balanced irreducible urn models Amites Dasgupta
We review the strong and weak laws for urn models. From the possible cases of the weak law we try to understand the plausible versions of the large deviation results in this context.

13 Dec A question about branching annihilating random walks Anish Sarkar
Consider a system of particles which each particle branches to its nearest neighbours with probability $\delta \in (0,1) $ and performs a random walk with probability $ 1- \delta $. If two particles land up at the same point they annihilate each other. If $ \delta $ is small and we start with one particle, it can be shown that there no particle survive. Interesting question is to study whether there exists any phase where the particle survive.

14 Dec Dense Graph Limits defined by a kernel and sequence of dependent points Siva Athreya
I will discuss convergence to a graph limit of a sequence of random graphs defined by a suitable kernel and a dependent sequence of points; this extends a well-known result for i.i.d. sequences which is basic in graph limit theory. I will present an open problem at the end of the discussion.

14 Dec Random Doubly Stochastic Matrices via Sinkhorn's Iterative Normalization Procedure Navin Kashyap
Consider a normalization procedure on an $n \times n$ positive matrix $A$ described as follows: first normalize the rows of $A$ (by dividing each row by its row sum) to get a stochastic matrix $A'$, and then normalize the columns of $A'$ to obtain a matrix $B = \phi(A)$. Iterating this procedure starting with $A_0 = A$ yields a sequence of matrices $A_k = \phi(A_{k-1}), k = 1,2,3,\ldots$ . It was shown by Sinkhorn in 1964 that for an arbitrary positive matrix $A$, the sequence of matrices $A_k$ obtained by this procedure always converges to a doubly stochastic matrix $D(A)$. The question we ask is: if start with a random positive matrix $A$, whose entries are chosen i.i.d. from some probability distribution, what can we say about the probability distribution of $D(A)$? In particular, is there a choice of distribution for the i.i.d. entries of $A$ that results in $D(A)$ being uniformly distributed over the set of all $n \times n$ doubly stochastic matrices (the Birkhoff polytope)? This question remains open, and we report on what little is known about it. This is joint work with Manjunath Krishnapur.

14 Dec De-Preferential Attachment Random Graphs Antar Bandyopadhyay
In this short talk we will introduce a new model of a growing sequence of random graphs where a new vertex is less likely to join to an existing vertex with high degree and more likely to join to a vertex with low degree. In contrast to the well known preferential attachment random graphs where higher degree vertices are preferred, we will call our model de-preferential attachment random graph model. We will consider two specific models of "de-preferential attachment schemes" and show that the asymptotic degree distributions have thin tails. We will also show that for a fixed vertex $v$, the degree grows as a power of $\sqrt{\log n}$. We will end the talk by indicating the difficulties in generalizing the results when each new vertex can join to $m > 1$ many existing vertices and state an open problem in this context.

[This is a joint work with Subhabrata Sen, Stanford University].

16 Dec Persistent diagrams of point processes. Yogeshwaran D.
Persistent diagram is a point process in the plane that encodes information about birth and death of topological features in spaces growing with time. I shall look at the example when the space is obtained as follows : At each time 't', the space is union of balls of radius 't' centered at the points of a point process on the plane (for simplicity). I shall describe basic results and questions regarding the persistent diagram of this (random) model of growing spaces.

16 Dec Extremes of Gaussian free field on transient graphs Rajat Hazra
In this talk we discuss some of the problems related to the maximum of Gaussian free field. The case of the integer lattice is well understood now. We specialise to some fractal graphs like Sierpinski carpets and discuss the technical difficulties that arise in these models.

16 Dec Randomised attacks on passwords Rajesh Sundaresan
The passwords we choose are often weak and susceptible to statistical attacks. For a particular model on the choice of passwords, I will suggest a natural Markov chain Monte Carlo method of attack. We do not yet know if the proposed attack is asymptotically optimal.

16 Dec Stochastic Sandpile and Related Models Riddhipratim Basu
In statistical physics, Stochastic Sandpile Model is a canonical example of the phenomenon of self-organised criticality, where a system is attracted by itself to a critical state. Unlike the (deterministic) Abelian Sandpile Model, mathematically rigorous understanding of the Stochastic Sandpile Model is rather limited. We shall discuss this and some related models and present a few important open questions.


15 Dec Branching Process with Competition Ranbir Singh
We consider a scenario where k different organisation(involved in same business) competing each other via advertising their products etc. on social networking site. We model this process as continuous time multitype Markovian branching process. The theory of branching processes is very rich. The standard branching theory talks about the extinction/survival of entire population together. However one may be interested in survival/extinction of some type(s) of population not all; as in our case. In our model with capture competition via time-line visibility; say if content of interest is in first 'm' time line level. We discuss the conditions under which survival/extinction happens.

15 Dec Problems related to Polling systems (Bunching of buses) M. Venkateshwara Rao K.
In bus transportation system the time gap between two successive buses is called headway. If the headways are small and the random variations (e.g., number using the facility, traffic etc.,) in the system is large, two consequent buses might start traveling together after a certain point in their journey. This is called bus bunching. Bus bunching results in inefficient service. We model the bus bunching problem as a multiple server polling system with fluid queues under gated service discipline. We obtain some initial results on optimal headway policies using Markov Decision Process (MDP) based techniques.

15 Dec Fractional Brownian markets with time-varying volatility Ananya Lahiri
Diffusion processes driven by Fractional Brownian motion (FBM) have often been considered in modeling stock price dynamics in order to capture the long range dependence of stock price observed in reality. Option prices for such models are obtained by Necula (2002) under constant drift and volatility. We obtain option prices under time varying volatility model. The expression depends on volatility and the Hurst parameter in a complicated manner. Properties of estimators of volatility and of Hurst parameter have been studied separately before. Using those results we derive a central limit theorem for the quadratic variation as an estimator for volatility.

15 Dec Polynomial generalizations of the sample variance-covariance matrix when $pn^{-1} \to 0$ Monika Bhattacharjee

Let $\{Z_{u} = ((\varepsilon_{u,i,j}))_{p \times n}\}$ be random matrices where $\{\varepsilon_{u,i,j}\}$ are independently distributed. Suppose $\{A_{i}\}$, $\{B_{i}\}$ are non-random matrices of order $p\times p$ and $n \times n$ respectively. Suppose $p \to \infty$, $n = n(p) \to \infty$ and $p/n \to 0$. Consider all $p\times p$ random matrix polynomials constructed from the above matrices of the form $\mathbb{P} = \big(\prod_{i=1}^{k_l}n^{-1}A_{t_{i}}$ $Z_{j_{i}} B_{s_{i}}Z_{j_{i}}^{*} \big)A_{t_{k_l+1}}$ and the corresponding centering polynomials $\mathbb{G}=\big(\prod_{i=1}^{k_l}n^{-1}\text{Tr}\left(B_{s_{i}}\right)\big)$ $\prod_{i=1}^{k_l+1}A_{t_{i}}$. We show that under appropriate conditions on the above matrices, the variables in the non-commutative $*$- probability space $\mathcal{U}_{p} = \text{Span}\left\{ (n/p)^{1/2}(\mathbb{P} - \mathbb{G})\right\}$ with state $p^{-1}E\text{Tr}$ converge. Also the limiting spectral distribution (LSD) of any self-adjoint polynomial from the above space exists almost surely and the limit can be expressed in terms of, semi-circular, circular and other families and, limits of $n^{-1}\text{Tr}(B_{i})$, $n^{-1}\text{Tr}(B_{i}B_{j})$ and non-commutative limit of $\{A_i: i \geq 1, \varphi_p=p^{-1}\text{Tr}\}$. These LSD results generalize fully the results already known for $\sqrt{np^{-1}}(n^{-1}B^{1/2}_{1}ZB_{2}Z^{*}B^{1/2}_{1}-n^{-1}\text{Tr}(B_2)B_{1})$.

This is a joint work with Arup Bose.

15 Dec Branching Random Walks, Stable Point Processes, and Regular Variation Ayan Bhattacharya
Strictly stable point processes were introduced and characterized by Davydov, Molchanov and Zuyev (2008). We obtain a sufficient condition for such a point process to be in the superposition domain of attraction of such a point process. This sufficient condition is then used to compute an explicit representation of the weak limit of a sequence of point processes induced by a branching random walk with jointly regularly varying displacements. We show that a prediction of Brunet and Derrida (2011) and a result of Durrett (1983) remain valid in this more general setup. This is a joint work with Rajat Subhra Hazra and Parthanil Roy