Abstracts of Reports
Abstracts of University of Warwick Department of Statistics Research Reports authored or co-authored by W.S. Kendall.
Note that WWW references to my preprints all point to gzipped postscript files. Here is information on how to deal with gzipped files. Alternatively email the departmental secretaryto request paper copies.
Topical guide:
- Computer Algebra software (includes symbolic Itô calculus): 203 , 217 , 223 , 238 , 327 , 328 , 333 , 409 , 410 .
- Computer algebra applications and surveys: 161 , 222 , 236 , 237 , 238 , 247 , 261 , 296 , 301 , 327 , 333 , 409 .
- Coupling: 162 , 212 , 214 , 218 , 247 , 257 , 260 , 261 , 292 , 295 , 308 , 323 , 331 , 347 , 348 , 349 , 350 , 371 , 382, 416, 427, 428, 445, 446.
- Point processes and stochastic geometry: 161 , 172 , 247 , 292 , 293 , 295 , 296 , 308 , 319 , 323 , 331 , 341 , 347 , 348 , 349 , 350 , 382 , 391 , 392 , 402 , 451.
- Stochastic differential geometry: 162 , 181 , 212 , 213 , 214 , 216 , 218 , 222 , 231 , 244 , 257 , 260 , 261 , 280 , 321 , 325 , 353 .
- Miscellaneous: 202 , 239, CRiSM 05-02.
(161) The Euclidean diffusion of shape:
In: Disorder in Physical Systems, edited by D. Welsh and G. Grimmett, Oxford University Press, Oxford, 203-217 (1990).
Topics: Computer Algebra applications and surveys, Point processes and stochastic geometry.
Taken from the introduction (edited): ... and investigation into the diffusion of Euclidean shape, using computer algebra to reduce complicated intermediate calculations to an informative final form. The computer algebra takes the form of an extension to the symbolic Itô calculus described in W.S. Kendall (1988) [see also reports on symbolic Itô calculus].
(162) Probability, convexity, and harmonic maps with small image I: Uniqueness and fine existence:
Proceedings of the London Mathematical Society61, 371-406 (1990).
Topics: Stochastic Differential Geometry, Coupling.
This paper uses probability theory to provide an approach to the Dirichlet problem for harmonic maps. The probabilistic tools used are those of manifold-valued Brownian motion and Gamma-martingales. Probabilistic proofs are given of uniqueness, continuous dependence on data, and existence of generalized solutions (finely harmonic maps), for target domains which have convex geometry. (This class of domain includes all regular geodesic balls.) Links are made with new results in other fields: the Gamma-martingale Dirichlet problem, Riemannian centres of mass (herein termedKarcher means), and the existence of certain convex functions. Future prospects include the development of the probabilistic approach in order to formulate the notion of a harmonic map defined on a fractal and to attack the corresponding Dirichlet problem.
1980 AMS Mathematics Subject Classification (1985 revision): 58G32, 60J65, 58E20.
Keywords and phrases: Harmonic maps, finely harmonic maps, harmonic map Dirichlet problem, regular geodesic ball, convex geometry, fractal, Karcher mean, Riemannian centre of mass, Brownian motion, Gamma-martingale, stochastic development, Gamma-martingale Dirichlet problem, confluence of Gamma-martingales}
(172) A spatial Markov property for nearest-neighbour Markov point processes:
Journal of Applied Probability28, 767-778 (1990).
Topic: Point processes and stochastic geometry.
Nearest neighbour Markov point processes were introduced by Baddeley and Møller as generalizations of the Markov point processes of Ripley and Kelly. This note formulates and discusses a spatial Markov property for these point processes.
Keywords and phrases: connected neighbours; Dirichlet neighbours; Markov partition; Markov point process; nearest neighbour Markov point process; rectangular neighbours; spatial Markov property; splitting boundary; splitting field; stochastic geometry.
(181) Convexity and the hemisphere:
Journal of the London Mathematical Society43, 567-576 (1991).
Topic: Stochastic Differential Geometry.
An explicit construction is given of continuous bounded nonnegative convex functions which are defined on the product of a small hemisphere with itself and which vanish precisely on the diagonal. It is shown that no such function exists for the strict hemisphere, even if the boundedness requirement is lifted. The generalization to regular geodesic balls is indicated.
1980 AMS Mathematics Subject Classification (1985 revision) 58C05, 26B25, 52A20.
Keywords and phrases: convex function, convex geometry, weak convex geometry, geodesic, great circle, hemisphere, regular geodesic ball.
(202) A remark on the proof of Itô's formula for C^{2} functions of continuous semimartingales:
Journal of Applied Probability29, 216-221 (1992).
Topic: Miscellaneous.
The Itô formula is the fundamental theorem of stochastic calculus. This short note presents a new proof of Itô's formula for the case of continuous semimartingales. The new proof is more geometric than previous approaches, and has the particular advantage of generalizing immediately to the multivariate case without extra notational complexity.
Keywords: Itô formula, continuous semimartingale, stochastic calculus.
(203) Computer algebra and stochastic calculus:
Notices of the American Mathematical Society37, 1254-1256 (1990).
Topic: Computer Algebra software.
From the introduction:I first obtained regular access to a computer algebra system (REDUCE) about four years ago and was immediately fascinated by the direct way in which mathematical problems could be formulated within the package. In particular the mechanisms for establishing rewrite rules (LET rules in REDUCE) and substitutions clearly had a great deal to offer in probability theory and stochastic calculus. This article describes some work I did in following this up.
(212) Convex geometry and nonconfluent Gamma-martingales I: Tightness and strict convexity:
In: Stochastic Analysis, Proceedings, LMS Durham Symposium, 11th -- 21st July 1990, edited by M.T. Barlow and N.H. Bingham, Cambridge University Press, Cambridge, 163-178 (1991).
Topics: Stochastic Differential Geometry, Coupling .
It is explained how four problems in convexity, Gamma-martingales, harmonic maps, and geodesic theory are all related. Indeed, if a conjecture by Emery is correct then all four problems are actually equivalent! A small step towards verification of Emery's conjecture is taken, using a tightness theorem for Gamma-martingales to show the following: If the Gamma-martingale Dirichlet problem for a compact domain B has unique solutions and if B supports a strictly convex function then there is a convex function Q mapping B x B to [0,1] and vanishing only on the diagonal. In short, B then has convex geometry.
Keywords: convexity, convex geometry, Dirichlet problems, geodesic, harmonic map, Gamma-martingale, tightness, stochastic control, value function, nonconfluence.
(213) The Propeller: a counterexample to a conjectured criterion for the existence of certain convex functions:
Journal of the London Mathematical Society46, 364-374 (1992).
Topic: Stochastic Differential Geometry.
A counterexample is given to a conjecture by Emery; it is shown how to construct a domain B (the propeller) of a two-dimensional Riemannian manifold such that any pair of points in B is connected by one and only one geodesic in B and yet there is no convex function Q mapping B x B to [0,1] vanishing only on the diagonal of B x B.
1980 AMS Mathematics Subject Classification (1985 revision): 58C05, 26B25, 52A20
(image size 14 Kb).
(214) Convex Geometry and nonconfluent Gamma-martingales II: Well-posedness and Gamma-martingale convergence:
Stochastics38, 135-147 (1992).
Topics: Stochastic Differential Geometry, Coupling.
In the terminology of the first paper of this series, Kendall (1991: report (212)), a closed domain B of a manifold furnished with a connection Gamma is said to have convex geometry, or property (A), if there is a bounded nonnegative Gamma-convex function Q defined on B x B vanishing only on the diagonal. It is said to have property (B) if solutions to its Dirichlet problem for Gamma-martingales are unique and well-posed (depend continuously on their limiting values at time infinity) when they exist. In this paper it is shown that (A) and (B) are equivalent if B is compact, strengthening Theorem 3.2 of the first paper of this series. In the course of the proof a result of independent interest is established: if the limits at time infinity of nontrivial Gamma-martingales in B are never nonrandom, and if the associated Gamma-martingale Liouville property is well-posed, then all Gamma-martingales in B converge as time tends to infinity.
Keywords and phrases: convexity, convex geometry, Dirichlet problems, Gamma-martingale, Gamma-martingale convergence theorem, Liouville property for Gamma-martingales, stochastic control, value function, nonconfluence.
(216) (with E. Hsu): Limiting angle of Brownian motion in certain two-dimensional Cartan-Hadamard manifolds:
Annales de la Faculté des Sciences de Toulouse1, 169-186 (1992).
Topic: Stochastic Differential Geometry.
Suppose that H is a two-dimensional Cartan-Hadamard manifold with sectional curvatures satisfying a weak negative upper bound and no lower bound. Then the angular part of Brownian motion on H tends to a limit as time tends to the explosion time of the Brownian motion. Moreover this limit angle has a distribution whose closed support is dense on the circle at infinity.
Keywords: Brownian motion, Cartan-Hadamard manifold, comparison arguments, geodesic, limiting angle, sectional curvature, stochastic differential equations.
(Sommaire) Soit H une surface du type Cartan-Hadamard dont la courbure satisfait une borne supérieure negative très faible mais aucune borne inférieure. Nous montrons que si le temps croit au temps déxplosion alors le processus angulaire du mouvement brownien riemannien sur H tend vers une limite non dégénérée dont la distribution est partout dense sur le cercle à infini de la variété H.
(217) Symbolic Itô calculus: an introduction:
Warwick Statistics Research Report217 (1991).
Topic: Computer Algebra software.
The ito procedures are an implementation of stochastic calculus for the computer algebra package REDUCE. In this paper it is explained how the implementation of ito grows naturally out of the formulation of stochastic calculus using modules of stochastic differentials. Two examples are given of ito in action: a simple example concerning various exponential martingales and a more involved example concerning the escape rate of the Bessel process of dimension exceeding 2. A basic subset of the ito procedures is listed in six appendices; details are given of how to obtain the full set from the author.
(218) (with H. Huang): Correction note toMartingales on manifolds and harmonic maps.
Stochastics37, 253-257 (1991).
Topics: Stochastic Differential Geometry, Coupling.
From the introduction:Correspondence between the two of us has elicited the need for some corrections to statements and proofs of results in the expository paper, Kendall (1988). This correction note fills that need. The principal requirements are: to correct the statement in Kendall (1988) of Theorem 4 (the Darling-Zheng Gamma-martingale convergence theorem), to clarify the partial proof given there of that theorem, and to correct the proof of theorem 6 (the Liouville theorem for harmonic maps). This second correction is facilitated by stating and proving a new but minor result (theorem 4A below) on the convergence of Gamma-martingales in regular geodesic balls. Because of the importance of the harmonic map Liouville theorem it seems worthwhile to give the corrected proof of theorems 4 and 6 in full. Note that theorem and equation numbering correspond to the numbering system used in Kendall (1988).
(222) (with O.E. Barndorff-Nielsen and P.E. Jupp): Stochastic calculus, statistical asymptotics, Taylor strings and phyla:
Annales de la Faculté des Sciences de Toulouse3, 5-62 (1994).
Topics: Computer Algebra applications and surveys, Stochastic Differential Geometry.
This paper provides an exposition without proofs of the theory of higher-order calculus known as (Taylor or statistical) string theory. This theory was introduced as a tool to deal with the geometric complexities of statistical asymptotics, but has a potentially wider rôle to play in geometric approaches in asymptotic studies. (Note that Taylor string theory is not related to the concept of a string as used in mathematical physics.) The exposition is a survey in three parts, intended to introduce and to motivate the study of Taylor strings. The paper begins by introducing string theory at the second order via a description of the formalism of the second-order stochastic calculus, a powerful method of analysis of an important class of random processes. There follows a description of some invariance considerations of statistical asymptotics and the geometry of statistical yokes, and the way in which they lead to the formulation of Taylor string theory. Finally a survey is given of the interrelationships between Taylor string theory and other concepts from mathematics such as jet bundles and natural bundles. The apparatus of Taylor string theory is introduced step-by-step as it becomes necessary, thus providing intuition and applications to motivate this approach to higher-order calculus and higher-order invariance.
Keywords: computer algebra,connection, connection string, coordinate string,derivative string, differential string, higher-order calculus, invariant Taylor series, Itô calculus, jets, likelihood, natural vector bundle, p*-formula, phyla, phylon group, REDUCE, scalar string, second-order differential, semi-holonomic jets, semimartingale, statistical asymptotics, stochastic calculus, string field, symbolic Itô calculus, T-th-order frame bundle, yoke.
AMS classification: 62A10, 62E20, 60H05, 58A20
(223) Symbolic Itô calculus: an overview:
In: Probabilités Numeriques, edited by N.Bouleau and D.Talay, INRIA, Rocquencourt, France, 186-192 (1991).
Topic: Computer Algebra software.
Taken from the introduction (edited): ... a short overview of symbolic Itô calculus, a set of procedures (also called the ito version 3.64 procedures, or Itovsn3) for the computer algebra language REDUCE. These procedures implement stochastic or Itô calculus within REDUCE in a very direct way, so that the unser may manipulate expressions within REDUCE in a manner which represents their theoretical content as directly as possible. A longer introduction (report (217)), which includes examples, is available as a research report ...
(231) The radial part of a Gamma-martingale and a non-implosion theorem:
Annals of Probability23, 479-500 (1995).
Topic: Stochastic Differential Geometry.
An upper bound is given for the behaviour of the radial part of a Gamma-martingale, generalizing previous work of the author on the radial part of Riemannian Brownian motion. This upper bound is applied to establish an integral curvature condition to determine when Gamma-martingales cannotimplode in finite intrinsic time, answering a question of Emery and generalizing work of Hsu on the C0-diffusion property of Brownian motion.
AMS (1991) Maths Subject Classification: 58G32 60H99
Keywords and phrases: Riemannian manifold, comparison theorems, Riemannian Brownian motion, implosion, convexity, C0-diffusion, Feller property, Toponogov's theorem.
(236) Computer algebra in probability and statistics:
Statistica Neerlandica47, 9-25 (1993).
Topic: Computer Algebra applications and surveys.
This paper discusses the uses of computer algebra within statistics and probability. A distinction is drawn between the use of computer algebra packages to support investigations, by performing calculations, and their use to implement structure; to build in elements of a theory (such as stochastic calculus or the Taylor string theory of Barndorff Nielsen and others) as a preliminary to research investigations. Brief surveys are given of instances in the literature of use of computer algebra in probability and statistics. Two examples of implementations of structure are discussed, both drawn from the author's own work with the computer algebra package REDUCE. One is a simple demonstration using moments of the Poisson distribution. The other is Itovsn3, an implementation of the semimartingale stochastic calculus. It is described how Itovsn3 may be used to derive the characteristic function of the Lévy stochastic area, following a proof due to S. Janson. Prospects for future work and for work in progress are discussed.
AMS (1991) Maths Subject Classification: 60H05 62A10 68C20 68K05
Keywords and phrases: Brownian motion, computer algebra, graph equivalence problem, invariant Taylor series, Itô formula, Itovsn3 , Ito procedures, Lévy stochastic area, MACSYMA , MAPLE , Mathematica, REDUCE, semimartingale, statistical asymptotics, statistical yoke geometry, stochastic calculus, stochastic differential, symbolic Itô calculus, Taylor string theory.
(237) Computer algebra and yoke geometry I: When is an expression a tensor?
Warwick Statistics Research Report237 (1992).
Topic: Computer Algebra applications and surveys.
This paper is the first of a series developing methods in the computer algebra package REDUCE for dealing with geometric statistical asymptotics. A collection of REDUCE procedures (known as idx) is introduced which can be used to determine whether or not a given expression in likelihood derivatives is actually tensorially invariant.
Keywords: computer algebra, likelihood, REDUCE, statistical asymptotics, Taylor string, yoke.
MSC classification: } 62A10, 62E20
(238) Itovsn3: doing stochastic calculus with Mathematica:
In Economic and Financial Modeling with Mathematicaedited by H. Varian, Springer-Verlag, New York, 214-238 (1993).
Topics: Computer Algebra software, Computer Algebra applications and surveys.
Itovsn3 is a collection of procedures implementing stochastic calculus within a computer algebra package. It was originally developed for the REDUCE computer algebra package (Kendall, 1985, 1988). This article describes the Mathematica version. It shows how the fundamental ItoD and Drift procedures were developed, documents the other procedures of the package, and gives an example of Itovsn3 used to carry out the calculations in a hedging problem originally treated by Duffie and Richardson (1991).
AMS (1991) Maths Subject Classification: 60H05 68Q40
Keywords and phrases: asset price, Brownian motion, computer algebra, hedging, Itô formula, Itovsn3, MACSYMA, Mathematica , REDUCE, semimartingale, stochastic calculus, stochastic differential, symbolic Itô calculus
(239) On the empty cells of Poisson histograms:
Journal of Applied Probability30, 561-574 (1993).
Topic: Miscellaneous.
This paper considers the histogram of unit cell size built up from m independent observations on a Poisson(μ) distribution. The following question is addressed: what is the limiting probability of the event that there are no unoccupied cells lying to the left of occupied cells of the histogram? It is shown that the probability of there being no such isolated empty cells (or isolated finite groups of empty cells) tends to unity as m tends to infinity, but that the corresponding almost-sure convergence fails. Moreover this probability does not tend to unity when the Poisson distribution is replaced by the Negative Binomial distribution arising when μ is randomized by a Gamma distribution. The relevance to empirical Bayes statistical methods is discussed.
AMS (1991) Maths Subject Classification: 60D05, 62C12, 62F12
Keywords and phrases: Borel-Cantelli lemmas, Geometric distribution, Gamma distribution, empirical Bayes, histogram, Negative Binomial distribution, Poisson distribution.
(244) (with M. Cranston and P. March): The radial part of Brownian motion II: Its life and times on the cut locus:
Probability Theory and Related Fields96, 353-368, (1993).
Topic: Stochastic Differential Geometry.
This paper is a sequel to Kendall (1987), which explained how the Itô formula for the radial part of Brownian motion X on a Riemannian manifold can be extended to hold for all time including those times at which X visits the cut locus. This extension consists of the subtraction of a correction term, a continuous predictable non-decreasing process L which changes only when X visits the cut locus. In this paper we derive a representation of L in terms of measures of local time of X on the cut locus. In analytic terms we compute an expression for the singular part of the Laplacian of the Riemannian distance function. The work uses a relationship of the Riemannian distance function to convexity, first described by Wu (1979) and applied to radial parts of Gamma-martingales in Kendall (1995: report (231)).
Mathematics Subject Classification (1991)} PRIMARY: 58G32, SECONDARY: 60H10, 60J45
Keywords and phrases: Brownian motion, conjugate locus, continuous additive functional, convexity, cut locus, geometric local time measure, Hausdorff measure, Itô formula, Itô-Tanaka formula, local time, Revuz measure, Riemannian distance function, Riemannian manifold, stochastic differential equation.
(247) Brownian motion and computer algebra:
(Text of talk to BAAS Science Festival '92, Southampton Wednesday 26 August 1992, with screenshots of illustrative animations). Warwick Statistics Research Report247 (1992).
Topics: Computer algebra applications and surveys, Coupling, Point processes and stochastic geometry.
This paper is the written-up version of a talk given to the Science Festival 92 of the British Association for the Advancement of Science, at Southampton on Wednesday 26th August 1992. The talk dealt with the Brownian path (a beautiful and useful random phenomenon) and was an illustrated introductory tour of the path, some of its applications, its relationship to the mathematics of heat flow and an open question thereof, and the way in which computer algebra helps us to investigate its properties. By their very nature the computer animations used to illustrate the talk cannot be presented here but appropriate screenshots are to be found interspersed in the course of the text.
AMS (1991) Maths Subject Classification: 60-01
Keywords and phrases: Brownian motion, computer algebra, DNA, heat diffusion, Itô formula, Itovsn3, leucocytes, mathematica , polymers, REDUCE, share prices, stochastic calculus, stochastic differential, symbolic Itô calculus, Wiener process.
(257) Brownian motion and partial differential equations: from the heat equation to harmonic maps (Special invited lecture, 49th session of the ISI, Firenze):
Proc. ISI 49th session, Firenze (August 1993)3, 85-101 (1993).
Topic: Stochastic Differential Geometry, Coupling.
From the introduction: The purpose of this paper is to describe recent developments in probability theory which extend the well-known connection between Brownian motion and elliptic and parabolic partial differential equations, so as to provide a probabilistic approach to important nonlinear elliptic systems of partial differential equations which are of great importance in geometry (the equations for harmonic maps: see the surveys of Eells and Lemaire (1983, 1988). At first glance the proposed generalization does not look very feasible, since the connection to linear partial differential equations arises by considering the behaviour of functions representing the essentially linear notions of probabilities and expectations. It is therefore not at all clear how one might naturally introduce not just nonlinear, but systems of nonlinear, partial differential equations. However it is possible to do this in a way which is both natural and effective, by using concepts developed for their own sakes in stochastic differential geometry. Remarkably, a close examination of the resulting approach shows that it really is a direct generalization of the classical linear relationship once expressed in the correct language.
RESUMÉ: Les relations bien connues entre le mouvement Brownien et les fonctions harmoniques s'étendent à l'étude probabiliste des applications harmoniques à valeurs dans une variété Riemannienne.
(260) Probability, convexity, and harmonic maps II: Smoothness via probabilistic gradient inequalities:
Journal of Functional Analysis126, 228-257 (1994).
Topic: Stochastic Differential Geometry, Coupling.
A conformal change of metric is used to construct a coupling of two time-changed Riemannian Brownian motions, such that there is an upper bound on the probability of the processes not coupling before either process leaves a small geodesic ball, with the bound being linear in the distance between the two starting points if these two points are close enough to the centre of the ball. This coupling is an alternative to that introduced by Cranston (1991), and is more geometric (and probabilistically less technical) than Cranston's coupling. It is used to provide a probabilistic approach to the regularity of harmonic maps, thus completing the probabilistic construction of solutions to small-image harmonic map Dirichlet problems described in Kendall (1990: report (162)). The approach includes a mild generalization to the case of harmonic maps defined using non-Riemannian connections in the target manifold and smooth strictly elliptic second-order differential operators in the domain.
Mathematics Subject Classification (1991): 58G32, 58G20, 60H30.
Keywords: Brownian motion; Conformal change of metric; Connection; Convex geometry; Coupling; Dirichlet problem for harmonic map; Finely harmonic map; Gamma-martingale; Gradient inequality; Martingale representation theorem; Parallel transport; Random time-change; Sectional curvature; Semimartingale; Stochastic development.
(261) (with G. Ben Arous and M. Cranston): Coupling constructions for hypoelliptic diffusions: Two examples:
in Stochastic Analysis: Summer Research Institute July 11-30, 1993 , edited by M. Cranston and M. Pinsky, American Mathematical Society, Providence, Proceedings of Symposia in Pure Mathematics; Contemporary Mathematics57, 193-212 (1995).
Topics: Computer algebra applications and surveys, Stochastic Differential Geometry, Coupling.
Coupling constructions are given for two examples of hypoelliptic diffusions with smooth coefficients: the two-dimensional diffusion formed by scalar Brownian motion and its time integral; and the three-dimensional diffusion formed by planar Brownian motion and its stochastic area. In both cases it is shown that one can construct co-adapted copies of Brownian motion such that the corresponding copies of the diffusion will couple in finite time. The first case uses stopping time arguments; the second is computationally more involved and the solution was found using a computer algebra implementation of stochastic calculus (though the final proof has been checked completely by hand). Questions are formulated about coupling problems for more general hypoelliptic diffusions with smooth coefficients.
Mathematics Subject Classification (1991): 60J65, 60H10
Keywords: Brownian motion; Computer Algebra; Coupling; Heisenberg group; Step one nilpotent Lie group; Lévy stochastic area; Stochastic control; Linear stochastic oscillator; Supermartingale; Symbolic Itô Calculus.
(280) (with M. Cranston and Yu. Kifer): Gromov's hyperbolicity and Picard's little theorem for harmonic maps:
in Stochastic Analysis and Applications, Gregynog, (9th-14th July 1995), edited by I.M. Davies, A. Truman, K.D. Elworthy, World Scientific Press Singapore, 139-164 (1996).
Topic: Stochastic Differential Geometry.
This paper extends some previous results concerning limiting direction of Brownian motion on manifolds satisfying Gromov's hyperbolicity criterion and other conditions, by generalizing from Brownian motion to the case of quasi-conformal Gamma-martingales (at the price of making some conditions more restrictive). The extended results are used to give a probabilistic proof for a new generalization of Picard's little theorem for harmonic maps of bounded quasi-conformality.
(292) Perfect Simulation for the Area-Interaction Point Process:
to appear in Probability Perspective, edited by C.C. Heyde and L. Accardi, World Scientific Press, Singapore (1997).
Topics: Coupling, Point processes and stochastic geometry.
The ideas of Propp and Wilson ("Exact sampling with coupled Markov chains and applications to statistical mechanics", Random Structures and Algorithms, 1996, 9:223-252) for exact simulation of Markov chains are extended to deal with perfect simulation of attractive area-interaction point processes in bounded windows. A simple modification of the basic algorithm is described which provides perfect simulation of the non-monotonic case of the repulsive area-interaction point process. Results from simulations using a C computer program are reported; these confirm the practicality of this approach in both attractive and repulsive cases. The paper concludes by mentioning other point processes which can be simulated perfectly in this way, and by speculating on useful future directions of research.
1991 mathematics subject classification: 62M30, 60G55, 60K35.
KEYWORDS: perfect simulation; spatial birth-and-death processes; area-interaction point process; Strauss point process; excluded-area point process; Poisson point process; Boolean model; coupling; Markov chain Monte Carlo.
Here are perfect simulations of the area-interaction point process:
(a) attractive case (image size 4kB) and (b) repulsive case (image size 4kB).
(293) (with A.J. Baddeley and M.N.M. van Lieshout): Quermass-interaction processes:
Warwick Statistics Research Report293 (1996).
Topic: Point processes and stochastic geometry.
This paper commences an investigation into a new class of random point and set processes, obtained using a rather natural weighting procedure. Given a Poisson point process, on each point one places a {\em grain}, a (possibly random) compact convex set. Let $\Xi$ be the union of all grains. One can now weight the process using the exponential of a quermass functional of $\Xi$. If the functional is the area functional then we recover the area-interaction point process. New point processes arise if we take the perimeter length functional, or the Euler functional (number of components minus number of holes). The main question addressed by the paper is that of when the resulting point process is well-defined: geometric arguments are used to establish conditions for the point process to be stable in the sense of Ruelle.
(295) On some weighted Boolean models:
Topics: Coupling, Point processes and stochastic geometry.
An overview is given of some recent work (joint with Adrian Baddeley of Perth and Colette van Lieshout of Warwick) on a new class of random point and set processes, obtained using a rather natural weighting procedure employing quermass integrals. The concept of exact (or perfect) simulation of point processes is then introduced, and a discussion is given of possibilities for perfect simulation of quermass weighted processes.
(296) A diffusion model for Bookstein triangle shape:
Topics: Computer algebra applications and surveys, Point processes and stochastic geometry.
[Gzipped PostScript: 67k] [PDF: 409k]
A stochastic dynamical context is developed for Bookstein's shape theory. It is shown how Bookstein's shape space for triangles arises naturally when the landmarks are moved around by a special Brownian motion on the general linear group of invertible 2x2 real matrices. Asymptotics for the Brownian transition density are used to suggest an exponential family of distributions analogous to the Fisher-von Mises spherical distribution. The computer algebra implementation Itovsn3 of stochastic calculus is used to perform the calculations (some of which actually date back to work by Dyson on eigenvalues of random matrices and by Dynkin on Brownian motion on ellipsoids). An interesting feature of these calculations is that they include the first application (to the author's knowledge) of the Gröbner basis algorithm in a stochastic calculus context.
1991 mathematics subject classification: 60D05, 60H30, 58G32, 62H11.
KEYWORDS: Bookstein shape, Brownian motion, computer algebra, D.G. Kendall shape, Fisher-von Mises distribution, Gröbner basis algorithm, holomorphic correspondence, hyperbolic plane, mean shape, Minakshisundaram-Pleijel recursion formulae, statistical shape, symbolic Itô calculus.
(301) COMPUTER ALGEBRA: an article for the Wiley Encyclopaedia of Biostatistics:
Topics: Computer algebra applications and surveys.
From the introduction:This article aims to provide a summary introduction to basic computer algebra, with some bias towards the typical statistical user. First of all we present basic common features, and list and give references for the current commercial computer algebra packages. We then sketch a simple introductory example of the use of computer algebra in a problem arising from statistical research. This is followed by a discussion of some fundamental considerations to be borne in mind concerning typical constraints and features of computer algebra systems. Finally we list a few representative examples of uses of computer algebra in statistical science, and conclude with suggestions for further reading.
(308) Perfect Simulation for Spatial Point Processes (Invited lecture, 51st session of the ISI, Istanbul):
Proc. ISI 51st session, Istanbul (August 1997).
Topic: Point processes and stochastic geometry, Coupling.
Summary: A survey is given of the ideas of perfect simulation involving Coupling From The Past (CFTP) as introduced by Propp and Wilson (1996), and its application to the perfect simulation of spatial point processes. A sketch is given of an extension to the perfect simulation of point processes defined over all R^{2}.
Sommaire: Voici un exposé des idées de la simulation parfaite au moyen de Coupling From The Past (CFTP) selon Propp et Wilson (1996), et son application à la simulation des processus ponctuels en espace. Une indication est fournie du moyen de conduire la simulation parfaite des processus ponctuels étendus à travers tout R^{2}.
(319) Geometry, statistics, and shape:
To appear in Geometry in Present-Day Science, edited by O.E. Barndorff-Nielsen and E. Vedel-Jensen.
Topic: Point processes and stochastic geometry.
Abstract: This essay is an introduction to the statistical theory of shape: a branch of statistics which arose independently from two source problems, one in archaeology, one concerning the biology of growth. After a brief history including a summary of the two source problems, the geometry and probability of statistical shape is described for two different shape theories which arose from these source problems (D.G. Kendall shape and Bookstein triangle shape). The two approaches are compared in their simplest possible case, describing the shape of three points in 2-space. The essay concludes with a brief survey of other kinds of shape.
(321) From Stochastic Parallel Transport to Harmonic Maps:
Topic: Stochastic differential geometry.
From the introduction:The aim of this account is to show how to do stochastic differential geometry: how one can work effectively and clearly with random processes which live on geometric objects, particularly by using semimartingale stochastic calculus. We shall do this by:
- explaining how one can carry out semimartingale stochastic calculus effectively in an intrinsic way;
- studying the interplay between particular semimartingales (such as Brownian motion on a manifold) and geometry;
- developing a probabilistic approach to the nonlinear elliptic theory of harmonic maps.
(323) (with E. Thönnes) Perfect Simulation in Stochastic Geometry:
Topics: Point processes and stochastic geometry, Coupling.
Abstract: Simulation plays an important rôle in stochastic geometry and related fields, because all but the simplest random set models tend to be intractable to analysis. Many simulation algorithms deliver (approximate) samples of such random set models, for example by simulating the equilibrium distribution of a Markov chain such as a spatial birth-and-death process. The samples usually fail to be exact because the algorithm simulates the Markov chain for a long but finite time, and thus convergence to equilibrium is only approximate. The seminal work by Propp and Wilson made an important contribution to simulation by proposing a coupling method, Coupling from the Past (CFTP), which delivers perfect, that is to say exact, simulations of Markov chains. In this paper we introduce this new idea of perfect simulation and illustrate it using two common models in stochastic geometry: the dead leaves model and a Boolean model conditioned to cover a finite set of points.
Here is an animated comparison (image size 128Kb) of imperfect and perfect simulations of the dead-leaves tessellation.
(325) (with J.M. Corcuera) Riemannian barycentres and geodesic convexity:
Topic: Stochastic differential geometry.
Abstract: Consider a closed subset of a Riemannian manifold, such that all geodesics with end-points in the subset are contained in the subset, and the subset has boundary of codimension one. Is it the case that Riemannian barycentres of probability measures supported by the subset must also lie in the subset? It is shown that this is the case for 2-manifolds but not the case in higher dimensions: a counterexample is constructed which is a conformally-Euclidean 3-manifold, for which geodesics never self-intersect and indeed cannot turn by too much (so small geodesic balls satisfy a geodesic convexity condition), but such that a probability measure concentrated on a single point has a barycentre at another point.
(327) Symbolic Itô calculus in AXIOM: an ongoing story:
Topics: Computer Algebra software, Computer algebra applications and surveys.
Abstract: Symbolic Itô calculus refers to the implementation of Itô calculus in a computer algebra package, and to its application. This article reports on progress in the implementation of Itô calculus in the powerful and innovative compter algebra package AXIOM, in the context of the ten-year history of previous implementations and applications. It is shown how the elegant algebraic structure underlying the expressive and effective formalism of Itô calculus can be implemented directly in AXIOM using the package's programmable facilities for strong typing of computational objects. An application is given of the use of the implementation to give a new proof, based on stochastic differentials, of the Mardia-Dryden distribution from statistical shape theory.
1991 mathematics subject classification: 58G32.
KEYWORDS: AXIOM, computer algebra, coupling of random processes, financial mathematics, Itô formula, Itô calculus, Itovsn3 , Mardia-Dryden density Mathematica, Macsyma, Maple , REDUCE, semimartingale, statistics of shape, stochastic calculus, stochastic integral, symbolic Itô calculus.
(328) Itovsn3 in AXIOM: modules, algebras and stochastic differentials:
Topic: Computer Algebra software.
Abstract: This document describes an actively developing implementation of Itovsn3 using the special object-oriented and mathematical-programming features of AXIOM code. It supersedes a direct translation from (a simplified form of) the Mathematica version of Kendall (1993a) , which itself derives from the REDUCE version described in Kendall (1991b) and at greater length in Kendall (1991a) .
(331) (with K. Burdzy) Efficient Markovian couplings: examples and counterexamples:
Topic: Point processes and stochastic geometry, Coupling.
Abstract: In this paper we study the notion of an efficient coupling of Markov processes. Informally, an efficient coupling is one which couples at the maximum possible exponential rate, as given by the spectral gap. This notion is of interest not only for its own sake, but also of growing importance arising from the very recent advent of methods of perfect simulation: it helps to establish theprice of perfection' for such methods. In general one can always achieve efficient coupling if the coupling is allowed tocheat (if each component's behaviour is affected by future behaviour of the other component), but the situation is more interesting if the coupling is required to be co-adapted. We present an informal heuristic for the existence of an efficient coupling, and justify the heuristic by proving rigorous results and examples in the contexts of finite reversible Markov chains and of reflecting Brownian motion in planar domains.
(333) Stochastic calculus in Mathematica: software and examples
Topic: Computer Algebra software (includes symbolic Itô calculus), Computer algebra applications and surveys.
[PDF: 253k] Abstract: This research report describes the Mathematica notebooks available in the Itovsn3 section of the CDROM for mathematics 1998 . These are seven notebooks ranging from a reference notebook, displaying the source-code of Itovsn3, through a simple introductory notebook, through to notebooks describing theory relating to problems in mathematical finance, coupling theory, and statistical shape.
(341) Stationary countable dense random sets
Topic: Point processes and stochastic geometry.
Abstract: We study the probability theory of countable dense random subsets of (uncountably infinite) Polish spaces. It is shown that, if such a set is stationary with respect to a transitive (locally compact) group of symmetries, then any event which concerns the random set itself (rather than accidents of its construction) must have probability zero or one. Indeed the result requires only quasi-stationarity (null-events remain so under the group action). In passing, it is noted that the property of being countable does not correspond to a measurable subset of the space of subsets of an uncountably infinite Polish space.
(347) (with J. Møller) Perfect Metropolis-Hastings simulation of locally stable point processes
Topics: Point processes and stochastic geometry, Coupling.
Abstract: In this paper we investigate the application of perfect simulation, in particular Coupling from The Past (CFTP), to the simulation of random point processes. We give a general formulation of the method of dominated CFTP and apply it to the problem of perfect simulation of general locally stable point processes as equilibrium distributions of spatial birth-and-death processes. We then investigate discrete-time Metropolis-Hastings samplers for point processes, and show how a variant which samples systematically from cells can be converted into a perfect version. An application is given to the Strauss point process. Programming details are to be found in the accompanying technical report Kendall & Møller (1999b) .
(348) (with J. Møller) Perfect implementation of a Metropolis-Hastings simulation of Markov point processes
Topics: Point processes and stochastic geometry, Coupling.
Abstract: This document describes a C implementation of a perfect algorithm for a Metropolis-Hastings simulation of a point process, based on
- a decomposition into types relating to different square sub-regions, and
- a dominating process which is composed of independent discrete-time M/M/1) queues, one for each square sub-region, each in equilibrium.
Mathematical details are to be found in Kendall & Møller (1999a) , which is the scientific paper corresponding to this research report. The differences between the current document and Kendall & Møller (1999a)are that
- this document gives a full listing of the program,
- this document does not discuss the underlying theory, which is covered in depth in Kendall & Møller (1999a) .
A full Nuweb source for this program (in gzipped tarfile form, together with figures) is available at my [homepage of available perfect simulation programs] .
(349) (with Y. Cai) Perfect simulation for correlated Poisson random variables conditioned to be positive.
Topics: Point processes and stochastic geometry, Coupling.
Abstract: In this paper we present a perfect simulation method for obtaining perfect samples from collections of correlated Poisson random variables conditioned to be positive. We show how to use this method to produce a perfect sample from a Boolean model conditioned to cover a set of points: in Kendall and Thönnes (1999) this special case was treated in a more complicated way. The method is applied to several simple examples where exact calculations can be made, so as to check correctness of the program using chi-squared tests, and some small-scale experiments are carried out to explore the behaviour of the conditioned Boolean model.
(350) (with Y. Cai) Perfect Implementation of Simulation for Conditioned Boolean Model via Correlated Poisson Random Variables.
Topics: Point processes and stochastic geometry, Coupling.
Abstract: This document describes a C implementation of an algorithm for a perfect simulation of a Boolean model conditioned to cover a set of points S={x_{1}, x_{2} , ..., x_{k}} in a bounded window W. This is done by using perfect simulation for a set of correlated Poisson random variables conditioned all to be non-zero. Mathematical details are to be found in research report 349. In this document, full listing of the programs are given.
(353) (with C.J. Price) Zeros of Brownian Polynomials.
Topics: Stochastic differential geometry.
Abstract: The time-evolving zeros of a polynomial-valued stochastic process P(z)=X_{1} z^{n}+ X_{2} z^{n}^{-1} +...+X_{n} z +X_{n}_{+1}, where X_{1},...,X_{n}_{+1} are real-valued or complex-valued semimartingales, can be viewed as stochastic processes in their own right: the root-processes of P. Away from points where they collide with each other or explode to infinity, the root-processes are complex-valued semimartingales and we describe their statistical behaviour by calculating their stochastic differentials. The main difficulty in analyzing the root processes lies in determining their behaviour at collisions: this is examined in the case where the coefficients are independent Brownian motions. If the coefficients are independent complex Brownian motions then almost surely neither collisions nor explosions will occur, and the root-processes are conformal martingales. In the corresponding real case, the root-processes interact in such a way that collisions can only occur between real or complex conjugate pairs. Colliding root-processes can be re-parameterized using elementary symmetric functions in a way which continues smoothly across the singularities where collisions occur, allowing a full description of the behaviour of the root-processes to be given. Using ideas which appear to have first been noted in quantum probability theory, we show how in favourable circumstances root-processes may be understood as members of an algebraic field of random processes, so-called algebraic semimartingales. An indication is given of the extent to which these phenomena extend to the root-processes of general polynomial-valued semimartingales.
(371) (with G. Montana) Small sets and Markov transition densities.
Topics: Coupling.
[Gzipped PostScript: 200k] [PDF: 226k]
Abstract: The theory of general state-space Markov chains can be related strongly to the case of discrete state-space by use of Doeblin's notion of small sets and associated minorization conditions . The general theory shows that small sets exist for all Markov chains on state-spaces with countably generated sigma-algebras, though the minorization provided by the theory concerns n-step transition kernels for some unspecified n. Partly motivated by the growing importance of small sets for Markov chain Monte Carlo and Coupling from the Past, we show that in general one cannot take n=1 even if the kernel is assumed to have a density function (though of course one can take n=1 if the kernel density is continuous). However n=2 will suffice for kernels with densities (integral kernels), and in fact small sets of order 2 abound in the technical sense that the kernel density can be expressed as a countable sum of separable summands based on small sets. This can be exploited to produce a representation using a latent discrete Markov chain; indeed one might say, inside every Markov chain with measurable transition density there is a discrete state-space Markov chain struggling to escape. We conclude by discussing complements to these results, including their relevance to Harris-recurrent Markov chains and relationships of the counterexample to Turán problems for bipartite graphs.
(382) (with A. Brix) Simulation of cluster point processes without edge effects.
Topics: Point processes and stochastic geometry, Coupling.
[Gzipped PostScript: 117k] [PDF: 293k]
Abstract: Cluster point processes are important models for many biological data sets, and their simulation is often required for purposes of model exploration and statistical inference. The usual direct method of simulation requires the generation of the parent point process over a region larger than the actual observation window, since one has to allow for all possible parents giving rise to observed daughter points, and some of these parents may fall outwith the observation window. When there is no a priori bound on the distance between parent and child then one has to take care to control approximations arising from edge effects. In this paper we present a simulation method which requires simulation only of those parent points actually giving rise to observed daughter points, thus avoiding edge effect approximation. The idea is to replace the cluster distribution by one which is conditioned to plant at least one daughter point in the observation window, and to modify the parent process to have an inhomogeneous intensity exactly balancing the effect of the conditioning. We furthermore show how the method extends to cases involving infinitely many potential parents, for example gamma-Poisson processes and shot-noise G-Cox processes, allowing us to avoid approximation due to truncation of the parent process.
(391) (with E. Thönnes, A. Bhalerao, and R.G. Wilson) A Bayesian approach to inferring vascular tree structure from 2D imagery
Topics: Point processes and stochastic geometry.
Abstract: We describe a method for inferring tree-like vascular structures from 2D imagery. A Markov Chain Monte Carlo (MCMC) algorithm is employed to sample from the posterior distribution given local feature estimates, derived from likelihood maximisation for a Gaussian intensity profile. A multi-resolution scheme, in which coarse scale estimates are used to initialise the algorithm for finer scales, has been implemented and used to model retinal images. Results are presented to show the effectiveness of the method.
(392) (with A. Bhalerao, E. Thönnes, and R.G. Wilson) Inferring vascular structure from 2D and 3D imagery
Topics: Point processes and stochastic geometry.
Abstract: We describe a method for inferring vascular (tree-like) structures from 2D and 3D imagery. A Bayesian formulation is used to make effective use of prior knowledge of likely tree structures with the observed data being modelled locally using Gaussian intensity profiles. The local feature models are estimated by combination of a multi-resolution, windowed Fourier approach followed by an iterative, minimum mean-square estimation which is both computationally efficient and robust. A Markov Chain Monte Carlo (MCMC) algorithm is employed to produce approximate samples from the posterior distribution given the feature model estimates. We present results of the multi-resolution parameter estimation on representative 2D and 3D data, and show preliminary results of our implementation of the MCMC algorithm.
(402) (with R.G. Wilson) Ising models and multiresolution quad-trees.
Topics: Point processes and stochastic geometry.
Abstract: We study percolation and Ising models defined on generalizations of quad-trees used in multiresolution image analysis. These can be viewed as trees for which each parent has 2d daughters, and for which daughters are linked together in d-dimensional Euclidean configurations. Retention probabilities / interaction strengths differ according to whether the relevant bond is between mother and daughter, or between neighbours. Bounds are established which locate phase transitions and show the existence of a coexistence phase for the percolation model. Results are extended to the corresponding Ising model using the Fortuin-Kasteleyn random-cluster representation.
(409) Constructing Markov chains for differentiable curves
Topic: Computer Algebra software (includes symbolic Itô calculus), Computer algebra applications and surveys.
Abstract: Motivated by a problem from medical image analysis, we investigate a Markov chain whose state-space is the space of differentiable curves. A stochastic calculus package is used to compute the formulae for updating the Markov chain.
(410) Simplification rules for ItoIntegral
Topic: Computer Algebra software (includes symbolic Itô calculus).
Abstract: The purpose of this notebook is to document and test the ItoIntegralRules package, which adds various properties and rules for ItoIntegral, a placeholder in the package Itovsn3.
(416) (with C.J. Price) Coupling iterated Kolmogorov diffusions.
Topics: Coupling.
Abstract: The Kolmogorov (1934) diffusion is the two-dimensional diffusion generated by real Brownian motion and its time integral. In this paper we construct successful co-adapted couplings for iterated Kolmogorov diffusions defined by adding further iterated time integrals to the original Kolmogorov diffusion. A Laplace-transform argument shows it is not possible successfully to couple all iterated time integrals at once; however we give an explicit construction of a successful co-adapted coupling method for the first two iterated time integrals; and a more implicit construction of a successful co-adapted coupling method which works for all finite sets of iterated time integrals.
(427) Geometric Ergodicity and Perfect Simulation.
Topics: Coupling.
Abstract: This note extends the work of Foss and Tweedie (1997), who showed that availability of the classic Coupling from The Past algorithm of Propp and Wilson (1996) is essentially equivalent to uniform ergodicity for a Markov chain (see also Hobert and Robert 2004). In this note we show that all geometrically ergodic chains possess dominated Coupling from The Past algorithms (not necessarily practical!) which are rather closely connected to Foster-Lyapunov criteria.
(428) Notes on Perfect Simulation.
Topics: Coupling.
Abstract: Perfect simulation refers to the art of converting suitable Markov Chain Monte Carlo algorithms into algorithms which return exact draws from the target distribution, instead of long-time approximations. The theoretical concepts underlying perfect simulation have a long history, but they were first drawn together to form a practical simulation technique in the ground-breaking paper of Propp and Wilson (1996), which showed (for example) how to obtain exact draws from (for example) the critical Ising model. These lecture notes are organized around four main themes of perfect simulation: the original or classic Coupling From The Past algorithm (CFTP); variations which exploit regeneration ideas such as small-set or split-chain constructions from Markov chain theory (small-set CFTP); generalizations of CFTP which deal with non-monotonic and non-uniformly ergodic examples (dominated CFTP); and finally some theoretical complements.
(05-02) Brownian confidence bands on Monte Carlo output (with JM Marin and CP Robert).
Topics: Miscellaneous.
Now accepted for publication by Statistics and Computing in substantially revised form as "Confidence bands for Brownian motion and applications to Monte Carlo simulation".
Abstract: When considering a Monte Carlo estimation procedure, the path produced by successive partial estimates is often used as a guide for informal convergence diagnostics. However the confidence region associated with that path cannot be derived simplistically from the confidence interval for the estimate itself. An asymptotically correct approach can be based on the Brownian motion approximation of the path, but no exact formula for the corresponding area-minimizing confidence region is yet known. We construct proxy regions based on local time arguments and consider numerical approximations. These are then available for a more incisive assessment of the Monte Carlo procedure and thence of the estimate itself.
(445) Coupling all the Lévy stochastic areas of multidimensional Brownian motion.
Topics: Coupling.
Abstract: It is shown how to construct a successful co-adapted coupling of two copies of an n-dimensional Brownian motion (B_{1}, ... , B_{n}) while simultaneously coupling all corresponding copies of Lévy stochastic areas. It is conjectured that successful co-adapted couplings still exist when the Lévy stochastic areas are replaced by a finite set of multiply-iterated path-and-time integrals, subject to algebraic compatibility of the initial conditions.
(446) (with S.B. Connor) Perfect Simulation for a Class of Positive Recurrent Markov Chains.
Topics: Coupling.
Abstract: This paper generalises the work of Kendall (2004), which showed that perfect simulation, in the form of dominated coupling from the past, is always possible (though not necessarily practical) for geometrically ergodic Markov chains. Here we consider the more general situation of positive recurrent chains, and explore when it is possible to produce such a simulation algorithm for these chains. We introduce a class of chains which we name tame, for which we show that perfect simulation is possible.
(451) (with D.J. Aldous) Short-length routes in low-cost networks via Poisson line patterns.
Topics: Point processes and stochastic geometry.
Abstract: In designing a network to link n cities in a square of area n, one might be guided by the following two desiderata. First, the total network length should not be much greater than the length of the shortest network connecting all cities. Second, the average route length (taken over source-destination pairs) should not be much greater than the average straight-line distance. How small can we make these two differences? For typical configurations the shortest network length is order n and the average straight-line distance is order n^{1/2}, so it seems implausible that one can construct a network in which the first difference is o(n) and the second difference is o(n^{1/2}). But in fact one can do better: for an arbitrary configuration one can construct a network where the first difference is o(n) and the second difference is almost as small as O(log n). The construction is conceptually simple: over the minimum-length connected network (Steiner tree) superimpose a sparse stationary and isotropic Poisson line process. The key ingredient is a new result about the Poisson line process. Consider two points at distance r apart, and delete from the line process all lines which separate these two points. The resulting pattern of lines partitions the plane into cells; the cell containing the two points has mean boundary length 2r+constant×log r. Turning to lower bounds we show that, under a weak equidistribution assumption, if the first difference is o(n) then the second difference cannot be O(sqrt(log n)).
If you want copies of any of these reports then please mail or fax your requests to the departmental secretary.