# Help with a textbook probability problem

I recently came across a probability problem of my textbook which I am unable to solve. Here is the problem:

Russel is playing a 20 overs cricket match. Each team can bat either till the end of 20 overs or until they lose 10 wickets. 6 balls are bowled every over. The possible things that can happen in any ball are dot-ball, 1 run, 2 runs, 3 runs, 4 runs, 5 runs, 6 runs, wide, no-ball, wicket. For any no-ball or a wide, 1 run is granted and the ball is not counted. Assume that these things can happen with equal probability. Each team can bat either till the end of 20 overs or until they lose 10 wickets. 6 balls are bowled every over.

The opposing team set a target of

a. 300 runs
b. 200 runs
c. 100 runs

Find the winning probability (as a percentage) of the chasing team.

Answer:
a. 18.02
b. 61.65
c. 97.60

Any help would be welcomed.

#include <stdio.h>
double P(int r, int b, int w) {
double final;
if (r >= 0 && (b <= 0 || w <= 0))
return 0;
else if (r <= 0 && (b >= 0 || w >= 0) )
return 1;
else {
final = 0.1 * P(r,b-1,w) + 0.1 * P(r-1,b-1,w) + 0.1 * P(r-2,b-1,w) + 0.1 * P(r-3,b-1,w) + 0.1 * P(r-4,b-1,w) + 0.1 * P(r-5,b-1,w) + 0.1 * P(r-6,b-1,w) + 0.1 * P(r-1,b,w) + 0.1 * P(r-1,b,w) + 0.1 * P(r,b-1,w-1);
return final;
}
}

int main()
{
double t;
t = P(300, 120, 10);
printf ("%lf\n", t);
return 0;
}


I ran this code but it is taking hell of a time

-
Any clue?   – Did May 29 '12 at 7:20
@did I am also totally clueless :( – Snehasish May 29 '12 at 7:27
Never done any other exercise looking like this one, even remotely? Then how can people here help you? – Did May 29 '12 at 7:30
Is this something where you have to do the exact computations manually, or is it some sort of programming assignment? It is not that hard to write a recursive function P(r,b) which will give probability of winning with target r in b balls. But it would be hard to think of a closed form for it. – Wonder May 29 '12 at 9:24
@Snehasish: You state that there are no extra rules, but then you state the extra rule that the batting stops after $10$ wickets; I don't see how anyone not familiar with cricket could have inferred that from the question. In the future, please make sure that your questions are self-contained and explain any non-mathematical aspects that they rely on. Also, please edit this information into the present question so that people don't have to dig into the comments to understand it. (This also applies to the fact that this is a programming assignment, which is an important aspect of the question.) – joriki May 29 '12 at 11:33

## 1 Answer

As you said, this is a programming assignment. Let P(r,b,w) be the probability of chasing r runs in b balls with w wickets in hand, Note that P(r,b,w) = 0 for all non negative r if either b or w (or both) is non-positive. P(r,b,w) = 1 whenever r is negative and w is positive.Now, assuming that the 10 situations you have given are all equally likely, P(r,b,w) = 0.1 * P(r,b-1,w) + 0.1 * P(r-1,b-1,w) + 0.1 * P(r-2,b-1,w) + 0.1 * P(r-3,b-1,w) + 0.1 * P(r-4,b-1,w) + 0.1 * P(r-5,b-1,w) + 0.1 * P(r-6,b-1,w) + 0.1 * P(r-1,b,w) + 0.1 * P(r-1,b,w) + 0.1 * P(r,b-1,w-1). So this is a standard dynamic programming problem. Make a rXbX10 (10 wickets at start) matrix, populate its boundary conditions, then gradually fill in its interior using this relation along increasing values of r+b+w. Eventually you will fill in the value for P(r,b,10) which is what you want.

If the 10 situations you are given are not equally likely, you can modify the recurrence accordingly.

-
Thanks for your answer but it's too slow to run!! Can you optimize it ?? – Snehasish May 30 '12 at 6:30
Are you sure it's slow? It takes only 10rb space and O(rb) computations, the bulk of the process being just 100rb multiplications and 90rb additions. – Wonder May 30 '12 at 6:35
Suppose r = 300 (as in case a.) ,b = 120 (20 overs), w = 10 then it will require 360000 multiplications and 90 * 300 * 120 additions !!! – Snehasish May 30 '12 at 6:42
Yes, and on a decent computer that's no more than a few seconds. If you want something that a human being can work out then sorry it doesn't look like that sort of solution exists. – Wonder May 30 '12 at 6:49
You could rewrite it as P(r,b,w) = 0.1 * [P(r,b-1,w) + P(r-1,b-1,w) + P(r-2,b-1,w) + P(r-3,b-1,w) + P(r-4,b-1,w) + P(r-5,b-1,w) + P(r-6,b-1,w) + P(r-1,b,w) + P(r-1,b,w) + P(r,b-1,w-1)] if you want to optimize. It will cut multiplications 10 times. I am not sure that is required though. – Wonder May 30 '12 at 6:56