We introduce an incidence-based random walk on the edges of a random two-dimensional simplicial complex with a complete $1$-skeleton and independently retained triangular faces. The dynamics combine two transport channels, one mediated by vertices and the other by triangular faces, through an effective transition operator controlled by a mixing parameter $q$. This construction isolates the effects of higher-order connectivity without modifying the underlying pairwise support of the walk. We characterize the model through structural observables, spectral relaxation, stationary localization, and first-passage transport. Our results show that partial face retention generates heterogeneous higher-order connectivity, giving rise to a pronounced transport bottleneck at intermediate face densities. In this regime, the second-largest eigenvalue modulus, the inverse participation ratio of the stationary distribution, and the mean first-passage time all exhibit non-monotonic behavior, reaching their largest values at intermediate face densities. The corresponding first-passage-time distributions reveal an enhanced probability of unusually long trajectories. Together, these results establish a simple framework for investigating how heterogeneous higher-order connectivity reshapes spectral and transport properties beyond pairwise network dynamics.
The navigation time and optimal search strategies deriving from random dynamical processes on binary graphs have been extensively explored and analyzed, being of prominent interest in the network science field. In this work, we study an extension of these topological measures for simplicial complexes: a specific type of geometric and algebraic structures that encapsulates higher-order interactions. Here, the explorability analysis of simplicial complexes has been conducted in terms of the mean first passage times between nodes, i.e. the 0th-order simplices, with the inclusion of a long-range stochastic teleportation term modulated with respect to the local random walk hopping across the various dimensions. We also provide a perturbative approximation scheme recovering the modulation parameter between pure random walk and teleportation mode (for higher-order setting) acting as the expansion parameter.
Diego Febbe, Duccio Fanelli, Gianluca Peri et al.· 0 citations
We investigate random recursive simplicial complexes growing by adding, at each step, a vertex together with a simplex formed by joining the new vertex with a randomly chosen existing simplex. We also add all faces of the new simplex to ensure that the resulting object remains a simplicial complex. If the choice of an existing simplex is uniform among simplices of dimension $<m$, the number $S_d$ of simplices of any admissible dimension $d\leq m$ is an asymptotically self-averaging random variable. This feature allows us to determine the asymptotic growth law of the average of $S_d$ when the number of vertices diverges. We also probe the degree distribution, examine the probabilities of various extreme outcomes, and analyze the characteristics of the first vertex.
Two competitors choose starting vertices for independent, constant-speed random walks, and each site is acquired by its first visitor. We study the spatial geometry of the resulting first-passage location game. On every finite path the optimal strategies are exactly the distributions supported on the central vertices. The proof combines reflecting-boundary harmonic barriers with a parameter-uniform aggregate estimate for product-chain exit probabilities. After diffusive rescaling, the complete two-start payoff landscape converges uniformly to the game between independent reflected Brownian motions. Its unique equilibrium concentrates at the midpoint, with explicit cubic stability. Beyond paths, attaching two leaves to every vertex of a clique of order k produces a 3k-vertex graph on which every exact optimal strategy randomizes over all k clique vertices; for k=2, this is a six-vertex tree with no pure equilibrium. The continuum best response to an endpoint is uniquely determined. A first-passage random-ranking representation relates the finite game to maximal lotteries without identifying it with nonstrategic painting, deterministic Voronoi allocation, or absorbing-trap placement. Parameter-uniform statements follow from analytic arguments or symbolic polynomial identities; identified finite exceptions and numerical enclosures have reproducible certificates.
A vertex-reinforced random walk steps to a neighbour with probability proportional to $1+\beta n^{a}$, where $n$ counts previous visits to that neighbour and $a\in(0,1)$ sets the memory strength. On the rooted $b$-ary tree the exponential growth of the vertex set drives the walk outward while the reinforcement pulls it back. We report a sharp condensation transition of the occupation measure at a finite $\beta_c(a,b)$: below it the occupation spreads and the range grows linearly; above it a single vertex holds an $O(1)$ fraction of the time, stable in the observation time, while the range keeps growing very slowly, at a rate better described by $\log t$ than by any power. We do not find the range to be bounded, and keep this condensation distinct from finite-range localization. Four estimators locate the same threshold, which shows no systematic drift out to $t=3\times10^{7}$. In a frozen environment the walk is reversible, with edge conductances $c_{uv}=w_{u}w_{v}$, $w_{v}=1+\beta n_{v}^{a}$, and measure $\mu_{v}\propto w_{v}\sum_{u\sim v}w_{u}$ describing the condensed core, whose neighbour coupling we test directly. Reversibility places the escape at the frontier within the branching-number criterion for biased walks on trees, predicting $\beta_c\propto b-1$; the measured lines for $b=2,3,4$ collapse under division by $b-1$ to a few percent (bootstrap). The value $a=1/2$ that governs the walk on $\mathbb{Z}$ enters only as the marginal exponent of the condensed profile. Near $\beta_c$ the occupancy is non-self-averaging and bimodal, a coexistence-type phenomenology.
We consider the probability that the convex hull of the first $n$ partial sums of a $d$-dimensional random walk contains the origin. Under symmetric exchangeability of the increments and a general-position assumption, this absorption probability is distribution-free and admits an explicit formula, previously obtained by Kabluchko, Vysotsky and Zaporozhets [Geom. Funct. Anal. 27 (2017)] using characteristic polynomials of hyperplane arrangements. We give a different proof, based on a wall-crossing method which we develop here. Starting from a deterministic configuration of increments, we count the signed permutations for which the convex hull of the corresponding partial sums contains the origin and show that this count remains unchanged under generic deformations of the increments, and hence is the same for all configurations outside a natural exceptional set of measure zero. Evaluating the invariant at a single well-chosen configuration reduces the remaining calculation to the enumeration of permutation records combined with Wendel's theorem. Our method also reproves Wendel's theorem on convex hulls of random points with a sign-flip-invariant joint distribution and, in dimension one, Sparre Andersen's theorem. Finally, we derive new probabilistic representations and recurrence relations for the absorption probabilities of random-walk convex hulls and their random-bridge analogues.
We consider a class of infinite critical tree-indexed random walks on $\mathbb Z$, where the motion of particles is subject to vertex reinforcement. We mainly focus on the strong reinforcement regime, where we expect the process to localize almost surely on two sites. Part of our analysis includes the study of a time-dependent generalized P\'olya urn process, where the number of draws at each step is prescribed by a sequence $(\sigma_n)_{n\ge 1}$ of arbitrary positive integers, and the probability to pick a ball of a given color is proportional to a function of the {\it number} of balls of that color. In particular for bounded sequences $(\sigma_n)_{n\ge 1}$, we recover Rubin's characterization for the fixation of one color.