Random Discrete Structures: Approximations and Applications

Long-term concentration of measure and cut-off

AD Barbour, G Brightwell, M Luczak

2022-10-01

We present new concentration of measure inequalities for Markov chains, generalising results for chains that are contracting in Wa..

PALM THEORY, RANDOM MEASURES AND STEIN COUPLINGS

Louis HY Chen, Adrian Rollin, Aihua Xia

2021-12-01

We establish a general Berry–Esseen type bound which gives optimal bounds in many situations under suitable moment assumptions. By..

On Stein's Factors for Poisson Approximation in Wasserstein Distance with Nonlinear Transportation Costs

Zhong-Wei Liao, Yutao Ma, Aihua Xia

2021-09-28

We establish various bounds on the solutions to a Stein equation for Poisson approximation in the Wasserstein distance with nonlin..

STEIN'S METHOD FOR THE POISSON-DIRICHLET DISTRIBUTION AND THE EWENS SAMPLING FORMULA, WITH APPLICATIONS TO WRIGHT-FISHER MODELS

Han L Gan, Nathan Ross

2021-04-01

We provide a general theorem bounding the error in the approximation of a random measure of interest—for example, the empirical po..

Local limit theorems for occupancy models

AD Barbour, Peter Braunsteins, Nathan Ross

2020-09-27

We present a rather general method for proving local limit theorems, with a good rate of convergence, for sums of dependent random..

The probability of intransitivity in dice and close elections

Jan Hazla, Elchanan Mossel, Nathan Ross, Guangqu Zheng

2020-08-19

We study the phenomenon of intransitivity in models of dice and voting. First, we follow a recent thread of research for n-sided d..

A large sample property in approximating the superposition of i.i.d. finite point processes

Tianshu Cong, Aihua Xia, Fuxi Zhang

2020-07-01

One of the main differences between the central limit theorem and the Poisson law of small numbers is that the former possesses th..

Central moment inequalities using Stein's method

AD Barbour, Nathan Ross, Yuting Wen

2020-01-01

We derive explicit central moment inequalities for random variables that admit a Stein coupling, such as exchangeable pairs, size–..

Exponential and Laplace approximation for occupation statistics of branching random walk

Erol A Pekoz, Adrian Rollin, Nathan Ross

2020-01-01

We study occupancy counts for the critical nearest-neighbor branching random walk on the d-dimensional lattice, conditioned on non..

APPROXIMATING STATIONARY DISTRIBUTIONS OF FAST MIXING GLAUBER DYNAMICS, WITH APPLICATIONS TO EXPONENTIAL RANDOM GRAPHS

Gesine Reinert, Nathan Ross

2019-10-01

We provide a general bound on the Wasserstein distance between two arbitrary distributions of sequences of Bernoulli random variab..

EXTINCTION IN LOWER HESSENBERG BRANCHING PROCESSES WITH COUNTABLY MANY TYPES

Peter Braunsteins, Sophie Hautphenne

2019-10-01

We consider a class of branching processes with countably many types which we refer to as Lower Hessenberg branching processes. Th..

Error bounds in local limit theorems using Stein's method

AD Barbour, Adrian Roellin, Nathan Ross

2019-05-01

We provide a general result for bounding the difference between point probabilities of integer supported distributions and the tra..

Shotgun Assembly of Labeled Graphs

Elchanan Mossel, Nathan Ross

2019-04-01

We consider the problem of reconstructing graphs or labeled graphs from neighborhoods of a given radius $r$r. Special instances of..

Polya urns with immigration at random times

Erol Pekoz, Adrian Rollin, Nathan Ross

2019-02-01

We study the number of white balls in a classical Pólya urn model with the additional feature that, at random times, a black ball ..

Multivariate approximation in total variation using local dependence

AD Barbour, A Xia

2019-01-01

We establish two theorems for assessing the accuracy in total variation of multivariate discrete normal approximation to the distr..

Local approximation of a metapopulation's equilibrium.

AD Barbour, R McVinish, PK Pollett

2018-09-01

We consider the approximation of the equilibrium of a metapopulation model, in which a finite number of patches are randomly distr..

When do wireless network signals appear Poisson?

H Paul Keeler, Nathan Ross, Aihua Xia

2018-08-01

We consider the point process of signal strengths from transmitters in a wireless network observed from a fixed position under mod..

Simulating the component counts of combinatorial structures.

Richard Arratia, AD Barbour, WJ Ewens, Simon Tavaré

2018-07-01

This article describes and compares methods for simulating the component counts of random logarithmic combinatorial structures suc..

Divergence from, and Convergence to, Uniformity of Probability Density Quantiles

Robert G Staudte, Aihua Xia

2018-05-01

We demonstrate that questions of convergence and divergence regarding shapes of distributions can be carried out in a location- an..

MULTIVARIATE APPROXIMATION IN TOTAL VARIATION, I: EQUILIBRIUM DISTRIBUTIONS OF MARKOV JUMP PROCESSES

AD Barbour, MJ Luczak, A Xia

2018-05-01

For integer valued random variables, the translated Poisson distributions form a flexible family for approximation in total variat..

MULTIVARIATE APPROXIMATION IN TOTAL VARIATION, II: DISCRETE NORMAL APPROXIMATION

AD Barbour, MJ Luczak, A Xia

2018-05-01

The paper applies the theory developed in Part I to the discrete normal approximation in total variation of random vectors in Zd ...

Physical-Layer Security in Full-Duplex Multi-User Relay Networks

Saman Atapattu, Nathan Ross, Yindi Jing, Yuanyuan He, Jamie Evans

2018-01-01

This paper studies the relay selection (RS) problem for full-duplex (FD) relay networks with multiple source-destination (SD) pair..

Scaling limits for some random trees constructed inhomogeneously

Nathan Ross, Yuting Wen

2018-01-01

We define some new sequences of recursively constructed random combinatorial trees, and show that, after properly rescaling graph ..

DIRICHLET APPROXIMATION OF EQUILIBRIUM DISTRIBUTIONS IN CANNINGS MODELS WITH MUTATION

Han L Gan, Adrian Rollin, Nathan Ross

2017-09-01

Consider a haploid population of fixed finite size with a finite number of allele types and having Cannings exchangeable genealogy..

JOINT DEGREE DISTRIBUTIONS OF PREFERENTIAL ATTACHMENT RANDOM GRAPHS

Erol Pekoz, Adrian Rollin, Nathan Ross

2017-06-01

We study the joint degree counts in linear preferential attachment random graphs and find a simple representation for the limit di..

Wireless Network Signals With Moderately Correlated Shadowing Still Appear Poisson

Nathan Ross, Dominic Schuhmacher

2017-02-01

We consider the point process of signal strengths emitted from transmitters in a wireless network and observed at a fixed position..

Stronger Wireless Signals Appear More Poisson

Paul Keeler, Nathan Ross, Aihua Xia, Bartlomiej Blaszczyszyn

2016-12-01

Keeler et al. recently derived approximation and convergence results, which imply that the point process formed from the signal st..

GENERALIZED GAMMA APPROXIMATION WITH RATES FOR URNS, WALKS AND TREES

Erol A Pekoz, Adrian Rollin, Nathan Ross

2016-05-01

We study a new class of time inhomogeneous Pólya-type urn schemes and give optimal rates of convergence for the distribution of th..

NORMAL APPROXIMATION FOR STATISTICS OF GIBBSIAN INPUT IN GEOMETRIC PROBABILITY

Aihua Xia, JE Yukich

2015-12-01

This paper concerns the asymptotic behavior of a random variable Wλ resulting from the summation of the functionals of a Gibbsian ..