Extension of results on generalized Pólya's urns for polynomially self-repelling walks

This technical note extends the results of Kosygina, Mountford, and Peterson on generalized Pólya's urns from a specific weight function to a broader family of functions relevant to Tóth's study of polynomially self-repelling walks, thereby facilitating future research on the scaling limits of these processes.

The Gist

Here is an explanation of the paper using simple language and creative analogies.

The Big Picture: A Walk That Remembers Its Past

Imagine a person walking down a long, straight street (the number line). Every time they take a step, they have to decide whether to go Left or Right.

In a normal random walk (like a drunk person stumbling), the decision is a coin flip: 50/50. But in this paper, we are studying a Self-Interacting Walk. This walker has a memory. They keep a tally of how many times they have crossed every specific "street corner" (the edge between two numbers).

• The Rule: The more times the walker has crossed a specific corner, the less likely they are to cross it again.
• The Analogy: Imagine the street corners are made of sticky mud. The more you walk through a patch of mud, the stickier it gets. Eventually, it becomes so sticky that you naturally want to step onto a fresh, clean patch of sidewalk instead. This is called a Self-Repelling Walk.

The "Urn" Game: How the Walker Decides

To figure out exactly how sticky the mud is, the authors use a mathematical tool called a Generalized Pólya Urn.

Think of the walker standing at a specific corner. In their pocket, they have a magical jar (the urn) containing Red Balls and Blue Balls.

• Red Ball: Means "Step Right."
• Blue Ball: Means "Step Left."

Every time the walker crosses this corner, they pull a ball out of the jar.

• If they pull a Red ball, they step Right, and they put two Red balls back in the jar (making it more likely to step Right again? Wait, no!).
• Correction for Self-Repelling: In this specific "sticky mud" scenario, the rules are slightly different. The "weight" of the balls changes based on how many times the corner has been visited. If a corner has been visited many times, the "Red Ball" (step Right) becomes very heavy and hard to pull, while the "Blue Ball" (step Left) becomes light and easy. The walker is mathematically pushed away from the path they just took.

The Problem: A Specific Recipe vs. A General One

In a previous study (by the same authors in 2023), they looked at a very specific recipe for this "stickiness." They assumed the stickiness followed a perfect, simple formula:
$$\text{Stickiness} = \frac{1}{(\text{visits} + 1)^{\alpha}}$$
Think of this as a specific brand of "Super-Sticky Mud" that behaves in a very predictable way. They proved that if you use this specific brand, the walker behaves in a certain surprising way: they do not settle into a smooth, predictable pattern (like a standard Brownian motion) when you zoom out and watch them from far away.

The Question: Does this weird behavior happen only because of that specific brand of mud? Or does it happen with any mud that gets sticky in a similar way?

The Solution: Expanding the Recipe

This new paper says: "It doesn't matter what the exact brand of mud is, as long as it gets sticky in the right general way."

The authors took the specific formula from the old paper and expanded it to a whole family of formulas. They showed that as long as the stickiness follows a general rule (where the "stickiness" gets weaker as the number of visits grows, following a specific mathematical curve), the results hold true.

They didn't just copy-paste the old math. They had to be very careful because:

1. The old math assumed the mud always got stickier in a straight line. The new math allows for mud that might get stickier, then slightly less sticky, then stickier again, as long as the overall trend is right.
2. They had to prove the "jitter" stays under control. Even with these messy, non-perfect mud types, the walker doesn't go crazy. The math proves that the walker's path remains stable enough to study.

Why Does This Matter? (The "So What?")

Imagine you are trying to predict traffic flow.

• The Old Result: "If cars avoid roads they've been on recently, and the avoidance follows Rule A, then traffic jams won't look like smooth waves."
• This New Result: "Actually, traffic jams won't look like smooth waves for any reasonable avoidance rule, not just Rule A."

This is a crucial step for the authors. They are preparing a future paper to answer the big question: "If this walker doesn't look like a standard wave, what does it look like?"

By proving that their previous results apply to this whole family of "sticky" walks, they have built a solid foundation to finally identify the true shape of these strange, self-repelling paths.

Summary in a Nutshell

1. The Walker: A person who avoids their own footsteps.
2. The Tool: A jar of balls that changes color probabilities based on history.
3. The Discovery: Previous work showed that with a perfectly smooth avoidance rule, the walker behaves strangely.
4. This Paper: Proves that the walker behaves strangely even if the avoidance rule is "messy" or "imperfect," as long as it follows the general trend of getting harder to cross as you visit more.
5. The Goal: To finally figure out exactly what kind of "strange" shape these walkers make when you watch them from a distance.

Technical Summary

Here is a detailed technical summary of the paper "Extension of Results on Generalized Pólya's Urns for Polynomially Self-Repelling Walks" by Kosygina, Marêché, Mountford, and Peterson.

1. Problem Statement and Context

The Core Problem:
The paper addresses the behavior of Polynomially Self-Repelling (PSR) walks, a class of self-interacting random walks on the integer lattice $\mathbb{Z}$. In these walks, the probability of stepping in a direction depends on the number of times the edge in that direction has been previously traversed.

Specifically, the walk is defined by a weight function $w(n)$, where the probability of crossing an edge $n$ times is proportional to $w(n)$. The authors focus on the asymptotic regime where the inverse weight function behaves as:
$$\frac{1}{w(n)} = n^\alpha \left(1 + \frac{2B}{n} + O(n^{-2})\right) \quad \text{as } n \to \infty$$
for some $\alpha > 0$ and $B \in \mathbb{R}$.

The Gap in Literature:

• Previous Work (Tóth, 1996): Established a generalized Ray-Knight theorem for PSR walks, suggesting convergence to a "Brownian motion perturbed at its extrema" (BMPE) under diffusive scaling.
• Recent Work (Kosygina, Mountford, Peterson, 2023 - [KMP23]): Demonstrated that for the specific weight function $w(n) = (n+1)^{-\alpha}$, the rescaled PSR walk does not converge to a BMPE. This proved that the Ray-Knight theorem alone is insufficient to identify the functional limit.
• The Open Question: The [KMP23] result was specific to a simple weight function. It remained unknown whether the non-convergence (or the specific scaling limits) holds for the general family of weight functions satisfying the asymptotic condition above. Furthermore, [KMP23] relied on the assumption that $w$ is non-increasing (monotone).

Objective:
The authors aim to extend the technical results of [KMP23] from the specific case $w(n)=(n+1)^{-\alpha}$ to the general family defined by the asymptotic expansion above, removing the requirement that $w$ be monotone. This extension is a prerequisite for future work on the scaling limits of these walks.

---

2. Methodology

The paper utilizes the connection between self-interacting random walks and Generalized Pólya Urn Models.

• Urn Construction: The sequence of left/right steps at any site $x$ is modeled as a generalized Pólya urn process.
  • Left of Origin ($x < 0$): Modeled by an urn with sequences $b^-(i) = w(2i)$ and $r^-(i) = w(2i+1)$.
  • Right of Origin ($x > 0$): Modeled by $b^+(i) = w(2i+1)$ and $r^+(i) = w(2i)$.
  • At Origin ($x = 0$): Modeled by $b^0(i) = r^0(i) = w(2i)$.
• Discrepancy Process: The authors analyze the difference process $D_n = R_n - B_n$ (Red balls minus Blue balls) in these urns. The behavior of $D_n$ dictates the local time and step distribution of the random walk.
• Rubin's Construction: The proofs heavily rely on Rubin's construction, which represents the urn process using independent exponential random variables. This allows for the coupling of the discrete urn process with continuous-time processes to derive tail bounds and variance estimates.
• Handling Non-Monotonicity: Unlike [KMP23], which used the monotonicity of $w$ to bound terms, this paper uses the precise asymptotic expansion of $1/w(n)$to derive bounds. This requires more careful Taylor expansions and error term analysis, particularly when$w$ is not strictly decreasing.

---

3. Key Contributions and Results

The paper establishes that the probabilistic estimates derived in [KMP23] for the specific weight function hold true for the general asymptotic class, even without monotonicity. The results are presented as extensions of Lemmas and Propositions from [KMP23].

A. Tail Bounds and Concentration (Lemma 3.1)

The authors prove that the discrepancy process $D_n$ satisfies strong concentration inequalities. For any integers $n, m \ge 1$:
$$P(|D_{\tau^B_n}| \ge m) \le C_1 e^{-c_1 \frac{m^2}{m \vee n}}$$
where $\tau^B_n$ is the time of the $n$-th blue ball draw.

• Significance: This exponential tail bound is crucial for controlling the fluctuations of the walk. The proof adapts the [KMP23] argument by carefully bounding the expectations of the exponential variables using the general asymptotic form of $w$, rather than relying on monotonicity.

B. Variance Estimates (Lemma 3.2 & Corollaries 3.3, 3.4)

The paper establishes the variance behavior of the discrepancy process.

• Martingale Approximation: For large $n$, the process $D_{\lfloor tn \rfloor} / \sqrt{n} t^\alpha$ behaves approximately like a martingale.
• Variance Limit: $\lim_{n \to \infty} n^{-1} \text{Var}(D_n) = (2\alpha + 1)^{-1}$.
• Local Variance: For $m \in [n, 2n]$, the variance of the increment $D_m - D_n$ is close to $(m-n)$, with error terms bounded by $O(\sqrt{n} \log^2 n)$.
• Significance: These results confirm that the diffusion coefficient of the discrepancy process is stable across the general class of weight functions.

C. Supremum Bounds (Lemma 3.5)

The authors prove a bound on the maximum fluctuation of the discrepancy process over a time interval of length proportional to $n$:
$$P\left( \sup_{\tau^B_{Mn} \le i \le \tau^B_{(M+1)n}} |D_i - D_{\tau^B_{Mn}}| \ge y\sqrt{n} \right) \le \frac{1}{c_4} e^{-c_4 y^2}$$

• Methodological Shift: The proof in [KMP23] relied on $w$ being non-increasing to bound the drift. Here, the authors use the asymptotic expansion to show that the conditional probability of an "up-step" deviates from $1/2$by an amount proportional to$y/\sqrt{Mn}$. They then couple the process with biased random walks and apply Hoeffding's inequality.

D. Asymptotic Mean of the Discrepancy (Proposition 3.9)

This is the most significant technical contribution, as the limit depends on the location of the site (the specific urn parameters).
The limit of the expected discrepancy at the $n$-th blue draw, $E[D^*_{\tau^{B^*}_n}]$, is:

1. Right of Origin ($*$ = +): $\lim_{n \to \infty} E[D^+_{\tau^{B^+}_n}] = \frac{1}{2(2\alpha + 1)}$
2. Left of Origin ($*$ = -): $\lim_{n \to \infty} E[D^-_{\tau^{B^-}_n}] = -\frac{4\alpha + 1}{2(2\alpha + 1)}$
3. At Origin ($*$ = 0): $\lim_{n \to \infty} E[D^0_{\tau^{B^0}_n}] = -\frac{\alpha}{2\alpha + 1}$

• Derivation: The proof uses Rubin's construction and a summation identity from Tóth (1996). The authors perform a detailed asymptotic expansion of the sums involving $1/b^(j)$and$1/r^(j)$, utilizing the specific$O(n^{-2})$ error term in the weight function definition to isolate the constant terms in the limit.

---

4. Significance and Implications

1. Robustness of Non-Convergence: By extending the results to the general weight function class, the authors confirm that the "negative result" from [KMP23] (non-convergence to BMPE) is not an artifact of the specific choice $w(n)=(n+1)^{-\alpha}$. It is a structural feature of the entire class of polynomially self-repelling walks.
2. Relaxation of Monotonicity: The results hold even if the weight function $w(n)$ is not monotone. This is a significant generalization, suggesting that the specific monotonicity of the repulsion is less critical than the asymptotic decay rate ($n^{-\alpha}$) and the second-order term ($B/n$).
3. Foundation for Scaling Limits: These technical estimates (variance, tail bounds, and mean limits) are the necessary "building blocks" for the authors' forthcoming work. They will use these results to rigorously derive the actual scaling limit of the PSR walk, which is expected to be a process distinct from the BMPE.
4. Technical Rigor: The paper demonstrates that while the qualitative behavior of these urn models is robust, the quantitative proofs require delicate adjustments when monotonicity is removed, specifically in the handling of error terms in Taylor expansions and the coupling arguments.

In summary, this technical note validates the universality of the probabilistic behavior of generalized Pólya urns associated with polynomially self-repelling walks, paving the way for a complete characterization of their scaling limits.