On the moments of the Ulam-Kac adder

Abstract

Let $\{U(n){\}}_{n\ge 0}$ be a sequence of independent random variables such that $U(n)$ is distributed uniformly on $\{0,1,2\dots 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_0=1$. We show that for each $m\ge 1$, it holds that $\log E[X_n^m]/\sqrt{n}$ approaches a constant $c_m$ as $n\to \infty$. Loose bounds are provided for the constants $c_m$.

Fixed typos, updated references/end matter. Removed citation of a conjecture which has actually been decided (in the negative.)