## Abstract

Ulam has defined a history-dependent random sequence by the recursion *X*_{n+1}=*X*_{n}+*X*_{U(n)}, where (*U*(*n*); *n*≥1) is a sequence of independent random variables with *U*(*n*) uniformly distributed on {1, …, *n*} and *X*_{1}=1. We introduce a new class of continuous-time history-dependent random processes regulated by Poisson processes. The simplest of these, a univariate process regulated by a homogeneous Poisson process, replicates in continuous time the essential properties of Ulam's sequence, and greatly facilitates its analysis. We consider several generalizations and extensions of this, including bivariate and multivariate coupled history-dependent processes, and cases when the dependence on the past is not uniform. The analysis of the discrete-time formulations of these models would be at the very least an extremely formidable project, but we determine the asymptotic growth rates of their means and higher moments with relative ease.

## 1. Introduction

Deterministic recurrence relations have long been widely used to describe the structure of many random processes, most notably in the moving average and autoregressive models of time series. More recently, stochastic recurrence relations have been introduced in other widely disparate fields, such as dynamical systems, continued fractions, ergodic theory and many problems in physics. For example, Embree & Trefethen (1999) have discussed the theory and applications of the random Fibonacci sequence(1.1)where *X*_{0}=*X*_{1}=1 and each of the i.i.d.r.v.s, *B*_{n}, takes one of the values +1 or −1 with probability 1/2. More generally, stochastic systems with long-range correlation are of interest in many scientific disciplines, from physics to economics; but the customary assumption of the Markov property, though extraordinarily convenient, constrains the amount and nature of such correlation. A natural next step is therefore to abandon that restriction, and allow the short-term development of the process to have an explicit dependence on its history. Typically, this makes the analysis of the model extremely difficult. For example, Keshet & Hod (2005) have discussed history-dependent random walks in which the probability distribution of the next step depends on the statistics of the preceding path.

Rather earlier (before 1969), S. Ulam had defined the sequence(1.2)where *X*_{1}=1 and (*U*(*n*); *n*≥1) is a sequence of independent random variables each uniformly distributed on {1, …, *n*}. Computer simulations of this, and related processes, can be found in Beyer *et al*. (1969). The sequence defined in (1.2) was sufficiently interesting to attract the attention of Kac (1970), who established that asymptotically as *n*→∞(1.3)and(1.4)where the notation *f*(*n*)∼*g*(*n*) indicates that *f*(*n*)/*g*(*n*) converges to a non-zero limit as *n*→∞. The sequence in (1.2) was later considered by Ben-Naim & Krapivsky (2002), who rediscovered (1.4). They also considered the sequence defined bywhere *U*(*n*) and *V*(*n*) are independently and identically distributed uniformly on {1, …, *n*}. In this caseas *n*→∞. In Ben-Naim & Krapivsky (2004), a further range of history-dependent sequences was examined, based on uniform random selection from the past.

Moving away from the assumption of uniformity, Krasikov *et al*. (2004) considered more general sequences of the form(1.5)where *β*>0 and *H*(*n*) has either a power-law or a truncated geometric distribution, over {1, …, *n*}. They established that a wide range of different types of asymptotic behaviour could be displayed by *EX*_{n}, depending on the parameter of the distribution of *H*(*n*). In particular, when *H*(*n*) is uniform on {1, …, *n*} they generalized Kac's result for Ulam's sequence to show that(1.6)and(1.7)When *β*=1, this yields (1.3) and (1.4), of course.

Finally, we note that another type of history-dependent random sequence has a long track record, and is very familiar outside the mathematical context.

### (a) The Labouchere system

The Labouchere system applies to a sequence of independent wagers paying out at evens. Initially, the gamer starts with a fixed ordered list of numbers, traditionally (1, 2, 3, 4). At each wager, the stake is the sum of the first and last members of the list (or the only number, if the list is of length 1). If the bet is won, these terms are struck off the list; if the bet is lost their sum is added to the list as a new term on the right. The sequence of lists until the list is empty comprises a very complicated history-dependent process about which very little is known. This is all the more remarkable when one notes that the system has been in use for at least 200 years, and probably more (see Downton (1980) for a statement of an interesting open problem; and Ethier (2006) for a recent result).

## 2. Poisson-regulated sequences

In finding *m*_{n}=*EX*_{n} and for the sequences above, the basic method of approach generally follows that pioneered by Kac (1970). The set of difference equations for *m*_{n} and *s*_{n} is cast into a suitably minimal and tractable form. In the special case of Ulam's process, it turns out that the appropriate difference equation is solved by values of Laguerre polynomials; and the differential equation for the generating function of *s*_{n} can be treated by the method of steepest descents.

More generally, a suitable form of the set of difference equations may be replaced by an appropriate set of differential equations, after taking a continuum limit of the discrete problem. These are then subjected to an asymptotic analysis. However, this method of approach is somewhat arduous mechanically, and the exact status of the continuous limit in relation to the original problem is not easily made explicit.

We therefore introduce a new class of history-dependent processes in continuous time, by randomizing the discrete-time processes above, using Poisson processes as the regulator. It appears that this manoeuvre (also called subordination or continuization) will transform processes that in their discrete-time version are extremely difficult to analyse into a tractable form. As a first step, therefore, a general form of the randomized Ulam–Kac process is thus defined as follows.

Let *T*_{0}=0, and let (*T*_{k}; *k*≥1) be the successive jump times of a Poisson process (*N*(*t*), *t*≥0) of rate *λ*. Let (*U*_{k}; *k*≥1) be a sequence of independent random variables such that *U*_{k} is uniformly distributed in (0, *T*_{k}). Then we let *X*(0)=1 (say) and define(2.1)and(2.2)where *α* and *β* are real constants.

Note that more general constructions are possible.

One could letwhere (

*A*_{k};*k*≥1) and (*B*_{k};*k*≥1) are sequences of random variables. When the component variables of these sequences are i.i.d. with respective means*α*and*β*, much of what follows remains true.The random variables (

*U*_{k};*k*≥1) may have a distribution other than uniform. We return to this in §6.The regulating Poisson process may be non-homogeneous of rate

*λ*(*t*). We return to this in §7.

*The expected value of* *in the process of* *definition 2.1* *is given by*(2.3)*where* *is the confluent hypergeometric function known as Kummer's first function*.

Let be the indicator of the event that *N*(*t*+*h*)−*N*(*t*)=0. Then for small positive *h*where *U* is uniformly distributed on (0, *t*) independently of *X*. Hence(2.4)Setting *λ*(*α*−1)*t*=*z*, for *α*≠1, we obtainThis is Kummer's equation with parameters *a*=1+*β*/(*α*−1) and *b*=1 (see Abramowitz & Stegun 1965, ch. 13). The solution taking the value 1 at *z*=0 iswhere (*a*)_{n}=*a*(*a*+1)⋯(*a*+*n*−1) is the rising factorial. ▪

From the asymptotic properties of , given in Abramowitz & Stegun (1965), we conclude that(2.5)and(2.6)

Turning to second moments, we define and *s*(*t*)=*EX*^{2}(*t*). Then we have the following.

*As t*→∞, *the second moment s*(*t*) *grows without bound outside the region* , *except on the line α*+*β*=1*, where**Within the region* , *the second moment converges to* 0.

Considering the events of the Poisson process in (*t*, *t*+*h*), as we did in theorem 2.1, yields(2.7)and(2.8)

Eliminating *r*, we find that *s*(*t*) satisfies(2.9)Following Erdélyi (1956), we obtain the leading terms in the asymptotic expansion of *s*(*t*) as *t*→∞ by substituting trial solutions of the form *s*_{1}=*t*^{σ}e^{δt} and *s*_{2}=*t*^{ρ}; and equating the coefficients of the highest order terms.

For *s*_{1}, equating the coefficients of *t*^{σ+2}e^{δt}, we obtainso that *δ* is either 0, *λ*(*α*−1) or *λ*(*α*^{2}−1).

For *s*_{2}, equating the coefficients of *t*^{ρ}, we find thatwhenceThe result of the theorem now follows. ▪

Based on numerical solutions, it is conjectured that, on the boundary of the region , the second moment has a non-zero limit and the process *X*(*t*) converges to equilibrium. This is supported by analysis of the following process.

Let *T*_{0}=0 and let (*T*_{k}; *k*≥1) be the successive jump times of a Poisson process of rate *λ*. Let (*U*_{k}; *k*≥1) be a sequence of independent random variables such that *U*_{k} is uniformly distributed in (0, *T*_{k}) and let (*I*_{k}; *k*≥1) be a sequence of independent Bernoulli variables each with probability 1/2. Then we let (say) and define(2.10)and(2.11)where *α* and *β* are real constants.

It is straightforward to show that this process has the same mean as that of definition 2.1. However, the second moment satisfies the simpler equation(2.12)and hence(2.13)where is Kummer's function, with a similar expression for the *n*th moment. From the asymptotic behaviour of (e.g. Abramowitz & Stegun 1965), it follows that diverges to infinity or converges to 0 depending on whether is greater than or less than 1/2. When *α*^{2}+*β*^{2}=1/2 the second moment . The behaviour of *m*(*t*), *s*(*t*) and is summarized in figure 1.

In the above analysis, we have excluded the case *α*=1, which is clearly both interesting and singular. If we set −*β*/(1−*α*)=*d* in (2.3), and let *α*→1, so that *d*→∞, then we have from (13.3.1) of Abramowitz & Stegun (1965) that(2.14)where *I*_{0}(.) and *J*_{0}(.) are Bessel functions, modified and of the first kind, respectively. We therefore turn to a more detailed analysis of this case.

## 3. Poisson-regulated Ulam–Kac sequences

Let *X*(*t*) be the process of definition 2.1 in the case *α*=1, so thatWe write *m*(*t*)=*EX*(*t*), *s*(*t*)=*EX*^{2}(*t*) and .

Equation (2.4) for *m*(*t*) now takes the form(3.1)Solving this equation directly with *m*(0)=1, we confirm that the mean has the limiting form given in (2.14).

For *s*(*t*), we have the following theorem.

*As t*→∞(3.2)*where*(3.3)

In advance of proving this, we note that, when *λ*=*β*=1, the expression in the exponent is exactly that found by Kac (1970) for the discrete-time process; when *λ*=1, we recover the discrete-time result of Krasikov *et al.* (2004). The value of *σ* is new.

Equations (2.7) and (2.8) now take the form(3.4)and(3.5)Substituting for the derivatives of *r*, yields(3.6)Following Erdélyi (1956), we assume that . Equating the coefficients of the leading term givesand the larger positive root of this is given byas required. Equating the coefficients of the next term in the expansion giveswhich yields *σ*, on substituting for *δ*. ▪

Differential equations for the higher moments can be established in exactly the same way, and the asymptotic expansion of their solution follows similarly. We omit the details.

## 4. Coupled Ulam–Kac sequences

It is natural to extend the field of enquiry to consider vector-valued, or coupled, processes. In discrete time, one may define a general bivariate Ulam–Kac sequence, thus(4.1)(4.2)where *U*_{n} and *V*_{n} are independent random variables, uniform on {1, …, *n*}. There seems to have been no investigation of such sequences. Here, we seek to analyse a Poisson-regulated bivariate Ulam–Kac sequence (*X*(*t*), *Y*(*t*)), defined as follows.

Let *T*_{0}=*S*_{0}=0 and let (*T*_{k}; *k*≥1) and (*S*_{k}; *k*≥1) be the successive jump times of Poisson processes of rates *λ* and *μ*, respectively. We may distinguish the following two cases.

*Synchronous*. The two Poisson processes are the same;*S*_{k}=*T*_{k}for all*k*and*λ*=*μ*.*Asynchronous*. The two Poisson processes are independent. In what follows, we shall assume asynchronicity, unless stated otherwise. (We may assume that*λ*=*μ*for independent Poisson processes.)

Let *U*_{k} and *V*_{k} be independent variables uniform on (0, *S*_{k}) and (0, *T*_{k}), respectively. We letand(4.3)(4.4)Definethen we have the following theorem.

*As t*→∞, *if* max{*α*, *β*}>1,*If* max {*α*, *β*}<1, *then**where*(4.5)

By conditional expectation, we haveEliminating *m*_{Y}, we obtain

Substituting *m _{X}*=

*t*

^{σ}e

^{δt}, and equating coefficients of the highest order terms, we find that

*δ*is given byEquating the coefficients of the terms of next highest order gives

*σ*as claimed.

Note that in this case the leading term in the asymptotic expansion does not depend on *a* or *b*; the exponential growth is dominated by the short-range effects of the recent history of the process. Roughly speaking, it is growing too fast to be affected by the terms in *a* and *b* representing its past; at least to first order.

If *α*<1 and *β*<1, we seek a solution of the form *m*_{X}∼*t*^{ρ}. Equating the coefficients of the highest order terms gives a quadratic equation for *ρ*with roots as claimed, for the second part. ▪

As in the uncoupled univariate case, one could pursue the second moments. And it is to be conjectured that, for suitable values of *a*, *b*, *α*, *β*, the pair (*X*(*t*), *Y*(*t*)) converges as *t*→∞. Furthermore, just as for the univariate process, the cases when *α*=1 or *β*=1, or both, are particularly interesting and singular. Note that we may see these as the natural bivariate generalization of Ulam's original process, when subject to Poisson regulation. We first let *β*=1, and *α*<1.

*For the process defined in* (*4.3*) *and* (*4.4*), *when* *and α*<1, *we have that as t*→∞

By conditional expectationand(4.6)HenceFor asymptotic representations of the form *m*_{Y}∼*t*^{σ}e^{δt}, it is easily shown thatWe therefore seek a subnormal asymptotic expansion. In this case, we can write *m*_{Y}∼*t*^{σ}exp(*δt*^{1/3}), and find from the highest order terms thatWith this value of *δ*, the terms of next highest order yield *σ*=−1/3. The result for *m*_{X}(*t*) is now obtained either likewise, or by substituting for *m*_{Y} in (4.6). ▪

Secondly, let us consider *α*=*β*=1. In this case, we have

*As t*→∞,

By conditional expectation as above(4.7)Eliminating *m*_{Y} gives(4.8)As *t*→∞, we assume that asymptotically . Substituting this expression into (4.8) and equating the coefficients of the leading-order terms yieldsThe required result follows. ▪

For the second moments we have this, when *α*=*β*=1.

*When λ*=*μ, as t*→∞,*where* , *and y is the root of*(4.9)*having largest real part and c*=*ab*. *Furthermore, for this y*,(4.10)*From this, we may readily obtain the asymptotic form of the other second moments*.

In advance of proving this, we note that, if *c*>0, then the largest root of (4.9) is real and larger than . To see this, evaluate (4.9) at to obtain .

Furthermore, when *c*<0, using either Rouché's theorem (or the principle of the argument applied to the function *f*(*z*)=*z*^{3}−*cz*^{2}−16*cz*+*c*^{2} of a complex variable in the first quadrant) we find that *f*(*z*) has exactly one zero there, and hence a conjugate zero in the fourth quadrant. Thus, the two complex roots of (4.9) have positive real part. When *c*=0, the entire problem reduces to triviality.

Writing *X*=*X*(*t*) and , etc. for brevity, we define the following second-order moments:

Then by conditional expectation, we have(4.11)(4.12)(4.13)together with(4.14)In the special case when *λ*=*μ*, we can eliminate all the variables except *R*_{XY} in this set of 10 simultaneous integro-differential equations to find that *R*_{XY} is the solution of the eighth-order differential equation , where *D* denotes the differential operator d/d*t* and is the operator(4.15)Again following Erdélyi (1956) and assuming an asymptotic representation of the form , we obtain the required result. ▪

We recall that this is the asynchronous case, when *X*(*t*) and *Y*(*t*) are regulated by independent Poisson process. It is of interest to consider the synchronous case, when both are regulated by the same Poisson process of rate *λ*.

*Under synchronous coupling, as t*→∞, , *where δ is given as above by* (*4.9*), *and* *is given by*(4.16)*differing from σ only in the numerator*.

In the synchronous case, we find in the usual way by conditional expectation that all the equations for the second moments when *λ*=*μ* are unchanged, except for (4.11), which becomes(4.17)Once again reducing the set of 10 simultaneous equations, including the extra term in (4.11), and assuming , now yields the required result in the same way as before. ▪

We could also obtain similar results for the second moments when *α*<1 and *β*=1.

## 5. Higher order couplings

One may extend the idea of history-dependent processes to the multivariate case in many ways. A general formulation is as follows.

Let be independent Poisson processes with constant rates *λ*_{1}, …, *λ*_{n}. Let be the jump times of the *j*th process and suppose that {*U*_{kjℓ}} are independent random variables such that *U*_{kjℓ} is uniformly distributed on (0, *T*_{kj}), *ℓ*=1, …, *n*.

The multivariate history-dependent ** X**(

*t*) is a process with components

*X*

_{1}(

*t*), …,

*X*

_{n}(

*t*) such thatwherewhere

*A*=(

*a*

_{jℓ}) is a matrix of real numbers and

*α*=(

*α*

_{1}, …,

*α*

_{n}) is a vector with real components.

Let *m*_{j}(*t*)=*EX*_{j}(*t*) and be the diagonal matrix with elements *λ*_{1}, …, *λ*_{n}, then theorem 4.3 can be extended as follows.

*Suppose that* *and* *has distinct eigenvalues* (*ϕ*_{1}, …, *ϕ*_{n}) *so that* *where* *is the diagonal matrix of eigenvalues, then*(5.1)*and as t*→∞*where ϕ*_{m} *is the eigenvalue with largest real part and where p*_{m} *and q*_{m} *are the left and right eigenvectors, respectively, associated with the eigenvalue ϕ*_{m}.

In vector form, with , and applying the usual conditional expectation argument, we haveafter replacing by . Pre-multiplying by *P* givesand hence, writing ** n**(

*t*) for

*P*

**(**

*m**t*), we obtain the uncoupled equationswith solutions given in §2 asSince

**(0)=**

*n**P*

**(0) and**

*m***(**

*m**t*)=

*P*

^{−1}

**(**

*n**t*), the result in (5.1) follows.

The behaviour for large *t* follows by rewriting:and using the asymptotic properties of the Bessel function *I*_{0}, where *p*_{j} and *q*_{j} are the left and right eigenvectors, respectively, associated with the eigenvalue *ϕ*_{j}. ▪

Theorems 4.2 and 4.3 can be generalized as follows.

*Let* ** X**(

*t*)

*be an n-dimensional multivariate history-dependent process as given by*

*definition 5.1*

*with α*

_{i}=1,

*i*=1, …,

*p*,

*p*>0

*and α*

_{i}<1,

*otherwise. Suppose A has a cyclic structure such that a*

_{i,i+1}=

*a*

_{i}

*for i*=1, …,

*n*−1

*and a*

_{n,1}=

*a*

_{n}

*with all other elements of A zero, then*

*where κ*=

*p*/(

*n*+

*p*), ,

*and*

Using the usual conditional arguments, we have the following equations:where , etc.

In principle, we can reduce the set of differential equations to a single equation of high order, substitute an asymptotic sub-normal form *t*^{ρ}exp*δt*^{κ} and use identities in the highest order terms to solve for *ρ*, *δ* and *κ*. Equivalently, we can substitute a trial form directly for say *M*_{1}, and apply the equations successively, retaining only the highest order terms at each stage. First note that in general if *M*=*t*^{ρ}exp*δt*^{κ}, with 0<*κ*<1, thenwhere *τ*=*t*^{κ}*δκ*, so that is of smaller order than .

We start by substituting *M*_{1}=*t*^{ρ}exp *δt*^{κ} into the first differential equation (*j*=1). To determine *δ* and *κ*, we need retain only the highest order term, giving and then, successively through *j*=2, …, *p*, we have eventually . For the next set of equations, the terms are dominant so that and successively and finally from the last differential equation , i.e.(5.2)For consistent powers of *t* on each side, this requires that *κ*=*p*/(*n*+*p*).

To obtain *δ*, we need to retain the constant factors in the asymptotic relations. For the first *p* equations, the cumulative product is and for the remaining equations . Retaining these factors, the asymptotic relation (5.2) becomesyielding the value of *δ*.

To find *ρ*, terms of the second highest order have to be retained. Again applying the equations successively starting with the substitution *M*_{1}=*t*^{ρ} exp *δt*^{κ}, from the first *p* equations we haveand then successively through the remaining equations to giveafter substituting *κ*=*p*/(*p*+*n*). Equating the second highest order terms on both sides then givesFinally, since we have , so that *ρ*_{1}=*ρ*+*κ*−1. The other values of *ρ*_{j} follow from the asymptotic relationships , etc. ▪

## 6. Non-uniform history dependence

As remarked above, it is natural to consider the case when the distribution of *U*_{k} (and of *V*_{k} in the coupled case) is not necessarily uniform on (0, *T*_{k}). In fact, Krasikov *et al*. (2004) considered other distributions in the univariate discrete-time model. Specifically, they studied the cases when *H*(*n*) (as defined in (1.5)) had either a power-law probability mass function of the formor a truncated geometric distribution of the formA variety of different types of asymptotic behaviour is exhibited by *X*_{n} as *n*→∞, depending on the value of *q*.

In the Poisson-regulated model, we consider analogously to (2.3),(6.1)where, given *T*_{k}=*t*, *Q*_{k} has the density function(6.2)By the usual conditional expectation argument, writing *EX*(*t*)=*m*(*t*), we havewhich can be shown to have solutionwhere is Kummer's function and *z*=*λ*(*α*−1)*t*.

Consulting (13.1.4–5) in Abramowitz & Stegun (1965), we find the leading terms in the asymptotic expansion of *m*(*t*), as *t*→∞, are as follows:andAs we have seen above, *α*=1 is an especially interesting and singular case; we therefore setand let *α*↑1 with *β*>0 so that *κ*→∞.

Hence, from (13.3.1) of Abramowitz & Stegun (1965), we find thatwhere *I*_{q}(.) is a Bessel function of fractional order. Note that, when *β*<0, it can be expressed in terms of the Bessel function *J*_{q}(.).

For the second moments of the process defined by (6.1), one may proceed as we did in theorem 2.2 by writing down a pair of equations for suitable second moments. We shall here confine our analysis to the particularly interesting case when *α*=1. We may term this the Poisson-regulated Ulam–Kac sequence with non-uniform history dependence, and we have the following theorem.

*Let s*(*t*)=*EX*^{2}(*t*) *and α*=1. *Then, as t*→∞,*where*

We define a new weighted version of *r*(*t*), thusThen by conditional expectation, we haveSeeking an asymptotic representation with leading term , we find in the usual way thatwhich gives the required value of *δ*. Likewise, the terms of next highest order provide an equation in *σ* and *δ* and, substituting the value of *δ* obtained above, this now yields the required value of *σ*. We note that, when *q*=0, these results reduce to those of theorem 2.2, naturally. ▪

Finally, we address the problem of coupled history-dependent processes in which the dependence is not uniform. Thus, in the now-familiar manner, we define analogously to (4.1) and (4.2) the pair *X*(*t*) and *Y*(*t*) that satisfyandwhere and are independent sequences of random variables such that, conditional on *T*_{k}=*t*, has the densityand, conditional on *S*_{k}=*s*, has the density(We recall that *T*_{k} and *S*_{k} are the jump times of independent Poisson processes of rate *λ* and *μ*, respectively.)

Defining *m*_{X}(*t*)=*EX*(*t*), and *m*_{Y}(*t*)=*EY*(*t*), conditional expectation givesEliminating *m*_{Y} we have,(6.3)Hence in the usual way, when max (*α*, *β*)>1, we find that , where *δ* and *σ* are the same as we obtained in theorem 4.1 in the case of uniform history dependence. However, if max (*α*, *β*)<1, we seek an expansion with leading term proportional to *t*^{ρ}. For this case,with some simplification when *p*=*q*. This should be compared with *ρ* obtained in theorem 4.1; to which this reduces when *p*=*q*=0, of course.

As usual, an interesting case arises when max (*α*, *β*)=1, so that we have coupled Ulam–Kac processes with non-uniform history dependence. Setting *β*=1 in (6.3) and proceeding as we did in theorem 4.2, it is now readily shown that as *t*→∞whereand further algebra would supply *σ*. We omit this.

## 7. Conclusion

We have considered a class of Poisson-regulated history-dependent random processes, in univariate and multivariate cases. The asymptotic form (for large times) of the first and second moments has been described in general; the same method will determine the asymptotic behaviour of any higher moment in principle, at the expense of formidable mechanical effort.

There are a number of natural extensions and generalizations of these processes; perhaps the most obvious is to consider regulation by a non-homogeneous Poisson process of intensity *λ*(*t*), *t*≥0, which, of course, has no parallel in discrete time. We do not explore this in detail, as in general the processes exhibit behaviour of formidable complexity, but it is amusing to consider special cases. When considering the moments, the effect is to replace *λ* with *λ*(*t*) in the differential equations. Thus, for example, considering the non-homogeneous Poisson-regulated Ulam–Kac sequence in the notation of §3, the mean *m*(*t*) satisfiesWhen *λ*(*t*)=*λt*, this yieldsfor suitable constants *A* and *B*. For *λ*(*t*)=*λ*/*t*, we find thatwhere . We omit consideration of other special cases, and further tractable forms of *λ*(*t*), of which there are many.

There remains a large number of interesting open problems, the most obvious of which is any determination of the probability distributions of the processes. Ben-Naim & Krapivsky (2002) conjecture that, for the discrete-time Ulam–Kac process, the limiting distribution of log *X*_{n}, suitably scaled, is normally distributed; this conjecture was suggested by Monte Carlo simulations. Similar simulations of the Poisson-regulated Ulam–Kac process lead us to the same conjecture in that case. Any proof seems elusive. Most other natural questions about these processes, such as first passage distributions and autocorrelation structure, also remain intractable.

## Footnotes

- Received October 29, 2007.
- Accepted January 7, 2008.

- © 2008 The Royal Society