On the moments of the Ulam-Kac adder

2023/03/07 by Gage Bonner, Bonner, Gage
Computer Science · Mathematics · #Algorithms and Data Compression #FOS: Mathematics #Mathematical Dynamics and Fractals #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2303.03606

openalex publication_date 2023/03/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let \U(n)\_{n ≥ 0} be a sequence of independent random variables such that U(n) is distributed uniformly on \0, 1, 2 … n\. The Ulam-Kac adder is the history-dependent random sequence defined by X_{n + 1} = X_n + X_U(n) with the initial condition X₀ = 1. We show that for each m ≥ 1, it holds that log E[X_n^m]/√(n) approaches a constant c_m as n → ∞. Loose bounds are provided for the constants c_m.

Related

• Ulam's History-dependent Random Adding Process
• Weight distribution of random linear codes and Krawchouk polynomials
• Moment inequalities for functions of independent random variables
• On the random variable \N^r \ni (k₁, k₂, ..., k_r) ↦ gcd(n,k₁k₂... k_r) ∈ \N
• Non-Conventional Limits of Random Sequences Related to Partitions of Integers