Ulam has defined a history-dependent random sequence of integers by the recursion $X_{n+1}$ $= X_{U(n)}+X_{V(n)}, n geqslant r$ where $U(n)$ and $V(n)$ are independently and uniformly distributed on ${1,dots,n}$, and the initial sequence, $X_1=x_1,do
ts,X_r=x_r$, is fixed. We consider the asymptotic properties of this sequence as $n to infty$, showing, for example, that $n^{-2} sum_{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 $lim_{nto infty} n^{-2} E X^2_n = (2 pi)^{-1} sinh(pi)$; and that for large $m < n$, we have $(m n)^{-1} E X_m X_n doteq (3 pi)^{-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.
We consider random processes that are history-dependent, in the sense that the distribution of the next step of the process at any time depends upon the entire past history of the process. In general, therefore, the Markov property cannot hold, but i
t is shown that a suitable sub-class of such processes can be seen as directed Markov processes, subordinate to a random non-Markov directing process whose properties we explore in detail. This enables us to describe the behaviour of the subordinated process of interest. Some examples, including reverting random walks and a reverting branching process, are given.
