A Gibbs sampler for a class of random convex polytopes

Abstract

We present a Gibbs sampler for the Dempster-Shafer (DS) approach to statistical inference for Categorical distributions. The DS framework extends the Bayesian approach, allows in particular the use of partial prior information, and yields three-valued uncertainty assessments representing probabilities "for", "against", and "don't know" about formal assertions of interest. The proposed algorithm targets the distribution of a class of random convex polytopes which encapsulate the DS inference. The sampler relies on an equivalence between the iterative constraints of the vertex configuration and the non-negativity of cycles in a fully connected directed graph. Illustrations include the testing of independence in 2 × 2 contingency tables and parameter estimation of the linkage model.

Keywords: Algorithms; Bayesian methods; Categorical data analysis; Simulation.

Fig. 1

Partition of Δ into (Δ_k (θ))_k∈[K] in 1(a), with K = 3. Each point u_n ∈Δ defines, for a fixed x_n ∈[K], a set of θ ∈Δ such that $u_n\in {\Delta }_{x_n}\left(\theta \right)$; three such sets are colored in 1(b), for x₁ = 1, x₂ = 3, x₃ = 2. Here, no θ ∈Δ is such that $u_n\in {\Delta }_{x_n}\left(\theta \right)$ for n = 1, 2, 3.

Fig. 2

Given $\mathbf{u}\in {\mathcal{R}}_{\mathbf{x}}$ (shown in 2(a)), drop components ${\mathbf{u}}_{{\mathcal{I}}_k}$ for some k ∈[K] (the red dots in 2(a)) and draw new components ${\mathbf{u}}_{{\mathcal{I}}_k}$ (the red squares in 2(b)) from their conditional distribution identified in Proposition 3.2 with support represented by the shaded triangle.

Fig. 3

Two views on the constraints in (3.2). In 3(a) the values ${\eta }_{k\to \ell }$ define linear constraints ${\theta }_{\ell }/{\theta }_k={\eta }_{k\to \ell }$. In 3(b) the log values are weights on the edges of a complete directed graph.

Fig. 4

Elapsed time in seconds for 100 iterations of the sampler. In 4(a), elapsed time as a function of N, for different K. In 4(b), elapsed time as a function of K, for different N.

Fig. 5

Upper bounds on the TV distance between u^(t) and ${\nu }_{\mathbf{x}}$ against t. Figure 5(a) shows varying K with 10 counts in each category. Figure 5(b) shows varying N with K = 5 and N / K counts in each category.

Fig. 6

Inference on θ₁ (6(a)) and on log(θ₁ / θ₂) (6(b)) using counts (4, 3) (K = 2) and (4, 3, 0) (K = 3). Including an empty third category modifies the inference on θ₁ but not on θ₁ / θ₂.

Fig. 7

Up-projection of posterior samples (θ₁, θ₂), obtained from (N₁ = 8, N₂ = 4) and a Dirichlet(2,2) prior (segments in 7(a)), and feasible sets obtained independently for counts (2, 1, 3) (polygons in 7(a)). The rule of combination retains non-empty intersections of these sets (7(b)).

Fig. 8

Two surfaces in the 4-simplex. 8(a) shows the independence surface θ₁θ₄ = θ₂θ₃ (Fienberg and Gilbert, 1970). 8(b) shows the linkage constraint of (5.1) for ϕ ∈(0,1) as a dashed segment.

Fig. 9

Support for the hypothesis of positive association H₊ : θ₁θ₄ ≥ θ₂θ₃ as observations in {1,2,3,4} are incorporated one by one. The dark ribbon delineates the probability p for H₊, and one minus the support against it, respectively as its lower and upper rims. The width of the ribbon represents the amount of “don’t know” about the hypothesis.

Fig. 10

“Dirichlet-DSM” approach of Lawrence et al. (2009) and the original approach of Dempster (1966), for the linkage model with data (25,3,4,7), the latter implemented with the proposed Gibbs sampler. Here 10(a) shows the lower and upper probabilities for assertions of the form {ϕ < c} for increasing c ∈[0,1], while 10(b) depicts the difference between these upper and lower probabilites, or equivalently the r values.