Random Feature Sampling and Split Availability

Why Split Availability Matters

A tree can split on a coordinate only if that coordinate is among the predictors considered at the node. Random feature sampling deliberately limits that set. This can reduce the number of candidates compared at each split, but it also means a useful coordinate may be absent from a particular node’s candidate set. The probability of availability quantifies this first step: it says whether a coordinate can be considered, not whether the tree will ultimately split on it.

The distinction is important when interpreting randomized trees and forests. A relevant coordinate might be available at some nodes and unavailable at others. Repeated opportunities can make it increasingly likely to appear among the candidates, but the resulting probability depends on the sampling scheme and on how many opportunities actually occur.

One Node: Availability Under Sampling Without Replacement

Suppose there are $p$ coordinates eligible for sampling at a node, and the algorithm selects $m$ distinct coordinates uniformly at random, where $0\leq m\leq p$. Let $A$ be a designated set of $s$ relevant coordinates among those $p$ coordinates. Here, “relevant” means relevant to the question being studied; it does not, by itself, say anything about which split criterion the algorithm will prefer.

Definition: A coordinate is available at a node if it belongs to the set of coordinates sampled for consideration at that node. The relevant set $A$ is available if at least one of its coordinates is sampled. Availability is not the same as being selected for the split.

There are $\binom{p}{m}$ equally likely sampled sets. A sampled set contains no relevant coordinate precisely when all $m$ sampled coordinates come from the $p-s$ coordinates outside $A$. If $m\leq p-s$, there are $\binom{p-s}{m}$ such sets. If $m>p-s$, there are none. Thus the chance that at least one relevant coordinate is available is

q(p,m,s) = 1-\frac{\binom{p-s}{m}}{\binom{p}{m}},

where $\binom{p-s}{m}=0$ when $m>p-s$. This formula includes the boundary cases: if $s=0$ or $m=0$, then $q(p,m,s)=0$; if $m>p-s$, then $q(p,m,s)=1$.

Theorem: Under uniform sampling of $m$ distinct coordinates from $p$, the probability that at least one of a fixed set of $s$ relevant coordinates is available is $q(p,m,s)$ as given above. For any one specified coordinate, its probability of being available is $m/p$ when $p>0$.

Proof. Each $m$-element subset has probability $1/\binom{p}{m}$. The event that no member of $A$ is sampled has $\binom{p-s}{m}$ possible subsets if $m\leq p-s$, and zero otherwise. Its probability is therefore $\binom{p-s}{m}/\binom{p}{m}$. Taking the complement gives the stated expression. For a specified coordinate, the number of sampled sets that include it is $\binom{p-1}{m-1}$ when $m\geq1$. Therefore its inclusion probability is

\frac{\binom{p-1}{m-1}}{\binom{p}{m}} = \frac{m}{p}.

When $m=0$, the coordinate is never sampled and the same formula gives zero. This proves both claims. $\square$

The probability for a set of relevant coordinates is generally not $s(m/p)$. That expression adds the marginal inclusion probabilities of the $s$ coordinates, counting samples that include two or more relevant coordinates more than once. The complement count handles overlaps exactly.

Worked Example: Several Relevant Coordinates at One Node

A node has $p=12$ eligible coordinates. The algorithm samples $m=4$ without replacement, and $s=3$ coordinates are relevant. Find the probability that at least one relevant coordinate is available.

There are $\binom{12}{4}=495$ equally likely sampled sets. A set with no relevant coordinate must choose all four coordinates from the $12-3=9$ irrelevant ones, giving $\binom{9}{4}=126$ such sets. Hence

q(12,4,3) = 1-\frac{\binom{9}{4}}{\binom{12}{4}} = 1-\frac{126}{495} = \frac{369}{495} = \frac{41}{55} \approx 0.7455.

So a relevant coordinate is available with probability about $74.55\%$. By contrast, each particular relevant coordinate has inclusion probability $4/12=1/3$. These are different questions: the set-level probability counts availability of any of the three coordinates, including samples that contain more than one.

Repeated Opportunities

Suppose the same relevant set is considered at $K$ opportunities, and at each opportunity a fresh uniform sample of $m$ coordinates is drawn independently of the other samples. At any one opportunity, the chance of no relevant coordinate is $1-q(p,m,s)$. Independence makes the probability of no relevant coordinate across all $K$ opportunities the product of these $K$ failure probabilities.

Theorem: For $K$ independent samples of $m$ coordinates from the same $p$ eligible coordinates, the probability that at least one relevant coordinate is available at least once is $$ 1-\left(1-q(p,m,s)\right)^K = 1-\left(\frac{\binom{p-s}{m}}{\binom{p}{m}}\right)^K. $$ If $q(p,m,s)>0$, this probability tends to $1$ as $K$ tends to infinity.

Proof. Let $F_k$ denote the event that the $k$th sample contains no relevant coordinate. For each $k$, $P(F_k)=1-q(p,m,s)$. The samples are independent, so $F_1,\ldots,F_K$ are independent and

P(F_1\cap\cdots\cap F_K) = \prod_{k=1}^{K}P(F_k) = \left(1-q(p,m,s)\right)^K.

The event that a relevant coordinate is available at least once is the complement of $F_1\cap\cdots\cap F_K$, which proves the finite-$K$ formula. If $q(p,m,s)>0$, then $0\leq 1-q(p,m,s)<1$, so $\left(1-q(p,m,s)\right)^K$ tends to zero as $K$ tends to infinity. The complementary probability therefore tends to one. $\square$

The same reasoning applies when the sampling size varies by opportunity. If opportunity $k$ uses $m_k$ coordinates and its sample is independent of the others, the probability of at least one relevant coordinate appearing is

1-\prod_{k=1}^{K} \frac{\binom{p-s}{m_k}}{\binom{p}{m_k}},

with the same zero convention for the numerator. More generally, a product formula is justified when the successive no-availability events are independent. If their conditional no-availability probabilities, given all previous samples, are fixed values $r_k$, successive conditioning gives a no-availability probability of $\prod_{k=1}^{K}r_k$. Independence is a sufficient and common way to obtain this condition.

Worked Example: Repeated Samples at a Fixed Sampling Size

Continue with $p=12$, $m=4$, and $s=3$, so that the probability of availability at one opportunity is $41/55$. Assume three independent samples are drawn. The chance that none contains a relevant coordinate is

\left(1-\frac{41}{55}\right)^3 = \left(\frac{14}{55}\right)^3 = \frac{2744}{166375} \approx 0.01649.

Therefore the probability of availability at least once is

1-\frac{2744}{166375} = \frac{163631}{166375} \approx 0.9835.

The increase from about $74.55\%$ at one opportunity to about $98.35\%$ at three is a statement about whether a relevant coordinate is offered for consideration. It is not a statement that the tree will make a relevant split.

Worked Example: Tracking One Specified Coordinate

There are $p=9$ eligible coordinates, and a particular coordinate of interest is sampled in sets of size $m=3$. At one opportunity its availability probability is $3/9=1/3$, so its chance of being absent is $2/3$. Across five independent opportunities, the chance that it appears at least once is

1-\left(\frac{2}{3}\right)^5 = 1-\frac{32}{243} = \frac{211}{243} \approx 0.8683.

This calculation concerns one specified coordinate, rather than any coordinate in a relevant set. For comparison, if two relevant coordinates were designated and the same $m=3$ sample used, the one-opportunity set-level probability would instead be

1-\frac{\binom{7}{3}}{\binom{9}{3}} = 1-\frac{35}{84} = \frac{49}{84} = \frac{7}{12}.

Repeated opportunities would then give probability $1-(5/12)^5$ that at least one of those two coordinates is available at least once. The set-level calculation is not obtained by treating the two coordinate-inclusion events as disjoint.

Worked Example: Changing the Sampling Size

Let $p=10$ and $s=2$. Suppose the first opportunity samples $m_1=2$ coordinates, while the second independently samples $m_2=4$. The first opportunity has probability

q_1 = 1-\frac{\binom{8}{2}}{\binom{10}{2}} = 1-\frac{28}{45} = \frac{17}{45}

of making at least one relevant coordinate available. At the second opportunity,

q_2 = 1-\frac{\binom{8}{4}}{\binom{10}{4}} = 1-\frac{70}{210} = \frac{2}{3}.

The probability of no relevant coordinate at either opportunity is $(28/45)(1/3)=28/135$. Thus the probability of availability at least once is

1-\frac{28}{135} = \frac{107}{135} \approx 0.7926.

The two per-opportunity probabilities are different, so it would be incorrect to use a single fixed-$m$ formula with $K=2$. The product of the two failure probabilities accounts for the changing sample sizes.

What Repeated Availability Does—and Does Not—Guarantee

Repeated sampling can make the probability of ever offering a relevant coordinate large. If the same positive availability probability $q$ applies independently at each of $K$ opportunities, the probability of never offering any relevant coordinate is $(1-q)^K$. This describes the candidate-sampling mechanism, not the full behavior of a fitted tree.

Even when a relevant coordinate is available, the splitting rule may select a different coordinate. A competing coordinate might yield a larger value of the chosen split criterion; there might be no admissible cut on the relevant coordinate; or a stopping rule might prevent any split at that node. Those outcomes require additional information about the data, the split criterion, and the tree-building procedure. Availability alone supplies none of it.

Likewise, a statement about $K$ opportunities needs a clear interpretation of $K$. The finite-$K$ formula applies to $K$ actual draws under the stated independence assumptions. A tree path might terminate before a proposed number of nodes is reached. The formula then cannot, without further assumptions, be read as the probability of availability along that path. One safe interpretation is a fixed sequence of $K$ sampling opportunities. For an adaptive path, the number of opportunities reached and the sampling events may need to be analyzed together.

Common Mistakes

Using $s(m/p)$ as the probability of any relevant coordinate being available. This adds the inclusion probabilities for individual coordinates but double-counts samples containing multiple relevant coordinates. Use the complement formula $1-\binom{p-s}{m}/\binom{p}{m}$.
Multiplying failure probabilities without a dependence assumption. The product across opportunities follows from independent samples, or from suitable fixed conditional failure probabilities. If the sampling events are dependent, the product need not be correct.
Equating availability with an actual split. A candidate coordinate can be available and still lose to another candidate or fail a split constraint. The calculations here concern candidate access only.
Treating a random path length as a fixed number of opportunities. If a path terminates early, not all proposed samples are realized along it. State whether $K$ counts fixed sampling draws or reached nodes, and do not apply the fixed-$K$ formula to a path without checking its assumptions.

Key takeaway: Under uniform sampling without replacement, the one-node probability of offering at least one of $s$ relevant coordinates is $1-\binom{p-s}{m}/\binom{p}{m}$. Repeated independent opportunities compound the failure probability, but candidate availability is not a guarantee of an actual split.

Check Your Understanding

Use the sampling assumptions in each question explicitly.

There are $p=15$ eligible coordinates, $m=5$ are sampled uniformly without replacement, and $s=2$ are relevant. Write the exact probability that at least one relevant coordinate is available.
For one specified coordinate, what is its inclusion probability at a node when $m$ of $p$ coordinates are sampled uniformly without replacement?
If the one-opportunity availability probability is $q$ and there are $K$ independent opportunities, what is the probability that a relevant coordinate is available at least once?
Why is the sum of the individual inclusion probabilities of several relevant coordinates generally not their set-level availability probability?
Give one reason a relevant coordinate may be available at a node but not used for the split.