Inference for partial orders from random linear extensions

Thesis

The study of random orders and of rankings models has attracted much work in the combinatorics and statistics literature. However, there has been little focus on random partial order models for statistical modelling. A partial order on a set P corresponds to a transitively closed, directed acyclic graph h(P) with vertices in P. Such orders generalize orders defined by partitioning the elements of P and ranking the elements of the partition. Observed orders are modelled as random linear extensions of suborders of an unobserved partial order h(P) evolving according to a stochastic process, and inference on the partial order is of interest.

Chapter 1 reviews some static random partial order models. Of particular interest for modelling is a latent variables model based on the random k-dimensional orders and a parameter controlling the mean depth of a partial order. In Chapter 2, it is extended to a stochastic process on latent variables to describe a partial order evolving continuously in time. As a Hidden Markov model, the process is observed by taking random linear extensions from suborders of the partial order at a sequence of sampling times. The posterior distribution for the unobserved process is doubly-intractable. The basis for a numerical inference algorithm in Chapter 3 is Particle MCMC with an efficient particle filtering transition distribution on the latent variables. Sampling latent variables relates to the well studied problem of estimating multivariate normal orthant probabilities, for which Chapter 4 gives a new importance sampler. It is competitive with existing samplers under some conditions on the covariance. Inference on the partial order process is computational, and Chapter 5 gives some numerical algorithms to reduce the complexity of some common latent variables computations. Lastly, Chapter 6 applies Chapter 2 and 3 to dynamic ranking problems in the areas of historical research and sport tournaments.

Authors: Watt, A

• DOI: 10.5287/ora-ny1d1jrgr
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford