0
$\begingroup$

So, I'm playing a game where there is a certain percent value that changes over time. I look at it occasionally, it seems to be approximately linear in time. However, the change is slow enough that I want something better than simple linear regression.

Problem:

$f(x) := ax+b$

$g(x) := \mathrm{round}(f(x))$

Given pairs $\{(x_1,g(x_1)),\dots,(x_n,g(x_n))\}$, estimate $a$ and $b$.

  • 0
    unless there are too many data points to practically find as exact of a solution as is possible.2010-12-04

1 Answers 1

1

Given pairs $(x_i,y_i)$, you can try to find $a,b$ that minimize the $L^\infty$ distance from $y_i$ to $ax_i+b$ using LP, which is $\max_i |y_i-ax_i-b|$; if $y_i$ indeed depends linearly on $x_i$ up to rounding, then there's a choice of $a,b$ with $L^\infty$ distance of less than $1/2$.

There may be a simpler way to solve this particular optimization problem, but an LP would work, especially with your small dataset. But if your model is wrong, you might get garbage because of the unforgiving $L^\infty$ metric. Minimizing the $L^1$ metric can also be formulated as an LP, and minimizing the $L^2$ metric is the well-known least-min-squares, for which there is an explicit solution.

  • 1
    [This](http://dx.doi.org/10.1007/BF02162565) details an algorithm for doing Yuval's suggestion. Remember though: "garbage in, garbage out".2010-12-04