Biased random walk on a locally infinite Galton-Watson tree
summary
The gist
We propose a new variant of a biased random walk on a Galton-Watson tree, in which some vertices have infinitely many children…
In short
The paper studies a biased random walk on a tree where some nodes have infinitely many children. It proves that the speed of this walk exists for any bias $\beta > 0$ and converges to a limit as the tree structure becomes more complex. Furthermore, it establishes that this speed is differentiable with respect to the bias parameter and is strictly increasing under certain conditions.
Key concepts
- Speed of the Random Walk
- The speed measures how fast the random walk moves away from its starting point as time progresses. The paper shows this speed exists for any positive bias $\beta$ and converges to a specific value $v_{\infty}(\beta)$ in the limit of an infinite tree.
- Galton-Watson Tree Approximation
- The complex tree with infinitely many children is approximated by standard Galton-Watson trees by only considering a fixed number $N$ of descendants at each marked vertex. This allows researchers to use known results from simpler trees to understand the behavior in the more complex model.
- Differentiability and Monotonicity
- The paper investigates whether the speed function changes smoothly with respect to the bias $\beta$. It proves that under specific conditions on the offspring law, this speed is differentiable and strictly increasing as $\beta$ increases, meaning a stronger bias leads to a faster walk.
- Bias Parameter ($\beta$)
- The bias parameter controls the direction or tendency of the random walk. A positive $\beta$ introduces a tendency for the walk to move in one direction, and the analysis focuses on how this tendency affects the long-term movement (speed) of the walker.
Terminology used across episodes
This episode discusses
- Biased random walk on a locally infinite Galton-Watson tree · Paper Radio
- Random Electrical Networks on Complete Graphs II: Proofs
- Central limit theorem for a random walk on Galton-Watson trees with random conductances
The paper
Biased random walk on a locally infinite Galton-Watson tree · Read on arXiv
Jan Nagel
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Biased random walk on a locally infinite Galton-Watson tree".
Emmy: Here's the gist of the paper. We propose a new variant of a biased random walk on a Galton-Watson tree, in which some vertices have infinitely many children, which allows to study differentiability and also monotonicity of the speed of the random walk in the bias parameter Existence and Definition of Speed The first result concerns the existence of the speed, stating that for all β > 0 there exists a constant v∞(β), such that Pβ-almost surely limn→∞ Xn n = v∞(β) If p0 = 0 or p0 = 1, we have v∞(β) > 0 for all β > 0 In the extreme case β = 0, the random walk always moves back towards the root, except when it is at a marked vertex When we condition on the root being a marked vertex, we still have a law of large numbers for β = 0 with explicit value v∞(0) = α2−α Approximation and Convergence to the Limit The tree with potentially infinitely many direct descendants can be approximated in a natural way by classical Galton-Watson trees, when we attach to a marked vertex only N descendant, for N ∈ N.
Ada: This yields a Galton-Watson tree with offspring law νN = αdN + (1 − α)ν The law of large numbers by
LPP96: shows that for all β ≥ 0 there exists a deterministic constant vN (β), such that P(N)β-almost surely limn→∞ Xn n = vN (β) We can show that vN converges to the speed in the new model with infinitely many children If p0 = 0, the speed vN (β) is positive if and only if β > 1/mN Theorem 1.2 states that when p0 = 0, we have for all β > 0 lim N→∞ vN (β) = v∞(β) Differentiability and Monotonicity We complement the convergence of the speed with a convergence of its derivative, where we need some additional assumptions on the offspring law ν Theorem 1.3 states that if p0 = 0, and P∞ k=1 pkγ k 1, then we have for all β > 0 lim N→∞ v′N (β) = v′∞(β) Our final result in this section concerns the monotonicity of v∞ in the bias parameter Theorem 1.4 states that if ν = δd for d ∈ N and α > 1 − 72ed, then v∞ is strictly monotone increasing on (0, ∞) Proof Techniques for Speed Properties The almost sure convergence in Theorem 1.1 is proven by defining the hitting time of the set M and showing that the increments between hitting times and generations define a sequence of random variables that are independent and identically distributed under Pβ The speed is then given by v∞(β):= limn→∞ Xn n = Eβ
Xσ2 − Xσ1: Eβ
σ2 − σ1: = E∗β
Xσ: E∗β
σ: The derivative of the speed is derived by differentiating the expression for the expected value of Xσ and Xσ, leading to d/dβ v∞(β) = E∗β
Xσ Yσ: E∗β
σ: - v∞(β)E∗β
σ Yσ: Monotonicity Proof Structure The proof of monotonicity relies on comparing the speed for two different bias parameters β1 < β2, leading to an inequality involving Eˆ1
σ: - Eˆ2
σ: and the difference in probabilities pˆ2 - pˆ1 Monotonicity is then proven once we show that for α sufficiently close to 1 Eˆ1
σ: − Eˆ2
σ: ≤ pˆ2 − pˆ1 for all 0 ≤ β1 < β2 < ∞ This is achieved through a coupling of two processes and using moment bounds on regeneration times, such as Lemma 6.4 which provides a uniform moment bound for the regeneration time E¯(N)β
τr1: < ∞ Moment Bounds and Final Result The proof of Lemma 6.
Paper summary: Ada: We're looking at "Biased random walk on a locally infinite Galton-Watson tree" again. The paper proposes this new variant of the walk where some vertices have infinitely many children, and the thesis is that this structure allows us to study both differentiability and monotonicity of the speed function in terms of the bias parameter.
Emmy: Basically, they show that when you have those marked vertices with infinite offspring, it changes how we analyze the walk's velocity as you tweak that bias beta. It moves beyond just finding a limit for the speed and looks at how smoothly that limit depends on beta.
Kolya: The abstract mentions they also show that this speed in this model is the limit of speeds from random walks on appropriate locally finite trees, which is pretty big because it connects it to models we already know well.
Ada: That connection means we can use tools from the simpler, locally finite trees to understand this more complex structure with infinite branching. It grounds the new model in something more familiar.
Emmy: The paper also gives us a specific starting point when the bias is zero, stating that for p zero being zero or one, the speed v infinity(beta) is positive for all biases beta greater than zero <ref:2610.08181#pg1>.
Kolya: And in that beta=zero case, they give us an explicit value for the speed if we condition on the root being a marked vertex, which is alpha squared minus alpha <ref:2610.08181#pg1>.
Ada: That specific result helps ground the general theory by giving us a concrete number for one of the key scenarios.
Emmy: And then they build up to approximating this infinite tree by looking at classical Galton-Watson trees with N descendants, where the offspring law is modified to nu N = alpha N d + (one - alpha) nu <ref:2610.08181#pg1>.
Kolya: This approximation allows them to use the law of large numbers result from LPP96 to show that for all biases greater than or equal to zero, there's a deterministic speed v N(beta) that converges to the true speed as N goes up.
Ada: The key condition they put on this convergence is when we assume the tree has no leaves, meaning the probability of having zero children is zero.
Emmy: And they state a crucial threshold for this convergence: if p zero is not zero, then the speed v N(beta) only stays positive if beta is greater than one over the mean of that modified offspring law, which we call m N <ref:2610.08181#pg1>.
Conclusion: Ada: So to wrap up "Biased random walk on a locally infinite Galton-Watson tree", the authors successfully established that their new model allows for studying both differentiability and monotonicity of the speed function as you vary the bias parameter.
Emmy: They showed that this speed is not just a fixed number, but a function of beta, and they proved it's strictly increasing under certain conditions, which is important because it tells us how sensitive the walk is to that bias.
Kolya: The paper bridges the gap between infinite branching structures and more manageable local finite trees by showing convergence in the speed calculation as we scale up the number of descendants.
Ada: It gives us a way to understand complex random environments by relating them back to simpler, known models, while also providing concrete results for specific cases like zero bias.
Emmy: The implication is that for researchers working with biased walks in random environments, this framework offers more tools to analyze the behavior of the walk's velocity across different parameter regimes.
More episodes
- 2509.05860-Concentration Inequalities for Branching Random Walks
- 2509.19309-Small Prime Primitive Roots in Arithmetic Progressions
- 2509.21830-Noncollapsing for Curvature Flows with Inhomogeneous Speeds
- 2510.08346-Separability and Submetrizability in Locally Convex Spaces
- 2510.27290-Borel Combinatorics of Schreier Graphs of Z-actions
- 2511.13500-Sampling Density for Gabor Phase Retrieval
- 2511.19161-Linear dynamics of random products of weighted shifts
- 2511.21548-Metastability of diffusion processes in narrow tubes
- 2512.01536-Abelian approximations for bicrossed products
- 2601.02524-Lagrangian slice disks with symplectomorphic exteriors