How many data points to see if one model is significantly better than other models in a finite set?

Question

I am working on a linear regression problem, let's say I'm looking for a model that predicts housing prices as a function of number of rooms and square feet.

Assume for each attempt to price a house, we randomly pick a model from a fixed set of three models and use it to estimate the price. If it is within 10% of the actual price without going over, we count that as a success.

The question is, how many successes do I need before I am statistically certain (or measurably confident) that a model is actually the best one, given that there's a 1/3 chance any given model will be selected for the job.

For example we may guess on 300 houses (each model gets 100 tries on average), and each model has 5, 3, and 2 successes respectively. Is this enough to know that the one with 5 is best, and not just best because it happened to be selected on houses that worked with this particular model.

For example, given three linear regression models, specified by:

[{"square_feet":1.5,"bedrooms":100, 
 {"square_feet":1.8,"bedrooms":110, 
 {"square_feet":1.2,"bedrooms":120]

if we tried to predict the price of a house with 1000 square feet and 3 bedrooms, and we randomly select the first model - it would predict (1.5*1000) + (3*100) = 1800.

Answer 1

First of all, the methodology of choosing a model randomly and not evaluating all the data using all the models is indefensible. Especially so in case of linear regression, where you can evaluate hundreds of thousands of models in one second. You do not save any resources and you lose a lot of precious knowledge.

With that out of the way, many different approaches are possible. Each approach is based on different assumptions. If you do not need to be very rigorous and just want some quick results, I would use the Friedman test. From the Wikipedia page:

Classic examples of use are:

$n$ wine judges each rate $k$ different wines. Are any of the $k$ wines ranked consistently higher or lower than the others?

here substitute "judges" for "houses" and "wines" for "models". Each house tells you which model computes the price with biggest precision. Of course, you would have to abandon your random model selection.

But what if you do not want to abandon the random model selection and, on top of that, are ready to get your hands dirty with some math?

In this case, you can formulate the problem in terms of Bayesian statistics. I will illustrate the reasoning for two models, but it is of course generalizable to any number of models.

Let us assume that the fractions of all homes that models $M_1, M_2$ estimate correctly is $f_1,f_2$. Then if in the absence of any data we have no reason to believe that any fraction is more likely than any other, we may express our prior beliefs about $f_1$ and $f_2$ using a uniform probability distribution in $[0; 1] \times [0; 1]$. In other words, $p(f_1), p(f_2) \sim Beta(1,1)$. Then, as described in this great answer, with each evaluation of the given model, you either bump up the $\alpha$ or $\beta$ parameter of the proper Beta distribution, depending on whether the model was successful for this particular house or not.

At each point in time you can ask what is the probability that $f_1 < f_2$. Thanks to the uniform joint prior, $p(f_1 | data), p(f_2 | data)$ are independent and we can calculate the given probability using the integral: $$ P(f_1 < f_2) = \iint_{\{(f_1, f_2); f_1 < f_2\}} f_{\alpha_1, \beta_1}(f_1) f_{\alpha_2, \beta_2}(f_2) df_1 df_2 =\\ \int_{0}^{1} f_{\alpha_2, \beta_2}(f_2) \left(\int_{0}^{f_2}f_{\alpha_1, \beta_1}(f_1)df_1 \right) df_2 =\\ \int_{0}^{1} f_{\alpha_2, \beta_2}(f_2) F_{\alpha_1, \beta_1}(f_2) df_2 $$ Where $f_{\alpha, \beta}$ and $F_{\alpha, \beta}$ are the PDF and CDF of the Beta distribution. You can solve this integral numerically to get your probability.