Upper Expected Meeting Times for Interdependent Stochastic Agents
Marco Sangalli, Erik Quaeghebeur, Thomas Krak · 2025
Read Upper Expected Meeting Times for Interdependent Stochastic Agents by Marco Sangalli, Erik Quaeghebeur, Thomas Krak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-07626.txt.
Introduction
Marco Sangalli, Erik Quaeghebeur, and Thomas Krak bound the time until two wandering agents first meet, in a 2025 paper. The agents move at random but choose their moves from a set of allowed actions, and the observer does not know which choices they make.
That uncertainty is modeled with imprecise Markov chains, which track ranges of chances rather than single values. Known algorithms then give exact bounds on the expected meeting time, tight for the stated uncertainty. The paper works the two-agent case in full. It also sketches the step to more agents, where counting explodes, and shows how symmetry in the setup can tame part of that growth.
Catalog record
| CREATOR | Marco Sangalli, Erik Quaeghebeur, Thomas Krak |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-07626
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Upper Expected Meeting Times for Interdependent Stochastic Agents Marco Sangalli, Erik Quaeghebeur, Thomas Krak Abstract We analyse the problem of meeting times for interdependent stochastic agents: random walkers whose behaviour is stochastic but controlled by their selections from some set of allowed actions, and the inference problem of when these agents will be in the same state for the first time. We consider the case where we are epistemically uncertain about the selected actions of these agents, and show how their behaviour can be modelled using imprecise Markov chains. This allows us to use results and algorithms from the literature, to exactly compute bounds on their meeting time, which are tight with respect to our epistemic uncertainty models. We focus on the two-agent case, but discuss how it can be naturally extended to an arbitrary number of agents, and how the corresponding combinatorial explosion can be partly mitigated by exploiting symmetries inherent in the problem. 1 Introduction Markov chains are a cornerstone of stochastic modelling, finding applications in fields as diverse as statistical physics, queuing theory, network science, and distributed computing. A fundamental question in this context is the hitting time : the first moment at which a stochastic process enters a given set of states [ 15 ] . When considering multiple independent Markov chains evolving on the same finite state space, a natural extension is the meeting time , defined as the first moment at which all chains occupy the same state. Equivalently, this can be viewed as a hitting-time problem on the Cartesian product of their state spaces, with the target set being the diagonal [ 15 , 13 , 12 ] . In this work, we generalize this problem to that of computing the expected meeting time of what we call interdependent stochastic agents . Broadly, these are random walkers on some shared state space, whose behaviour is stochastic, but controlled by their selection of transition probabilities from some set representing their allowed actions. Crucially, we allow the selections that these agents make to depend on the state(s) of the other agent(s) in the system; this induces the “interdependency”. On top of this construction, we consider the case where we are epistemically uncertain about the selections that the agents will use, and show that meaningful and conservative estimates for the expected meeting time can still be computed in this setting. We focus in particular on three such uncertainty models: the degenerate belief, which simply describes the case where we do know the selections exactly; the vacuous belief, in which we are fully ignorant; and the degenerate-vacuous mixture, which combines these other models and may be particularly useful in some practical settings. We show how the vacuous belief model allows us to describe the joint behaviour of the agents as an imprecise Markov chain [ 9 , 8 , 3 ] on their product space. This allows us to leverage known results from the literature, and in particular iterative algorithms for computing upper- and lower expected hitting times [ 11 ] , to exactly solve the expected meeting time problem in this setting. We largely focus on the two-agent case, but show how the formalization can be naturally extended to an arbitrary number of agents using an m -fold product construction. Moreover, we discuss how we can partly mitigate the combinatorial explosion of this problem, by quotienting the (exponentially large) product space over the symmetries obtained by permuting the order of the agents. The remainder of this paper is structured as follows. Section 2 reviews preliminary notions of precise and imprecise Markov chains, known theory about hitting- and meeting times, and presents an extension of Krak’s characterizations and algorithms [ 10 ] to hold under weaker conditions than their original assumptions. Section 3 formalizes the setting of two interdependent stochastic agents with epistemic uncertainty models for their selections, and the characterization of meeting times in terms of the hitting times of an imprecise Markov chain on the product space. In Section 4 we extend the theory to an arbitrary number of interdependent stochastic agents, and Section 5 concludes the paper and gives directions for future work. 2 Preliminaries This section introduces the basic concepts of stochastic processes and Markov chains [ 15 ] , hitting and meeting times for Markov chains [ 15 , 6 , 7 ] and imprecise Markov chains [ 9 , 8 , 3 , 11 ] . 2.1 Stochastic Processes and Markov Chains Let us denote by \mathbb{N} the set of positive integers and define \mathbb{N}_{0}:=\mathbb{N}\cup\{0\} . Let \mathcal{Z} be a finite state space of cardinality N\geq 2 . A discrete-time stochastic process on \mathcal{Z} is a sequence of \mathcal{Z} –valued random variables (Z_{n})_{n\in\mathbb{N}_{0}} , and we write \mathbb{P}_{Z} for its associated probability measure. Throughout, we use the notations “ (Z_{n}) ” and “ \mathbb{P}_{Z} ” interchangeably to refer to this process. The process (Z_{n}) is called a Markov chain if, for every n\in\mathbb{N}_{0} and every z_{0},\dots,z_{n+1}\in\mathcal{Z} , \mathbb{P}_{Z}\bigl(Z_{n+1}=z_{n+1}\mid Z_{0}=z_{0},\dots,Z_{n}=z_{n}\bigr)=\mathbb{P}_{Z}\bigl(Z_{n+1}=z_{n+1}\mid Z_{n}=z_{n}\bigr). The chain (Z_{n}) is called (time-) homogeneous if the one-step transition probabilities do not depend on n . Equivalently, there exists a single matrix T=(T(z,z^{\prime}))_{z,z^{\prime}\in\mathcal{Z}}, with T(z,z^{\prime})=\mathbb{P}_{Z}\bigl(Z_{n+1}=z^{\prime}\mid Z_{n}=z\bigr)\quad\text{for all }n\in\mathbb{N}_{0}, and each row of T summing to unity. Similarly, a non-homogeneous Markov chain (Z_{n}) is identified by a family of transition matrices (T_{n}) . 2.2 Hitting and Meeting Times in the Precise Setting Hitting Times. Let (Z_{n}) be a homogeneous Markov chain on \mathcal{Z} with transition matrix T=(T(z,z^{\prime}))_{z,z^{\prime}\in\mathcal{Z}} . For any target set A\subset\mathcal{Z} , define the hitting time \tau_{A}=\inf\{\,n\geq 0:Z_{n}\in A\}\,\in\mathbb{N}_{0}\cup\{+\infty\}. This random variable represents the number of steps the process needs to first reach A . Conditioned on the chain starting at z\in\mathcal{Z} , the expected hitting time is h_{A}^{T}(z)=\mathbb{E}_{\mathbb{P}_{Z}}\bigl[\tau_{A}\mid Z_{0}=z\bigr]. The quantity h^{T}_{A}(z) represents the expected number of steps that the process (Z_{n}) , starting in z\in\mathcal{Z} , will take before reaching the set A . Theorem 2.1 ( [ 15 ] ) Let A\subset\mathcal{Z} and let (Z_{n}) be a homogeneous Markov chain with transition matrix T . The vector of expected hitting times h^{T}_{A}=(h_{A}^{T}(z))_{z\in\mathcal{Z}} is the minimal non-negative solution to the following system of equations: \begin{cases}h^{T}_{A}(z)=0&\text{ for all $z\in A$,}\\ h^{T}_{A}(z)=1+\sum_{z^{\prime}\in\mathcal{Z}}T(z,z^{\prime})h^{T}_{A}(z^{\prime})&\text{ for all $z\notin A$,}\end{cases} (1) which can be rewritten as h^{T}_{A}=\mathbbm{1}_{A^{c}}+\mathbbm{1}_{A^{c}}\cdot Th^{T}_{A}, (2) where \mathbbm{1} is the indicator function and \cdot represents the element-wise multiplication. Meeting Times. Consider a joint stochastic process (X_{n},Y_{n})_{n\in\mathbb{N}_{0}} on \mathcal{Z}^{2}:=\mathcal{Z}\times\mathcal{Z} . Define the meeting time for X_{n} and Y_{n} as \mu=\inf\{\,n\geq 0:X_{n}=Y_{n}\}\,\in\mathbb{N}_{0}\cup\{+\infty\}. If the joint process starts at (X_{0},Y_{0})=(x,y) then the expected meeting time is m{(x,y)}:=\mathbb{E}_{\mathbb{P}_{(X,Y)}}\bigl[\mu\mid X_{0}=x,\;Y_{0}=y\bigr]. (3) The quantity m{(x,y)} represents the expected number of steps that the two processes, when starting in x and y respectively, will take before meeting. In the case where the joint process (X_{n},Y_{n}) is obtained as the independent product of two homogenous Markov chains (X_{n}) and (Y_{n}) with transition matrices T and S , respectively, the expected meeting time has a particularly nice characterisation. Theorem 2.2 ( [ 6 , 7 ] ) Let (X_{n}) and (Y_{n}) be two homogenous Markov chains with transition matrices T and S respectively. The matrix of expected meeting times m=(m{(x,y)})_{x,y\in\mathcal{Z}} is the minimal non-negative solution to the following system of equations: \begin{cases}m{(x,x)}=0&\text{for all $x\in\mathcal{Z}$,}\\ m{(x,y)}=1+\sum_{x^{\prime},y^{\prime}\in\mathcal{Z}}T{(x,x^{\prime})}S{(y,y^{\prime})}m{(x^{\prime},y^{\prime})}&\text{for all $x\neq y$,}\end{cases}