pith. sign in

arxiv: 2212.05524 · v3 · pith:SFY2627Gnew · submitted 2022-12-11 · 📊 stat.ME · stat.AP

Bayesian inference for partial orders from random linear extensions: power relations from 12th Century Royal Acta

Geoff K. Nicholls , Jeong Eun Lee , Nicholas Karn , David Johnson , Rukuang Huang , Alexis Muir-Watt This is my paper

Pith reviewed 2026-05-24 09:53 UTC · model grok-4.3

classification 📊 stat.ME stat.AP
keywords Bayesian inferencepartial orderslinear extensionshidden Markov modelsocial hierarchyroyal actaqueue-jumping noiseposet estimation
0
0 comments X

The pith

A hidden Markov model on evolving posets recovers changing bishop hierarchies from noisy witness lists in 12th-century royal documents.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper builds a Bayesian hidden Markov model whose hidden states are partial orders on bishops and whose observations are dated witness lists treated as noisy linear extensions of the current poset. It introduces a queue-jumping noise process and a marginally consistent prior on the sequence of posets, then fits the model to historical data to estimate the underlying hierarchies and test whether they change over time. The work rejects simpler restricted classes of orders and compares results against a time-series Plackett-Luce model, offering historians a quantitative route to detect shifts in social status.

Core claim

The evolving social order is represented as a sequence of posets; each dated witness list is generated as a random linear extension of the poset active at that time, corrupted by independent queue-jumping noise. A hidden Markov model with a depth-controlling parameter and actor covariates is used to infer the sequence of posets; fitting the model to the royal acta yields evidence of temporal changes in bishop status that can be interpreted in terms of court politics, while simpler bucket-order and vertex-series-parallel models are rejected.

What carries the argument

Hidden Markov model whose states are posets, emissions are random linear extensions plus queue-jumping noise, and prior is marginally consistent across time.

If this is right

  • The fitted posets give quantitative estimates of relative bishop status at different dates.
  • Simpler models restricted to bucket orders or vertex-series-parallel orders are statistically rejected by the data.
  • Actor covariates can be used to inform the position of specific bishops within the hierarchy.
  • Results can be compared directly with a time-series Plackett-Luce model on the same lists.
  • The software implementation allows the same model to be applied to other dated rank-order data sets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same framework could be used to test whether status hierarchies in other historical rank lists (e.g., court or monastic) also evolve as posets rather than total orders.
  • If the inferred poset changes align with independent records of promotions or royal favor, that would strengthen the historical interpretation.
  • The marginal consistency of the poset prior might allow the model to be extended to data sets with irregular or missing observation times without additional tuning.

Load-bearing premise

The observed witness lists arise as random linear extensions of a single latent poset at each time, plus independent queue-jumping noise; misspecification of either the extension process or the noise would make the recovered posets and any detected temporal changes unreliable.

What would settle it

Re-running the inference on the same lists after randomly permuting the dates within each century and checking whether the posterior probability of poset change drops to near zero.

read the original abstract

In the eleventh and twelfth centuries in England, Wales and Normandy, Royal Acta were legal documents in which witnesses were listed in order of social status. Any bishops present were listed as a group. For our purposes, each witness-list is an ordered permutation of bishop names with a known date or date-range. Changes over time in the order bishops are listed may reflect changes in their authority. Historians would like to detect and quantify these changes. There is no reason to assume that the underlying social order which constrains bishop-order within lists is a complete order. We therefore model the evolving social order as an evolving partial ordered set or {\it poset}. We construct a Hidden Markov Model for these data. The hidden state is an evolving poset (the evolving social hierarchy) and the emitted data are random total orders (dated lists) respecting the poset present at the time the order was observed. This generalises existing models for rank-order data such as Mallows and Plackett-Luce. We account for noise via a random ``queue-jumping'' process. Our latent-variable prior for the random process of posets is marginally consistent. A parameter controls poset depth and actor-covariates inform the position of actors in the hierarchy. We fit the model, estimate posets and find evidence for changes in status over time. We interpret our results in terms of court politics. Simpler models, based on Bucket Orders and vertex-series-parallel orders, are rejected. We compare our results with a time-series extension of the Plackett-Luce model. Our software is publicly available.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper develops a Hidden Markov Model whose hidden states are time-evolving posets representing social hierarchies of bishops, with observed witness lists emitted as random linear extensions of the current poset corrupted by independent queue-jumping noise. Actor covariates and a depth parameter regularize the poset prior, which is constructed to be marginally consistent. The model is applied to dated 12th-century Royal Acta data to estimate poset trajectories, detect status changes, reject bucket-order and vertex-series-parallel baselines via formal model comparison, and compare against a time-series Plackett-Luce extension. Public software is provided.

Significance. If the linear-extension-plus-queue-jump generative model is adequate, the framework supplies a principled Bayesian approach to inferring and testing changes in partial orders from noisy rank data, extending Mallows/Plackett-Luce models to the poset setting with an HMM. The public code, the marginally consistent prior, and the concrete historical application are clear strengths that would make the work useful to both statisticians and historians.

major comments (2)
  1. [Abstract and model description] The headline claims (evidence of temporal status changes and rejection of bucket-order/VSP baselines) rest on the assumption that each witness list is a uniform random linear extension of the latent poset plus independent queue jumps. No sensitivity analysis that replaces the queue-jumping kernel with an alternative noise process (while retaining the same poset prior and HMM transitions) is reported; this is load-bearing for both the recovered trajectories and the model-comparison results.
  2. [Abstract] The abstract states that simpler models are rejected, yet provides no visible details on the model-comparison procedure, effective sample sizes, or uncertainty quantification around the Bayes factors or posterior probabilities; without these, the strength of the rejection cannot be assessed.
minor comments (2)
  1. [Abstract] The phrase 'marginally consistent' for the latent-variable prior would benefit from a one-sentence clarification or pointer to the relevant construction.
  2. [Model section] Notation for the queue-jumping probability and the depth parameter should be introduced explicitly with symbols when first used.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed report. We address each major comment below and indicate the revisions we will make to strengthen the manuscript.

read point-by-point responses

  1. Referee: [Abstract and model description] The headline claims (evidence of temporal status changes and rejection of bucket-order/VSP baselines) rest on the assumption that each witness list is a uniform random linear extension of the latent poset plus independent queue jumps. No sensitivity analysis that replaces the queue-jumping kernel with an alternative noise process (while retaining the same poset prior and HMM transitions) is reported; this is load-bearing for both the recovered trajectories and the model-comparison results.

    Authors: We agree that the noise kernel is central to the recovered trajectories and model comparisons. The queue-jumping process is chosen because it models plausible local perturbations in historical witness lists while exactly preserving the poset constraints. However, we did not report sensitivity to alternative noise processes in the submitted version. In revision we will add a dedicated sensitivity section that re-fits the HMM using the same poset prior and transition structure but with two alternative emission kernels (independent random transpositions and a Mallows-style noise model with fixed dispersion). We will report the resulting changes (or lack thereof) in inferred poset trajectories, status-change detection, and Bayes factors against the bucket-order and VSP baselines. revision: yes

  2. Referee: [Abstract] The abstract states that simpler models are rejected, yet provides no visible details on the model-comparison procedure, effective sample sizes, or uncertainty quantification around the Bayes factors or posterior probabilities; without these, the strength of the rejection cannot be assessed.

    Authors: The model-comparison details (bridge-sampling Bayes factors, effective sample sizes >2000 for all chains, and posterior model probabilities with 95% credible intervals) appear in Section 5 of the full manuscript. The abstract is space-constrained and therefore summarizes only the conclusion. We will revise the abstract to include a concise clause on the comparison procedure and the strength of evidence (e.g., “Bayes factors exceeding 10 in favor of the poset HMM”). revision: yes

Circularity Check

0 steps flagged

No circularity: model fitted to external historical data

full rationale

The paper specifies an HMM with latent evolving posets, emissions as random linear extensions plus independent queue-jumping noise, and a marginally consistent prior; it then performs Bayesian inference on dated historical witness lists to obtain posterior poset trajectories and evidence of temporal change. These outputs are produced by applying the model to independent external data rather than being redefined or forced by the inputs in a closed loop. No self-citation chains, fitted parameters renamed as predictions, or self-definitional steps appear in the derivation. Model rejection of bucket-order and VSP baselines is standard likelihood-based comparison on the same data and does not create tautology.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The model rests on a standard HMM Markov assumption, a linear-extension likelihood, and an independent queue-jumping noise process. One free parameter controls poset depth; actor covariates are additional inputs. No new entities are postulated.

free parameters (1)
  • poset depth parameter
    Controls the depth of the latent poset; its value is chosen or estimated from data.
axioms (2)
  • domain assumption The observed lists are random linear extensions of the latent poset plus independent queue-jumping noise.
    Stated in the abstract as the generative model for the data.
  • domain assumption The sequence of posets follows a Markov process that is marginally consistent.
    Required for the hidden-state prior.

pith-pipeline@v0.9.0 · 5840 in / 1511 out tokens · 24608 ms · 2026-05-24T09:53:15.243271+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

74 extracted references · 74 canonical work pages

  1. [1]

    Robert, II, count of Meulan; [12] David, King of Scots; [13] Robert, de Ferrers, earl of Derby. List id 2627 Year range [1130,1135], List: [1] Odo, Stigandus; [2] Osmund, Boenot; [3] Serlo, de Mansione, Malgerii; [4] William, de Mirebel; [5] Hugh, Buscard; [6] Ranulf, de Iz; [7] Grento, de Vals; [8] Ralph, de Vals; [9] William I, king of England; [10] Joh...

    work page

  2. [2]

    out of order

    Walter, of Salisbury, temp. Stephen; [8] Robert, de Vere; [9] William, de Pont de, l’Arche. A.3. Dioceses of interest. The data display bishops with 31 distinct diocese names: Lin- coln, Durham, Chester, Sherborne, Winchester, Chichester, Bayeux, Lisieux, Evreux, Sees, Avranches, Coutances, Exeter, London, Rochester, Worcester, Salisbury, Bath, Thetford, ...

    work page 1937

  3. [3]

    top elements

    provided some exception to this. Given-Wilson provided a quantitative as well as qual- itative analysis; but, although he noted the general fact that individuals were grouped together into groups related to their status and societal role (bishops, earls and so on), Given-Wilson’s concern was not with relative status but rather with the frequency with whic...

    work page 1980

  4. [4]

    b) For t ∈ [B, E] set Mt,1 = {j1} ∩ M t, h(t) (1) = ∅ and simulate Zj1 ∼ V AR(bj1 ,ej1 ) K,ρ,θ (1) (recall β = 0S)

    Initialise: INFERENCE FOR PARTIAL ORDERS FROM RANDOM LINEAR EXTENSIONS 35 a) Fix K ≥ 1, simulate (ρ, θ) ∼ π(ρ, θ) and set β = 0S. b) For t ∈ [B, E] set Mt,1 = {j1} ∩ M t, h(t) (1) = ∅ and simulate Zj1 ∼ V AR(bj1 ,ej1 ) K,ρ,θ (1) (recall β = 0S)

    work page

  5. [5]

    For i = 2, ..., M do a) Simulate Zji ∼ V AR(bji ,eji ) K,ρ,θ (1). b) For t ∈ [B, E] set Mt,i = {j1, ..., ji} ∩ M t and construct h(t) (i) by adding to h(t) (i−1) the order relations between ji and j1, ..., ji−1, as follows: For j ∈ {j1, ..., ji−1} the order relation ⟨ji, j⟩ (resp. ⟨j, ji⟩) is added if Z(t) ji,k > Z (t) j,k (resp. Z(t) j,k > Z (t) ji,k) fo...

    work page

  6. [6]

    The final partial-order time series h ∼ πH(B,E)(·|β = 0S) does not depend on the order in which actors j1, ..., jM arrive so we may makejM = j the last arrival

    Set h(t) = h(t) (M ) for each t ∈ [B, E] and h = (h(t))E t=B. The final partial-order time series h ∼ πH(B,E)(·|β = 0S) does not depend on the order in which actors j1, ..., jM arrive so we may makejM = j the last arrival. Also, by Proposition 4, g = h(t) −j = h(t) (M −1) is the poset state of the process for each t ∈ [B, E] before jM = j arrives. By cons...

    work page 1951

  7. [7]

    Wulfstan, bishop of Worcester

    work page

  8. [8]

    Walkelin, bishop of Winchester, 1070−1198

    work page

  9. [9]

    Robert, bishop of Seez

    work page

  10. [10]

    Osmund, bishop of Salisbury

    work page

  11. [11]

    Gundulf, bishop of Rochester

    work page

  12. [12]

    Gilbert, bishop of Lisieux

    work page

  13. [13]

    Remigius, bishop of Lincoln

    work page

  14. [14]

    Robert, Losinga, bishop of Hereford

    work page

  15. [15]

    Gilbert, bishop of Evreux

    work page

  16. [16]

    Geoffrey, bishop of Coutances

    work page

  17. [17]

    Stigand, bishop of Chichester

    work page

  18. [18]

    Peter, bishop of Chester

    work page

  19. [19]

    Odo, bishop of Bayeux

    work page

  20. [20]

    Michael, bishop of Avranches

    work page

  21. [21]

    Arfastus, bishop of Thetford

    work page

  22. [22]

    Osbern, bishop of Exeter

    work page

  23. [23]

    William, de Saint−Calais, bishop of Durham

    work page

  24. [24]

    Maurice, bishop of London

    work page

  25. [25]

    Robert, de Limesey, bishop of Chester

    work page

  26. [26]

    John, bishop of Bath

    work page

  27. [27]

    Ralph, bishop of Chichester

    work page

  28. [28]

    Hervey, bishop of Bangor

    work page

  29. [29]

    Robert, Bloet, bishop of Lincoln

    work page

  30. [30]

    Turgis, bishop of Avranches

    work page

  31. [31]

    Samson, bishop of Worcester

    work page

  32. [32]

    Turold, de Envermeu, bishop of Bayeux

    work page

  33. [33]

    Ranulf, Flambard, bishop of Durham

    work page

  34. [34]

    William, Giffard, bishop of Winchester, 1100−1129

    work page

  35. [35]

    Roger, Bishop of Salisbury

    work page

  36. [36]

    John, Bishop of Lisieux

    work page

  37. [37]

    Reinhelm, bishop of Hereford

    work page

  38. [38]

    Richard, Bishop of Bayeux

    work page

  39. [39]

    Urban, bishop of Llandaff

    work page

  40. [40]

    Richard, de Belmeis I, bishop of London, 1108−1127

    work page

  41. [41]

    Roger, bishop of Coutances

    work page

  42. [42]

    Theulf, Bishop of Worcester

    work page

  43. [43]

    Ouen, Bishop of Evreux

    work page

  44. [44]

    Arnulf, bishop of Rochester

    work page

  45. [45]

    Bernard, Bishop of St David's

    work page

  46. [46]

    Everard, bishop of Norwich

    work page

  47. [47]

    Richard, de Capella, bishop of Hereford

    work page

  48. [48]

    Robert, Peche, bishop of Chester, 1121−6

    work page

  49. [49]

    Alexander, Bishop of Lincoln

    work page

  50. [50]

    Godfrey, bishop of Bath

    work page

  51. [51]

    John, Bishop of Sees

    work page

  52. [52]

    Richard, bishop of Coutances

    work page

  53. [53]

    Simon, Bishop of Worcester

    work page

  54. [54]

    John, Bishop of Rochester

    work page

  55. [55]

    Seffrid, Bishop of Chichester

    work page

  56. [56]

    Gilbert, the Universal, bishop of London

    work page

  57. [57]

    Roger, de Clinton, Bishop of Chester

    work page

  58. [58]

    Henry, de Blois, Bishop of Winchester, 1129−1171

    work page

  59. [59]

    Robert, de Bethune, Bishop of Hereford

    work page

  60. [60]

    Algar, Bishop of Coutances

    work page

  61. [61]

    Nigel, Bishop of Ely

    work page

  62. [62]

    Geoffrey, Rufus, Bishop of Durham

    work page

  63. [63]

    Adelulf, Bishop of Carlisle

    work page

  64. [64]

    Richard, de Beaufeu, Bishop of Avranches

    work page

  65. [65]

    Robert, of Lewes, Bishop of Bath

    work page

  66. [66]

    Robert, de Sigillo, Bishop of London

    work page

  67. [67]

    Jocelin, de Bohun, bishop of Salisbury

    work page

  68. [68]

    William, Turbe, Bishop of Norwich

    work page

  69. [69]

    Hilary, Bishop of Chichester 1146−1169

    work page

  70. [70]

    Walter, Bishop of Rochester

    work page

  71. [71]

    Robert, de Chesney, Bishop of Lincoln

    work page

  72. [72]

    Richard, de Belmeis II, bishop of London 1152−1162

    work page

  73. [73]

    whiskers

    Hugh, du Puiset, Bishop of Durham FIG 24. Name index for vertices in the order graphs in Figs 1, 12, 13, 23 and 27. INFERENCE FOR PARTIAL ORDERS FROM RANDOM LINEAR EXTENSIONS 47 −2 0 2 x.vals rep(0, T) Wulfstan Samson Theulf Simon Worcester x.vals rep(0, T) Walkelin William Henry Winchester −2 0 2 x.vals rep(0, T)Robert John Sees x.vals rep(0, T) Osmund R...

    work page 1920

  74. [74]

    plus” and “minus

    The other intervals are close to the (uniform) prior. However, this simply reflects the fact that we get little information about a correlation from a short time interval (5 years). We see no evidence here against our assumption that ρ, θ and p are constant in time. 52 1+ 2+ 3− 4 5− S P− S+ S 1 2 3 4 FIG 29. (left) BDT representation of the poset in Fig 6...

    work page 1982