(If this doesn't make sense it is because I am inexperienced at statistics)
Assume I have a broad universe of actions $A$ I could pursue, and for each $a_i \in A$ there is an associated characteristic $x_i \in X$, where $X$ is drawn from a normal distribution centered at 0 with standard deviation 1. Let's also say there is an associated value $v_i$ for each $a_i$ that in this case simply follows the equation: $$v_i = .13x_i+\epsilon,$$ where $\epsilon$ is just a noise term, drawn from a normal distribution with mean $0$ and standard deviation $\sigma$. Further assume that I am not aware of this relationship, but I want to figure it out.
One more constraint: I am not allowed to use linear regression. What I've been doing is selecting $n$ $a_i$'s with characteristic $x_1$ and $n$ $a_j$'s with characteristic $x_2$, taking the means of their values $v_i$ and $v_j$: $u_1$ and $u_2$, and inferring the line from the points $(x_1,u_1)$ and $(x_2, u_2)$. The problem is, the line is usually off by a lot, especially when the standard deviation of the noise, $\sigma$, gets larger.
To see why this is I constructed a worst case scenario. Basically we are just sampling from the normal distributions for the $v$'s corresponding to $x_1$ and $x_2$. Therefore we can construct confidence intervals around each point. I figured the worst case scenario would be inferring a line from the bottom of one confidence interval to the top of the other. I want to be 95% confident that the actual line will be within these bounds, so the confidence interval around each point needs to have confidence $1-p$ where $p^2/2=.05$, meaning $p=.316$ and we need a 68.4% confidence around each mean. Now using Chebyshev's inequality, we can solve for the number of points we have to draw to get within an acceptable error $\epsilon_a$: $$P(|u_i-\bar{v_i}|\geq\epsilon_a) \leq \frac{\sigma^2}{n\epsilon_a^2} = .316.$$ Solving for n we get: $$n = \frac{\sigma^2}{.316\epsilon^2_a}.$$ Now putting actual parameters in, for the real standard deviation we have $\sigma = .1$, for acceptable error, how about within 1% of the actual $\Delta v$, which is a function of the difference in $x$'s, which we'll say is 1 (regression can easily do this), so we get: $$n = \frac{.1^2}{.361(.01*.13*(x_1-x_2))^2} \approx 16000.$$ The problem is, it takes me anywhere from 5 seconds to 5 minutes to generate each triple of $(a_i, x_i, v_i)$ (there are a lot of things going on in the background), so doing up to 32000 iterations is very tedious and unmanageable. Is there a more efficient way of doing this, besides using a linear model?
Also, is there a name for the algorithm that I am using so I can better research it?
