Limits to tree-based ensemble methods in small n, large p problems? Tree-based ensemble methods such as Random Forest, and subsequent derivatives (e.g., conditional forest), all purport to be useful in so-called "small n, large p" problems, for identifying relative variable importance. Indeed, this appears to be the case, but my question is how far can this ability be taken? Can one have, say 30 observations and 100 variables? What is the breaking point to such an approach, and are there any decent rules of thumb that exist? I'd prefer and will accept answers backed by links to actual evidence (not conjecture), using either simulated or real data sets. I haven't found much on the latter (here and here), so your thoughts/advice/(on topic) reference suggestions are most welcome!
 A: I suspect there won't be a definitive answer to this question until some simulation studies are conducted. In the meantime, I found Genuer et al's Random Forests: some methodological insights helped put some perspective on this question, at least in terms of testing RF against a variety of "low n, high p" datasets. Several of these datasets have >5000 predictors and <100 observations!!
A: The failure mode you'll encounter is that, with enough random features, there will exist features that relate to the target within the bagged samples used for each tree but not within the larger dataset. A similar issue to that seen in multiple testing.
Rules of thumb for this are hard to develop since the exact point at which this happens depends on the amount of noise and strength of the signal in the data. There also exist methods that address this by using multiple test corrected p-values as splitting criteria, doing a feature selection step based on variable importance and/or comparison of feature importances to artificial contrast features produced by randomly permutating the actual feature, use of out of bag cases to validate split selection and other methods. These can be extremely effective.
I've used random forests (including some of the above methodological tweaks) on data sets with ~1000 cases and 30,000-1,000,000 features. (Data sets in human genetics with varying level of feature selection or engineering). They can certainly be effective in recovering a strong signal (or batch effect) in such data but don't do well piecing together something like a disease with heterogenous causes as the amount random variation overcomes each signal 
A: It will also depend on the signal and noise in your data. If your dependent variable is pretty well explained by a combination of the variables in your model than I think you can get away with a lower n/p ratio. 
I suspect an absolute minimum number of n will also be required to get a decent model apart from just the ratio.
One way to look at it is that each tree is build using about SQRT(p) variables and if that number is large and number of points are small trees can be fitted without really having a real model there. Hence lot of such over-fitted trees will give false variable importance.
Usually if in variable importance chart, I see lot of top variables with almost same level of importance I conclude that it is giving me just noise. 
