Why Enumerate a Conditional Sample Space?
An exact conditional calculation starts with a set of configurations that satisfy the observed conditioning constraints. Depending on the model, a configuration may be a contingency table with fixed margins or a response allocation with a fixed number of cases in each matched set. To calculate an exact probability, we must identify every feasible configuration and assign each its correct conditional probability.
Enumeration is straightforward when the sample space is small, but it requires care: local choices can violate margins that have not yet been filled, and distinct configurations need not have equal probability. Recursive search and network-flow methods organize the task. Once the feasible set has been listed, conditional probabilities are obtained by normalizing the configurations’ weights.
The weights come from the conditional model, not from the enumeration algorithm. For example, conditioning independent Poisson counts on their row and column sums makes the cell means cancel from the conditional distribution, leaving weights proportional to the reciprocal of the product of cell factorials. In a conditional logistic model, allocations are weighted by the exponential of the coefficient times their sufficient statistic. Enumeration identifies the support; the model determines the weights.
Recursive Enumeration of Tables
Consider a nonnegative integer table \(y=(y_{ij})\) with fixed row sums \(r_i\) and column sums \(c_j\). A recursive enumerator fills cells in a fixed order, maintaining the residual row and column sums. At each step it tries only integer values consistent with the remaining totals. If a partial choice makes it impossible to complete any row or column, that branch is discarded.
For a cell \(y_{ij}\), a basic valid range is from zero to the smaller of its residual row and column sums. If structural zeros or cell-specific upper bounds apply, the range must also respect them. These bounds are necessary but may not by themselves guarantee that the remaining margins can be completed; stronger feasibility checks can prune a branch earlier.
Set each residual row total to \(r_i\) and each residual column total to \(c_j\).
Use a fixed cell order so each completed table has one unique path through the search.
Respect the current residual margins, any cell bounds, and any structural zeros; subtract the chosen value from both relevant residuals.
Discard a branch if its remaining margins are infeasible. Otherwise recurse until all cells are assigned.
At a complete table, verify all constraints and calculate its model weight.
Worked Example: Enumerating a 2-by-3 Table by Residual Margins
Suppose a \(2\times3\) table has row sums \((3,3)\) and column sums \((2,2,2)\). Write the first row as \((a,b,c)\). Its entries must be nonnegative integers, each at most 2, and satisfy \(a+b+c=3\). The second row is then forced to be \((2-a,2-b,2-c)\).
The possible first rows are \((1,1,1)\) and the six permutations of \((2,1,0)\). There are no others: a coordinate cannot exceed 2, and the nonnegative integer triples summing to 3 are precisely these seven possibilities. Each produces a nonnegative second row with the required sum, so all seven are feasible.
Now suppose the table arises from independent Poisson cell counts with a common mean, conditioned on these margins. The conditional weight is \(w(y)=1/\prod_{i,j}y_{ij}!\). For first row \((1,1,1)\), the whole table has all entries equal to 1, so its weight is 1. For each permutation of \((2,1,0)\), the second row is the complementary permutation and the product of all cell factorials is \(2!\,2!=4\); its weight is \(1/4\). The total weight is therefore \(1+6(1/4)=5/2\).
For the event that the upper-left cell equals 2, the first coordinate of the first row must be 2. Exactly two of the six permutations have this property, each with weight \(1/4\). Thus the event’s conditional probability is \((2/4)/(5/2)=1/5\).
Network Algorithms for Fixed-Margin Tables
A fixed-margin table can also be represented as an integer flow in a bipartite network. Create a source node, one node for each row, one node for each column, and a sink node. An arc from the source to row \(i\) has capacity \(r_i\); an arc from row \(i\) to column \(j\) carries the cell value \(y_{ij}\); and an arc from column \(j\) to the sink has capacity \(c_j\). The row-to-column arc can be omitted for a structural zero, or given a capacity if the cell has an upper bound.
A flow of total size \(\sum_i r_i=\sum_j c_j\) saturates the source-to-row and column-to-sink arcs. Flow conservation then says that the values on the row-to-column arcs have the specified row and column sums. Conversely, every table with those margins defines such a flow. With integer capacities, maximum-flow algorithms can find an integer feasible flow whenever a feasible flow exists. For enumeration, one can fix a cell value, reduce the residual capacities and margins, and use a flow-feasibility check to prune choices that cannot lead to a completion. A fixed order of cells prevents duplicate output.
Worked Example: A Network View of a 2-by-2 Conditional Distribution
Take row and column sums \((2,2)\). A network has two row nodes and two column nodes, with all four row-to-column arcs available. Let \(t=y_{11}\). The margins force the table to have the form \(\begin{pmatrix}t&2-t\\2-t&t\end{pmatrix}\). Nonnegativity requires \(t\) to be an integer from 0 to 2, so the network’s feasible integer flows correspond exactly to three tables, one for each of \(t=0,1,2\).
Suppose the conditional model assigns weight \(w(y)=\theta^t/\prod_{i,j}y_{ij}!\), and take \(\theta=2\). For \(t=0\), the weight is \(1/(0!2!2!0!)=1/4\). For \(t=1\), it is \(2/(1!1!1!1!)=2\). For \(t=2\), it is \(2^2/(2!0!0!2!)=1\). The total weight is \(1/4+2+1=13/4\). Consequently, the conditional probability of the table with \(t=2\) is \(1/(13/4)=4/13\).
The flow representation verifies feasibility and makes the role of the margins explicit. It does not make the three tables equally likely: their weights differ, so counting tables alone would give the wrong probability.
Enumerating Response Allocations
The same logic applies when a configuration is an allocation of responses rather than a table. In a conditional logistic analysis with matched sets, fixing the number of cases in each set defines the allowable allocations. If set \(s\) contains covariates \(x_{s1},\ldots,x_{sm_s}\) and exactly one case, an allocation selects one index \(j_s\) in that set. Its sufficient statistic for a scalar coefficient is \(S=\sum_s x_{s j_s}\); under coefficient \(\beta\), its conditional weight is \(\exp(\beta S)\). Enumerating allocations means taking one allowed choice from each set and retaining its resulting statistic and weight.
Worked Example: Exact Probability From Matched-Set Allocations
There are two matched sets, each with one case. In the first set the two covariate values are 0 and 1; in the second they are 0 and 2. An allocation selects one value in each set. The four allocations have sufficient statistics \(S\) equal to 0, 1, 2, and 3, respectively.
For \(\beta=\log 2\), the weight of an allocation is \(\exp(\beta S)=2^S\). In the order \(S=0,1,2,3\), the weights are \(1,2,4,8\), and their sum is \(15\). Therefore the conditional probability of \(S\geq2\) is \((4+8)/15=12/15=4/5\).
The enumeration is over the four distinct labeled choices of cases, not just over the possible statistic values in the abstract. Here each statistic value happens to occur once. In a larger problem, several allocations can have the same \(S\), and the weight for that statistic value must include the weight of every allocation producing it.
Why the Normalization Works
Proof. On the finite fiber, the conditional mass assigned to configuration \(z\) is \(w(z)/W\). The event \(A\) consists of the disjoint configurations in \(A\cap\mathcal{F}_t\), so additivity gives \(P(Z\in A\mid T(Z)=t)=\sum_{z\in A\cap\mathcal{F}_t}w(z)/W\). If enumeration lists every member of the fiber once, its total weight is exactly \(W\), and its event weight is exactly the numerator. Their ratio is the stated probability. \(\square\)
The enumeration itself can be justified by a simple recursive invariant. At any stage, the partial assignments on a branch agree with the choices already made, and the residual constraints are exactly the original constraints minus the contributions of those choices. Thus any completion of the partial assignment must occur in one of the branches tried at the next step. Conversely, every branch retained through to a complete assignment satisfies the constraints checked at each step and, at the terminal step, all original constraints.
To see why there are no omissions, take any feasible configuration. Its value for the first variable is among the tried values; after that choice, its value for the second variable remains among the tried values, and so on. It therefore determines a path to a completed leaf. For uniqueness, two different paths first differ at some variable, so they cannot produce the same full configuration. Pruning preserves this argument only when the feasibility check is valid: a branch may be removed only if it has no completion. This is why residual-flow checks can be useful beyond simple cellwise bounds.
Common Mistakes and Practical Checks
- Giving every table equal probability. Fixed margins determine the support, not a uniform distribution on it. Calculate the model weight for each table or allocation and normalize those weights.
- Listing only distinct sufficient-statistic values. Several labeled configurations may share the same statistic. Sum the weights of all configurations contributing to an event or statistic value.
- Pruning on a guess. A partial table that looks difficult to complete must not be discarded unless the residual constraints prove it infeasible. Otherwise feasible configurations disappear from the denominator.
- Counting a configuration more than once. Use a fixed variable order and a canonical representation. Different paths or permutations that encode the same table should not be treated as distinct tables.
- Failing to check the total weight. For a small example, list the configurations and weights explicitly, then recompute the denominator independently. This catches omitted branches and arithmetic errors.
Enumeration is useful when an exact conditional distribution is needed and its support is manageable. Recursive algorithms exploit bounds and structure; network algorithms provide an effective feasibility test for margin-constrained tables. When the support is too large to enumerate, a different computational strategy is needed, but the target remains the same: the conditional law defined by all feasible configurations and their model-based weights.
Check Your Understanding
Use the definitions and calculations above to answer these questions.
- For a fixed-margin table, what information must be maintained during a cell-by-cell recursive enumeration?
- Why does a fixed order of cells help ensure that a table is listed only once?
- In the first worked example, why does the event that the upper-left cell equals 2 contain two tables rather than one?
- What does a feasible integer flow correspond to in the bipartite network representation?
- Why can configurations with the same sufficient-statistic value still need to be enumerated separately?
- In the matched-set example, what conditional probability would result if the four allocations were incorrectly treated as equally likely for \(\beta=\log 2\)?