What is the smallest value of n such that the probability that a wins the match is at least 0.9?

Question

This question is based around a game I made in python, based on the racket sport, Squash. Basically simulation of games inside the code take the two ability ratings, one from player a, one from player b, and uses this probability formula to calculate the winner:

p = ra/(ra+rb)

Where p(probability), ra(rating of player a), rb(rating of player b)

Here are two of the main functions I've created in my code, just to give you some context as to how the game works:

def game(ra, rb):
    "simulates a single game and returns scores"
    p = ra/(ra+rb) #Calculating the probability that player A wins a point
    score = [0,0]
    while(((max(score)>10) & ((max(score)-2)<min(score))) or ((max(score)<11))):
        r = uniform(0,1)
        if r < p:
            score[0]+=1
        else:
            score[1]+=1
    else:
        return((score[0],score[1]))


def winProbability(ra, rb, n):
    "simulates n number of games and returns probability based on results"
    p = 0.5
    wins = [0,0]
    for i in range(n):
        curgame = game(ra,rb)
        if (curgame[0] > curgame[1]):
        wins[0]+=1
        else:
            wins[1]+=1
    if (max(wins)>0):
        p = wins[0]/(wins[0]+wins[1])
    return p

The question: Suppose player a has ability 60 and player b has ability 40, and they play a match where the winner is the first player to win n games. What is the smallest value of n such that the probability that a wins the match is at least 0.9? You may answer using simulation, theory, or a combination of both.

If you don't understand the code that's fine, It's the maths way around finding out this answer that i'm interested in most. I've already tried creating a loop of simulating games which has currently been running for 30 minutes and just reached 0.837 (rounded), so I know for a fact this method is way to long. I'm unsure of what equation would be needed to solve this problem?

Answer 1

The approximate methods described by other solutions certainly narrow the computation down a lot. It is likely, of course, that an approximate answer is satisfactory. To do the calculation exactly: if you seek $n$ wins, play out all of the $2n-1$ games. In such a series, the winning team will be the only team to have won at least $n$. If you favored team wins each game with probability $p$ then the probability that they will win the series is $$P_n=\sum_{i=n}^{2n-1}\binom {2n-1}ip^i(1-p)^{2n-1-i}$$

Taking $p=.6$ for your problem, we compute (with mechanical assistance) that $$P_{20}=0.897941369\quad \&\quad P_{21}=0.903482784$$ Thus you need $21$ games to clear the $.9$ hurdle.

Answer 2

You can actually think of this as a game with $2n-1$ rounds, and you play all the rounds, and the winner is the winner who gets $n$ or more wins. That's actually easier.

This is the same as asking about confidence intervals. Given a random variable $X$ that is $0$ with probability $1-p$ and $1$ with probability $p$, your mean value is $p$ and your standard deviation is $\sqrt{p(1-p)}$. What you want is a confidence interval of 80% (because half the time you win more than $p$ games.) So your $z^*=1.28$ and you need:

$$z^*\frac{\sqrt{0.6\cdot0.4}}{\sqrt{2n-1}}<0.1$$

Or $$\sqrt{2n-1}\geq\frac{1}{0.1}\cdot 1.28\cdot \sqrt{0.6\cdot 0.4}$$

or $2n-1> 39$, or $n>20$.

This will only be an estimation, of course, but, as can be seen, it can be quite accurate ($n=21$ is the value Lulu computed.)

In general, if $p>0.5$ you'll need approximately:

$$2n-1\geq \left(\frac{1.28\sqrt{p(1-p)}}{p-0.5}\right)^2=1.64\frac{p(1-p)}{(p-0.5)^2}$$

games to get a 90% confidence that you'll win the majority of games.

For 95% confidence that you'll win, you'd need the $z^*=1.654$ for a 90% confidence interval, and replace $1.64$ above with $1.654^2\approx 2.71$.

Answer 3

You can find your answer here Binomial distribution

In probability theory and statistics, the binomial distribution with parameters n and p is the discrete probability distribution of the number of successes in a sequence of n independent yes/no experiments, each of which yields success with probability p.

Probability mass function is$$f(k;n,p)={n\choose k}p^k(1-p)^{n-k}$$ it's a function that gives the probability of getting exactly k successes in n trials.

To use this formula to answer your question we put: $$p={r_b \over r_a+r_b}$$ $${_{the\,word\,success\,is\,unfortuate,\,lets\,call\,it\,event\,instead}\choose _{and\,the\,event\,we\,count\,will\,be\,"player\,a\,lost"}} $$ $$k=\left \lfloor {n \over 2} \right \rfloor$$

and we will be looking for probability that event "player a lose" happned less then half of matches:$$x=\sum_{i=0}^{k}f(i;n,p)=\sum_{i=0}^{k}{n\choose i}p^i(1-p)^{n-i}$$

and since Python:

def pascal_row_gen():
    row = [1]
    while True:
        yield row
        row = map(lambda x,y:x+y,row+[0],[0]+row)

def geo_gen(a,r,n=0):
    y = [a]
    c = 0
    while not n or c<n:
        yield y
        y.append(r*y[-1])
        c+=1

a,b,pas=geo_gen(1,p),geo_gen(1,1-p),pascal_row_gen()

n=0
while True:
    win_prob = sum(half(map(ple,next(pas),next(a),reversed(next(b)))))
    print "%3i games:porbability of win: %d" % (n,win_prob)
    if(win_prob>=0.9):break