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)
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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:
and have a program determine it for you. But this is slow compared to the other method when the ranges become narrow.