2
$\begingroup$

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   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

  • 0
    @joriki Sorry for the trouble. The post has been edited. Can you please tell your method of solving?2012-05-30

1 Answers 1

2

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.

  • 0
    Sorry for the trouble again but sir, it's still very slow!!!2012-05-30