Ties and Order Dependence in Stepwise Paths

Why Ties Matter in a Stepwise Search

A stepwise procedure makes a sequence of local decisions: at each stage, it compares eligible candidate changes and chooses one according to a stated rule. If two candidates produce the same improvement, the rule alone does not identify a unique next predictor. If their improvements are very close, tiny changes in numerical precision or implementation can determine which one is chosen. Because later comparisons are made from the model reached at the current step, different early choices can lead to different paths.

This is a question about the behavior of a search algorithm, not evidence that one predictor is intrinsically the “right” choice. A path records the choices made under a particular candidate set, criterion, eligibility rule, and tie policy. It should not be mistaken for a unique ranking of predictors that is independent of those details.

Setup and Definitions

Suppose a response is modeled using a fixed set of candidate predictors. At each forward-selection step, the current model is compared with models formed by adding one eligible predictor. For backward elimination, the analogous comparison removes one eligible predictor; bidirectional procedures can consider both types of change. To isolate the issue of order and ties, the examples below use forward additions.

Assume candidate models use the same response observations, include the same intercept, and are fitted by least squares. The usual Gaussian regression likelihood underlying the AIC formula assumes independent errors with mean zero, a common variance, and a normal distribution; the conditional mean is represented by the candidate regression model. These assumptions concern the model-based criterion, not whether a particular stepwise path is unique. The candidate set and the rule for which changes are eligible must also be fixed before comparing choices.

For example, if all candidates add one predictor and are compared by residual sum of squares, the preferred addition is the one with the smallest resulting residual sum of squares, or equivalently the largest decrease in that quantity. If candidates have different numbers of parameters, a criterion that penalizes model size may rank them differently. Comparisons are meaningful only when the criterion and candidate changes are clearly specified.

For Gaussian least-squares models fitted to the same \(n\) observations, AIC can be written, up to a constant common to all the models, as

where \(\mathrm{RSS}\) is the residual sum of squares and \(k\) is the number of fitted parameters. Lower AIC is preferred. When two additions each introduce one slope coefficient, they add the same number of parameters. In that comparison, lower RSS and lower AIC give the same ranking, though their numerical differences are on different scales.

Why the AIC Improvement Rule Works

The following short derivation helps distinguish a tied comparison from a decision to stop. Let the current model have RSS \(R\) and \(k\) parameters. Suppose adding one predictor gives RSS \(R_{\mathrm{new}}\) and \(k+1\) parameters. Subtracting the old AIC from the new AIC gives

Thus the addition lowers AIC exactly when

The penalty means that a decrease in RSS alone does not guarantee a lower AIC. For comparing two additions of one predictor from the same current model, however, the \(+2\) penalty is identical for both. Their AIC difference is determined by their RSS values. If the candidate RSS values are equal, their AIC values are equal as well. If the values are close, so are their AIC values.

Near Ties and Numerical Precision

A near tie requires more care than an exact tie. With full-precision values, a deterministic rule may identify one candidate as slightly better. That ordering is technically well-defined, but if the difference is tiny, reporting only the winner hides how little separated the candidates were. A display that rounds the values can also make unequal candidates look identical. Conversely, an implementation that rounds before comparing, or treats differences within a tolerance as ties, may deliberately use a tie-breaking rule.

When Predictor Order Can Change the Path

There is an important distinction between the order in which candidates are stored or printed and the sequence of decisions made by the algorithm. In a forward search that evaluates every eligible addition at each step, uses exact criterion values, and selects the unique best candidate, merely permuting the labels or input order cannot change the choice. The minimum remains the same. Order can matter when candidates tie and the software resolves ties by taking the first encountered candidate, or when near ties are treated as tied because of rounding or a numerical tolerance.

Once a different candidate is selected, the current model changes. Each subsequent addition or removal is then evaluated conditional on that model, so the later candidate comparisons can differ. Other implementation details can matter too: a procedure may stop after a first qualifying change rather than compare all eligible changes, or may use rules that alter which candidates are eligible at a later step. For those procedures, changing the candidate evaluation order can affect the path even when the underlying data are unchanged. The algorithm’s actual search and stopping rules must therefore be reported along with its criterion.

A useful diagnostic is to separate three questions: Were the candidate improvements actually equal? If not, how large was their difference at full precision? And did the software choose based on the criterion values, or on an order or tolerance convention? This separates a substantive near tie from a purely mechanical tie-breaking effect.

Common Mistakes and Practical Reporting

• Calling the first-listed predictor the statistically strongest. If the candidates tie and software takes the first one, its position in the input list—not a larger improvement—determined the choice. Report the tie and the tie-breaking rule.
• Treating a rounded display as proof of an exact tie. Values displayed as equal may differ at full precision. Check the unrounded criterion values and the software’s comparison tolerance.
• Assuming every reorder changes a valid search. With a unique best candidate and a procedure that compares all eligible candidates, input order alone does not change that step. Order effects require a tie, a tolerance or rounding convention, or an order-dependent implementation.
• Interpreting a small numerical win as a large practical distinction. A selected candidate may rank first by a very small criterion difference. State the difference and avoid treating a near tie as clear separation.
• Reporting only the final selected set. A final set hides how a tied choice was resolved and whether a different order produced another path. Give the relevant alternative paths and their criteria when sensitivity is present.

A compact sensitivity report should name the selection procedure, the criterion, the tied or near-tied candidates, the tie-breaking or tolerance policy, and the paths obtained under plausible alternative orders. This is not a claim that every possible order must be tried. It is a way to make a consequential dependence visible when it occurs. The path is an outcome of a defined search procedure; it should be described with that procedure in view.