Technische Universität Graz Institut für Mathematik A Central Limit Theorem for Convex Chains in the Square

Imre Bárány  Günter Rote  William Steiger  Cun-Hui Zhang

Report 293 May 1998

[figure]

Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria

Version 2 This is a successor of a report with the title The Limit Shape of Random Convex Polygons by G. Rote from August 1994.

Title page processed by TEX on May 14, 1998

A Central Limit Theorem for Convex Chains in the Square

Imre Bárány

Mathemetical Institute Hungarian Academy of Sciences

Günter Rote^{∗}

Institut für Mathematik Technische Universität Graz

William Steiger

Computer Science Rutgers University

Cun-Hui Zhang

Statistics Rutgers University

May 1, 1998

Abstract

Points P_{1}, …, P_{n} in the unit square define a convex n-chain if they are below y = x and, together with P_{0} = (0, 0) and P_{n+1} = (1, 1), they are in convex position. Under uniform probability, we prove an almost sure limit theorem for these chains that uses only probabilistic arguments, and which strengthens similar limit shape statements established by other authors. An interesting feature is that the limit shape is a direct consequence of the method. The main result is an accompanying central limit theorem for these chains. A weak convergence result implies several other statements concerning the deviations between random convex chains and their limit.

1 Introduction and Summary

Take n points in the unit square in the plane. Write them in order of increasing x-coordinate as P_{1}, …, P_{n} and let P_{0} = (0, 0) and P_{n+1} = (1, 1). The points are the vertices of a convex n-chain if the vectors P_{i+1}−P_{i} have increasing slope, i = 0, …, n. The chain itself is the set of points on the segments that connect successive vertices. To sample a random n-chain C, just take the n points uniformly and independently from the unit square, conditional on the event E that they form a convex chain. This defines the uniform probability on convex n-chains and we refer to it as the uniform model for chains. The event E occurs rarely because, as shown in Section 2 by elementary methods,

Theorem 1 Let P_{1}, …, P_{n} be a sample of n points, independently and uniformly distributed in [0, 1]^{2}. Then

Prob(the sample forms a convex n-chain) = \frac{1}{n!(n + 1)!}

In deriving this result the vertices on random convex n-chains are revealed as quantiles of n uniform [0, 1] random variables.

∗Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria; e-mail:

rote@opt.math.tu-graz.ac.at. Research of Günter Rote was supported by the Fonds zur Förderung der wissenschaftlichen Forschung, project P8971-PHY.

[figure: L; (0, 0); (1, 1)]

Figure 1: The limit shape L.

Random convex chains have a limit in a rather strong sense. We define the parabolic arc

L = \{ (x, y) : \sqrt{y} = 1 − \sqrt{1 − x}, 0 ≤ x ≤ 1 \}.  (1)

of points in the square equidistant from (1/2, 1/2) and the line y = x − 1, see Figure 1. Denoting the Hausdorff distance by δ, we prove the following statement in Section 3.

Theorem 2 For each n let C_{n} be a random convex n-chain. Then

Prob (δ(C_{n}, L) → 0) = 1.

Thus sequences C_{1}, C_{2}, … of random, convex chains converge to L with probability 1, an analogue of the strong law of large numbers. The curve L is called the limit shape. It is interesting that the proof technique derives L directly.

In Section 4 we prove our main result, which shows that deviations between random chains and the limit shape are asymptotically normally distributed in the following sense. For t ∈ [0, 1], x_{t} = 2t − t^{2} and y_{t} = t^{2} are the coordinates of the point on L where the tangent slope is t/(1 − t). Then the difference between (x_{t}, y_{t}) and the vertex on the random chain where the tangent slope is t/(1 − t) converges in distribution to a bivariate normal vector with mean (0, 0).

The technique used to establish these results can be pushed further without much difficulty. In Section 5 we show that random chains converge weakly as stochastic processes, and then use the invariance principle to obtain results for various functionals, e.g., the area between a convex chain and L.

In the remainder of this introduction we discuss the context for the above theorems and mention some previous, related results. Most pertain to the lattice model of random chains and respond to a question posed by Vershik about 15 years ago: “Is there a limit shape for the set of convex lattice polygons contained in a given convex body K ⊂ R^{2}?” Let K = [0, 1]^{2} denote the unit square and P_{n}, the set of all (upward) convex polygonal paths in K that connect (0, 0) to (1, 1) and whose vertices are in \frac{1}{n}Z^{2}. Bárány [1], Sinai [7], and Vershik [10] each proved theorems giving a positive answer to the question. It is shown for example, that for any ε > 0,

\frac{|\{P ∈ P_{n} : δ(P, L) < ε\}|}{|P_{n}|} → 1  (2)

as n → ∞. In other words a random convex lattice chain is close to the limit shape L with (uniform) probability converging to 1. A main difference between (2) and Theorem 2 is that in the lattice model the number of vertices on a chain P ∈ P_{n} is a random variable. This

Figure 2: Permuting segments in monotone chains

variable was studied in Sinai’s paper [7] where in addition, a central limit theorem for the deviations between P and L was stated. A further development in the lattice model appeared in Bárány [2] where a statement like (2) was shown to hold for every compact, convex body K ⊂ R^{2} with nonempty interior. In addition he characterized the limit shape as the convex curve with maximal affine perimeter.

Finally, Theorem 2 may be regarded as a strengthening of the following recent result.

Proposition 1 (Bárány [3]) For every ε > 0, Prob (δ(C_{n}, L) > ε) → 0;

Like (2), this is a weak law of large numbers but here, it pertains to the uniform model for chains.

2 The Uniform Distribution on Chains

From now on P_{i} = (x_{i}, y_{i}), i = 1, …, n will denote a sample of n points taken independently and uniformly from [0, 1]^{2}, and numbered so that x_{1} ≤ ⋯ ≤ x_{n}. We write P_{0} = (0, 0) and P_{n+1} = (1, 1). The sample space is S = { z = (x_{1}, …, x_{n}; y_{1}, …, y_{n}) : x_{i}, y_{i} ∈ [0, 1], x_{i} increasing }; probability is Lebesgue measure, normalized so Prob(S) = 1.

Proof of Theorem 1: By definition, the P_{i} are vertices on a convex chain C_{n} only if the slopes of the difference vectors Δ_{i} ≡ P_{i} − P_{i−1} are increasing, i = 1, …, n + 1. For this it is necessary that the sample define a monotone chain; i.e., the y_{i} are non-decreasing. Otherwise, Δ_{1} has positive slope but some Δ_{i} will have negative slope. The probability that a sample defines a monotone chain is (n!)^{−1} since the subset M ⊂ S where y_{1} ≤ ⋯ ≤ y_{n} clearly has the same probability as the subset where y_{π_{1}} ≤ ⋯ ≤ y_{π_{n}}, for any permutation π.

Now we condition on the event z ∈ M, that the sample defines a monotone chain. We make the following Claim: On the event M, all permutations of the slopes of the segments Δ_{i} are equally likely. The proof is based on an idea of Valtr [9] who made a similar statement for increasing paths in a lattice. This fact will complete the proof of the theorem. First note that points in M are in one-to-one correspondence with the set D = \{ \underline{Δ} = (Δ_{1}, …, Δ_{n+1}) : Δ_{i} = (u_{i}, v_{i}), u_{i}, v_{i} ≥ 0, and ∑_{i=1}^{n+1} Δ_{i} = (1, 1) \}. For a chain in z ∈ M with differences \underline{Δ}, if we interchange Δ_{i} and Δ_{i+1} (see Figure 2), then

1. the vertices P_{0}, …, P_{i−1} and P_{i+1}, …, P_{n+1} remain fixed.

Figure 3: A sample of 4 points, its random monotone chain (dotted), and its convex chain (solid).

2. P_{i} is reflected at (P_{i−1} + P_{i+1})/2 to P′_{i}.

3. in the new chain, the ranks of the slopes of Δ_{i} and Δ_{i+1} are interchanged.

Therefore, since P_{i} is uniform in the rectangle with corners at P_{i−1} and P_{i+1}, given the other points, the chains z ∈ M whose differences have slopes with ranks given by π have the same probability as the chains whose slopes obey π′, a permutation differing from π by a single transposition. Because all permutations may be obtained by a sequence of such transpositions, the claim, and thus the theorem, is proved.

Remark 1: By definition, a random convex chain C_{n} may be generated as a sample of n points in the square, rejecting the sample if (0, 0), (1, 1) and the points are not in convex position; the P_{i} in an accepted sample are the internal vertices of the convex chain. Theorem 1 implies that the expected number of samples until one is accepted is n!(n + 1)!. On the other hand, the proof suggests a more efficient algorithm in which a single random sample is transformed into a convex chain:

1. Generate P′_{i} = (u_{i}, v_{i}), i = 1, …, n, a sample of n points uniformly distributed in the square.

2. Writing u_{(i)} for the i^{th} smallest among u_{1}, …, u_{n} [it is called the i^{th} order statistic] and v_{(i)}, the i^{th} smallest among v_{1}, …, v_{n} [also an i^{th} order statistic], Q_{i} = (u_{(i)}, v_{(i)}) denotes the n internal vertices on a random, monotone chain in M (dotted line in Figure 3).

3. Compute difference vectors Δ_{i} = Q_{i} − Q_{i−1}, i = 1, …, n + 1, let Δ_{(j)} be the vector with the j^{th} smallest slope, and compute P_{i} = Δ_{(1)} + ⋯ + Δ_{(i)}, i = 1, …, n. These are the internal vertices — in order of increasing x-coordinate — of a random convex chain C_{n} (solid line in Figure 3).

3 A Limit Shape Theorem

The proofs of Theorems 2 and 3 are direct, once we have a more convenient representation for the vertices of a convex chain. By definition, the sample space for convex n-chains is S ⊂ R^{2n} defined by

S = \{(x_{1}, …, x_{n}; y_{1}, …, y_{n}) : x_{i}, y_{i} ∈ [0, 1], x_{i}, y_{i} increasing, and \frac{y_{i} − y_{i−1}}{x_{i} − x_{i−1}} increasing\};

probability is Lebesgue measure, normalized so Prob(S) = 1. Given n, let (Ω, μ) be a probability space on which we define two sequences X_{1}, …, X_{n+1} and Y_{1}, …, Y_{n+1} of mutually independent random variables, each exponentially distributed; i.e., μ{w ∈ Ω : X_{i}(w) ≤ t} = F (t) = 1 − e^{−t}. For each i, write

R_{i} = \frac{Y_{i}}{X_{i}}

W_{i} = X_{i} + Y_{i}  (3)

Z_{i} = \frac{R_{i}}{1 + R_{i}} = \frac{Y_{i}}{W_{i}} .

It is not difficult to verify three known facts concerning exponential variables.

1. Z_{i} is uniformly distributed in [0, 1].

2. Z_{i} and W_{i} are independent.

3. For every n > 0, k ≤ n, and any permutation (j_{1}, …, j_{n+1}) of 1, …, n + 1, the ratio

\frac{Y_{j_{1}} + ⋯ + Y_{j_{k}}}{Y_{1} + ⋯ + Y_{n+1}}  (4)

is distributed like the k^{th} order statistic of n independent, uniform random variables.

Write I_{A} for the indicator of the event A ⊂ Ω and fix n > 0. For t ∈ (0, 1) define the functions

x_{n}(t) ≡ \frac{∑_{i=1}^{n+1} W_{i}(1 − Z_{i})I_{[Z_{i}≤t]}}{∑_{i=1}^{n+1} W_{i}(1 − Z_{i})} = \frac{∑_{i=1}^{n+1} X_{i}I_{[Z_{i}≤t]}}{∑_{i=1}^{n+1} X_{i}}  (5)

and

y_{n}(t) ≡ \frac{∑_{i=1}^{n+1} W_{i}Z_{i}I_{[Z_{i}≤t]}}{∑_{i=1}^{n+1} W_{i}Z_{i}} = \frac{∑_{i=1}^{n+1} Y_{i}I_{[Z_{i}≤t]}}{∑_{i=1}^{n+1} Y_{i}} .  (6)

These functions describe the vertices of a random convex n-chain.

Lemma 1 Let X_{1}, …, X_{n+1} and Y_{1}, …, Y_{n+1} be i.i.d. exponential random variables on (Ω, μ) with ratios R_{i} = Y_{i}/X_{i} and write Z_{i} = R_{i}/(1 + R_{i}). Let t_{1} < ⋯ < t_{n+1} be the ordered values of Z_{1}, …, Z_{n+1}. The points

P_{i} = (x_{n}(t_{i}), y_{n}(t_{i})), i = 1, …, n

are in convex position, and for any measurable A ⊂ S,

μ{w : (x_{n}(t_{1}), …, x_{n}(t_{n}); y_{n}(t_{1}), …, y_{n}(t_{n}))(w) ∈ A} = Prob(A);

i.e., the P_{i} are the n internal vertices of a random, convex n-chain.

Proof: Let j_{1}, …, j_{n+1} be the permutation that sorts the ratios; i.e., R_{j_{1}} < ⋯ < R_{j_{n+1}}. Therefore t_{i} = Z_{j_{i}}. Observe from (6) that y_{n}(t) is a step function with a step of size

\frac{Y_{j_{i}}}{Y_{1} + ⋯ + Y_{n+1}}

at t_{i} and that on [t_{k}, t_{k+1}),

y_{n}(t) = b_{k} ≡ \frac{Y_{j_{1}} + ⋯ + Y_{j_{k}}}{Y_{1} + ⋯ + Y_{n+1}} , k = 1, …, n.

Similarly x_{n}(t) has a step of size

\frac{X_{j_{i}}}{X_{1} + ⋯ + X_{n+1}} ,

at t_{i} and on [t_{k}, t_{k+1}),

x_{n}(t) = a_{k} ≡ \frac{X_{j_{1}} + ⋯ + X_{j_{k}}}{X_{1} + ⋯ + X_{n+1}} .

So as t increases from 0 to 1, (x_{n}(t), y_{n}(t)) “jumps” from (0, 0) through the set of points P_{k} = (a_{k}, b_{k}), k = 1, …, n, to (1, 1). These are the vertices on a random convex chain because from (4),

u_{(i)} = \frac{X_{1} + ⋯ + X_{i}}{X_{1} + ⋯ + X_{n+1}} and v_{(i)} = \frac{Y_{1} + ⋯ + Y_{i}}{Y_{1} + ⋯ + Y_{n+1}}

are both distributed like the i^{th} order statistics from a sample of n independent uniforms. Also the points Q_{i} = (u_{(i)}, v_{(i)}) have differences Δ_{i} = Q_{i} − Q_{i−1} whose slopes are

R_{i} [\frac{X_{1} + ⋯ + X_{n+1}}{Y_{1} + ⋯ + Y_{n+1}} ] ,  (7)

and they are ordered by the permutation j_{1}, …, j_{n+1}. Therefore using part 2 of Remark 1,

P_{k} = Δ_{j_{1}} + ⋯ + Δ_{j_{k}}

is seen to be the k^{th} vertex on a random convex n-chain, and for t ∈ [t_{k}, t_{k+1}), P_{k} = (x_{n}(t), y_{n}(t)).

To prove Theorem 2 we need the following statement; here, and throughout, ∥(x, y)∥ = \sqrt{x^{2} + y^{2}}.

Lemma 2 For each t ∈ (0, 1) and ε > 0,

Prob(∥(x_{n}(t), y_{n}(t)) − (2t − t^{2}, t^{2})∥ > ε) → 0

as n → ∞.

Proof:

Multiply the numerator and denominator of (6) by 1/(n + 1) and apply the (weak) law of large numbers to each to observe

y_{n}(t) → \frac{E(W ZI_{[Z≤t]})}{1}

in probability; here W is the sum of 2 exponentials and Z is uniform on (0, 1) and independent of W. Therefore y_{n}(t) → t^{2} in probability. The same steps applied to (5) show that

x_{n}(t) → [E(W I_{[Z≤t]}) − E(W ZI_{[Z≤t]})] = 2t − t^{2}.

in probability.

Remark 2: For each t ∈ [0, 1] the limits

(x_{t}, y_{t}) ≡ (2t − t^{2}, t^{2})

satisfy \sqrt{y_{t}} = 1 − \sqrt{1 − x_{t}}, t ∈ [0, 1], because 1 − x_{t} = (1 − t)^{2}; therefore (2t − t^{2}, t^{2}) is on the limit curve L defined in (2). Since L is the limit of (x_{n}(t), y_{n}(t)), it has been “discovered” as a consequence of the method of proof. Previous limit shape theorems start with L and show that the difference from a random chain converges to zero.

Remark 3: The tangent to L at (2t − t^{2}, t^{2}) has slope t/(1 − t). On the other hand for t ∈ [t_{k}, t_{k+1}), (7) says that (x_{n}(t), y_{n}(t)) is the vertex on the n-chain supporting the line of slope

R_{j_{k+1}} \frac{X_{1} + ⋯ + X_{n+1}}{Y_{1} + ⋯ + Y_{n+1}} ;

this quantity → t/(1 − t) in probability as n → ∞ because t/(1 − t) ∈ [R_{j_{k}}, R_{j_{k+1}}) and the ratio of sums converges to 1.

Proof of Theorem 2: For each n > 0 let X_{1}^{(n)}, …, X_{n+1}^{(n)} and Y_{1}^{(n)}, …, Y_{n+1}^{(n)} be mutually independent exponential variables on Ω and define x_{n}(t) and y_{n}(t) as in (5) and (6) except we use Z_{i}^{(n)} = Y_{i}^{(n)}/(X_{i}^{(n)} + Y_{i}^{(n)}) and the formulas

x_{n}(t) = \frac{∑_{i=1}^{n+1} X_{i}^{(n)}I_{[Z_{i}^{(n)}≤t]}}{∑_{i=1}^{n+1} X_{i}^{(n)}} ,  (8)

and

y_{n}(t) = \frac{∑_{i=1}^{n+1} Y_{i}^{(n)}I_{[Z_{i}^{(n)}≤t]}}{∑_{i=1}^{n+1} Y_{i}^{(n)}} .  (9)

These functions describe a random convex chain C_{n}. Fix t ∈ (0, 1). Lemma 2 was based on the facts that for large enough n,

Prob(|\frac{1}{n + 1} ∑_{i=1}^{n+1} X_{i}^{(n)}(I_{[Z_{i}^{(n)}≤t]} − (2t − t^{2}))| > ε) < ε

and

Prob(|\frac{1}{n + 1} ∑_{i=1}^{n+1} Y_{i}^{(n)}(I_{[Z_{i}^{(n)}≤t]} − t^{2})| > ε) < ε.

In fact a much stronger statement is true because X_{i}^{(n)} and Y_{i}^{(n)} have finite variance. According to the complete convergence theorem of Hsu and Robbins [5], (see e.g. [4, p. 375]) the denominators in (8) and (9) satisfy

∑_{n=1}^{∞} Prob(|\frac{1}{n + 1} ∑_{i=1}^{n+1}(X_{i}^{(n)} − 1)| > ε) < ∞

and

∑_{n=1}^{∞} Prob(|\frac{1}{n + 1} ∑_{i=1}^{n+1}(Y_{i}^{(n)} − 1)| > ε) < ∞,

and this implies that both ∑_{i=1}^{n+1} X_{i}^{(n)}/(n + 1) and ∑_{i=1}^{n+1} Y_{i}^{(n)}/(n + 1) converge to 1 almost surely. The same result applied to the numerators shows that

∑_{n=1}^{∞} Prob(|\frac{1}{n + 1} ∑_{i=1}^{n+1}[X_{i}^{(n)}(I_{[Z_{i}^{(n)}≤t]} − (2t − t^{2}))]| > ε) < ∞

and

∑_{n=1}^{∞} Prob(|\frac{1}{n + 1} ∑_{i=1}^{n+1}[Y_{i}^{(n)}(I_{[Z_{i}^{(n)}≤t]} − t^{2})]| > ε) < ∞.

Together these facts guarantee that for fixed t ∈ (0, 1), (x_{n}(t), y_{n}(t)) → (2t − t^{2}, t^{2}) almost surely; i.e., for any ε > 0, and almost all w ∈ Ω there is N(t, ε, w) for which

∥(x_{n}(t), y_{n}(t)) − (2t − t^{2}, t^{2})∥ < ε,

n > N(t, ε, w).

Now take t_{i} = i/(m + 1), i = 1, …, m and apply the previous fact to each t_{i}. For almost all w ∈ Ω there is N(ε, w) such that

∥(x_{n}(t_{i}), y_{n}(t_{i})) − (x_{t_{i}}, y_{t_{i}})∥ < ε, for all i = 1, …, m,

when n > N(ε, w). If m is sufficiently large, this condition for the m points of the chain is sufficient to ensure that δ(C_{n}, L) < 2ε when n > N(ε, w), since the curves are convex.

Remark 4: Lemma 2 says that a random, convex n-chain C_{n} is likely to be close to L when n is large. Theorem 2 says that in a sequence C_{1}, C_{2}, … of chains, C_{j} having j vertices, the chains are sure to be close to L and they remain close. Note also that the chains need not be independent.

4 A Central Limit Theorem

For each n > 0, we have mutually independent exponential variables X_{1}, …, X_{n+1} and Y_{1}, …, Y_{n+1}, and use the definitions in (3), (5), and (6). We will show that for any t ∈ [0, 1], the deviations

D_{n}(t) ≡ (x_{n}(t) − (2t − t^{2}), y_{n}(t) − t^{2})

have a limiting normal distribution, a fact responsible for the heading of this section. Consider first

\sqrt{n + 1} [y_{n}(t) − t^{2}] = \frac{\frac{1}{\sqrt{n+1}} ∑_{i=1}^{n+1} [Y_{i}(I_{[Z_{i}≤t]} − t^{2})]}{\frac{1}{n+1} ∑_{i=1}^{n+1} Y_{i}}.

The random variables in the numerator sum are independent with mean zero and variance σ_{y}^{2}(t) = 2t^{3}(1 − t)(1 + 2t) so by the central limit theorem

Prob \{y_{n}(t) − t^{2} ≤ \frac{v}{\sqrt{n + 1}}\} → \frac{1}{\sqrt{2πσ_{y}^{2}(t)}} ∫_{−∞}^{v} e^{− \frac{w^{2}}{2σ^{2}_{y}(t)}} dw.

Similarly the quantity

\sqrt{n + 1} [x_{n}(t) − (2t − t^{2})] = \frac{\frac{1}{\sqrt{n+1}} ∑_{i=1}^{n+1} [X_{i} (I_{[Z_{i}≤t]} − (2t − t^{2}))]}{\frac{1}{n+1} ∑_{i=1}^{n+1} X_{i}}

has a limiting normal distribution because the numerator is the sum of random variables with mean zero and variance σ_{x}^{2}(t) = 2(1 − t)^{3}t(3 − 2t). Thus

Prob \{x_{n}(t) − (2t − t^{2}) ≤ \frac{v}{\sqrt{n + 1}}\} → \frac{1}{\sqrt{2πσ_{x}^{2}(t)}} ∫_{−∞}^{v} e^{− \frac{w^{2}}{2σ^{2}_{x}(t)}} dw.

Clearly σ_{x}^{2}(t) = σ_{y}^{2}(1−t). Not only does the central limit theorem hold independently for each coordinate of the point (x_{n}(t), y_{n}(t)) representing vertices of a random convex chain, but also

Theorem 3 For each t ∈ [0, 1]

P (u, v) = Prob\{x_{n}(t) ≤ (2t − t^{2}) + \frac{u}{\sqrt{n + 1}} and y_{n}(t) ≤ t^{2} + \frac{v}{\sqrt{n + 1}}\}

converges to the bivariate normal distribution with mean (0, 0) and covariance matrix

K_{t} = ( \begin{matrix}σ_{x}^{2}(t) & σ_{x,y}(t) \\ σ_{x,y}(t) & σ_{y}^{2}(t) \end{matrix} ) ;

σ_{x}^{2}(t) = 2(1 − t)^{3}t(3 − 2t), σ_{y}^{2}(t) = 2t^{3}(1 − t)(1 + 2t), and σ_{x,y}(t) = 3t^{2}(1 − t)^{2}. Thus

P (u, v) → ∫_{−∞}^{u} ∫_{−∞}^{v} ϕ(r, s)drds,

where ϕ(r, s) = \frac{1}{2π\sqrt{det(K_{t})}} exp(−\frac{1}{2}(r, s)K_{t}^{−1}(r, s)^{T}).

Proof: Using (6) and (7) we write \sqrt{n + 1}D_{n}(t) as

\frac{\frac{1}{\sqrt{n+1}} ∑_{i=1}^{n+1} (X_{i}(I_{[Z_{i}≤t]} − (2t − t^{2})), A_{n}[Y_{i}(I_{[Z_{i}≤t]} − t^{2})])}{\frac{1}{n+1} ∑_{i=1}^{n+1} X_{i}},  (10)

where A_{n} = (∑_{i=1}^{n+1} X_{i})/(∑_{i=1}^{n+1} Y_{i}). Concentrating on the numerator, we estimate the probability that it is componentwise less than (u, v), an arbitrary pair of reals. This is

Prob [\frac{1}{\sqrt{n + 1}} ∑_{i=1}^{n+1} (X_{i}(I_{[Z_{i}≤t]} − (2t − t^{2})), Y_{i}(I_{[Z_{i}≤t]} − t^{2})) ≤ (u, \frac{v}{A_{n}})] .

The sum adds independent random vectors, each of mean (0, 0); the expectation of the product of the components of these vectors is easily verified to be σ_{x,y}(t) = 3t^{2}(1 − t)^{2}. Therefore the sum has a limiting normal distribution with mean (0, 0) and covariance matrix K_{t}. The asserted limit statement holds because both A_{n} and the denominator of (10) converge to 1.

In fact all finite dimensional distributions along a random chain are asymptotically normal. Suppose we are given s_{1} < ⋯ < s_{k} in [0, 1]. An argument similar to the previous one leads to the conclusion that (x_{n}(s_{1}), y_{n}(s_{1}), …, x_{n}(s_{k}), y_{n}(s_{k})) converges to a certain 2k-dimensional normal random variable.

5 Weak Convergence

Again, for each n > 0 we have mutually independent exponential variables X_{1}, …, X_{n+1} and Y_{1}, …, Y_{n+1}, and use (5) and (6) to define x_{n}(t) and y_{n}(t), t ∈ [0, 1]. In Section 2 we showed that (x_{n}(t), y_{n}(t)) describes the vertices of a random convex chain C_{n}. Here we study the chain itself and show that it converges as a stochastic process. This allows us to invoke the invariance principle to study various functionals of the chain, for example A(C_{n}, L) and δ(C_{n}, L), respectively the area and Hausdorff distance between the chain and the limit shape.

Under the notation of Lemma 1, W_{i} = X_{i} + Y_{i}, Z_{i} = Y_{i}/W_{i} and t_{1} < ⋯ < t_{n+1} denotes the ordered values of Z_{1}, …, Z_{n+1}. For each t ∈ [t_{k}, t_{k+1}] define

C_{n}(t) = \frac{t_{k+1} − t}{t_{k+1} − t_{k}} (x_{n}(t_{k}), y_{n}(t_{k})) + \frac{t − t_{k}}{t_{k+1} − t_{k}} (x_{n}(t_{k+1}), y_{n}(t_{k+1})),

k = 0, …, n, where t_{0} = 0. By Lemma 1, this function interpolates linearly between vertices on a random n-chain C, so C_{n}(t), 0 ≤ t ≤ 1 provides a parametrization of the chain. Write

L(t) = (x(t), y(t)) = (2t − t^{2}, t^{2})

and define

ξ_{n}(t) = \sqrt{n + 1} (C_{n}(t) − L(t)) .  (11)

Since |C_{n}(t) − (x_{n}(t), y_{n}(t))| < c log n/n almost surely, we can write

ξ_{n}(t) = \sqrt{n + 1}((x_{n}(t), y_{n}(t)) − L(t)) + o(1),

a fact we will use repeatedly.

Let C_{0}^{2}[0, 1] be the Banach space of all continuous functions g(t) from [0, 1] to R^{2} under the sup-norm ∥g∥_{∞} = sup_{0≤t≤1} ∥g(t)∥. Define

f(z; t) = (f_{1}(z; t), f_{2}(z; t)) ,

where

f_{1}(z; t) = \sqrt{6}(1 − z)(I_{[z≤t]} − (2t − t^{2})) ; f_{2}(z; t) = \sqrt{6}z(I_{[z≤t]} − t^{2}),

and, letting B(z) be a standard Wiener process, define

ξ(t) = ∫_{0}^{1} f(z; t)dB(z).  (12)

From (10)

ξ_{n}(t) = \frac{\frac{1}{\sqrt{n+1}} ∑_{i=1}^{n+1} \frac{W_{i}}{\sqrt{6}} (f_{1}(Z_{i}; t), A_{n}f_{2}(Z_{i}; t))}{\frac{1}{n} ∑_{i=1}^{n+1} X_{i}} + o(1),

and this has a normal limit. Calculation of the covariance operator of ξ_{n} shows that

lim_{n→∞} Cov(ξ_{n}(t), ξ_{n}(s)) = K(t, s) = ∫ f(z; t)^{T} f(z; s) dz,

which is identical to that of ξ(·). (In fact K_{t} = K(t, t) is explicitly given in Theorem 3.) This is the intuition behind the following statement which gives much more information about the convergence.

Figure 4: Area and Hausdorff distance.

Theorem 4 The stochastic process ξ_{n}(·), n ≥ 1, converges weakly (in distribution) to the Gaussian process ξ(·) in (12) as random elements in C_{0}^{2}[0, 1]; i.e.,

lim_{n→∞} Eh(ξ_{n}) = Eh(ξ)  (13)

for all bounded continuous mappings h from C_{0}^{2}[0, 1] to the reals. The covariance operator of ξ(·) is K(t, s) = ∫ f(z; t)^{T} f(z; s) dz. In addition,

sup_{n} E exp[λ∥ξ_{n}∥_{∞}] < ∞

for all λ < ∞.

Proof: (The argument is straightforward, but somewhat technical, so it appears in the appendix.)

Theorem 4 can be used to investigate the convergence of many functionals of the random chain C_{n}. Perhaps the easiest example is the coordinate functional h_{t}(ξ) = ξ(t) which gives Theorem 3.

The boundedness of the moment generating function implies that (13) also holds for all continuous mappings h from C_{0}^{2}[0, 1] to the reals which, for some λ satisfy |h(g)| ≤ exp[λ∥g∥_{∞}], g ∈ C_{0}^{2}[0, 1], even for unbounded ones. This property is needed in some of the following applications.

We first study the limiting Hausdorff distance. From (11) we write

ξ_{n}(t) = \sqrt{n + 1}((x_{n}(t), y_{n}(t)) − L(t)) + o(1) = (ξ_{1,n}(t), ξ_{2,n}(t))

and note that (t, t − 1)/\sqrt{t^{2} + (t − 1)^{2}} is the unit normal to the tangent line at L(t). Then (see Fig. 4) d(C_{n}(t), L) and d(C_{n}, L(t)) [distance from C_{n}(t) to the limit shape and distance from L(t) to the random chain, respectively] are both

(1 + o(1)) |\frac{tξ_{1,n}(t) + (t − 1)ξ_{2,n}(t)}{\sqrt{t^{2} + (t − 1)^{2}}} | .

Therefore \sqrt{n}δ(C_{n}, L) = h(ξ_{n}) + o(1) where

h(ξ_{n}) = sup_{t}(|(tξ_{1,n}(t) + (t − 1)ξ_{2,n}(t))|/\sqrt{t^{2} + (t − 1)^{2}}).

Clearly h is continuous and h(g) ≤ 2∥g∥_{∞} ≤ exp[λ∥g∥_{∞}], λ = 2. Now,

E(h(ξ)) = E sup_{t} |∫_{0}^{1} \frac{(tf_{1}(z; t) + (t − 1)f_{2}(z; t))}{\sqrt{t^{2} + (t − 1)^{2}}}dB(z)| ,

and Theorem 4 implies

Corollary 1 The Hausdorff distance between the random convex chain C_{n} and its limit L satisfies

lim_{n→∞} \sqrt{n}Eδ(C_{n}, L) = E sup_{0≤t≤1} | ∫_{0}^{1} f^{∗}(z; t)dB(z)| < ∞,

where

f^{∗}(z; t) = \frac{\sqrt{6}\{(t − z)I_{[z≤t]} − t^{2}(2 − 3z − t + 2tz)\}}{\sqrt{t^{2} + (t − 1)^{2}}}.

Next let A(C_{n}, L) denote the area between the random convex chain C_{n} and its limit L and v_{n}(t) the vertical distance from L(t) to C_{n} (Fig. 4). Then

\sqrt{n}A(C_{n}, L) = \sqrt{n} ∫_{0}^{1} v_{n}(t)dx(t) = 2\sqrt{n} ∫_{0}^{1}(1 − t)v_{n}(t)dt.

Since (see Figure 4) \sqrt{n}(1 − t)v_{n}(t) = |tξ_{1,n}(t) + (t − 1)ξ_{2,n}(t)| + o(1),

\sqrt{n}A(C_{n}, L) = ∫_{0}^{1} |tξ_{1,n}(t) + (t − 1)ξ_{2,n}(t)|dx(t) + o(1).

The integrand converges uniformly on 0 ≤ t ≤ 1 − ε so we write

\sqrt{n}A(C_{n}, L) = h_{ε}(ξ_{n}) + 2\sqrt{n} ∫_{1−ε}^{1}(1 − t)v_{n}(t)dt + o(1),  (14)

where

h_{ε}(ξ_{n}) = ∫_{0}^{1−ε} |tξ_{1,n}(t) + (t − 1)ξ_{2,n}(t)|dx(t).

\sqrt{n}v_{n}(t)(1 − t) converges in distribution to |∫_{0}^{1}[tf_{1}(z; t) + (t − 1)f_{2}(z; t)]dB(z)|, which is the absolute value of a normal random variable with mean zero and variance V_{t} = ∫_{0}^{1}[tf_{1}(z; t) + (t − 1)f_{2}(z; t)]^{2}dz, by Theorem 3. A simple calculation shows V_{t} to be 2t^{3}(1 − t)^{3}. In addition, |h_{ε}(ξ_{n})| ≤ ∥ξ_{n}∥_{∞}, so that by Theorem 4,

Eh_{ε}(ξ_{n}) → Eh_{ε}(ξ) = ∫_{0}^{1−ε} |Normal(0, 2t^{3}(1 − t)^{3})|dt.

It is easy to show that lim_{ε→0} lim_{n→∞} of the last two terms in (14) is zero. Therefore, since the L_{1}-norm of Normal(0, 2t^{3}(1 − t)^{3}) is 4\sqrt{(t^{3}(1 − t)^{3}/π)},

Corollary 2 The area A(C_{n}, L) between C_{n} and L satisfies

lim_{n→∞} \sqrt{n}E[A(C_{n}, L)] = 2\sqrt{\frac{2}{π}} ∫_{0}^{1} \sqrt{2t^{3}(1 − t)^{3}}dt = \frac{4}{\sqrt{π}} \frac{Γ^{2}(5/2)}{Γ(5)} = \frac{3\sqrt{π}}{32} .

Appendix — Proof of Theorem 4

Weak convergence is easy to prove. From (5), (6) and the definition of (f_{1}(z; t), f_{2}(z; t)) it follows that

\frac{(x_{n}(t), y_{n}(t)) − L(t)}{(n + 1)^{−1/2}} = (\frac{∑_{i=1}^{n+1}(W_{i}/\sqrt{6})f_{1}(Z_{i}; t)}{(n + 1)^{−1/2} ∑_{i=1}^{n+1} X_{i}}, \frac{∑_{i=1}^{n+1}(W_{i}/\sqrt{6})f_{2}(Z_{i}; t)}{(n + 1)^{−1/2} ∑_{i=1}^{n+1} Y_{i}}).  (15)

By the strong law of large numbers ∑_{1}^{n} X_{i}/n → 1, ∑_{1}^{n} Y_{i}/n → 1 and ∑_{1}^{n} W_{i}/n → 2. By the Borel-Cantelli lemma, lim sup_{n} max_{1≤i≤n} W_{i}/ log n = 1. Thus, by (11) and (15), the weak convergence of ξ_{n} follows from that of ξ′_{n}(t) = (n + 1)^{−1/2} ∑_{i=1}^{n}(W_{i}/\sqrt{6})f(Z_{i}; t) under the ∥ · ∥_{∞} norm, and the two should share the same limiting distribution if the weak convergence holds. Since F = \{(w/\sqrt{6})f(z; t) : 0 ≤ t ≤ 1\} is a Vapnik-Červonenkis class of functions of (w, z), the weak convergence of ξ′_{n} follows from standard results in the empirical process theory, e.g. van der Vaart and Wellner [8, Theorems 2.6.7 and 2.5.2]. The limiting covariance operator E(W_{1}/\sqrt{6})^{2}f^{T} (Z_{1}; t)f(Z_{1}; s) of ξ′_{n} is clearly identical to K(t, s) as E(W_{1}/\sqrt{6})^{2} = 1 and Z_{1} is independent of W_{1} and uniformly distributed on [0, 1], so (13) holds.

To prove the boundedness E exp[λ∥ξ_{n}∥_{∞}] we shall compare ξ_{n}(t) and (15) with

ξ′′_{n}(t) = \sqrt{n + 1}\frac{∑_{i=1}^{n} W_{i}f(Z_{i}; t)}{∑_{i=1}^{n} W_{i}}.  (16)

By the large deviation results for gamma-distributions,

\frac{1}{n} log P \{ ∑_{i=1}^{n} \frac{X_{i}}{n} ≤ c\} → I(c) ∀0 < c < 1,

\frac{1}{2n} log P \{ ∑_{i=1}^{n} \frac{W_{i}}{2n} > c\} → I(c) ∀c > 1,

where I(c) = 1 − c + log c. Since I(c) → −∞ as c → 0 or c → ∞ and ∥ξ_{n}∥_{∞} ≤ \sqrt{n + 1}, the boundedness of E exp[λ∥ξ_{n}∥_{∞}] for all λ follows from that of E exp[λ∥ξ′′_{n}∥_{∞}] for all λ. Note here that by (11), the maximum of each component of ξ_{n}(t) in absolute value over 0 < t < 1 is identical to those of (15). Since {Z_{i}} are independent of {W_{i}}, (16) and the standard symmetrization methods imply

E exp[λ∥ξ′′_{n}∥_{∞}] ≤ E exp [2λ∥ ∑_{i=1}^{n+1} a_{i}ϵ_{i}∥_{∞}],  (17)

where a_{i} = a_{i}(t) = \sqrt{n + 1}W_{i}f(Z_{i}; t)/ ∑_{i=1}^{n} W_{i} and \{ϵ_{i}\} are Rademacher variables (i.e., ε_{i} = ±1, each with probability 1/2), independent of {(W_{i}, Z_{i})}. Let Ẽ be the expectation with respect to \{ϵ_{i}\} given \{(W_{i}, Z_{i})\}. Since F = \{(w/\sqrt{6})f(z; t) : 0 ≤ t ≤ 1\} is a Vapnik-Červonenkis class of functions, by the Dudley-Pisier and Hoeffding inequalities, (cf. van der Vaart and Wellner [8, Corollary 2.2.8]).

μ̃_{n} =^{def} Ẽ∥ ∑_{i=1}^{n+1} a_{i}ϵ_{i}∥_{∞} ≤ KJ(τ̃_{n})  (18)

for some finite constant K, where J(c) < ∞ is the entropy integral of F and τ̃_{n}^{2} = ∑_{i=1}^{n+1} ∥a_{i}∥_{∞}^{2}. We apply Talagrand’s deviation inequalities for product measures, (cf. e.g. Ledoux [6, top of p. 70]) to f = (∑_{i=1}^{n+1} a_{i}ϵ_{i})/τ̃_{n} (but using λτ̃_{n} instead of λ) to see

Ẽ exp [λ∥ ∑_{i=1}^{n+1} a_{i}ϵ_{i}∥_{∞}] ≤ exp [λμ̃_{n} + λ^{2}τ̃_{n}^{2}/2]  (19)

for all λ > 0. It follows from inequalities (17)–(19) that, for any M,

Ee^{λ∥ξ′′_{n}∥_{∞}} ≤ e^{2KλJ(M)+2λ^{2}M^{2}} + e^{2λ\sqrt{12(n+1)}} Prob \{\frac{12(n + 1) ∑_{i=1}^{n+1} W_{i}^{2}}{( ∑_{i=1}^{n+1} W_{i})^{2}} > M^{2}\},

since ∥ξ′′_{n}∥_{∞} ≤ \sqrt{12(n + 1)} and τ̃_{n}^{2} ≤ 12(n + 1) ∑_{i=1}^{n+1} W_{i}^{2}/( ∑_{i=1}^{n+1} W_{i})^{2}. For each λ and as n → ∞, the probability in the above expression is of an order smaller than exp\{−2λ\sqrt{12(n + 1)}\} for large M.

References

[1] Imre Bárány. The limit shape of convex lattice polygons. Discrete Comp. Geom. 13 (1995), 270–295.

[2] Imre Bárány. Affine perimeter and limit shape. J. reine angew. Mathematik 484 (1997), 71–84.

[3] Imre Bárány. Sylvester’s question: the probability that n points are in convex position. Preprint, 1997.

[4] Y. S. Chow and H. Teicher. Probability Theory. Springer-Verlag, New York, 1978.

[5] P. L. Hsu and H. Robbins. Complete Convergence and the Law of Large Numbers. Proc. Nat. Acad. Sci. 33 (1947), 229–240.

[6] M. Ledoux. On Talagrand’s deviation inequalities for product measures. ESAIM: Probab. Statist. 1 (1995/97), Art. 4, 63–87 (electronic).

http://www.emath.fr/Maths/Ps/Articles/psEng-Vol1.4.html

[7] Ya. G. Sinai. Probabilistic approach to the analysis of statistics for convex polygonal curves. Funkts. Anal. Prilozh. 28, No. 2 (1994), 41–48 (in Russian). English translation in Funct. Anal. Appl. 28 (1994), 108–113.

[8] A. van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes. Springer, New York 1996.

[9] Pavel Valtr. Probability that n random points are in convex position. Discrete Comput. Geom. 13, (1995), 637–643.

[10] A. M. Vershik. The limit shape for convex lattice polygons and related topics. Funkts. Anal. Prilozh. 28, No. 1 (1994), 16–25 (in Russian). English translation in Funct. Anal. Appl. 28 (1994), 13–20.