2
$\begingroup$

This question was asked as a programming puzzle recently, but I want to know the math behind how to solve it.

The kingdom of Byteland contains $N$ cities numbered $1$ through $N$. For each city $i$, the king assigns some money to that city for its annual maintenance. The amount assigned is chosen randomly between $a_i$ (the minimum amount needed by that city), and $b_i$ (the maximum amount that can be assigned to that city). Note that the amount assigned to a city need not be an integer. The total tax collected this year is $C$.

What is the probability that the kingdom will issue a loss this year? In other words, what is the probability that the total amount assigned to all cities exceeds the total tax collected?

And a sample answer was

$N = 1, ~C = 3, ~a_1 = 1, ~b_1 = 10, ~\text{Answer} = 0.77778.$

And where can I find good references for studying some advanced topics of probability theory. I am quite aware of the basics but while applying to problems like above I get lost.

  • 0
    Heh! Once every 30 days,changed it 15 days back, another 15 days to go2012-07-18

1 Answers 1

3

The exact distribution of a sum of $N$ independent uniformly distributed random variables is quite messy. To get an idea of how messy, you might want to look at the wikipedia article on the Irwin-Hall distribution. There the random variables are uniformly distributed on the same interval $[0,1]$. Already at $N=4$ or $5$, the density function, and therefore the cumulative distribution function, has a complicated "cases" expression involving unpleasant polynomials.

You can reduce the problem a little, by letting $A=\sum a_i$, and $c_i=b_i-a_i$. then our problem becomes the problem of determining the probability that a sum of independent random variables uniformly distributed on $[0,c_i]$ is $\le C-A$. Then we can use the same methods as in the derivation of the pdf for the Irwin-Hall distribution.

For $N=1$ the problem is easy. If $a_1 \le C \le b_1$, then the probability the budget will not be exceeded is $\frac{C-a_1}{b_1-a_1}$. For $N=2$, one could get a pleasant enough answer. Already $N=3$ is somewhat complicated.

Higher dimensional problems are most conveniently handled by simulation. If $N$ is fairly large, and the $b_i-a_i$ are not too wildly different, a normal approximation might give useful estimates. The mean and variance of the sum are easy to compute.

  • 0
    Thanks! Let me try to understand what you mean and look at Irwin Hall and I ll get back to mark the answer2012-07-17