Question

Suppose two teams, A and B, are playing a match to see who is the first to win games (for some particular n). We can suppose that A and B are equally competent, so each has a 50% chance of winning any particular game. Suppose they have already played i+j games, of which A has won i and B has won j. Give an efficient algorithm to compute the probability that A will go on to win the match. For example, if i=n-1 and j=n-3 then the probability that A will win the match is $\frac{\mathbf{7}}{\mathbf{8}}$, since it must win any of the next three games.

Short answer

To solve the given problem, use dynamic programming approach.$\frac{7}{8,}\mathrm{i}=\mathrm{n}-1\mathrm{and}\mathrm{j}=\mathrm{n}-3,\mathrm{i}+\mathrm{j}$

Step-by-step solution

Dynamic programming approach.

In dynamic programming there are all possibilities and more time as compared to greedy programming. and the Dynamic programming approach always gives the accurate or correct answer. In dynamic programming have to compute only distinct function call because as soon as compute and store in one data structure so that after this reuse afterward if it is needed.

Defining Recursive Relation and Implementation of Algorithm.

Let us suppose P (i,j ) is the probability for A to win the first n games.

Given that, i = Number of match A has won

And j=Number of match B has won

So, there are two conditions they are,

If P (i,j )=1 where i > 0 and j=1 this mean the probability of A to win is ‘one’.

If P (i,j )=0 where i > 0 and j=1 , this means the probability of A for won is ‘zero’.

Now for rest of the value of 'i' and 'j' then the value of evaluations is,

$\mathrm{p}\left(\mathrm{i},\mathrm{j}\right)=\frac{1}{2}\left(\mathrm{P}\left(\mathrm{i},\mathrm{j}+1\right)+\mathrm{P}\left(\mathrm{i}+1\right)\right)$

After that let P (0,j ) is as zero or one then compare each situation.

$$\begin{gathered} \mathrm{P}\left(0,\mathrm{i}\right)=1\mathrm{and} \\ \mathrm{P}\left(\mathrm{i},1\right)=0 \\ \mathrm{if}\left(\left(\mathrm{n}-\mathrm{j}\right)>0\mathrm{and}\left(\mathrm{n}-\mathrm{i}\right)=0\right) \\ \mathrm{P}\left(\mathrm{n}-\mathrm{i},\mathrm{j}-\mathrm{i}\right)=1 \\ \mathrm{if}\left(\left(\mathrm{n}-\mathrm{j}\right)=0\mathrm{and}\left(\mathrm{n}-\mathrm{i}\right)>1\right) \end{gathered}$$

Here, A will go on to win the match. For example, if i=n-1 and j=n-3 then the probability that A will win the match is $\frac{7}{8}$, since it must win any of the next three games.

$$\begin{gathered} \mathrm{if}\left(\left(\mathrm{n}-\mathrm{i}\right)>1\mathrm{and}\left(\mathrm{n}-\mathrm{j}\right)>1\right) \\ \mathrm{P}\left(\mathrm{n}-\mathrm{i},\mathrm{j}-\mathrm{i}\right)=\frac{1}{2}\left(\mathrm{P}\left(\mathrm{i}-1,\mathrm{j}\right)+\mathrm{P}\left(\mathrm{i},\mathrm{j}-2\right)\right) \\ \mathrm{return}\mathrm{P}\left(\mathrm{n}-\mathrm{i},\mathrm{j}-\mathrm{i}\right) \end{gathered}$$

By approach of dynamic programming for playing a match to see who is the first to win number of games where equally competent and each has fifty percent chance of winning any particular game and the probability that A will go for to win the match an A will go on to win the match. ifi=n-1 and j=n-3 then the probability that A will win and it will take time of O(n) Since, we are playing ‘n’ times, so our algorithm will trace output of n output. Thus, runtime would be O(n)