Minimal number of games to narrow down the win rate

Question

This just popped up in my head, so there might be a famous known solution/algorithm for the solution. The situation is this.

Suppose know the (not exactly accurate) win rate(in percentage) of your opponent. The percentage is given in maximum two digits, with rounding off the decimal points. So for example, if the exact win rate is $61.9\%$, then you will only know the number $61$. If the win rate is $33.333333..\%$, then you will only be given $33$. Knowing your opponent's win rate(only exact up to its integer parts), you want to know the set of all possible number of matches your opponent has done. Especially, you want to know the possible minimal number of games your opponent has done.

One can notice pretty obvious things, for example

• The minimal number of games cannot exceed 100.

(Which brings me to another question, what win rate yields a minimal number of games $100$?)

• The set of all possible number of games include the multiple of the minimal possible number of game.

For given win rate $n$ ($0\leq n\leq 99, n \in \mathbb{Z})$, is there a particular relation between $n$ and the possible minimal number of games?

Answer 1

Here's the continued fraction approach for a win rate of $61$.

First, we do the Euclidean algorithm on $61/100$:

$61=0\times100+61$
$100=1\times61+39$
$61=1\times39+22$
$39=1\times22+17$
$22=1\times17+5$
$17=3\times5+2$
$5=2\times2+1$
$2=2\times1$, done.

The quotients in this system of equations form the partial quotients of the continued fraction for $61/100$, and the notation commonly used is $61/100=[0,1,1,1,1,3,2,2]$.

[This is really $${61\over100}=0+{1\over1+{1\over1+{1\over1+{1\over1+{1\over3+{1\over{2+{1\over2}}}}}}}}$$ which shows you why it's called a continued fraction, and also why we use the other notation for it.]

Now we make a little table: $$\matrix{n&&&0&1&2&3&4&5&6&7\cr a&&&0&1&1&1&1&3&2&2\cr p&0&1&0&1&1&2&3&11&25&61\cr q&1&0&1&1&2&3&5&18&41&100\cr}$$ The second row is just the partial quotients, the third row is formed by the recursion $p_n=a_np_{n-1}+p_{n-2}$, the fourth row by $q_n=a_nq_{n-1}+q_{n-2}$. The numbers $p_n/q_n$ are successively closer approximations to $61/100$, called convergents:

$p_0/q_0=0;\quad p_1/q_1=1/1=1;\quad p_2/q_2=1/2=.5;\quad p_3/q_3=2/3=.66\dots;\quad p_4/q_4=3/5=.6;\quad p_5/q_5=11/18=.611;\quad p_6/q_6=25/41=.609\dots;\quad p_7/q_7=61/100=.61$.

The first of these convergents to round down to $.61$ is $p_5/q_5$, so it is possible that your opponent played $18$ games (and won $11$ of them). This is good, but we can do better: we can experiment with smaller values of $a_5$. $a_5=1$ gives $p_5/q_5=5/8=.625$, which is no good, but $a_5=2$ gives $p_5/q_5=8/13=.615\dots$, which rounds down to $.61$, so this is best; the smallest number of games our opponent could have played is $13$ (winning $8$ of them).

I know I have omitted lots of exposition. Fill in the gaps by reading up on continued fractions.

Answer 2

I would say the only way is by force. For rounding-up-to-integers it may be quiet easy you just see all possibilities: (won/played) 0/1=0%, 1/1=100%, 1/2=50%, 1/3=33%, 2/3=66%, 1/4=25%, 3/4=75%, ... and check which one is the one with the smallest number of games played. But lets suppose we aren't tired enough and we want to get it to a N-2 number of decimals.

Percentage: $P=A*10^{1-N}$, Maximum digits: $N$ $\Rightarrow$ Number: $A$, Number of maximum possibilities: $10^N$,

(example: 0.853%, 4 $\Rightarrow$ 0853 (it would take from 0 to 1000), $10^4$)

So the maximum number of games are $10^N$. Lets suppose we know it was only needed one victory and $J$ number of played games for the percentage $P$.

Since $J$ is a number it can be written as product of their primes:

$J=J_{1}*J_{2}*...*J_{b}$

I'm going to use $\downarrow$ to symbol rounding down.

So:

$A=\frac{1}{J}*10^N\downarrow=\frac{1}{J_{1}*J_{2}*...*J_{b}}*10^{N-1}\downarrow$

If we rearrange:

$J_{1}*J_{2}*...*J_{b}=\frac{1}{A}*10^N\downarrow$

Since it doesn't exist a formula to get the prime factors for a number (in our case $\frac{1}{A}*10^N\downarrow$), we could not even know how many games it would take if we garanteed there was only one win

Answer 3

Loosely related to continued fractions, you may try Farey sums. Start with $\frac ab=\frac01$ and $\frac cd=\frac11$. As long as the interval corresponding to a win rate (e.g., $[0.61,0.62)$ for a win rate of 61%) is completely between $\frac ab$ and $\frac cd$, form the Farey sum $\frac uv=\frac{a+c}{b+d}$ and replace either $\frac ab$ or $\frac cd$ with it, depending on whether it is below or above said interval. The first time such a Farey sum hits the interval, you have found the fraction with smallest possible denominator in that interval.

The key observation why this works is that in each round $ad-bc=-1$ (in particular, the fractions are always in lowest terms). Also, any fraction in between has denominator at least as big as the Farey sum: If $$\frac ab<\frac xy <\frac cd$$ then the numerators of $\frac zu-\frac ab=\frac{bx-ay}{by}$ and $\frac cd-\frac xy=\frac{cy-dx}{dy}$ must be positive integers. Then $$x=x(bc-ad)=cbx-cay+acy-adx=c(bx-ay)+a(cy-dx)\ge a+c$$ as well as $$y=y(bc-ad)=bcy-bdx+dbx-day=b(cy-dx)+d(bx-ay)\ge b+d$$