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
    Any clue? $ $ $ $2012-05-29
  • 0
    @did I am also totally clueless :(2012-05-29
  • 0
    Never done any other exercise looking like this one, even remotely? Then how can people here help you?2012-05-29
  • 0
    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.2012-05-29
  • 0
    a) Could it be that the idea is to approximate the actual distribution by a normal distribution? b) I think you'll have to explain some more of the rules. I get an expected value of $23/8$ runs per ball; with $120$ balls in $20$ overs, that seems incompatible with the answer for a. Is there some extra rule, e.g. that an over ends after a wicket?2012-05-29
  • 0
    @Wonder Yes, it's a form of programming assignment. Can you please elaborate how we can write the function as I am unable to think the logic..!!!2012-05-29
  • 0
    @joriki No, there is no extra rules. Only following rules: 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.2012-05-29
  • 0
    Perhaps you are expected to run a large number of *simulations* to estimate the probabilities.2012-05-29
  • 0
    I agree with AndréNicolas. I doubt this is easily solvable without random number simulation. Also, @joriki's method of calculating expectation is the way I tried as well but since a wide or no-ball causes an extra delivery, the number of overs is not 20 but can go higher as well.2012-05-29
  • 1
    @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.)2012-05-29
  • 0
    @Nunoxic: I took the wide and no-ball into account by making their payoff $1$ plus the expected payoff; that allows the number of overs to be fixed at $20$ (except for the wicket rule that's now been introduced in the comments).2012-05-29
  • 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
    Thanks for your answer but it's too slow to run!! Can you optimize it ??2012-05-30
  • 0
    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.2012-05-30
  • 0
    Suppose r = 300 (as in case a.) ,b = 120 (20 overs), w = 10 then it will require 360000 multiplications and 90 * 300 * 120 additions !!!2012-05-30
  • 0
    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.2012-05-30
  • 0
    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.2012-05-30
  • 0
    Sorry for the trouble again but sir, it's still very slow!!!2012-05-30