CMS 75th+1 Anniversary Summer Meeting

Ottawa, June 7 - 11, 2021


Applied Probability and Stochastic Processes
Org: Rafal Kulik and Aaron Smith (Ottawa)

ALEXANDRE BOUCHARD, University of British Columbia
Approximation of intractable integrals using non-reversibility and non-linear distribution paths  [PDF]

In the first part of the talk, I will present an adaptive, non-reversible Parallel Tempering (PT) allowing MCMC exploration of challenging problems such as single cell phylogenetic trees. A sharp divide emerges in the behaviour and performance of reversible versus non-reversible PT schemes: the performance of the former eventually collapses as the number of parallel cores used increases whereas non-reversible benefits from arbitrarily many available parallel cores. These theoretical results are exploited to develop an adaptive scheme to efficiently optimize over annealing schedules.

In the second half, I will talk about the global communication barrier, a fundamental limit shared by both reversible and non-reversible PT methods, and on our recent work that leverage non-linear annealing paths to provably and practically break that barrier.

My group is also interested in making these advanced non-reversible Monte Carlo methods easily available to data scientists. To do so, we have designed a Bayesian modelling language to perform inference over arbitrary data types using non-reversible, highly parallel algorithms.


- Non-Reversible Parallel Tempering: a Scalable Highly Parallel MCMC Scheme. Saifuddin Syed, Alexandre Bouchard-Côté, George Deligiannidis, Arnaud Doucet.

- Software:

HAOSUI DUANMU, University of California, Berkeley
Mixing and Hitting Times for General Markov Processes  [PDF]

Nonstandard analysis, a powerful machinery derived from mathematical logic, has had many applications in probability theory as well as stochastic processes. Nonstandard analysis allows construction of a single object—a hyperfinite probability space—which satisfies all the first order logical properties of a finite probability space, but which can be simultaneously viewed as a measure-theoretical probability space via the Loeb construction. As a consequence, the hyperfinite/measure duality has proven to be particularly in porting discrete results into their continuous settings.

In this talk, for every general-state-space discrete-time Markov process satisfying appropriate regularity conditions, we construct a hyperfinite Markov process which has all the basic order logical properties of a finite Markov process to represent it. We show that the mixing time and the hitting time agree with each other up to some multiplicative constants for discrete-time general-state-space reversible Markov processes satisfying certain condition, hence extending a well-known result of Yuval Peres and Perla Sousi.

PHILIP ERNST, Rice Statistics
Quickest real-time detection of a Brownian coordinate drift  [PDF]

Consider the motion of a Brownian particle in two or more dimensions, whose coordinate processes are standard Brownian motions with zero drift initially, and then at some random/unobservable time, one of the coordinate processes gets a (known) non-zero drift permanently. Given that the position of the Brownian particle is being observed in real time, the problem is to detect the time at which a coordinate process gets the drift as accurately as possible. We solve this problem in the most uncertain scenario when the random/unobservable time is (i) exponentially distributed and (ii) independent from the initial motion without drift. The solution is expressed in terms of a stopping time that minimizes the probability of a false early detection and the expected delay of a missed late detection. To our knowledge this is the first time that such a problem has been solved exactly in the literature. This is joint work with Goran Peskir (University of Manchester).

On ordered beta distributions and their applications  [PDF]

Ordered beta distribution can be constructed by taking independent beta random variables $X_1,...,X_n$ and conditioning on the event $X_1<X_2<...<X_n$. Such distributions were introduced recently in operations research literature in connection with the following two problems: (i) dynamic pricing with demand learning and (ii) finding optimal bidding policies in a name-your-own-price (NYOP) product markets. In this presentation we will first talk about the above two problems and the methods used to solve them; then we will discuss various properties of ordered beta distributions and we will conclude by presenting two efficient numerical algorithms for working with ordered beta distributions.

FLORIAN MAIRE, Université de Montréal
Weak Peskun ordering for approximate MCMC comparison  [PDF]

Despite the popularity of Markov chain Monte Carlo methods (MCMC) in Bayesian statistics and elsewhere, very few tools are available to establish a theoretical comparison between two (or more) competing MCMC algorithms. The Peskun ordering (Peskun, 1973) is well known for achieving this task. However, showing that a Markov kernel dominates another one (in the Peskun sense) is usually a strenuous exercise and since the Peskun ordering is only a partial ordering, two kernels need not be ordered. In this work, we propose a weaker version of the Peskun ordering which is more widely applicable and easier to establish, and this, at the price of giving only approximate comparison results. This weak Peskun ordering is applied to give elements of answers to two recent questions in the MCMC literature, namely when does a non-reversible Metropolis random walk dominate a reversible one and when does a locally-weighted Gibbs sampler dominate a random-scan Gibbs sampler.

TAKASHI OWADA, Purdue University
Convergence of persistence diagram in the subcritical regime  [PDF]

The objective of this work is to examine the asymptotic behavior of persistence diagrams associated with \v{C}ech filtration. A persistence diagram is a graphical descriptor of a topological and algebraic structure of geometric objects. We consider \v{C}ech filtration over a scaled random sample $r_n^{-1}\mathcal X_n = \{ r_n^{-1}X_1,\dots, r_n^{-1}X_n \}$, such that $r_n\to 0$ as $n\to\infty$. We treat persistence diagrams as a point process and establish their limit theorems in the subcritical regime: $nr_n^d\to0$, $n\to\infty$. In this setting, we show that the asymptotics of the $k$th persistence diagram depends on the limit value of the sequence $n^{k+2}r_n^{d(k+1)}$. If $n^{k+2}r_n^{d(k+1)} \to \infty$, the scaled persistence diagram converges to a deterministic Radon measure almost surely in the vague metric. If $r_n$ decays faster so that $n^{k+2}r_n^{d(k+1)} \to c\in (0,\infty)$, the persistence diagram weakly converges to a limiting point process without normalization. Finally, if $n^{k+2}r_n^{d(k+1)} \to 0$, the sequence of probability distributions of a persistence diagram should be normalized, and the resulting convergence will be treated in terms of the $\mathcal M_0$-topology.

ZBIGNIEW PALMOWSKI, Wroclaw University of Science and Technology
On the renewal theorem for maxima on trees  [PDF]

We consider the distributional fixed-point equation: \[R \stackrel{\mathcal{D}}{=} Q \vee \left( \bigvee_{i=1}^N C_i R_i \right), \] where the $\{R_i\}$ are i.i.d. copies of $R$, independent of the vector $(Q, N, \{C_i\})$, where $N \in \mathbb{N}$, $Q, \{C_i\} \geq 0$ and $P(Q > 0) > 0$. By setting $W = \log R$, $X_i = \log C_i$, $Y = \log Q$ it is equivalent to the high-order Lindley equation \[W \stackrel{\mathcal{D}}{=} \max\left\{ Y, \, \max_{1 \leq i \leq N} (X_i + W_i) \right\}.\] It is known that under Kesten assumptions, \[P(W > t) \sim H e^{-\alpha t}, \qquad t \to \infty,\] where $\alpha>0$ solves the Cram\'er-Lundberg equation $E \left[ \sum_{j=1}^N C_i ^\alpha \right] = E\left[ \sum_{i=1}^N e^{\alpha X_i} \right] = 1$. The main goal of this paper is to provide an explicit representation for $P(W > t)$, which can be directly connected to the underlying weighted branching process where $W$ is constructed and that can be used to construct unbiased and strongly efficient estimators for all $t$. Furthermore, we show how this new representation can be directly analyzed using Alsmeyer's Markov renewal theorem, yielding an alternative representation for the constant $H$. We provide numerical examples illustrating the use of this new algorithm. This is a joint work with Bojan Basrak, Michael Conroy and Mariana Olvera-Cravioto.

TOM SALISBURY, York University
Random walk in degenerate random environments  [PDF]

Classical work on RWRE assumes uniform ellipticity of the environments, so the walker always has available the maximal number of directions to move in. But interesting questions arise when this condition is relaxed, adding an aspect of percolation to the analysis. I will describe a number of results for such models (joint with Mark Holmes [Melbourne]), including a recent shape theorem for the set of accessible sites in what is called the orthant model.

A new shape of extremal clusters for certain stationary semi-exponential processes with moderate long range dependence  [PDF]

Extremal clusters of stationary processes can be quite intricate if the process has long memory affecting its tails. They can become random fractals, taking the shape of the stable regenerative set for certain stationary infinitely divisible processes with subexponential tails, including both power-like tails, and certain lighter tails, of which lognormal-like tails are an example. In this work we show that if the tails of the process are even lighter, specifically semi-exponential-like tails, then a new shape of extremal clusters arises, in which each stable regenerative set supports a random panoply of varying extremes.

The talk is based on joint work with Zaoli Chen.

YI SHEN, University of Waterloo
Random topology in soft-thresholded Gaussian models  [PDF]

The soft-thresholded Gaussian model have been developed in biostatistics with applications in brain imaging. It has a Bayesian structure, and hence requires a rule to choose an appropriate prior distribution. This often means choosing the height of the threshold according to known information, for example, the number of active areas, which corresponds to the number of connected components of the excursion set above the threshold. In this talk we discuss the recent results that we obtained concerning the distribution of such a number. More precisely, for certain Gaussian random fields, when the threshold tends to infinity and the searching area expands with a matching speed, both the location of the excursion sets and the location of the local maxima above the threshold will converge weakly to a Poisson point process. We will further discuss the possibility to approximate these locations when the threshold is high but not extremely high, by studying the local behavior of the critical points above the threshold of the random field. This work provides theoretical support to predict the number of active areas in the brain when using a particular threshold. This is a joint work with Jian Kang, Paul Marriott and Weinan Qi.

AHMED SID-ALI, Carleton University
Large-Scale and Large-Time Behaviour of Finite-State Mean-Field Interacting Particle Systems on Block-structured Networks  [PDF]

Since Kac’s and McKean’s seminal works, the mean-field theory has been widely exploited to study the time evolution of large stochastic interacting particle systems. In the classical homogeneous setting with complete interaction graphs, the big picture is well understood, and various asymptotic results have been established. Though such assumptions are reasonable in statistical physics, it might no longer be the case when considering other applications. Therefore, it is of interest to study systems where the homogeneity and/or the complete interaction assumption are no more relevant. In this talk, we take one direction towards heterogeneity by considering systems in a multi-population paradigm. Namely, we present a model for block-structured networks with dynamically changing multi-colors nodes where the interactions are described through local empirical measures. Two levels of heterogeneity are considered: between and within the blocks. We then look at the large-scale and large-time asymptotics of the system. We first present, under original regularity conditions, a bunch of limiting results in the $N\rightarrow\infty$ asymptotics: Propagation of chaos, laws of large numbers, and large deviation principles for the vectors of empirical measures and the empirical processes together with the LDP of the corresponding unique invariant measure. We will then see how to exploit the latter results to investigate the large-time behavior of the empirical process vector by relying on the Freidlin-Wentzell theory and the work of \text{Hwang and Sheu}. In particular, we present some metastable phenomena arising at large $N$ and large $t$ when the limiting McKean-Vlasov system contains multiple $\omega$-limit sets.

YIZAO WANG, University of Cincinnati
Recent advances on Karlin models  [PDF]

This talk presents an overview on recent developments of the so-called Karlin models, which originally were introduced as an infinite urn scheme and the distribution on the urns is with a regularly-varying tail. Driven by an underlying random partition, the Karlin models present a new type of long-range dependence for stationary processes.

The talk will briefly present several recent advances on the Karlin models, and highlight on two recent results. First, the dependence structure of the scaling limits of the Karlin models can be naturally extended to set-indexed stable (including Gaussian) random fields, including and generalizing a few well-known manifold-indexed random fields. Second, a seemingly different aggregation model is introduced and shown to have the same scaling limit as the Karlin models driven by random partitions studied earlier in the literature.

The talk is based on several joint works with Olivier Durieu, Zuopeng Fu, Gennady Samorodnitsky, Yi Shen, and Na Zhang.

QUAN ZHOU, Texas A&M University
Mixing of local Metropolis-Hastings algorithms for variable selection  [PDF]

Yang et al. (2016) proved that the symmetric random walk Metropolis-Hastings algorithm for Bayesian variable selection is rapidly mixing under mild high-dimensional assumptions. In this work, we introduce a novel Metropolis-Hastings algorithm, which still proposes new states via add-delete-swap moves but has a much faster mixing time independent of the number of covariates. The key idea is to use a locally informed proposal scheme with bounded weights. Motivated by the theoretical analysis of our algorithm, we further propose a method called "two-stage drift condition" for studying convergence rates of Markov chains on general state spaces. Joint work with J. Yang, D. Vats, G. Roberts and J. Rosenthal.

© Canadian Mathematical Society :