2287. Fit

In science there are often data points (xi, yi) measured, for which an affine correlation is assumed by theory. That means, you can choose the parameters a and b for a straight line f(x)=a+b*x in such a way, that the sum of the squared y-distances (Chi2) from the points to the line is very low.

For example, if the points (1,2), (2,3) and (3,4) are measured, the line f(x)=1+1*x fits the points best, cause Chi2 then equals 0. That was easy! Now to a more challenging example: How should a and b be chosen, if the second point would be (2,2) instead of (2,3)?

Maybe you found out, that b again is 1, and a is about 0.67. If not, don’t worry, I’ll give you some hints to find out a and b for even more difficult situations. And you’ll need those hints, cause reality is even harder!

For example, imagine two police men. They want to know, if the average value of alcohol in people increases in the evening and if so, how fast. To this end, they stop one car exactly every 5 Minutes to measure the drunkness of the driver. This means an exact xi value (where i is an index which tells how many cars have been stoped before). Unfortunatelly, the alcohol analysers are still not so exact, so the yi value is not known for sure. But at least their analyser is good enough to give some information about the uncertainty of the measured yi-value, which will be called sigmai in the following.

In science and measurement it very often happens, that the y value can not be measured exactly, and you can only say that the real value is in the intervall [ yi-sigmai , yi+sigmai ] with a probability of 68%. You see why sigmai often is called uncertainty of yi: The bigger the sigmai, the less you know about the real value.

Now the police men have lots of triples (xi, yi, sigmai). Your task is to help them find out the best fit parameters a and b for the straight line, with which they can see, if and how fast the drunkness is increasing in the evening.

To make your task easier, I give you some tips. In the first sentences it was said, that the Chi^2 is the sum over the squared differences between f(xi) and yi. But now the y-coordinate is not so sure anymore, and so you have to divide each of those differences by the corresponding sigma value before squaring and summing. By this, you make sure that values, which are not so very well known (big sigma) are less much counted than values, which are nearly exactly known (small sigma).

To get the best fit with the given values (xi, yi, sigmai) you have to minimize the Chi^2, which means you have to build the derivative of (1)

with respect to a and b and set them equal to zero. That means you get an equation system with 2 equations and 2 unknown variables (a and b). By solving this equation system you get (check this to learn more!!!) :

This looks awful! But thats why nobody (including our police man and all scientists) wants to calculate a and b by hand. For your task - writing a little programm to calculate a and b - you only need (2)-(4). But be sure to write a memory efficient programm, there could be millions of triples!!! Though this looks like lots of work, if you’re clever you will only need about 10 lines for the main part of the programm plus some lines for in- and output.