We study locally interacting processes in discrete time, often called probabilistic cellular automata, indexed by locally finite graphs. For infinite regular trees and certain generalized Galton–Watson trees, we show that the marginal evolution at a single vertex and its neighborhood can be characterized by an autonomous stochastic recursion referred to as the local-field equation. This evolution can be viewed as a nonlinear or measure-dependent chain, but the measure dependence arises from the symmetries of the underlying tree rather than from any mean-field interactions. We discuss applications to simulation of marginal dynamics and approximations of empirical measures of interacting chains on several generic classes of large-scale finite graphs that are locally tree-like. In addition to the symmetries of the tree, a key role is played by a second-order Markov random field property, which we establish for general graphs along with some other novel Gibbs measure properties.
Lacker, Daniel, Ramanan, Kavita, Wu, & Ruoyu (2026). Marginal dynamics of probabilistic cellular automata on trees. Queueing Systems. https://doi.org/10.1007/s11134-026-09985-2
Lacker, et al. “Marginal dynamics of probabilistic cellular automata on trees.” Queueing Systems, 2026. doi:10.1007/s11134-026-09985-2.
@article{Lacker2026,
title = {Marginal dynamics of probabilistic cellular automata on trees},
author = {Lacker and Daniel and Ramanan and Kavita and Wu and Ruoyu},
journal = {Queueing Systems},
year = {2026},
doi = {10.1007/s11134-026-09985-2},
url = {http://link.springer.com/openurl/fulltext?id=doi:10.1007/s11134-026-09985-2}
}
We introduce several dynamic models of sources of “posts” publishing them on a “newsfeed” in e.g. some social media. All of them have a product-form stationary distribution. We define four metrics relevant to these newsfeeds and compute...
We study a restricted version of the Erlang-R queueing model that has both server and space constraints, in which the space restriction is administered by two types of admission policies: blocking or holding in a pre-entrant queue. This...
Single-server queues with customer abandonment arise in call centers and other service systems, yet their steady-state performance is analytically tractable only in special cases. We develop Robust Queueing approximations for the mean...
Semimartingale reflecting Brownian motions (SRBMs) are an integral part of queueing theory. Fluid paths are a standard tool for demonstrating positive recurrence of SRBMs, and their convergence provides both necessary and sufficient...
We study a non-stationary state-dependent Hawkes single-server queueing model with both time-varying arrival and service rates, under the first-come first-served discipline. The arrival process is a Hawkes process with a time-varying...