Two Different Meanings of a Size Limit
When a regression analysis considers subsets of a fixed set of candidate predictors, the word size refers to how many predictors a model includes. A search described as “size two” can mean either models containing exactly two predictors or models containing no more than two. These are different candidate sets: the second includes the first, along with every eligible smaller model.
For clarity, assume a common response variable and a fixed set of \(p\) candidate predictors. Unless stated otherwise, every model includes an intercept, and the intercept is not counted as a predictor. Thus, the model with no predictors is the intercept-only model. The distinction here concerns which subsets are included in the candidate space, not how their fitted values or performance are compared.
Counting the Two Candidate Spaces
For an exact-size \(k\) search, the task is to choose \(k\) predictors from \(p\), without regard to their order. Its number of models is \(\binom{p}{k}\), provided \(0\leq k\leq p\). The at-most-size \(k\) search collects the models of every size from zero through \(k\), so its number is the sum of the counts for those sizes.
The index \(j\) in the sum is the model size. The term for \(j=0\) is \(\binom{p}{0}=1\): the single empty predictor subset, corresponding to the intercept-only model. Consequently, for \(k\geq 1\), an at-most-size \(k\) search contains the exact-size \(k\) models and additional models of smaller sizes. If a particular problem explicitly excludes the intercept-only model, omit the \(j=0\) term. Always check which convention is being used.
Why the At-Most Count Is a Sum
Every predictor subset has one definite size. The collection of all subsets of size zero, the collection of all subsets of size one, and so on are therefore disjoint: a subset cannot have two different sizes. Counting all models up to size \(k\) means adding the count at each allowed size, with no overlap to subtract.
For each fixed \(j\), the count is \(\binom{p}{j}\) because selecting a subset means choosing \(j\) distinct predictors from \(p\), where changing their order does not create a different model. This also explains why the exact-size count is just one term of the at-most-size sum.
Worked Example: Four Predictors and a Size-Two Limit
A hypothetical pricing analysis has candidate predictors \(A\), \(B\), \(C\), and \(D\). The intercept is included in every model but is not counted. Enumerate the exact-size two models and the at-most-size two models, then verify both counts.
Method. First group models by the number of predictors included. The exact-size search uses only the group of size two; the at-most-size search uses the groups of sizes zero, one, and two.
Exact size two. The pairs are \(AB\), \(AC\), \(AD\), \(BC\), \(BD\), and \(CD\). There are six models. The count agrees with \(\binom{4}{2}=4!/(2!2!)=6\).
At most size two. The size-zero group contains \(\varnothing\). The size-one group is \(A\), \(B\), \(C\), and \(D\). The size-two group is the six pairs listed above. Thus the candidate set has \(1+4+6=11\) models. The formula gives \(\binom{4}{0}+\binom{4}{1}+\binom{4}{2}=1+4+6=11\).
Check and common mistake. All six exact-size models are included in the 11-model at-most-size set, along with the empty model and four one-predictor models. Calling the at-most search “six models” would incorrectly count only the size-two group.
Enumerating Carefully
A reliable enumeration proceeds one size at a time. This prevents smaller models from being forgotten and makes it easier to check that the displayed list has the expected number of entries. The following process is useful when the predictor set is small enough to list.
Write down the distinct predictors available. Keep the response variable and the intercept convention fixed.
“Exactly \(k\)” means list only subsets with \(k\) elements. “At most \(k\)” means include each size from zero through \(k\).
List the empty subset if allowed, then single predictors, pairs, and larger subsets as far as the specified limit.
For size \(j\), compare the list with \(\binom{p}{j}\). For an at-most search, add the group counts.
Worked Example: Comparing Two- and At-Most-Two Searches
A hypothetical claim study has five candidate predictors: policy duration \(D\), region \(R\), payment frequency \(F\), a risk score \(Q\), and a renewal indicator \(H\). The intercept is included. List every exact-size two model, then determine the number of additional models in an at-most-size two search.
Method. Choose unordered pairs for the exact-size set, then count the smaller sizes separately for the at-most set.
Exact size two. The pairs are \(DR\), \(DF\), \(DQ\), \(DH\), \(RF\), \(RQ\), \(RH\), \(FQ\), \(FH\), and \(QH\). There are ten. The binomial check is \(\binom{5}{2}=5!/(2!3!)=10\).
Smaller sizes. The size-zero group is \(\varnothing\), so it contributes one model. The size-one group consists of \(D\), \(R\), \(F\), \(Q\), and \(H\), so it contributes five. The number of additional models beyond the exact-size two set is \(1+5=6\).
At-most-size two total. Add the ten pairs to the six smaller models: \(10+6=16\). Independently, the formula gives \(\binom{5}{0}+\binom{5}{1}+\binom{5}{2}=1+5+10=16\).
Check and common mistake. The exact-size search has ten models, while the at-most-size search has 16. The six additional models are not six more pairs; they are the intercept-only model and five one-predictor models.
Boundary Cases and Conventions
Boundary cases provide quick checks on whether the wording has been translated correctly. At \(k=0\), an exact-size search contains only the empty predictor subset, and an at-most-size zero search contains that same subset. At \(k=p\), an exact-size search contains only the full predictor set, whereas an at-most-size search contains every subset of the \(p\) predictors.
The last count follows because each of the \(p\) predictors is either included or omitted, giving two choices per predictor. If a limit \(k\) is at least \(p\), no subset can exceed the limit, so an at-most-size search includes all \(2^p\) subsets. An exact-size search with \(k>p\), in contrast, has no eligible models.
Some descriptions use “size” to count all model terms, including an intercept. Do not silently switch conventions. If the intercept counts as one term, a model with \(k\) total terms contains \(k-1\) candidate predictors. State the convention before using a count formula, and interpret any reported model size accordingly.
Worked Example: A Limit Just Below the Full Model
A hypothetical monitoring model has four candidate predictors \(W\), \(X\), \(Y\), and \(Z\), with an intercept included separately. Compare exact-size three with at-most-size three, listing the exact-size models and checking the at-most total.
Method. Enumerate the three-predictor subsets, then count the at-most search by sizes zero through three.
Exact size three. Each model omits one of the four predictors. The four models are \(WXY\), \(WXZ\), \(WYZ\), and \(XYZ\). The count is \(\binom{4}{3}=4\).
At most size three. The size counts are \(\binom{4}{0}=1\), \(\binom{4}{1}=4\), \(\binom{4}{2}=6\), and \(\binom{4}{3}=4\). Their sum is \(1+4+6+4=15\). There are \(2^4=16\) total subsets of four predictors, and the at-most-size three set excludes just the full four-predictor model. Therefore it also has \(16-1=15\) models.
Check and common mistake. The four listed triples are the exact-size set, not the at-most-size set. The latter contains those triples and every smaller subset, for 15 models total.
Common Counting Traps
- Reading “at most” as “exactly.” An at-most-\(k\) search includes every allowed size below \(k\), not just size \(k\).
- Omitting the empty subset without checking. If the intercept-only model is permitted and the intercept is not counted as a predictor, include the size-zero model.
- Counting order as a distinction. The model containing \(A\) and \(B\) is the same subset as the model containing \(B\) and \(A\). Use combinations, not ordered arrangements.
- Mixing predictor count and total terms. If an intercept is included, confirm whether the stated size counts it before translating the limit into a number of predictors.
- Forgetting the range of \(k\). Exact size \(k\) is impossible when \(k>p\). An at-most limit at least \(p\) includes every predictor subset.
Check Your Understanding
For each problem, distinguish the specified candidate spaces and verify the counts from the number of predictors. Assume the intercept is included but is not counted as a predictor.
- A model has four candidate predictors. How many models are in an exact-size one search, and how many are in an at-most-size one search? (Answer: 4 exact-size models; 5 at-most-size models.)
- Five candidate predictors are available. Find the number of exact-size two models and the number of at-most-size two models, including the intercept-only model. (Answer: 10 exact-size models; 16 at-most-size models.)
- For predictors \(A,B,C,D\), list the exact-size three models and give the at-most-size two count. (Answer: \(ABC, ABD, ACD, BCD\); 11 at-most-size-two models.)
- A search has six candidate predictors and permits at most four. Compute its number of models, then determine how many subsets are excluded from all possible predictor subsets. (Answer: 57 included; 7 excluded.)
- There are three candidate predictors and the limit is at most three. How many models are included, and how many have exactly three predictors? (Answer: 8 included; 1 exact-size-three model.)