Graph-based Pólya's urn: completion of the linear case

DOI10.1142/S0219493716600078zbMATH Open1335.60185arXiv1409.7826MaRDI QIDQ2797922FDOQ2797922

Authors: Yuri Lima 

Publication date: 1 April 2016

Published in: Stochastics and Dynamics (Search for Journal in Brave)

Abstract: Given a finite connected graph $G$, place a bin at each vertex. Two bins are called a pair if they share an edge of $G$. At discrete times, a ball is added to each pair of bins. In a pair of bins, one of the bins gets the ball with probability proportional to its current number of balls. Previous works proved that when $G$ is not balanced bipartite, the proportion of balls in the bins converges to a point $w(G)$ almost surely. We prove almost sure convergence for balanced bipartite graphs: the possible limit is either a single point $w(G)$ or a closed interval $mathcalJ(G)$.

Full work available at URL: https://arxiv.org/abs/1409.7826

Recommendations

• A generalized Pólya's urn with graph based interactions: convergence at linearity
• A generalized Pólya's urn with graph based interactions
• Interacting urns on a finite directed graph
• Generalizations of Polya's urn problem
• A new two-urn model

zbMATH Keywords

almost sure convergencestochastic approximation algorithmbalanced bipartite graphsreinforcementgradient-like systemPólya's urn

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Strong limit theorems (60F15) Combinatorial probability (60C05) Dynamics induced by flows and semiflows (37C10)

Cites Work

• Title not available (Why is that?)
• A survey of random processes with reinforcement

Cited In (12)

• Networks of reinforced stochastic processes: probability of asymptotic polarization and related general results
• Lyapunov function for interacting reinforced stochastic processes via Hopfield's energy function
• The trace-reinforced ants process does not find shortest paths
• A generalized Pólya's urn with graph based interactions
• Interacting nonlinear reinforced stochastic processes: Synchronization or non-synchronization
• Interacting urns on a finite directed graph
• Interacting reinforced stochastic processes: statistical inference based on the weighted empirical means
• Networks of reinforced stochastic processes: asymptotics for the empirical means
• Networks of reinforced stochastic processes: a complete description of the first-order asymptotics
• Urns with multiple drawings and graph-based interaction
• A generalized Pólya's urn with graph based interactions: convergence at linearity
• Synchronization of reinforced stochastic processes with a network-based interaction

This page was built for publication: Graph-based Pólya's urn: completion of the linear case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2797922)