Ulam's History-dependent Random Adding Process

MaRDI QIDQ6329381zbMATH OpenFDO

Authors Peter Clifford, David R. Stirzaker

Publication date 18 November 2019

Mathematics Subject Classification ID

Ordinary differential equations and systems with randomness (34F05) Stochastic difference equations (39A50) Martingales with discrete parameter (60G42) Sums of independent random variables; random walks (60G50)

Abstract: Ulam has defined a history-dependent random sequence of integers by the recursion $X_{n+1}$ $=X_{U(n)}+X_{V(n)},ngeqslantr$ where $U(n)$ and $V(n)$ are independently and uniformly distributed on $1,dots,n$, and the initial sequence, $X_1=x_1,dots,X_r=x_r$, is fixed. We consider the asymptotic properties of this sequence as $noinfty$, showing, for example, that $n^{-2}su{m}_{k=1}^n{X}_k$ converges to a non-degenerate random variable. We also consider the moments and auto-covariance of the process, showing, for example, that when the initial condition is $x_1=1$ with $r=1$, then $li{m}_{noinfty}{n}^{-2}E{X}_n^2=(2pi{)}^{-1}sinh(pi)$; and that for large $m<n$, we have $(mn{)}^{-1}E{X}_m{X}_{n}doteq(3pi{)}^{-1}sinh(pi).$ We further consider new random adding processes where changes occur independently at discrete times with probability $p$, or where changes occur continuously at jump times of an independent Poisson process. The processes are shown to have properties similar to those of the discrete time process with $p=1$, and to be readily generalised to a wider range of related sequences.

This page was built for publication: Ulam's History-dependent Random Adding Process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6329381)