# What is the relation between minimum instances per node and max depth?

In bagging and boosting models like random forest and xgboost we have hyper-parameters like minimum instances per node and max depth. If max depth is high the minimum instances per node will be less and vice versa.

Is there a mathematical equation I can make out the between two hyperparameters? That is if I had to calculate depth as a function of min instances per node, what it would be like?

This is what I have for now-

Let us say we have only one numerical variable with the number of bins set to mB. This is the number of levels in the case of categorical variables. We N number of samples in our dataset and the minimum number of samples needed to create a node is n. Our aim is to find the maximum possible depth(maxDepth) this tree could go to.

Now, for the tree to go the maximum depth the other nodes have to terminate instantly. If they get more samples than the bare minimum, our max depth suffers. Here in the diagram, I have shown the node to be splitting into 3 (mB) nodes. mB-1 of them have to terminate so that more and more samples can go to one node and we can thus calculate the maxDepth the tree can go to.

So at the end of the first split, we have two leaf nodes and one active/parent node. This parent node has N-N*(mb-1) samples at depth=1. So for the tree to terminate, at the depth=maxDepth, it should have at least n samples or else the tree won't grow to maxDepth.

And the number of samples at depth=maxDepth would be $$N-n*(mB-1)*maxDepth$$

thus giving us

$$N-n*(mB-1)*maxDepth \ge n$$

$$maxDepth \le \frac{(N-n)}{n*(mB-1)}$$
I have made the following assumptions to reach here 1. The number of splits made at each level are same - mB 2. Each split will result in mB-1 nodes being leaf nodes and just one node capable of being a parent node.