Re: Pain in the ass


nnthayer@xxxxxxxxxxx wrote:
> Some guy posted the following problem at work:
> "Given n positive real numbers, r_1, r_2, ... r_n, that sum to an
> integer, what is the probability that [(sum from 1 to n) r_i] = [(sum
> from 1 to n) r_i, each rounded to the nearest integer]?"

If you're using brackets [ ] for the floor function (smallest integer),
then you can get rid of them since the sum of r_i and the sum of (r_i
rounded off) are both integers.

> I must say that I'm making headway, but I have no idea how to phrase it
> to people when I post a start on a solution.

One thing you definitely should say is the distribution for the r_i's.
I suspect you're choosing r_1, ..., r_{n-1} uniformly on the interval
[0,1) and letting
r_n be n-1 - sum(r_i). (Clearly, it doesn't matter what the integer
part of r_i is; the n-1 is chosen to make r_n nonnegative.)

The distribution (how the r_i's are chosen) is important: If the
distribution is uniform on [0,1/n), then the probability the equation
is true is 1.

For notation, you may want to let s_i be "the integer closest to r_i."
If the probability of choosing a 1/2 for an r_i is zero (like it is in
the uniform distribution), then you don't have to say how you handle
rounding 1/2. (The probability of the fractional part of r_n being 1/2
is zero, as well.)

> My solution involves some
> pretty easy (n-1)-dimensional integrals (integrating 1 over shapes
> analogous to right triangles and pyramids), and then calculating harder
> (n-1)-dimensional integrals (crazier shapes) by adding and subtracting
> the easy ones. I am quite far from a general solution, mind you; I've
> just worked n from 1 to 6.
>
> N = 4 is the last easily-explained case, as it involves visualizing
> 3-space. One can take a cube of unit volume, slice it up using 7 [2 *
> (n-1) + 1] planes, and then find the total volume of some choice
> sections.
>
> With n = 5, it's easy enough to say "4-cube," but I have no idea how to
> cope with the word "volume" in 4-space, nor do I know how to explain
> that yes, I'm dividing up 4-space using 9 3-spaces.

Your integrals for n = 5 will be similar to the ones for n = 4; you'll
just have an extra integral sign.

> For the record, here are my results, which might very well be wrong:
> n Probability
> 1 1 (trivial)
> 2 1 (also trivial)
> 3 3/4 [ = 6 / 8 = 0.75]
> 4 2/3 [ = 32 / 48 = 0.6666...]
> 5 115/192 [ = 230 / 384 = 0.5989...]
> 6 19/30 [ = 2432 / 3840 = 0.6333...]
> To put each beast in its native habitat, the proper denominator would
> be (n-1)! * (2^(n-1)).

It would be nice to see your work. Your answer for n = 5 looks
suspicious, though. (The probability seems like it should be monotonic
as a function of n.)

--- Christopher Heckman

.