Hydrodynamical methods for analyzing longest increasing subsequences.
Let Ln be the length of the longest increasing subsequence of a random permutation of the numbers 1 .... , n, for the uniform distribution on the set of permutations. We discuss the "hydrodynamical approach" to the analysis of the limit behavior, which probably started with Hammersley (Proceedings of the 6th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1 (1972) 345-394) and was subsequently further developed by several authors. We also give two proofs of an exact (non-asymptotic) result, announced in Rains (preprint, 2000).
Introduction
In recent years quite spectacular advances have been made with respect to the distribution theory
of longest increasing subsequences L n of a random permutation of the numbers 1, . , n, for the
uniform distribution on the set of permutations. Recent reviews of this work are given in Aldous
and Diaconis (1999) and Deift (2000).
However, rather than trying to give yet another review of this recent work, I will try to give a
description of a di#erent approach to the theory of the longest increasing subsequences, which in
Aldous and Diaconis (1995) is called "hydrodynamical".
As an example of a longest increasing subsequence we consider the permutation
also used as an example in Aldous and Diaconis (1999). A longest increasing subsequence is:
(1, 3, 4, 6, 9).
and another longest increasing subsequence is:
(2, 3, 4, 6, 9).
MSC 2000 subject classifications. Primary: 60C05,60K35, secondary 60F05.
Key words and phrases. Longest increasing subsequence, Ulam's problem, Hammersley's process.
For this example we get
It was proved in Hammersley (1972) that, as n #,
-# denotes convergence in probability, and
lim
for some positive constant c, where #/2 # c # e. Subsequently Kingman (1973) showed that
and later work by Logan and Shepp (1977) and Vershik and Kerov (1977) (expanded more fully
in Vershik and Kerov (1981) and Vershik and Kerov (1985)) showed that actually 2. The
problem of proving that the limit exists and finding the value of c has been called "Ulam's problem'',
see, e.g., Deift (2000), p. 633.
In proving that Aldous and Diaconis (1995) replace the hard combinatorial
work in Logan and Shepp (1977) and Vershik and Kerov (1977), using Young tableaux by
"hydrodynamical argument", building on certain ideas in Hammersley (1972), and it is this
approach I will focus on in the present paper.
I will start by discussing Hammersley (1972) in section 2. Subsequently I will discuss the
methods used in Aldous and Diaconis (1995) and Sepp al ainen (1996). Slightly as a side-track,
I will discuss an exact (non-asymptotic) result announced in Rains (2000), for which I have not
seen a proof up till now, but for which I will provide a hydrodynamical proof below. Finally, I will
discuss the rather simple (and also hydrodynamical) proof of
Hammersley's approach
The Berkeley symposium paper Hammersley (1972) is remarkable in several ways. The opening
sentences are: "Graduate students sometimes ask, or fail to ask: "How does one do research in
mathematical statistics?" It is a reasonable question because the fruits of research, lectures and
published papers bear little witness to the ways and means of their germination and ripening".
This beginning sets the tone for the rest of the paper, where Hammersley describes vividly the
germination and ripening of his own research on the subject.
In section 3, called "How well known is a well-known theorem?", he describes the di#culties
encountered in finding a reference for a proof of the following theorem:
Theorem 2.1 Any real sequence of at least mn+1 terms contains either an ascending subsequence
of m+ 1 terms or a descending subsequence of n
This result, due to Erd os and Szekeres (1935), is called the "pigeonhole principle" in
Hammersley (1972), a term also used by other authors. A nice description of this problem and
other related problems is given in Aigner and Ziegler (1998). The relevance of the pigeonhole
principle for the behavior of longest increasing subsequences is that one can immediately conclude
from it that
As noted in Deift (2000), it is probable that Ulam, because of a long and enduring friendship
with Erdos, got interested in determining the asymptotic value of EL n and for this reason started
(around 1961) a simulation study for n in the range 1 # being very large at the
time, quoting Deift (2000)), from which he found
leading him to the conjecture that
lim
exists. This is the first part of "Ulam's problem'', the second part being the determination of c.
Relation (2.1) then shows:
c #2 ,
if we can deal with the first part of Ulam's problem (existence of the limit (2.2)).
The first part of Ulam's problem is in fact solved in Hammersley (1972). It is Theorem 2.2
below (Theorem 4 on p. 352 of Hammersley (1972)):
Theorem 2.2 Let .) be an i.i.d. sequence of real-valued continuously distributed
random variables, and let, respectively, L n and L # n be the lengths of a longest increasing and a
longest decreasing subsequence of (X 1 , . , X n ). Then we have:
-# c and L # n / # n
for some positive constant c, where p
-# denotes convergence in probability. We also have
convergence in the pth absolute mean of L n
Note that, for a sample of n continuously distributed random variables, the vector of ranks
(R 1 , . , R n ) of the random variables X 1 , . , X n (for example ordered according to increasing
magnitudes) has a uniform distribution over all permutations of (1, . , n). Because of the
continuous distribution we may disregard the possibility of equal observations ("ties"), since this
occurs with probability zero. So the random variable L n , as defined in Theorem 2.2, indeed
has exactly the same distribution as the length of a longest increasing subsequence of a random
permutation of the numbers 1, . , n, for the uniform distribution on the set of permutations.
The key idea in Hammersley (1972) is to introduce a Poisson process of intensity 1 in the
first quadrant of the plane and to consider longest North-East paths through points of the Poisson
point process in squares [r, North-East path in the square [r, s] 2 is a
sequence of points (X 1 of the Poisson process such that X 1 < . < X k
and Y 1 < . < Y k . We call k the length of the path.
Note that we can disregard the probability that since this
happens with probability zero. A longest North-East path is a North-East path for which k is
largest. Conditional on the number of points of the Poisson process in [r, s] 2 , say n, the length of
the longest North-East path has the same distribution as the longest increasing subsequence of a
random permutation of 1, . , n. This follows from the fact that, if (U 1 , are the
points of the Poisson process belonging to [r, s] 2 , where we condition on the event that the number
of points of the Poisson process in [r, s] 2 is equal to n, and if V (1) < . < V (n) are the order statistics
of the second coordinates, then the corresponding first coordinates U k1 , . , U kn behave as a sample
from a Uniform distribution on [r, s]. A longest increasing North-East path will either consist of
just one point (provided that the rectangle contains a point of the Poisson process, otherwise the
length will be zero) or be a sequence of the form:
< . < U k j
. So the length of a longest North-East path in [r, s] 2 , conditionally
on the number of points in [r, s] 2 being n, is distributed as the longest increasing subsequence of the
sequence random variables (U 1 , . , U n ), and hence, by the remarks following Theorem 2.2 above,
distributed as the length of a longest increasing subsequence of a permutation of the numbers
1, . , n. If the length is zero and everything is trivial of course.
Following Hammersley (1972), we denote the length of a longest North-East path in the square
[r, s] 2 by W r,s , and for the collection of random variables {W r,s obviously
have the so-called superadditivity property:
meaning that -W r,t has the subadditivity property:
Furthermore, we clearly have, for each r > 0, that # W nr,(n+1)r is an i.i.d. sequence
of random variables, since W nr,(n+1)r is a function of the Poisson point process restricted to the
square [nr, (n+1)r] 2 , and since the restrictions of the Poisson point process to the squares [nr, (n+
are i.i.d. For the same type of reason, the distribution of W r,r+k does not depend on r # (0, #).
Finally max{0, -W 0,n each n, and it will be shown below (see (2.11)) that
for a finite constant K > 0. So we are in a position to apply Liggett's version of Kingman's
subadditive ergodic theorem,
r
a.s.
r
, r #.
and also
r
r
, r #.
Hammersley next defines t(n) as the smallest real number such that [0, t(n)] 2 contains exactly
n points of the Poisson process. Then it is clear from the properties of the Poisson point process
in
that
a.s.
and hence that
a.s.
and
where the constant c is the same in (2.4) and (2.5). But since W 0,t(n) has the same distribution as
we obtain from (2.4)
-# denotes convergence in probability, and from (2.5),
Remark. Note that we went from the almost sure relation (2.4) to the convergence in probability
(2.6) for the original longest increasing subsequence, based on a random permutation of the numbers
1, . , n. It is possible, however, also to deduce the almost sure convergence of L n / # n from (2.4),
using an extra tool, as was noticed by H. Kesten in his discussion of Kingman (1973) (see p. 903
of Kingman (1973)). I want to thank a referee for giving the latter reference, setting "the record
straight" for this issue that was still bothering Hammersley in Hammersley (1972).
From (2.1) we now immediately obtain
(see also the remark below (2.2)), but we still have to prove (2.3). This problem is dealt with by
Theorem 2.3 below (Theorem 6 on p. 355 of Hammersley (1972)):
Theorem 2.3 Let, for x # IR, #x# be the smallest integer # x, and let, for a fixed t # 0 and each
positive integer N , denote the uniform distribution on the set of
permutations of the sequence (1, . , N) with corresponding expectation EN , let # N
be the length of a
longest monotone (decreasing or increasing) subsequence of a permutation of the numbers 1, . , N ,
and let m n,N the number of monotone subsequences of length n under the probability measure PN .
Then we have
e -2t
Proof: This is proved by an application of Stirling's formula (for details of this computation
which is not di#cult, see Hammersley (1972), pp. 355-356). #
Elementary calculations show that Theorem 2.3 implies:
for a constant K > 0. Returning to the situation of longest increasing North-East paths in the
plane, we obtain from (2.10)
which proves (2.3). Moreover, we have:
lim sup
e,
using Theorem 2.3.
Combining this result with (2.6) and (2.7), we obtain:
e,
and, in particular, it is proved that c # (0, #), since also c # 1/2, by (2.8).
So the first part of Ulam's problem is now solved, and we know that the constant c in the limit
(2.2) is a number between 1/2 and e. As noted above, Hammersley improved the lower bound to
#/2 and in Kingman (1973) the bounds were tightened further to
However, Hammersley was in fact quite convinced that p. 372 of Hammersley (1972),
where he says: "However, I should be very surprised if (12.12) is false", (12.12) being the statement
his paper). Hammersley (1972) contains three "attacks on c" of which we will discuss
the third attack, since the ideas of the third attack sparked other research, like the development
in Aldous and Diaconis (1995). Somewhat amusingly, his second attack yielded c # 1.961, but
apparently he did not believe too much in that attack, in view of the remark ("I should be very
quoted above.
"Hammersley's process'' is introduced in section 9 of Hammersley (1972). In this section on
Monte Carlo methods he introduces a kind of interacting particle process in discrete time. The
particles of this process all live on the interval [0, 1] and are at "time n" a subset of a Uniform(0,1)
sample . We now give a description of this process.
. be an i.i.d. sequence of Uniform(0,1) random variables, and let, for each n,
be defined by
Moreover let, for x # (0, 1), X x
be defined as the subsequence of X n obtained by omitting all
As before, #(X n ) is the length of the longest increasing subsequence of X n . In a similar
way, #(X x
) is the length of the longest increasing subsequence of X x
. Hammersley now notes that
n ) is an integer-valued step function of x, satisfying the recurrence relation
and that, for a simulation study, one only needs to keep the values of the X i 's, where the function
makes a jump. The recurrence relation starts from:
Suppose that the jumps of the function x # (X x
) occur at the points Y i,n ,
Y 1,n < . < Y I(n),n .
Then it is clear from (2.12) that the jumps of the function x # X x
# occur at the points
Y 1,n+1 < . < Y I(n+1),n+1 ,
which is obtained from the points (2.14) by adding Y to the points (2.14), if
by replacing the smallest value y i,n > X n+1 by X n+1 . Note that
we call the particle process n # Y n Hammersley's discrete time interacting particle process.
In Hammersley (1972) the following simple example is given, clarifying the way in which this
process evolves. Let
Then the sequence (Y 1 , . , Y 6 ) is represented by the sequence of states
So either a new point is added (which happens, e.g., at the second step in the example above), or
the "incoming point" replaces an existing point that is immediately to the right of this incoming
point (this happens, e.g., at the third step in the example above).
We note in passing that the first stage of Viennot's geometric construction of the Robinson-Schensted
correspondence, given in Viennot (1976), is in fact Hammersley's discrete time
interacting particle process on a lattice. A nice exposition of this construction is given in Sagan
(1991).
We can now discuss the "third attack on c" (section 12 in Hammersley (1972)). The argument
at the bottom of p. 372 and top of p. 373 is close to the equation (9) of Aldous and Diaconis (1995),
(as pointed out to me by Aldous (2000)), and is the hydrodynamical argument that inspired the
approach in Aldous and Diaconis (1995). The argument (called "treacherous" by Hammersley)
runs as follows.
. be i.i.d. Uniform(0,1) random variables, and let Y 1,n < . < Y I(n),n be the
points of Hammersley's discrete time interacting particle process at time n, associated with the
sample described above. Moreover, let # (X n ) be the length of a longest increasing
subsequence of X 1 , . , X n . Then we have:
since # (X n+1
#, we have (quoting Hammersley (1972), bottom of p. 372) that "the left
side of (2.16) is the result of di#erencing c # n n) with respect to n, and ought to be about2 c/ # n if the error term is smooth". Continuing quoting Hammersley (1972) (top of p. 373) we
get that "the right side of (2.16) is the displacement in x near just su#cient to ensure unit
increase in #(X x
and should be the reciprocal of #
) at namely 2/ (c # n)". The last
statement is referring to relation (12.1) on p. 370 of Hammersley (1972), which is:
There is of course some di#culty in interpreting the equality sign in (2.17), does it mean "in
probability", "almost surely" or is an asymptotic relation for expectations meant? Let us give
(2.17) the latter interpretation. Then we would get from (2.16), following Hammersley's line of
argument:
c
This would yield 2. Following Hammersley's daring practice (in section 12 of Hammersley
(1972)) of di#erentiating w.r.t. a discrete parameter (in this case n), we can rewrite (2.18) in the
#n
c
or
#n
#x
We shall return to equation (2.20) in the next sections, where it will be seen that it can be given
di#erent interpretations, corresponding to the di#erent approaches in Aldous and Diaconis (1995)
and Groeneboom (2000) (and perhaps more implicitly in Sepp al ainen (1996)).
3 The Hammersley-Aldous-Diaconis interacting particle process
As I see it, one major step forward, made in Aldous and Diaconis (1995), is to turn Hammersley's
discrete time interacting particle process, as described in section 2, into a continuous time process.
One of the di#culties in interpreting relation (2.20) is the di#erentiation w.r.t. the discrete time
parameter n, and this di#culty would be removed if we can di#erentiate with respect to a continuous
time parameter (but other di#culties remain!).
The following gives an intuitive description of the extension of Hammersley's process on IR
to a continuous time process, developing according to the rules specified in Aldous and Diaconis
(1995). Start with a Poisson point process of intensity 1 on IR 2
. Now shift the positive x-axis
vertically through (a realization of) this point process, and, each time a point is caught, shift to
this point the previously caught point that is immediately to the right.
Alternatively, imagine, for each x > 0, an interval [0, x], moving vertically through the Poisson
point process. If this interval catches a point that is to the right of the points caught before, a
new extra point is created in [0, x], otherwise we have a shift to this point of the previously caught
point that is immediately to the right and belongs to [0, x] (note that this mechanism is exactly the
same as the mechanism by which the points Y i,n of Hammersley's discrete time process are created
in section 2). The number of points, resulting from this "catch and shift" procedure at time y on
the interval [0, x], is denoted in Aldous and Diaconis (1995) by
So the process evolves in time according to "Rule 1" in Aldous and Diaconis (1995), which is
repeated here for ease of reference:
Rule 1 At times of a Poisson (rate x) process in time, a point U is chosen uniformly on [0, x],
independent of the past, and the particle nearest to the right of U is moved to U , with a new particle
created at U if no such particle exists in [0, x].
We shall call this process the Hammersley-Aldous-Diaconis interacting particle process. For a
picture of the space-time curves of this process, see Figure 1; an "#-point" is an added point and
a "#-point" is a deleted point for this continuous time process (time is running along the vertical
axis).
In Hammersley's ``third attack on c'', one of the crucial assumptions he was not able to prove
was the assumption that the distribution of the points Y i,n was locally homogeneous, so, actually,
is locally behaving as a homogeneous Poisson process; he calls this "assumption #" (p. 371 of
Hammersley (1972)). This key assumption is in fact what is proved in Aldous and Diaconis
(1995) for the Hammersley-Aldous-Diaconis interacting particle process in Theorem 5 on p. 204
(which is the central result of their paper):
(0,y)
a-point b-point

Figure

1: Space-time curves of the Hammersley-Aldous-Diaconis process, contained in [0, x][0, y].
Theorem 3.1 (a) 2.
(b) For each fixed a > 0, the random particle configuration with counting process
y,
converges in distribution, as t #, to a homogeneous Poisson process with intensity a -1 .
After stating this theorem, they give the following heuristic argument. Suppose the spatial
process around position x at time t approximates a Poisson process of some rate #(x, t). Then
clearly
#t
where D x,t is the distance from x to the nearest particle to the left of x. For a Poisson process,
ED x,t would be 1/(spatial rate), so
ED x,t ##(x, t) ##
In other words, w(x, approximately the partial di#erential equation
#w
#x
#w
#t
whose solution is w(x, tx. Note that (3.1) is very close to (2.20) above, but that
we got rid of the di#erentiation w.r.t. a discrete time parameter!
Appealing as the above argument may seem, a closer examination of Aldous and Diaconis
(1995) learns that their proof not really proceeds along the lines of this heuristic argument. In
fact, they prove separately that c # 2 and that c # 2, by arguments that do not seem to use the
di#erential equation (3.1). The proofs of c # 2 and of c # 2 are based on coupling arguments,
where the Hammersley-Aldous-Diaconis process is coupled to a stationary version of this process,
starting with a non-empty configuration, and living on IR instead of IR + . This process evolves
according to the following rule (p. 205 of Aldous and Diaconis (1995)).
Rule 2 The restriction of the process to the interval [x 1 ,
(i) There is some arbitrary set of times at which the leftmost point (if any) in the interval is
removed.
(i) At times of a rate x 2 -x 1 Poisson process in time, a point U is chosen uniformly on [x 1 , x 2 ],
independent of the past, and the particle nearest to the right of U is moved to U , with a new
particle created at U if no such particle exists in [x 1 , x 2 ].
To avoid a possible misunderstanding, rule 2 above is not the same a "rule 2" in Aldous and
Diaconis (1995). The existence of such a process is ensured by the following lemma (Lemma 6 in
Aldous and Diaconis (1995))
Lemma 3.1 Suppose an initial configuration N(, 0) of particles in IR satisfies
lim inf
x#
x
> 0, a.s.
Let P be a Poisson point process of intensity 1 in the plane, and let L # ((z, 0), (x, t)) be the maximal
number of Poisson points on a North-East path from (z, 0) to (x, t), in the sense that it is piecewise
linear with vertices (z, 0),
t, for points belonging a realization of P, and such that k is largest.
Then the process, defined by
-#<z#x
evolves according to Rule 2.
A process of this type is called "Hammersley's process on IR'' in Aldous and Diaconis (1995),
but we will call this the Hammersley-Aldous-Diaconis process on IR. As an example of such a
process, consider an initial configuration, corresponding to a Poisson point process P # of intensity
# > 0. The initial configuration will be invariant for the process; that is: N(, t) will have the same
distribution as P # , for each t > 0. The following key lemma (Lemma 7 in Aldous and Diaconis
(1995)) characterizes the invariant distributions the process on IR.
Lemma 3.2 A finite intensity distribution is invariant and translation-invariant for the
Hammersley-Aldous-Diaconis process on IR if and only if it is a mixture of Poisson point processes
Other key properties are given in the next lemma (part (i) is Lemma 8, part (ii) and (iii) are
Lemma 3, and part (iv) is Lemma 11 in Aldous and Diaconis (1995)).
Lemma 3.3 (i) Let N be a Hammersley-Aldous-Diaconis process on IR, with the invariant
distribution
N(x, t) be defined by
number of particles of {N(s, (t, #)} which exit during the time interval [0, x].
Hammersley-Aldous-Diaconis process on IR, with invariant
distribution P 1/# .
(ii) (Space-time interchange property) Let
Then
(iii) (Scaling property) For all x, y, k > 0,
(iv) For fixed x, y # IR we have:
lim
Part (ii) and (iii) are immediately clear from the fact that the distribution of
only depends on the area of the rectangle [x 1 , y 1 since the expected
number of points of the Poisson point process only depends on the area of the recatangle, and since
the shape of the rectangle has no influence on the distribution of L # ((x 1 , y 1 )). The proofs
of (i) and (iv) rely on somewhat involved coupling arguments, and we refer for that to Aldous and
Diaconis (1995).
The argument for c # 2 now runs as follows. The processes
have subsequential limits, which have to be translation-invariant and invariant for the Hammersley-
Aldous-Diaconis process. By part (ii) of Lemma 3.3 (the space-time interchange property)) these
limit processes must have the same distribution. By Lemma 3.2 and the invariance properties
the limit process must have, these processes must be mixtures of Poisson pocesses. Suppose the
subsequential limit of the process t # N(t is such a mixture of Poisson processes with
random intensity #. Then, according to part (i) of Lemma 3.3, the subsequential limit of the
process must be a mixture of Poisson processes with random intensity # -1 . We have
and, by Jensen's inequality, E# implying
But, since the limit processes must have the same distribution, we also have
hence
implying E# 1. Using this fact, in combination with Fatou's lemma and part (iv) of Lemma 3.3,
we get
is the sequence for which we have the subsequential limit. Hence c # 2.
Proving c # 2 is easier; it is proved by a rather straightforward coupling argument in Aldous
and Diaconis (1995) and it also follows from the result in section 4 below (see the last paragraph
of section 4). So the conclusion is that 2. Moreover, since # d
and since the covariance
of # and # -1 is equal to zero, we can only have: almost surely. This proves part (b) of
Theorem 3.1 for the case a = 1, and the case a #= 1 then follows from part (iii) of Lemma 3.3.
4 An nonasymptotic result for longest North-East paths in the
unit square
The purpose of the present section is to give a proof of the following result.
Theorem 4.1 Let P 1 be a Poisson process of intensity # 1 on the lower edge of the unit square
process of intensity # 2 on the left edge of the unit square, and P a Poisson
process of intensity # 1 # 2 in the interior of the unit square. Then the expected length of a longest
North-East path from (0, 0) to (1, 1), where horizontal or vertical parts are allowed at the start of
the path, is equal to # 1
Here, as before, the length of the path is defined as the number of points of the point process,
"picked up" along the path. However, in the present situation it is allowed to pick up points from
the boundary, and, moreover, there are Poisson point processes on both the left and the lower
boundary. The exact result about the expectation of the length of the longest North-East path
(for the case # announced in Rains (2000), who refers to a manuscript in preparation of
Prahofer and Spohn (which I have not seen).
The idea of the proof is to show that if we start with the (possibly empty) configuration of points
on the lower edge, and let the point proces develop according to the rules of the Hammersley-Aldous-
Diaconis process, where we let the leftmost point "escape" at time t, if the left edge of the unit
square contains a point of the Poisson process of intensity # 2 at (0, t), the process will be stationary.
This means that the expected number of points of the process will be equal to # 1 at each time t, so
in particular at time t = 1. Since the expected number of points on the left edge is # 2 , the expected
number of space-time curves of the Hammersley-Aldous-Diaconis process (with "left escapes") will
be This implies the result, since the length of a longest North-East path is equal to the
number of space-time curves (note that such a longest North-East path "picks up" one point from
each space-time curve).
A proof of Theorem 4.1 in the spirit of the methods used in Aldous and Diaconis (1995) and
al ainen (1996) would run as follows. Start with a Poisson process # 0 of intensity # 1 on IR
and a Poisson process of intensity # 1 # 2 in the upper half plane. Now let the Poisson process # 0
develop according to the rules of the Hammersley-Aldous-Diaconis process on the whole real line,
and let # t denote the process at time t. Then the process {# will be invariant in the sense
that it will be distributed as a Poisson process of intensity # 1 at any positive time. The restriction
of # t to the interval [0, 1] will be a Poisson process of intensity # 1 on this interval. Since (by the
"bus stop paradox") the distribution of the distance of the rightmost point in the interval (-#,
to 0 will have an exponential distribution with (scale) parameter 1/# 1 , the leftmost points in the
interval [0, 1] will escape at rate # 2 , because an escape will happen if a new point is "caught" in
the interval between the rightmost point of the process in (-#, 0) and 0, and because the intensity
of the Poisson process in the upper half plane is # 1 # 2 . So the point process on [0, 1], induced
by the stationary process {# t : t # 0} on IR, develops exactly along the rules of the Hammersley-
Aldous-Diaconis process "with left escapes", described above, and the desired stationarity property
follows.
The proof of Theorem 4.1 below uses an "infinitesimal generator" approach. It is meant to draw
attention to yet another method that could be used in this context and this is the justification of
presenting it here, in spite of the fact that it is much longer than the proof we just gave (but most
of the work is setting up the right notation and introducing the right spaces). Also, conversely,
the proof below can be used to prove the property that a Poisson process on IR is invariant for the
Hammersley-Aldous-Diaconis process; this property is a key to the proofs in Aldous and Diaconis
(1995).
Let # denote a point process on [0, 1]. That is, # is a random (Radon) measure on [0, 1], with
realizations of the form
are the points of the point process # and f is a bounded measurable function
. If we define the right side of (4.1) to be zero.
We can consider the random measure # as a random sum of Dirac measures:
and hence
for Borel sets B # (0, 1). So #(B) is just the number of points of the point process #, contained in
B, where the sum is defined to be zero if The realizations of a point process, applied on
Borel subsets of [0, 1], take values in Z+ and belong to a strict subset of the Radon measures on
[0, 1]. We will denote this subset, corresponding to the point processes, by N , and endow it with the
vague topology of measures on [0, 1], see, e.g., Kallenberg (1986), p. 32. For this topology, N is a
(separable) Polish space and a closed subset of the set of Radon measures on [0, 1], see Proposition
15.7.7 and Proposition 15.7.4, pp. 169-170, Kallenberg (1986). Note that, by the compactness of
the interval [0, 1], the vague topology coincides with the weak topology, since all continuous functions
contained in the compact interval [0, 1]. For this reason we
will denote the topology on N by the weak topology instead of the vague topology in the sequel.
Note that the space N is in fact locally compact for the weak topology.
In our case we have point processes # t , for each time t # 0, of the form
denotes the number of points at time t, and where defined
to be the zero measure on [0, 1], if N if we start with a Poisson process of intensity
the initial configuration # 0 will with probability one be either the zero measure or be of the
for some n > 0, but since we want to consider the space of bounded continuous functions on N ,
it is advantageous to allow configurations where some # i 's will be equal. We also allow the # i 's to
take values at 0 or 1. If we have a "stack" of # i 's at the same location in (0, 1], we move one point
("the point on top") from the stack to the left, if a point immediately to the left of the location
of the stack appears, leaving the other points at the original location. Likewise, if a stack of # i 's is
located at 0, we remove the point on top of the stack at time t if the Poisson point process on the
left lower boundary has a point at (0, t).
Now let F c be the Banach space of continuous bounded functions # with the supremum
norm. For # N and t > 0 we define the function P
We want to show that the operator P t is a mapping from F c into itself.
Boundedness of P t # is clear if # : N # IR is bounded and continuous, so we only must prove
the continuity of P t #, if # is a bounded continuous function # : N # IR. If # is the zero measure
and sequence of measures in N , converging weakly to #, we must have:
lim
and hence # n ([0, large n. This implies that
for all large n. If
sequence of measures in N , converging
weakly to #, we must have # n ([0, is of the form
for all large n. Moreover, the ordered # n,i 's have to converge to the ordered # i 's in the Euclidean
topology. Since the x-coordinates of a realization of the Poisson process of intensity # 1 # 2 in (0, 1)
(0, t] will with probability one be di#erent from the # i 's, sample paths of the processes {#
either starting from # or from # n , will develop in the same way, if n is su#ciently large, for such a
realization of the Poisson process in (0, 1)  (0, t]. Hence
lim
So we have:
lim
if the sequence (# n ) converges weakly to #, implying the continuity of P t #.
process with respect to the natural filtration {F
generated by this process, we have the semi-group property
for bounded continuous functions # Moreover, we can define the generator G of the
process working on the bounded continuous functions #
if # is the zero measure on (0, 1), and by
defined by
The first term on the right of (4.5) corresponds to the insertion of a new point in one of the intervals
the shift of # i to this new point if the new point is not in the rightmost interval, and
the second term on the right of (4.5) corresponds to an "escape on the left". Note that G#) is
computed by evaluating
lim
# .
The definition of G can be continuously extended to cover the configurations
working with the extended definition of P t , described above.
So we have a semigroup of operators P t , working on the Banach space of bounded continuous
G. It now follows from Theorem 13.35 in Rudin (1991) that
we have the following lemma.
Lemma 4.1 Let N be endowed with the weak topology and let # : N # IR be a bounded continuous
function. Then we have, for each t > 0,
d
dt
Proof: It is clear that the conditions (a) to (c) of definition 13.34 in Rudin (1991) are satisfied,
and the statement then immediately follows. #
We will also need the following lemma (this is the real "heart" of the proof).
Lemma 4.2 Let for a continuous function f : [0, , the function be defined
by
Then:
Proof. We first consider the value of GL f (# 0 ) for the case where # 0 is the zero measure, i.e., the
interval [0, 1] contains no points of the point process # 0 . By (4.4) we then have:
x
Hence:
e -f(x)-f(u) dx du
e -f(x)-f(u) dx du.
Now generally suppose that, for n > 1,
Then, by a completely similar computation, it follows that
So we get
since
and similarly
We now have the following corollary.
Corollary 4.1 Let # : N # IR be a continuous function with compact support in N . Then:
Proof. Let C be the compact support of # in N . The functions L f , where f is a continuous
are closed under multiplication and hence linear combinations of these
functions, restricted to C, form an algebra. Since the constant functions also belong to this algebra
and the functions L f separate points of C, the Stone-Weierstrass theorem implies that # can be
uniformly approximated by functions from this algebra, see, e.g., Dieudonn e (1969), (7.3.1), p.
137. The result now follows from Lemma 4.2, since G is clearly a bounded continuous operator on
the Banach space of continuous functions
Now be a continuous function with compact support in N . Then P t # is also
a continuous function with compact support in N , for each t > 0. By Corollary 4.1 we have:
Hence, by Lemma 4.1,
implying
for each continuous function # : N # IR with compact support in N . But since N is a Polish space,
every probability measure on N is "tight", and hence # t has the same distribution as # 0 for every
(here we could also use the fact that N is in fact locally compact for the weak topology).
Theorem 4.1 now follows as before.
Remark. For a general result on stationarity of interacting particle processes (but with another
state space!), using an equation of type (4.13), see, e.g., Liggett (1985), Proposition 6.10, p. 52.
The argument shows more generally that, if we start with a Poisson point process of intensity
and a Poisson point process of intensity
, the starting distribution
on IR + is invariant for the Hammersley-Aldous-Diaconis process, if we let points escape at zero at
rate # 2 .
It is also clear that the inequality c # 2 follows, since the length of a longest North-East path
from (0, 0) to a point (t, in the construction above, be always at least as big
as the length of a longest North-East path from (0, 0) to a point (t, t), if we start with the empty
configuration on the x- and y-axis: we simply have more opportunities for forming a North-East
path, if we allow them to pick up points from the x- or y-axis. Since, starting with a Poisson
process of intensity 1 in the first quadrant, and (independently) Poisson processes of intensity 1 on
the x- and y-axis, the expected length of a longest North-East path to (t, t) will be exactly equal
to 2t, according to what we proved above, we obtain from this c # 2.
5 Seppalainen's stick process
The result proved by hydrodynamical arguments in sections 8 and 9 of Sepp al ainen (1996).
I will summarize the approach below.
First of all, a counting process on IR instead of (0, #) is used, and for this process a number
of starting configurations are considered. Note that we cannot start with the empty configuration
on IR, since points would immediately be pulled to -#, as noted in Aldous and Diaconis (1995).
For the purposes of proving 2, the most important starting configurations are:
(i) a Poisson process of intensity 1 on (-#, 0] and the empty configuration on (0, #).
(ii) a Poisson process of intensity 1 on IR.
Let (z k ) k#Z be an initial configuration on IR. Seppalainen's stick process is defined as a process of
functions associated with this particle process, by
Instead of z k (0) we write z k .
We now define
and
-#<z#x
where L # ((z, 0), (x, y)) is the maximum number of points on a North-East path in (z, x]  (0, y],
as in Lemma 3.1 of section 3.
as the maximum number of points on a North-East path in
. The key to the approach in Sepp al ainen (1996) is to work with a kind of inverse of (5.2),
defined by
in words: # ((x 1 , y 1 is the minimum horizontal distance needed for building a North-East
path of k points, starting at in the "time interval" (y 1 , y 2 ]. This can be seen as another way
of expanding relation (2.16), which, in fact, is also a relation between the discrete time Hammersley
process and its inverse.
Now, given the initial configuration (z k ) k#Z , the position of the particle z k at time y > 0 is
given by
z
Note that for each point point z k (y) at time y, originating from z k in the original configuration,
there will always be a point z j of the original configuration, with j # k, such that
For example, if z k-1 < z k (y) < z k we get a path of length 1 from z k-1 to z k (y), and
Similarly, if z k (y) < z k-1 , we can always construct a path from a point z j , with j < k to z k (y)
through points of the Poisson point process, "picked up" by the preceding paths ("seen from z k (y)",
these are descending corners in the preceding paths).
These points need not be uniquely determined. Proposition 4.4 in Sepp al ainen (1996) clarifies
the situation. It asserts that almost surely (that is: for almost every realization of the point
processes) we have that for all y > 0 and each k # Z there exist integers i - (k, y) and i
that
z
holds
The proof of this
Proposition 4.4 in Sepp al ainen (1996) is in fact fairly subtle!
We now first consider (proceeding a little bit di#erently than in Sepp al ainen (1996)) the
evolution of the initial configuration on (-#, 0] in the case that we have a Poisson process of
intensity 1 on (-#, 0] and the empty configuration on (0, #), using the same method as used in
section 4. Let F be the set of continuous functions f
We denote the point process of the starting configuration by # 0 and the configuration at time t > 0
by # t , where we let it develop according to the rules of the Hammersley-Aldous-Diaconis process.
Then, just as before, we can prove
lim
for f # F . So, in the case that we have a Poisson process of intensity 1 on (-#, 0], the empty
configuration on (0, #), and a Poisson process of intensity 1 in the upper half plane, the distribution
of the initial confirguration is invariant for the Hammersley-Aldous-Diaconis process.
Let P 0 be the probability measure, associated with the initial configuration (i) in the beginning
of this section, and let, for (the length of the "stick" at location i), where
we let z -1 be the biggest point of the initial configuration in (-#, 0). Moreover, let the measure
m 0 on the Borel sets of IR be defined by
and let # defined for all i # Z). Then we have, for each # > 0, and
each interval [a, b] # IR:
lim
which corresponds to condition (1.10) in Sepp al ainen (1996). This condition plays a similar role
as condition (3.2) in section 3 above. Here [x] denotes the largest integer # x, for x # IR. It is then
proved that, if x > c 2 y/4
y,
where u is a (weak) solution of the partial di#erential equation
#y
#x
under the initial condition u(x, since we also have
if we can prove
lim
This is in fact proved in Sepp al ainen (1996) on page 32. The first term on the right of (5.8) comes
from 1
using
We return to (5.6). Another interpretation of this relation is
where
z
and
z#x
using Theorem A1 on p. 38 of Sepp al ainen (1996), with
This corresponds
to relation (8.8) on p. 29 of Sepp al ainen (1996), which implies that
An easy calculation shows:
since U(x, y) # 0 (note that z # 0 since U(x, y) < 0 can only
occur if x - 1
which case the minimizing z is given by z
y. Note that
y, and that the right side of (5.9) in this case is given by
y.
So the partial di#erential equation (5.7), with initial condition
is solved by
which, considered as a function of x, is the Radon-Nikodym derivative of the Borel measure m y on
IR, defined by
Note that u only solves (5.7) in a distributional sense. That is: for any continuously
di#erentiable "test compact support and any y > 0, we have:
see also (1.6) on p. 5 of Sepp al ainen (1996).
We note that in Seppalainen's interpretation of the particle process, we cannot get new points
to the right of zero in the situation where we start with a Poisson point process of intensity 1 on
(-#, 0] and the empty configuration on (0, #). In this situation we have z so we
have infinitely many particles at location z -1 . This means that at each time y, where a new point
of the Poisson point process in the plane occurs with x-coordinate just to the left of x-1 , and also
to the right of points z i (y), satisfying z i (y) < z -1 , one of the infinitely many points z i (y) that are
still left at location z -1 shifts to the x-coordinate of this new point. Seppalainen's interpretation
with the "moving to the left" is perhaps most clearly stated in the first paragraph of section 2 of
al ainen (1998).
In the interpretation of Seppalainen's ``stick process'', we would have an infinite number of sticks
of zero length at sites 0, 1, 2, . Each time an event of the above type occurs, one of the sticks
of length zero gets positive length, and the stick at the preceding site is shortened (corresponding
to the shift to the left of the corresponding particle in the particle process). In this way, mass
gradually shifts to the right in the sense that at each event of this type a new stick with an index
higher than all indices of sticks with positive length gets itself positive length. The corresponding
"macroscopic" picture is that the initial profile u(, shifts to u(,
y.
The interpretation of the relation
taking in (5.10), is that z [tx] (0) travels roughly over a distance t(y -x) to the left in the time
interval [0, ty], if y > x # 0 (we first need a time interval tx to get to a "stick with index [tx]" and
length zero, then another time interval of length t(y - x) to build a distance left from zero of order
t(y - x)), and that (with high probability) z [tx] (0) does not travel at all during this time interval,
if x > y (a "stick with index [tx]" is not reached during this time interval).
6 An elementary hydrodynamical proof of
It turns out that a very simple proof of the result possible, only using the subadditive ergodic
theorem and almost sure convergence of certain signed measures, associated with the Hammersley-
Aldous-Diaconis process. We give the argument, which is based on Groeneboom (2000), below.
be the length of a longest increasing sequence from (0, 0) to (x, y) in the rectangle
[0, x]  [0, y], if we start with the empty configuration on IR + and a Poisson point process of
intensity 1 in IR 2
. has the same meaning as N + (x, y) in Aldous and Diaconis (1995),
see section 3 above. We further call a point of the Poisson point process in IR 2
an #-point and a
point where a Hammersley-Aldous-Diaconis space-time curve has a North-East corner a #-point.
The situation is illustrated in Figure 1, where the number of #-points and #-points is 9 and 5,
respectively, and N
has the following alternative interpretation:
number of #-points in B minus number of #-points in B.
So we can associate with N + (x, y) a random signed measure, defined by:
number of #-points in B minus number of #-points in B,
for Borel sets B # IR 2
, and we shall write
dN(x, y).
Note that N now has an interpretation di#erent from that in sections 3 and 5.
In a similar way we can associate a random measure V t with the process
We get:
{ number of #-points in tB minus number of #-points in tB},
where the set tB is defined by
Furthermore, we define:
{number of #-points in [0, tx]  [0, ty]}
and
{number of #-points in [0, tx]  [0, ty]}.
With these definitions we clearly have:
Moreover, we define
so we omit the upper edge of the rectangle [0, x]  [0, y] (we can also omit the right edge of this
rectangle, but not both edges, as will be clear from the sequel!). With these definitions we have
the following lemma.
Lemma 6.1 For each rectangle
Proof. Suppose (as we may) that the boundary of the rectangle [0, tx]  [0, ty] does not contain
#- or #-points. Further suppose that there are m space-time curves, going through the rectangle
[0, tx]  [0, ty] (meaning that N(tx,
Crossing the space-time curves, going from (0, 0) in a North-East direction, we can number
these paths as is the path closest to the origin. Then, for an #-point (u, v)
on P i , we get
1)/t, and for a #-point (u, v) on P i , we get
(here the fact
that we omit the upper edge of the rectangle [0, u]  [0, v] becomes important!). Let A 1 be the set
of #-points and A 2 be the set of #-points, contained in [0, tx]  [0, ty], respectively. Then we get:
- 1)#-points on P i } - i#-points on P i }}
But for each space-time curve P i , contained in [0, tx]  [0, ty], we have:
#-points on P i } -points on P i
So we get
From this, the result easily follows. First of all
a.s.
by the subadditive ergodic theorem (this is the fundamental result in Hammersley (1972)). Hence,
by the continuity theorem for almost sure convergence,
a.s.
a.s.
-# 2xy,
since, by (6.3), t a.s.
-# 0, and since 2t
a.s.
(x, y) is the number of
points of the Poisson point proces in [0, tx][0, ty], divided by t 2 . Finally, defining V (x, y)
(i.e., the almost sure limit of V t (x, y)), we get
a.s.
see Groeneboom (2000). The result now follows from (6.4) to (6.6) and Lemma 6.1.
Now, to give some insight into the "germination and ripening of the present proof" and to show
that "it did not spring fully armed like Pallas Athene from the brow of Zeus" (quoting Hammersley
(1972)), consider a twice di#erentiable function (x,
and
#x#y
#x#y
for twice di#erentiable functions f IR. The motivation for looking at (6.8) came from
considering the asymptotic behavior of
#x#y
for twice di#erentiable functions f From a study of the asymptotic behavior of
for small h, k > 0, it can be seen that the following relation has to hold:
#x#y
where G(tx, ty) and H(tx, ty) are the distances between (tx, ty) and the nearest crossings of a
Hammersley-Aldous-Diaconis space-time curve with the line segments
respectively. We conjectured that
lim
implying in particular that
lim
Since it is not di#cult to show that
lim
the statement that would then be equivalent to saying that the covariance between G(tx, ty)
and H(tx, ty) tends to zero, as t #. But since I was not able to prove these conjectures, I looked
for another way to arrive at relation (6.8).
Returning to (6.8), and combining this relation with the straightforward di#erentiation
#x#y
#x#y
#x
#y
we recover the relation:
#x
#y
under the side condition (6.7). Note that this is exactly the partial di#erential equation (3.1) (the
"heuristic argument" in Aldous and Diaconis (1995)), which in turn goes back to the heuristic
relation (2.20) in Hammersley (1972). This partial di#erential equation has as solution:
which is the almost sure limit of V t (x, y).
The (random) function (x, y) # V t (x, y) satisfies the side condition (6.7), but is clearly not
di#erentiable in x and y. However, we might still hope to have a relation of the form
in some sense, for rectangles taking
which leads to the preceding proof.
7 Concluding remarks
In the foregoing sections I tried to explain the "hydrodynamical approach" to the theory of
longest increasing subsequences of random permutations, for the uniform distribution on the set
of permutations. This approach probably started with the paper Hammersley (1972) and the
heuristics that can be found in that paper have been expanded in di#erent directions in the papers
discussed above. The hydrodynamical approach has also been used to investigate large deviation
properties, see, e.g., Sepp al ainen (1998), and for large deviations of the upper tail: Deuschel and
Zeitouni (1999); they still treat the large deviations of the lower tail by combinatorial methods,
using Young diagrams, but apparently would prefer to have a proof of a more probabilistic nature,
as seems clear from their remark: "The proof based on the random Young tableau correspondence
is purely combinatoric and sheds no light on the random mechanism responsible for the large
deviations".
I conjecture that is it is possible to push the hydrodynamical approach further for proving
the asymptotic distribution results in Baik, Deift and Johansson (1999), but at present these
results still completely rely on an analytic representation of the probability distribution of longest
increasing subsequences using Toeplitz determinants, see, e.g. Deift (2000), p. 636.

Acknowledgement

. I want to thank the referees for their constructive comments.



--R

Hammersley's interacting particle process and longest increasing subsequences.
Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
Personal communication.
Proofs from THE BOOK.
On the distribution of the length of the longest increasing subsequences of random permutations.
Integrable systems and combinatorial theory.
On increasing subsequences of I.


A combinatorial problem in geometry.
Ulam's problem and Hammersley's process.
A few seedlings of research.

Random measures
Subadditive ergodic theory.
Interacting particle systems.
A variational problem for random Young tableaux.
A mean identity for longest increasing subsequence problems.
Functional analysis
The symmetric group.


Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux.
Asymptotic behavior of the maximum and generic dimensions of irreducible representations of the symmetric group.
Asymptotic theory of the characters of the symmetric group.
Une forme g
--TR

--CTR
Michael H. Albert , Alexander Golynski , Angle M. Hamel , Alejandro Lpez-Ortiz , S. Srinivasa Rao , Mohammad Ali Safari, Longest increasing subsequences in sliding windows, Theoretical Computer Science, v.321 n.2-3, p.405-414, August 2004
ulam's problem;longest increasing subsequence;hammersley's process