Wikipedia:Reference desk/Archives/Mathematics/2007 August 7

From Wikipedia, the free encyclopedia

Mathematics desk
< August 6 << Jul | August | Sep >> August 8 >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


Contents

[edit] August 7

[edit] Integral help

I have been working over this (seemingly simple) integral for several hours, and keep getting zero, which I am fairly confident is wrong (more on why below). Anyone want to take a crack at spotting my error? I am fairly stumped.

I am trying to find

\frac{d}{dc}\left(\int_0^{\frac{c-b}{a}}\int_0^1f(x)g(y)dxdy+ \int_{\frac{c-b}{a}}^1\int_0^{\frac{c-ax}{b}}f(x)g(y)dydx\right)

which is supposed to be the derivative (wrt c) of the volume under f(x)g(y) over the region bounded by y=0, y=1, x=0, x=1, and the line ax+by=c, where c>b, c>a, and c<a+b. I have done this several ways, and keep getting zero. One method is shown below.

\frac{d}{dc}\left(\int_0^{\frac{c-b}{a}}\int_0^1f(x)g(y)dxdy+ \int_{\frac{c-b}{a}}^1\int_0^{\frac{c-ax}{b}}f(x)g(y)dydx\right)
=\frac{1}{a}f\left(\frac{c-b}{a}\right)\int_0^1dy - \frac{d}{dc}\int_1^{\frac{c-b}{a}}\int_0^{\frac{c-ax}{b}}f(x)g(y)dydx
\frac{1}{a}f\left(\frac{c-b}{a}\right)\int_0^1g(y)dy - \frac{1}{a}f\left(\frac{c-b}{a}\right)\int_0^1g(y)dy
= 0

The problem stems from trying to find the probability density aX+bY where X is a random variable on [0,1] with probability density f(x) and Y (independent of X) is a RV with density f(y) on [0,1]. Thus I am fairly confident that the solution should not be zero. Am I overlooking some basic fact of multivariate calculus (it has been five or so years since I took the class). I can clarify the problem or steps I used to solve it if need be. Any help would be appreciated. Thanks, --TeaDrinker 03:25, 7 August 2007 (UTC)

I'm not sure what rule you are using in absorbing your d/dcs into the definite integrals. You can use
\int_0^{\frac{c-b}{a}}\int_0^1f(x)g(y)dydx+ \int_{\frac{c-b}{a}}^1\int_0^{\frac{c-ax}{b}}f(x)g(y)dydx = \int_0^1 f(x)\int_0^1g(y)dydx-\int_{\frac{c-b}{a}}^1 f(x)\int_{\frac{c-ax}{b}}^1g(y)dydx
to simplify this a bit. (Added later: I also think you swapped dx and dy in the first integral.) If I did not make any mistakes, the derivative w.r.t. c equals
\frac{1}{b}\int_{\frac{c-b}{a}}^1 f(x)g\left(\frac{c-ax}{b}\right)dx\,.
The basic rule I used is that
\frac{d}{dz}\int_{u(z)}^{v(z)}f(x,z)dx = v'(z)f(v(z),z)-u'(z)f(u(z),z)+ \int_{u(z)}^{v(z)}\frac{d}{dz}f(x,z)dx\,.
 --Lambiam 05:23, 7 August 2007 (UTC)
Many thanks. I think I see my mistake, and your method seems much better. Best, --TeaDrinker 22:36, 7 August 2007 (UTC)

[edit] dice odds question

(A Fudge die is a 6-sided die with two faces marked "0", two faces marked "+1", and two faces marked "-1". So if you roll four Fudge dice and get the result +1 -1 0 -1, then the total result would be -1.)

If two people roll 4 Fudge dice each, and then compare to see who got the highest result, then obviously the odds of person A winnig the bet versus person B would be 50% and 50%.

But what if one player was given the advantage of adding +1 to their rolled score? What would the new odds be? Would it be 80% and 20% or something like that? What if that person was given an advantage of +2 to their rolled score? What about +3?

I am looking for these three answers. I am also looking for the same three answers, but assuming each side only rolls three Fudge dice instead of the four in the previous questions.

MUCH THANKS!--Sonjaaa 11:57, 7 August 2007 (UTC)

First of all, you're missing ties. Second of all, to figure out the probabilities of ties, at each level, you need to multiply the probabilities of getting each die roll by the the probability of getting the die roll that would tie it, if that makes sense. Best way to start would be to work out the chance of getting each possibility on the dice. Gscshoyru 12:47, 7 August 2007 (UTC)
Well first step is let's find the distribution of scores for four dice. You can treat the dice as three-sided for this purpose. You have a total of nine possible outcomes, ranging from -4 to +4. There are various ways of enumerating these, my preference is to first find the outcomes for two dice. There are nine possible rolls:
-1 0 +1
-1 -2 -1 0
0 -1 0 +1
+1 0 +1 +2
so we get probabilities of 1/9 for -2, 2/9 for -1, 1/3 for 0 etc. Now you can make a 5x5 table to get the possibilities for rolling four dice, using -2 to +2 as the column and row headers. The cells have differing values, though now, so you'll multiply the probabilities to get the value of each cell, then add up those numbers for each cell to get the probability of each value. (not really caring to spend oodles of time on wikitables, I'll skip typing them out).
Now we repeat the process to make a 9x9 table for the roll-off between the two players. You can shade the cells according to A wins, B wins or tie (doing different shading for the "fair" version and for the bonus scores. I would fill in the this table with the probabilities rather than the exact values since here you just want to be able to add up the probabilities in each of the three categories. Donald Hosek 16:51, 7 August 2007 (UTC)
This question got me to finally try out Graphviz. :-) Below is a tree describing the process of throwing four Fudge dice and computing their sum. The uppermost row is the starting position (zero dice thrown), the next row contains the possible states after one die has been thrown and so on down to four dice thrown at the bottom row. Each node contains the sum so far (above) and the probability of getting to that node (below). Each node passes its probability forward in three equal parts along the arrows emanating at that node. Each node gets its probability as the sum of the probabilities coming through the arrows pointing at that node.
The last row thus describes the possible outcomes for one of the players (player A, say). For player B, which has a bonus point, the situation is similar, only shifted one step, so to speak. In summary, these are the probabilities for the possible sums for each player alone:
-4 -3 -2 -1 0 1 2 3 4 5
player A 1/81 4/81 10/81 16/81 19/81 16/81 10/81 4/81 1/81
player B 1/81 4/81 10/81 16/81 19/81 16/81 10/81 4/81 1/81
The probability of a certain combination, e.g., that player A gets − 1 and player B gets 3, is the product of the individual probabilities, (16/81)\times (10/81)=160/6561. To find the probability of victory for B, you list all combinations that gives B victory (A gets − 4 and B gets − 3, A gets − 4 and B gets − 2 etc.) along with their probabilities and add them together. I'm leaving that to you or someone else, because after all this, I'm exhausted. Who knew maths could carry with it so many numbers? I want my letters back! —Bromskloss 19:47, 7 August 2007 (UTC)
Actually the problem could be solved by building upon the formula given in Dice#Probability. However, I had a feeling that the questioner would appreciate avoiding technicalities, but perhaps I misunderestimated her. —Bromskloss 20:02, 7 August 2007 (UTC)
If you're content with approximate values (rounded to one percent), here are the odds for the advantage d increasing from 0 to 8:
   d → 0    1    2    3    4    5    6    7   8   
A wins 42% 58% 74% 86% 94% 98% 99% 100% 100%
B wins 42% 26% 14% 6% 2% 1% 0% 0% 0%
tie 17% 15% 12% 8% 4% 2% 1% 0% 0%
 --Lambiam 21:41, 7 August 2007 (UTC)

WOW, thanks! That last table was exactly what I needed, however only from +1 to +3 advantage. I am also looking for the same three answers, but assuming each side only rolls three Fudge dice instead of the four in the previous questions. How would that change the odds?--Sonjaaa 01:50, 8 August 2007 (UTC)

I get this for three rolls:
   d → 0    1    2    3    4    5    6   
A wins 40% 60% 77% 89% 96% 99% 100%
B wins 40% 23% 11% 4% 1% 0% 0%
tie 19% 17% 12% 7% 3% 1% 0%
 --Lambiam 02:43, 8 August 2007 (UTC)
Good work, Lambiam. —Bromskloss 07:23, 8 August 2007 (UTC)

[edit] max sum problem

Dear Wikipedians:

Say I have a 20 by 20 matrix of natural numbers. I would like to pick 20 numbers from the matrix such that when added together they produce the maximum sum.

If there were no constraint, then I would simply sort the 400 numbers from the biggest to the smallest and pick the top 20.

If the constraint that the column indices of the 20 numbers have to be all distinct, then I could simply add the biggest number from each row together to get the biggest sum.

Now, if both the column indices and the row indices have to be distinct, is there a more efficient algorithm (preferably of polynomial time) than the exponential time brute-force algorithm that tries all permutations of the row indices?

I remember seeing the problem in a programming contest couple years ago, but I wasn't able to find the same problem on google anymore.

Thanks.

129.97.225.195 23:42, 7 August 2007 (UTC)

This is a linear assignment problem. In the common formulation the sum is to be minimized, but by taking the difference of each entry with the overall max entry, or the max in each column (or each row), you swap minimization and maximization. The Hungarian algorithm is a reasonably simple fast algorithm for solving this.  --Lambiam 00:02, 8 August 2007 (UTC)