# Finding a linear relationship without linear model

(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?

-
It looks like you are doing sensitivity analysis for a two point slope estimate. Of course you are lossing accuracy because you are ignoring the information from the other data points. The value of the linear model (simple linear regression in this case) is that you use it to get the least squares estimate of the slope which will be a lot more accurate than a two point estimator even if it come from the smallest and largest x$_i$s. So for efficiency reasons you should use all the data and the least squares estimate for the most accuracy and hence the smallest sample size to achieve that accuracy.