The Gold Standard of Algebraic Statistics

Chapter index

Suppose each observation records two binary variables, X and Y. These could be two responses on a questionnaire, two features of a manufactured item, or two classifications of an event. Before writing equations, specify what counts as one observation, whether observations can reasonably be treated as independent, and whether both variables were measured on every observation. A table assembled from incompatible populations cannot be repaired by an elegant determinant.

Write p11, p12, p21 and p22 for the probabilities of the four joint outcomes. They must be nonnegative and sum to one. This set is the probability simplex. A statistical model selects some distributions within that simplex. The unrestricted model allows every such probability vector; an independence model allows only those in which the joint probabilities factor into marginal probabilities.

Keep three objects separate. The population probabilities are unknown quantities in the model. Observed counts are random outcomes under a sampling process. Fitted probabilities are estimates calculated from those counts under chosen assumptions. An equation that holds exactly for the population model usually does not hold exactly for empirical proportions in a finite sample.

This distinction gives the subject its working rhythm: translate an assumption into mathematics, derive its observable consequences, and compare those consequences with data while accounting for randomness. Algebra answers questions about exact relationships. Statistics addresses estimation, testing and uncertainty around those relationships. Neither task makes the other unnecessary.

A useful question is therefore specific: does this population distribution satisfy independence; what distribution best fits this sample under independence; or how surprising is the observed table under an independence hypothesis? These are three different calculations. State which one you are doing at the top of the working, because the same four numbers can otherwise be interpreted as counts, probabilities or expected counts without warning.

Contents · Next chapter

For independent binary variables, choose row probabilities a and 1−a and column probabilities b and 1−b. The joint probability matrix, read row by row, is (ab, a(1−b); (1−a)b, (1−a)(1−b)). Both parameters lie between zero and one. Multiplying the diagonal entries gives the same result as multiplying the off-diagonal entries.

Thus independence implies p11p22−p12p21=0. This expression is the determinant of the two-by-two probability matrix. It is a polynomial constraint: the variables appear in products, and no division is needed. Geometrically, the independence model is the portion of this determinant-zero surface that also satisfies nonnegativity and total probability one.

The converse holds for a nonnegative two-by-two table with total one. A zero determinant gives rank one, and the matrix equals the outer product of its row and column margins. This includes boundary cases where an entire row has zero probability. The sum condition excludes the all-zero matrix. Without these probability restrictions, a determinant-zero matrix need not describe a distribution at all.

For an original numerical example, take a=0.6 and b=0.25. The four probabilities are 0.15, 0.45, 0.10 and 0.30. Their sum is one, and 0.15×0.30=0.45×0.10=0.045. The row margins are 0.6 and 0.4; the column margins are 0.25 and 0.75. Multiplying those margins reconstructs every cell.

When all cells are positive, the odds ratio p11p22/(p12p21) equals one exactly when this determinant vanishes. At a zero cell, however, that quotient may be undefined. The polynomial equation remains meaningful. This is a first example of algebra removing an unnecessary division while retaining a precise boundary interpretation. It does not remove the need to ask whether the zero belongs to the population or only to the observed sample.

Previous chapter · Contents · Next chapter

Consider thirty independent observations with counts (12,8;3,7), read row by row. The row totals are 20 and 10; the column totals are 15 and 15. Under multinomial sampling and the independence model, the maximum likelihood fitted probabilities are the products of the observed marginal proportions. The expected counts are therefore (10,10;5,5).

The calculation follows directly from the likelihood. Ignoring a factor independent of the parameters, the likelihood is the product of the cell probabilities raised to their observed counts. Substituting the independence parametrisation separates it into a row factor a^20(1−a)^10 and a column factor b^15(1−b)^15. Each factor is maximised at its observed proportion: a=20/30 and b=15/30.

The empirical odds ratio is (12×7)/(8×3)=3.5. The Pearson discrepancy against the fitted table is 4/10+4/10+4/5+4/5=2.4. These are different summaries. The odds ratio describes the direction and size of association on one scale; the discrepancy compares departures with expected cell sizes. Neither number, standing alone, establishes a causal relationship.

The fitted table has determinant zero because the fitting procedure imposed independence. That is not evidence that the original observations were generated independently. A fitting algorithm always returns something inside its allowed model when it succeeds. Model assessment asks whether the discrepancy is plausible under an appropriate reference distribution and whether the sampling assumptions are defensible.

A familiar large-sample chi-square reference uses one degree of freedom for this two-by-two comparison under regular conditions. Sparse cells, dependence between observations and design restrictions require more care. Rather than attaching an automatic significance label here, retain the complete calculation: observed counts, margins, fitted counts, discrepancy and sampling assumptions. This makes the result auditable and leaves room to choose an inference method suited to the actual experiment.

Previous chapter · Contents · Next chapter

Now add a discrete variable Z, such as a recorded group. Conditional independence X independent of Y given Z says that X and Y factor within every stratum of Z that has positive probability. For binary X and Y, write joint probabilities pijk. The condition becomes p11k p22k−p12k p21k=0 for each value k.

Why can joint probabilities be used instead of conditional probabilities? Dividing the four entries in a stratum by P(Z=k) multiplies its determinant by the reciprocal of P(Z=k) squared. For a positive stratum probability, multiplying by that common nonzero quantity does not change whether the determinant is zero. For a zero-probability stratum, conditional probabilities are undefined; its joint cells are all zero and its determinant equation is automatically satisfied.

Take two equally probable strata. In the first, X and Y are independent with probability 0.8 of their first category. Its conditional matrix is (0.64,0.16;0.16,0.04). In the second, both first-category probabilities are 0.2, giving (0.04,0.16;0.16,0.64). Each determinant is zero.

Pooling the equally weighted strata gives (0.34,0.16;0.16,0.34). Its determinant is 0.1156−0.0256=0.09, so the pooled variables are dependent. Their marginal first-category probabilities are both 0.5, but the first-first probability is 0.34 rather than 0.25. A common group variable creates association after averaging even though each within-group distribution factors.

This example explains why conditioning and marginalising are different operations. Do not carry an independence statement from one to the other without checking it. The specialist guide to Bayesian networks and conditional independence develops graphical reasoning about such statements. The determinant calculation here provides a direct numerical check of what survives when a variable is hidden or ignored.

Previous chapter · Contents · Next chapter

A collection of polynomial equations defines an algebraic set. A statistical model usually adds inequalities, normalisation, or a parametrisation with restricted parameters. These extra conditions are essential. For example, a matrix with entries (2,−1;0,0) sums to one and has determinant zero, but its negative entry prevents it from being a probability table.

An ideal packages polynomial equations together with all their polynomial combinations. If f and g vanish throughout a model, then hf+kg also vanishes for any polynomials h and k. This language lets algebraic methods organise consequences of assumptions. A generating set can be much smaller than the full collection of equations it implies.

Elimination asks which equations remain among observable quantities after parameter variables are removed. Starting from p11=ab and the other independence formulas, eliminating a and b reveals the determinant relation. That relation captures the equality constraint, while the simplex restrictions still have to be imposed separately. Eliminating symbols is not permission to forget inequalities or admissible parameter ranges.

In more complicated models, the algebraic closure may include points absent from the statistical model. An equality can therefore be necessary without being sufficient for statistical membership. Numerical solutions over complex numbers, negative real solutions and points excluded by parameter restrictions must not be reported as valid fitted distributions merely because a polynomial solver returned them.

The foundational paper Algebraic statistical models, by Drton and Sullivant explains how polynomial and rational parametrisations connect with statistical model spaces. For a first calculation, the practical lesson is to carry a small admissibility ledger: real values, nonnegative probabilities, total one, required strict positivity, and any design-specific restrictions. Test those conditions after solving as well as before. A correct symbolic transformation can enlarge the solution set if a denominator or inequality has been discarded.

Previous chapter · Contents · Next chapter

Suppose a two-by-two count table has row totals 4 and 4, and column totals 3 and 5. Once its first cell x is chosen, all remaining cells are forced: the table is (x,4−x;3−x,1+x). Requiring nonnegative integer counts gives x=0,1,2,3. There are exactly four tables with these margins.

This finite set is a fibre: all nonnegative integer count vectors with the same specified summary. More generally, collect the cell counts into a vector n and use an integer matrix A to calculate the summary An. For an observed summary t, the fibre is all nonnegative integer u satisfying Au=t. Here A records row and column sums.

One equation among the margins is redundant because the total of the row sums equals the total of the column sums. Redundancy is harmless if recognised, but it affects rank calculations. Four cells with three independent margin constraints leave one free integer coordinate. The nonnegativity bounds then cut that line into the four feasible states above.

The reason for fixing margins must come from the statistical problem. Some designs fix totals in advance. In other settings, conditioning on sufficient statistics removes nuisance parameters under a specified null model. These are related motivations, but they are not the claim that margins are always fixed in every repeated sampling experiment.

To audit a fibre, reconstruct the whole table from each proposed value, recompute every margin, and check integrality and nonnegativity. The unconstrained real solutions are a line; the statistical states are four lattice points. Confusing those two sets can produce fractional people or negative observations. This simple exercise also prepares for larger tables, where describing the affine equations is easy but enumerating every feasible integer point can be computationally difficult.

Previous chapter · Contents · Next chapter

Moving from x to x+1 in the preceding fibre adds the pattern (+1,−1;−1,+1). Every row and column sum remains unchanged. Its negative moves in the opposite direction. Starting from any of the four tables, repeatedly applying a feasible sign of this move reaches every other table without leaving the nonnegative counts.

In vector language, a move m satisfies Am=0. That condition preserves the selected summary, but it is not the whole requirement. The proposed new count vector n+m must also be nonnegative. A move can preserve every total and still be impossible at the boundary because it asks to subtract an observation from an empty cell.

A Markov basis is a finite collection of moves that connects every nonempty fibre for the specified matrix A, using both signs and staying in the nonnegative integers. The word every is important. Demonstrating connectivity on one convenient observed table is weaker than establishing a Markov basis for the model.

For an unrestricted two-way independence model, the basic two-by-two moves connect tables with fixed row and column margins. The two-by-two example makes this visible without an abstract proof: the feasible values form an interval of integers and the move changes x by one. More complex constraints can require larger moves, so that reassuring picture must not be generalised without checking.

The connection to polynomial algebra sends a move to a binomial. The positive and negative parts of our move give the binomial z11z22−z12z21. Its two monomials encode two arrangements with the same margins. The Diaconis–Sturmfels paper on conditional sampling establishes the foundational link between suitable ideal generators and fibre connectivity. Here the binomial is useful because it certifies a permissible exchange pattern, not because its symbols look similar to the earlier probability determinant.

Previous chapter · Contents · Next chapter

Connectivity tells us which states can be reached. It does not tell us how frequently they should be visited. Under multinomial independence, conditional on the two-by-two margins in Chapter 6, the probability of x is C(3,x)C(5,4−x)/C(8,4), where C(n,k) is a binomial coefficient. The denominator is C(8,4)=70.

For x=0,1,2,3, the numerator weights are respectively 5,30,30,5. Hence the probabilities are 1/14,3/7,3/7,1/14. They sum to one. The central tables are six times as probable as either extreme table. Sampling uniformly from the four tables would therefore answer a different probability question.

The cancellation behind this distribution is informative. In the multinomial probability, the independence parameters appear through fixed row and column totals. Once those totals are conditioned upon, the parameter-dependent factors are the same for every table in the fibre and cancel from relative probabilities. The remaining weights are proportional to the reciprocal of the product of cell factorials.

For an explicit Markov-chain construction, choose a sign of the basic move with equal probability. If the proposed table would contain a negative count, remain at the current table. Otherwise accept a proposed table v from current table u with probability min(1,w(v)/w(u)), using the target weights above. The proposals are symmetric because both signed moves are chosen from the same fixed list.

From x=0 to x=1, the weight ratio is six and the proposal is always accepted. From x=1 to x=0, it is one-sixth. Including the one-half proposal probabilities, the probability flow in either direction at stationarity is 1/28. This detailed-balance check is small enough to perform by hand. If instead you select uniformly among only currently feasible neighbours, the proposal probabilities can change at boundaries; the acceptance formula must then include the reverse-to-forward proposal ratio.

Previous chapter · Contents · Next chapter

For the four-state example, exact enumeration is simpler than simulation. If the observed x is 3 and the prespecified alternative points towards larger x, the inclusive upper-tail probability is P(X≥3)=1/14, approximately 0.0714. There is only one table in that tail. Under a two-sided probability-ordering rule, both equally unlikely extreme tables contribute, giving 1/7.

The choice of tail rule matters. Two-sided tests on discrete spaces need an explicit definition; doubling a one-sided number is not a universal recipe. This symmetric example happens to make those two calculations agree. A different margin configuration can remove that symmetry. The specialist discussion of mid-p tests and tail splitting explains why changing treatment of the observed probability mass changes a test’s properties.

For a large fibre, a Markov chain can approximate a conditional tail probability by the proportion of sampled tables meeting a specified extremeness rule. The target conditional distribution is mathematically exact, but a finite Monte Carlo estimate has simulation error. Successive chain states are generally correlated, so treating them as independent Bernoulli trials can understate that error.

A complete computational report should identify the statistic, the tail convention, the conditional target, the move set, the acceptance rule and evidence about convergence. Multiple starting states and effective-sample-size diagnostics can reveal problems, but they do not replace a proof that the move set connects the required state space. Nor does connectivity guarantee rapid mixing within an affordable runtime.

The review Markov bases: a 25 year update is useful for the distinction between algebraic guarantees and practical sampling limitations. In a learning exercise, first reproduce a fibre small enough to enumerate. Compare the chain’s long-run frequencies with the exact weights. That gives a concrete debugging target before moving to a problem whose true answer cannot be printed on one page.

Previous chapter · Contents · Next chapter

A sampling zero means a possible category happened to receive no observations. A structural zero means the category is impossible under the design or definition. These have different consequences. A sampling zero can acquire a positive count in another feasible table. A structural-zero cell must remain zero in every allowed table.

Consider a three-by-three table with every row and column total equal to one, but with all three diagonal cells structurally forbidden. Think of three labelled objects assigned to three labelled destinations, with assignment to the identically numbered destination disallowed. Counts are integers. Each row and column therefore contains exactly one entry equal to one.

There are exactly two feasible assignments: occupied cells (1,2),(2,3),(3,1), or occupied cells (1,3),(2,1),(3,2). No ordinary two-by-two move can connect them. Any choice of two rows and two columns in a three-by-three matrix shares at least one label between the row and column sets, so the corresponding rectangle includes a forbidden diagonal cell. A move that changes all four rectangle cells cannot preserve that structural zero.

The required exchange changes six cells at once. Add one in (1,2),(2,3),(3,1) and subtract one in (1,3),(2,1),(3,2), or use the reverse sign. Row and column totals remain one, and the diagonal stays zero. Its binomial is z12z23z31−z13z21z32, of degree three rather than two.

This example provides a decisive diagnostic. A sampler restricted to ordinary rectangle moves would never leave its starting assignment, even though another admissible assignment exists. Running it for longer would not fix the missing move. The repair is to encode the forbidden cells in the model and construct moves for that support. Do not treat observed zeros as forbidden simply to simplify computation; doing so changes the sample space and the inferential question.

Previous chapter · Contents · Next chapter

A hidden-class model can describe the joint distribution as a mixture of simpler distributions. For binary observations, one form is p(x,y)=λp1(x)p1(y)+(1−λ)p2(x)p2(y), with separate component-specific distributions for X and Y. Conditional independence holds within each hidden class, but the observed mixture need not be independent.

The pooled table (0.34,0.16;0.16,0.34) from Chapter 4 has one representation with equal class weights, both first-category probabilities 0.8 in one class, and both 0.2 in the other. There is also a different representation: use equal class weights, let X be certainly in its first category in class one and certainly in its second in class two, and let Y’s first-category probabilities be 0.68 and 0.32 respectively. Multiplying within classes and adding reproduces the same four cells.

These representations are more than a relabelling of the same hidden classes. Their component probabilities differ substantially. The observed two-variable table alone cannot distinguish them. An optimizer returning one representation has not demonstrated that this is the unique underlying mechanism. In applications, naming fitted classes can encourage a stronger interpretation than the observations support.

Parameter counting gives an initial warning: an unrestricted two-component mixture of two independent binary variables has five scalar parameters, while a binary joint distribution has only three free probabilities. Counting is not a complete identifiability proof, but the two explicit constructions establish nonuniqueness for this example without relying on a vague dimensional argument.

Additional measurements, restrictions or experimental information can change identifiability, but each change requires a new argument. Separate identification of the observable distribution from identification of hidden parameters, and distinguish generic identification from exceptional boundary cases. A model may predict the observed categories accurately while remaining unable to reveal a unique hidden explanation. That limitation is an informative result, not a computational embarrassment to conceal.

Previous chapter · Contents · Next chapter

Algebraic statistics also studies continuous-variable models. For three jointly Gaussian variables with positive definite covariance matrix Σ, conditional independence of X and Y given Z is equivalent to σXYσZZ−σXZσYZ=0. The corresponding conditional covariance is σXY−σXZσYZ/σZZ, and σZZ is positive under these assumptions.

Take unit variances and covariances σXY=0.3, σXZ=0.5 and σYZ=0.6. The conditional covariance is 0.3−0.5×0.6=0. The leading principal minors are 1, 0.91 and 0.48, all positive, so this symmetric matrix is positive definite. It is therefore a valid nonsingular Gaussian covariance example with the stated conditional independence.

Now change σXY to 0.4 while keeping the other entries. The determinant becomes 0.47 and the second leading principal minor becomes 0.84, so positive definiteness remains. But the conditional covariance becomes 0.1. The conditional variances are 0.75 and 0.64; the partial correlation is 0.1 divided by the square root of 0.48, approximately 0.1443. A small algebraic change has removed an exact independence constraint.

The Gaussian qualification is essential. For general distributions, zero covariance or zero partial correlation does not by itself establish independence. Likewise, an arbitrary symmetric matrix with a desired vanishing minor might fail to be positive semidefinite and therefore fail to represent any covariance structure. Algebraic equations and admissibility conditions must travel together.

For the wider relationship between graphical structures and polynomial constraints, see Kahle, Rauh and Sullivant on conditional independence and graphical models. The site’s Markov random fields and factor graphs guide explains factorisation and inference. Read those mechanisms alongside the equations: a graph, an algebraic model and a numerical inference algorithm are related descriptions, with assumptions that must be checked at their points of connection.

Previous chapter · Contents · Next chapter

Try this exercise before reading the answer. Begin with the two-by-two fibre having row totals (4,4) and column totals (3,5). The observed table is (3,1;0,4). First treat the zero in the lower-left cell as a sampling zero. Then change the problem so that this cell is structurally forbidden. How many states remain, and what happens to the upper-tail calculation?

With a sampling zero, nothing removes the other feasible tables. The parameter x still runs from zero to three, and the conditional independence weights remain 5,30,30,5 divided by 70. The observed x=3 has inclusive upper-tail probability 1/14 for the specified one-sided test. The zero is an observation, not a restriction on future or alternative tables.

With a structural zero in the lower-left cell, the equation 3−x=0 forces x=3. The fibre now contains only the observed table. Conditional on these margins and this support, there is no remaining variation to compare. Any conditional distribution on this singleton assigns probability one to it. Carrying over the earlier tail probability would silently use the wrong sample space.

There is an additional modelling issue. Ordinary independence with both row margins and both column margins positive assigns positive probability to every cell. It cannot also give an exactly zero lower-left probability. A support-restricted model needs to be specified; it is not automatically the ordinary independence model with one entry erased. The singleton argument describes the conditional state space, not a claim that the original null model remains valid.

A second transfer question changes the summary rather than the support. If only the total sample size eight is fixed and the margins are free, are the four tables in Chapter 6 the whole sample space? No. There are C(11,3)=165 nonnegative integer four-cell tables summing to eight. Conditioning on margins selected four of them. Restoring the other 161 changes the target distribution, nuisance-parameter treatment and relevant moves. A method transfers only after these changed constraints have been made explicit.

Previous chapter · Contents · Next chapter

A practical learning route begins with small probability matrices. Derive the determinant condition, create independent and dependent examples, and verify margins by hand. Next fit an independence model to counts and explain why the fitted determinant vanishes even when the empirical one does not. Only then move to fibres, conditional weights and sampling algorithms.

For a computational project, retain both an exact small case and a larger case. The small case should enumerate all feasible states and verify target probabilities. The larger case should report the model matrix, support restrictions, move construction, acceptance rule and simulation diagnostics. Keep a record of the data-generation assumptions separately from software settings. A reproducible program can consistently compute the wrong statistical quantity if the initial model is wrong.

Does algebraic statistics mean every statistical problem becomes a polynomial?

No. Polynomial structure is useful in many models, but not every question has a convenient algebraic form or an efficient symbolic solution. The subject provides additional tools for constraints, identification and computation. It does not replace probability theory, study design, domain knowledge or numerical analysis.

Is a lattice basis automatically a Markov basis?

No. Generating integer solutions of Am=0 is not by itself a guarantee that nonnegative tables can be connected without passing through negative entries. A Markov basis addresses connectivity within every feasible nonnegative fibre. This is precisely where boundary restrictions make a purely linear description insufficient.

Can a zero polynomial residual prove that a fitted model is true?

It can verify an exact equality for specified numbers, subject to arithmetic accuracy. It cannot establish that the population follows the model merely because fitted values satisfy imposed constraints. Use residuals to check computations, and use an appropriate statistical assessment to compare model predictions with observations.

What should I check when results disagree?

Check cell ordering, margins and normalisation first. Then inspect structural versus sampling zeros, the chosen conditioning statistics, denominator assumptions and the target weights. For a sampler, separate disconnected states from slow mixing and wrong acceptance probabilities. For a solver, inspect admissibility and multiple solutions before blaming numerical precision.

Where can this learning go next?

The primary papers linked above support deeper study of conditional independence, algebraic model spaces and Markov bases. Lectures on Algebraic Statistics, by Drton, Sturmfels and Sullivant, offers a sustained mathematical route. The neighbouring Tropical Geometry root introduces another way that algebra produces geometric structure; its min-plus operations should not be substituted for ordinary probability arithmetic.

The durable skill is to explain the complete chain from question to model to calculation to interpretation. In a good solution, another reader can reconstruct the admissible distributions, repeat the numerical example, identify what changes under a new condition, and see which conclusions remain uncertain. That is the standard that makes the algebra useful beyond the original exercise.

Previous chapter · Contents · Gold Standard master