# Mathematics behind a programming puzzle

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?

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

-
Geometrically, the case of $N=3$ is the same as computing the volume of the part of a cube when it is cut by a plane. This generalizes to $n$ dimensions. If you start imagining the number of ways you can cut a cube by a plane, you start to see why it is hard to figure out a general solution. – Thomas Andrews Jul 16 '12 at 18:54
spelling: en.wikipedia.org/wiki/Slartibartfast – Will Jagy Jul 16 '12 at 19:36
^ Ha! Thanks! I always thought it didnt have a t there – Slartibartfast Jul 17 '12 at 5:19
You can edit your user name. – Will Jagy Jul 17 '12 at 19:32
Heh! Once every 30 days,changed it 15 days back, another 15 days to go – Slartibartfast Jul 18 '12 at 7:11

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.
The $c_i$ are not necessarily all the same, so you can't borrow known results about the Irwin-Hall distribution. – Michael Lugo Jul 16 '12 at 20:44