Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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
    
Thanks! Let me try to understand what you mean and look at Irwin Hall and I ll get back to mark the answer –  Slartibartfast Jul 17 '12 at 6:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.