0
$\begingroup$

The game is as follows:

  • Two players A and B play consecutive rounds, and the winner of each round obtains one point.
  • Each round is independent of the others, and player A has probability $p$ of winning, player B has probability $1-p$.
  • The game ends when one of the players obtain N points.

If $n_A$ is the number of points obtained by player A, what is the value of the probability $P(n_A=i) ~,~i=0,1,...,N$? i.e. what is the probability mass function of $n_A$?


Background:

I'm currently learning probability on my own, using the textbook A First Course in Probability - Sheldon Ross, 8th edition". When doing the self-test exercise 4.11, I had the idea of generalizing the problem to the one I posted here.


Similar, but different question:

$\endgroup$
1
$\begingroup$

You just need to separate the winning state where the points will be N from the other states.

Define $f(N,k,a) = \binom {N+k-1}{k}a^k$ as an auxiliary function to simplify the following.

We can write the points distribution for player $A$ $$ n_A(k) = \left\{ \begin{array}{ll} q^Nf(N,k,p) & k={0 \dots (N-1)} \\ p^N \sum_{k=0}^{N-1} f(N,k,q) & k=N \end{array} \right. $$

simply swap $p$ and $q$ for player $B$.

$\endgroup$
  • $\begingroup$ Hey, Karafka. Thank you for your time. Am I right in assuming that $q=1-p$ and $n_A(k)$ in your notation means $P(n_A=k)$ in mine? $\endgroup$ – JLagana Jan 3 '18 at 22:28
  • $\begingroup$ Also, could you elaborate on why does the $f$ function use a combination from $N+k-1$ terms? I was expecting $N+k$ terms instead. $\endgroup$ – JLagana Jan 3 '18 at 22:30
  • $\begingroup$ Yes, $q=1-p$ and $n(k)$ is the probability. $-1$ comes since the last round is won by the overall winner. Try for $p=q=\frac12$ and $N=3$. $\endgroup$ – karakfa Jan 4 '18 at 0:20
  • $\begingroup$ Aha, and since $k < N$, the winner must be player B! Brilliant. I'm still digesting the rest of the answer, thanks for now :) $\endgroup$ – JLagana Jan 4 '18 at 0:24
  • $\begingroup$ I understand your answer now, and it does seem correct. I upvoted you, but I feel like the community would benefit from a more pedagogic explanation. I answered my own question, inspired by your answer. $\endgroup$ – JLagana Jan 4 '18 at 17:17
0
$\begingroup$

First, Let's calculate $P(n_{A}=i,n_{b}=k)$. According to binomial distribution we have $P(n_{A}=i,n_{b}=k)=C(i+k,i)p^{i}(1-p)^{k}$ then the requested probability equals $P(n_{A}=i)=\Sigma_{k=0}^{N-1}C(i+k,i)p^{i}(1-p)^{k}$

$\endgroup$
  • $\begingroup$ what is $r$? Not defined. If you meant $i$, I don't think it's right. The game may take $2N-1$ rounds to finish. $\endgroup$ – karakfa Jan 3 '18 at 21:01
  • $\begingroup$ Sorry :)....I edited it right now! $\endgroup$ – Mostafa Ayaz Jan 3 '18 at 21:08
0
$\begingroup$

Disclaimer: Karakfa's answer originally helped me solve this problem. Although he provided the correct solution, I believe it can be helpful for other users to have a more detailed, pedagogic solution to this question. What follows is my attempt on doing so.


The key to solving this question is to separate the cases when player A loses and when player A wins. These correspond to when $n_a<N$ and $n_a=N$. Let's start with the first one.

In this case, we note that since $n_a<N$, then player A lost the game and consequently player B won. This means that $n_B=N$ (where $n_B$ denotes the points accumulated by player B in a given game), and hence $k+N$ rounds were played. Additionally, we also know that the winner of the last round was player B, since in this game the winner necessarily has to win the last round (otherwise the game would either not end at that round, or the winner already had $N$ points before that round, which means that the game would have already ended).

Now, we note that the problem of counting in how many different ways player A wins $k$ times, and player B wins $N$ times, including the last one, is equivalent to counting in how many ways we can select $k$ games, among $N+k-1$ (-1 since the last round was necessarily won by player B) to be won by player A. Putting it this way, it's clear that this is trivially ${N+k-1}\choose{k}$. For example, in the case where $k=2$ and $N=3$, there are 6 such sequences: $(AABBB), (ABABB),(ABBAB),(BAABB),(BABAB),(BBAAB)$ (here, each letter in the sequence denotes who won that particular round).

Now, back to the general case, we can see that all of the ${N+k-1}\choose{k}$ possible sequences of wins have probability $p^k(1-p)^N$ of happening, since each round is independent of the others. Finally, the sequences are mutually exclusive for one realization of the game, so we can obtain the desired probability by summing these individual, equal probabilities. This leads to:

$$ P(n_a=k) = \binom{N+k-1}{k} p^k(1-p)^N \quad,\quad\text{if}~k<N.$$

Now, for the case where player A wins, i.e. when $k=N$, then we know that $n_b<N$. This time, we have to consider all the sequences where player A won $N$ times and player B won $0,1,2,...,N-1$ times.

For a given $n_b=j,j<N$, there are $\binom{N+j-1}{j}$ possible sequences where player A wins the last round (similar argument as before). All of them are mutually exclusive and have the same probability: $(1-p)^jp^N$. Therefore, $P(N_b=j)=\binom{N+j-1}{j}(1-p)^j p^N,j<N$. To find $P(n_a=N)$, we simply have to sum the probabilities of the mutually exclusive events $n_b=j$, for $j=0,1,2,...N-1$.

$$P(n_a=N)=\sum_{j=0}^NP(n_b=j)$$ $$ = \sum_{j=0}^N\binom{N+j-1}{j}(1-p)^jp^N$$ $$ = p^N\sum_{j=0}^N\binom{N+j-1}{j}(1-p)^j$$

Finally, putting both results together yields Karakfa's answer:

$$ P(n_a=k) = \left\{\begin{matrix} \binom{N+k-1}{k}p^k(1-p)^N & \text{if }k<N\\ \\ p^N\sum_{j=0}^N\binom{N+j-1}{j}(1-p)^j & \text{if }k=N \end{matrix}\right. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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