The edge-reinforced branching random walk on the triangle and generalised balls and bins with positive feedback
Edge-reinforced random walks are processes with reinforcement, on which the effect of branching has not been investigated. Our discrete time model starts with a particle at the vertex of a triangle, initialised with edge-crossing numbers, which branches at a constant rate. The offspring particles, independently of each other, traverse the incident edges at random, with probabilities proportional to the edge-crossing numbers, correspondingly updated at each traversal. Then the process repeats. We show the convergence of the proportions of edge-crossings to a random variable using dynamical systems techniques, and prove that two events have positive probability: when none of the edges is crossed negligibly, and when exactly one is. We show that all edges are crossed infinitely many times and conjecture that no two edges can be negligibly crossed.
This conjecture stems from connections between this model and balls and bins, where balls are added to bins at random, following certain rules. There is positive feedback when the probability of incoming balls choosing a bin with $m$ balls is proportional to a power of $m$, bigger than $1$; no feedback when the power is $1$. In a time-dependent version, the number of balls added at discrete times varies, yielding different regimes of growth. Generalising results known for two bins to any number of bins, we investigate the proportion of balls in each bin, depending on feedback and regime of growth. We focus on the events of monopoly (eventually one of the bins will receive all incoming balls) and dominance (one of the bins gets all but a negligible number of balls). When there is no feedback, neither monopoly nor dominance occur. When feedback is introduced, several regimes are identified, at which dominance and monopoly occur. While at certain regimes monopoly does not occur, we conjecture dominance to always occur.