Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

An experiment was performed n times. The success rate was given as 85.8% Clearly, if there were 858 successes out of 1000 trials it would give that percentage. However, the percentages are rounded to three digits, and so s/n could be anything such that 0.8575 ≤ s/n < 0.8585 . What is the simplest way to determine the minimum values of s (successes) and n (#trials) given the success rate as a percentage rounded to a given number of digits? (In general: not just for this example)

share|improve this question
    
Look up the paragraph with best rational approximation here. Following the recipe there I got 91/106. Possible that I made a mistake, because I really need to catch some sleep. G'night! –  Jyrki Lahtonen Jul 24 '11 at 21:07
    
It seems like representing the numbers as decimals: $\frac {8575}{10000}$ and $\frac{8585}{10000}$ and simplifying would be a good start, maybe even the actual answer. Then any choice of q in $\mathbb Q\cap\I$ , where I is the interval between the two fractions above, then you want to select the number in I with smallest denominator. –  gary Jul 24 '11 at 21:12
    
Having found the smallest acceptable denominator of 106, it might also be worth looking for the largest unacceptable denominator, which seems to be 947. –  Henry Jul 24 '11 at 22:33

2 Answers 2

up vote 4 down vote accepted

A good way to construct fractions which approximate numbers is to use continued fractions.

Namely, if we have that $x=a_0+1/(a_1+1/(a_2+1/(\cdots$ (which we shall write with the shorthand $x=[a_0,a_1,a_2,\ldots]$), we can define the convergents of $x$ to be the partial sums $[a_1, \ldots, a_k]=a_0+1/(a_1 + 1/(\ldots +1/(a_k))\cdots))$. These will give the best rational approximations to $x$ given the size of the denominator. For example, the approximations $22/7$ and $355/113$ for $\pi$ are both convergents of the continued fraction expansion.

A small caveat: given a continued fraction $x=[a_0,a_1,\ldots]$, increasing $a_i$ gives something larger when $i$ is even, but something smaller when $i$ is odd.

As in Charles's solution, the continued fractions of 0.8575 and 0.8585 are [0, 1, 6, 57] and [0, 1, 6, 14, 1, 8, 2] respectively, and so the solutions with the minimum length for the continued fraction expansion will be of the form $[0,1,6,15\ldots 57]$. Among these, $[0,1,6,15]$ will have the smallest denominator. The length of the expansion isn't the only thing that determines the size of the denominator, as $[1,1,1,1,2]$ has a smaller denominator than $[1,1000000000]$, and so one might suspect that something like $[0,1,6,14,0,1]$ could have a smallest denominator (although this is a bad example, because $[a_0,\ldots, a_k,1]=[a_0,\ldots, a_k+1]$, and so $[0,1,6,14,0,1]=[0,1,6,15]$). However, wikipedia asserts that Charles's method will be optimal and works in general. Proving optimality is likely a good exercise in working with continued fractions.

If instead of finding the smallest denominator the goal is just to find small denominators that make quite good approximations, the continued fraction expansion of $0.858$ is [0,1,6,23,1,2], and the convergents are $1/1, 6/7,139/162$, and $145/169$. We see that $139/162$ has a larger denominator than $91/106$, but the accuracy is $.000025$ versus $.0005$, approximately a 20-fold improvement in accuracy. Taking the next convergent, $145/169$ gives a 2-fold accuracy improvement over the previous convergent.

share|improve this answer

You can determine this by looking at the continued fractions of 0.8575 and 0.8585. They are [0, 1, 6, 57] and [0, 1, 6, 14, 1, 8, 2] so anything in [0, 1, 6, 15..57] would work. [0, 1, 6, 15] has the smallest denominator in that range which corresponds to 0+1/(1+1/(6+1/15)) = 91/106.

I just tested smaller denominators and this checks out right. Alternately, you could just start there:

ok(x)=0.8575<=x && x<=0.8585
{for(n=1,10^99,
  x=.858*n;
  if(ok(ceil(x)/n),return(ceil(x)/n));
  if(ok(floor(x)/n),return(floor(x)/n))
)}

and have a program determine it for you. But this is slow compared to the other method when the ranges become narrow.

share|improve this answer
    
Pari FTW! $$$$ ;) –  The Chaz 2.0 Jul 24 '11 at 21:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.