Wikipedia:Reference desk/Archives/Mathematics/2006 September 25

< September 24	Mathematics desk archive	September 26 >

Humanities

Science

Mathematics

Computing/IT

Language

Miscellaneous

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 at one of the pages linked to above.

< August	September	October >

Dice-sum probability formula

It's September 24th here on the East Coast, but anyway: suppose I roll n s-sided dice. What is the theoretical probability of getting each possible sum, irrespective of the individual die values that make up that sum? I know a little bit of combinatorics and probability, but not quite enough to figure this one out on my own. Google has failed to enlighten me, so I turn to your collective wisdom for help. —Saric (Talk) 01:20, 25 September 2006 (UTC)[reply]

I think there is no truly simple formula for that. For one die the graph of the probabilities as a function of the sum is a horizontal line: a segment from a polynomial of order 0. For two dice you get a roof shape: two segments of polynomials of order 1. I guess that continues, like N segments of polynomials of order N−1 glued together. It should be possible to find a general formula for the i-th polynomial. I haven't given the issue much thought, though. --Lambiam ^Talk 02:32, 25 September 2006 (UTC)[reply]

Lambiam is right. Here are several additional suggestions:

First, we will denote by f (n, s, k) the number of possibilities (from which the probability is easily calculated) of receiving a sum of k when throwing n s-sided dice.
For sufficiently large n, You can approximate the function with the normal distribution as:

f(n,s,k)\approx s^{n}\exp {\left({\frac {3(n(s+1)-2k)^{2}}{2n(1-s^{2})}}\right)}{\sqrt {\frac {6}{\pi n(s^{2}-1)}}}

You can define f recursively: f (1, s, k) is 1 if k is an integer between 1 and s, and 0 otherwise; And

f(n+1,s,k)=\sum _{i=1}^{s}f(n,s,k-i)

If I'm not mistaken, the piecewise polynomials from which the function is made are stitched at points of the form $s(1+j)+n/2\,\!$ , where 0 ≤ j ≤ n-2. You can use this and the above formula to find, for every n, the polynomials that make up the nth function (though you shouldn't hope for a closed form for the nth polynomials).

I hope this helps. -- Meni Rosenfeld (talk) 07:42, 25 September 2006 (UTC)[reply]

Ah, yes, thank you both. I implemented that function in Perl and it seems to work nicely:

sub funkshun
 {my ($n, $s, $k) = @_;
  my ($i, $sum);
  if ($n == 1)
     {if ($k >= 1 and $k <= $s)
         {return 1;}
      return 0;}
  foreach $i (1 .. $s)
     {$sum += funkshun(($n - 1), $s, ($k - $i));}
  return $sum;}

All you do is divide the result by s to the nth power, and there's your probability. There is, however, one problem: it's really slow. f(5, 20, 55), for example, takes a couple of seconds. Maybe it's just my 300-megahertz processor, but I think the recursion makes this a relatively inefficient algorithm.

Now, here's the interesting part: some searching brought me to this site. The instructions page attempts the explain the math, but the explanation eluded me, which is why I came here to the reference desk for an algorithm I could understand (and thus implement myself). However, rereading it afterwards, I realized that the words "(k = 0) to the next lowest integer of…", which had puzzled me before, were implying the use of summation, like you, Meni Rosenfield, had used in your formula. That was enough for me to figure out the rest and code it thus:

sub funkshun
 {my ($n, $s, $k) = @_;
  my ($i, $sum);
  foreach $i ( 0 .. int(($k-$n)/$s) )
     {$sum += ( ((-1)**$i) * comb($n, $i) *
                comb($k-1-($s*$i),$n-1) );}
  return $sum;}

("Comb" is the combination function; "**" is the Perl exponentiation operator.) Looks crazy, doesn't it? It does to me, at least— but it works, and a lot faster than the other way, too. Who woulda thunk? —Saric (Talk) 00:11, 26 September 2006 (UTC)[reply]

I see. Rewriting this in terms I can understand, it's:

f(n,s,k)=\sum _{i=0}^{\left\lfloor {\frac {k-n}{s}}\right\rfloor }(-1)^{i}{n \choose i}{k-1-si \choose n-1}

Which is simpler than I imagined. Nice! -- Meni Rosenfeld (talk) 09:21, 26 September 2006 (UTC)[reply]

By the way, the reason your first implementation was so slow is because each value of f is calculated many times, making the complexity exponential in n. If you are able to store calculated values of f in memory, and add some more fine-tuning, the complexity will only be quadratical (that is, much faster). -- Meni Rosenfeld (talk) 09:32, 26 September 2006 (UTC)[reply]

Density Curve (?)

In my basic Stat class (Algebra Based) the teacher was explaining density curves. She then gave us various examples, including one that had uniform distribution. She described the density curve as being the base times the height, where the density curve would follow the box-shaped outline exactly. However, I don't understand how that could be a "curve" because of the sharp points. The only way I could see a function like that defined is with a piece-wise equation. Help me - just try to keep it within Calc II understanding. ;) --AstoVidatu 02:48, 25 September 2006 (UTC)[reply]

If you define the function as having result 0 for arguments outside the range of the random variable, you're right, technically speaking the shape of the graph of that function is not a curve, since it's not continuous. It does not "climb up" the sides of the box, but it jumps from 0 to this constant positive value. If you pay close attention mathematicians say very sloppy things all the time, like they say "the function f(x)" when they mean "function f" and think that is fine, which is a bit amazing for a field that is supposed to be exact and precise. --Lambiam ^Talk 03:41, 25 September 2006 (UTC)[reply]

If she described the graph of the density function as following the vertical edges of the box, she must have been confused; a piece-wise definition for the density function is indeed what you're looking at here.

Of course, that leaves the question of the points where the function jumps, and which function value to choose there; however, it turns out that it doesn't matter.

Using "curve" to describe this graph might indeed be a bit problematic, but the graph of the absolute value function - despite having a corner, is usually considered a curve.

RandomP 16:32, 25 September 2006 (UTC)[reply]

Parallelepipeds' volume

I know that to get the volume of a parallelepiped, when given three vectors, you use the formula ${\vec {a}}\cdot [{\vec {b}}\times {\vec {c}}]$ , which gives you a 3x3 determinant. However, does it matter, when evaluating the determinant, the order in which I put the rows? My Engineering and my Calculus textbooks put the row outside the parenthesis (e.g. $a_{x}$ , $a_{y}$ , $a_{z}$ ) on the top row of the 3x3 matrix, but I don't know if this is a coincidence, a convention, or if there is some mathematical reason this happens. And the reason I'm asking is because I can't ever remember which row goes where, so it would be quite relaxing to know it doesn't matter... Tito xd^(?!?) 03:04, 25 September 2006 (UTC)[reply]

Changing the order can only cause a sign flip: see Triple product for the relevant identity. If you're looking for a positive quantity, you'll want to take the absolute value anyway, so short answer: no, it doesn't matter. Melchoir 03:26, 25 September 2006 (UTC)[reply]

If, for any reason (such as determining orientation), you wish to preserve the sign of

{\vec {a}}\cdot [{\vec {b}}\times {\vec {c}}]

, then the order does matter, but it's not a biggie - if I'm not mistaken, the order of the rows is exactly the order in which they appear in this expression. -- Meni Rosenfeld (talk) 06:30, 25 September 2006 (UTC)[reply]

Yes, it matters. Since you already know the volume is a determinant, you should also know a basic definition of a determinant:

The determinant of the identity matrix is 1.
The determinant is a linear function of each column.
The determinant is an alternating function of the columns.
(Two equal columns gives a zero result, so swapping two columns negates the result.)

We can show that transposing a matrix does not change its determinant, so the above facts can use rows instead of columns. Either way, these three rules uniquely define the determinant of any n×n matrix.

The cross product is also an alternating function of its arguments, so the sign change is already visible when swapping b and c.

But why should we care about the sign, when the magnitude is the same either way? Because when we are calculating more complicated volumes with this as a portion of a larger sum, we must get the sign right. Consider a complicated polygon in 2D, but one that does not intersect itself. (Technically, it is called a "simple" polygon.) We can compute the area inside the polygon by summing triangles each of which consists of a polygon edge and the origin — but only if we get the signs right. In 3D, using faces to give tetrahedra (sliced parallelepipeds) works similarly. This convenient method can be viewed as a specialization of Stokes' theorem, which itself is just a fancy version of the fundamental theorem of calculus, telling us we can find the integral over the interior of a region from what happens on the boundary.

So resist the urge to forget the order. The investment in good habits today will pay off in easier computations tomorrow. --KSmrq^T 15:58, 25 September 2006 (UTC)[reply]

But of course, "the identity matrix" has no special parallelepiped associated to it: see right-hand rule for one convention on it, though. (To mathematicians, this rarely matters, because we're usually just as happy to see our geometry mirrored. Physicists have that whole "real world" thing to take into account, though.)

KSmrq is right, of course: it's essential to get into the habit of getting things right.

RandomP 16:23, 25 September 2006 (UTC)[reply]

Arc length

I need to find the length of a circular arc (shown). I know the length of the straight line between the two end nodes (BD), and I know the height of the arc (AC), but cannot think of any way to find the length of the curve. Is there a formula I can use in this case? smurrayinchester^{(User), (Talk)} 11:03, 25 September 2006 (UTC)[reply]

Let O be the centre of the arc. OA=OB=r is the radius of the circle. From the OBC triangle: OB²=BC²+OC², or r²=BC²+(r-AC)²; you can find r from this equation. After this, the angle BOC is equal to arcsin(BC/r), and the arc length is 2rarcsin(BC/r). Conscious 11:24, 25 September 2006 (UTC)[reply]

After simplifications, it's

l={\frac {a^{2}+4h^{2}}{4h}}\arcsin {\frac {4ah}{a^{2}+4h^{2}}}

where a=BD and h=AC. Conscious 11:32, 25 September 2006 (UTC)[reply]

Another method: Find the center, and hence the radius, by constructing tangent lines at both ends and constructing perpendicular lines to those. The intersection of those two lines will be the center point. Then measure the angle swept by the arc. You can then apply the simple formula l = piR(theta/360), where theta = the angle swept in degrees. StuRat 11:35, 25 September 2006 (UTC)[reply]

Thanks to both of you; I've gone for Conscious's method as I don't have an accurate sketch of the arc available. The result is also close enough to my very simple approximation

l\approx 2{\sqrt {AC^{2}+CD^{2}}}

. smurrayinchester^{(User), (Talk)} 11:53, 25 September 2006 (UTC)[reply]

My preferred approximation is l ≈ BD :) Conscious 11:57, 25 September 2006 (UTC)[reply]

OK, maybe not that simple... smurrayinchester^{(User), (Talk)} 12:10, 25 September 2006 (UTC)[reply]

Factoring A Polynomial

Yes, yes, I realize this is a math HW prob. But we're kinda stuck. How does one go about factoring this polynomial: y^2-cy-dy+cd=0 ? I don't need answer, just advice on how to solve it. Thanks in advance. John 17:00, 25 September 2006 (UTC)[reply]

Just try to look what you can factor out from the first two terms, and from the two last ones. Conscious 17:04, 25 September 2006 (UTC)[reply]

Yes, I see that now. John 17:23, 25 September 2006 (UTC)[reply]

Using the angle (in radians) and length to get coordinates

Hi, if I have a line, starting at the origin (0,0), 10 units long, at a certain angle in radians, how can I work out what the coordinates of the end of the line is?

Any help would be much appreciated!

--Mary

[note: this isn't for homework: I'm writing a program where circles move around on a screen, and I want to include a line in the circle that shows a current direction.]

Take a look at our article on the trigonometric functions. Conscious 17:54, 25 September 2006 (UTC)[reply]

Better still, look at the circle article. --KSmrq^T 18:19, 25 September 2006 (UTC)[reply]

This is a conversion issue, from polar coords to 2D rectangular coords. StuRat 18:30, 25 September 2006 (UTC)[reply]

Thanks all! --Mary Bold text

Whoever adds all these "ANSWERED -> " stuff to the titles, I kindly ask that you don't do it in the future, as it will break #-links. Thanks. – b_jonas 16:15, 26 September 2006 (UTC)[reply]

Hmm, I didn't think about that. Are there many links to these questions ? StuRat 16:34, 26 September 2006 (UTC)[reply]

What's with the "m"? Are there any links to these questions? -- Meni Rosenfeld (talk) 16:56, 26 September 2006 (UTC)[reply]

Well, I occasionally link to some of them, especially when someone asks a suspicously similar question on RD again. Of course, I'm not an authority here so if the community decides for these title changes, you can do that, then I will resort to adding explicit Anchor tags instead of linking to lables. – b_jonas 18:10, 26 September 2006 (UTC)[reply]

How about if we create a subsection titled "ANSWERED" instead ? This will still show up in the TOC but won't keep your link from working. Sound good ? StuRat 22:10, 26 September 2006 (UTC)[reply]

Central Angle of a Tetrahedron

According to VSEPR theory, molecules such as methane are arranged in a tetrahedral form where the angle from one hydrogen to the carbon to another hydrogen is approximately 109 degrees. Is there any way to derive this angle mathematically? I have tried using the Pythagorean Thm in three dimensions, but it was a complete mess. Thanks, --JianLi 21:08, 25 September 2006 (UTC)[reply]

It's the top angle α of an equilateral triangle with base (2/3)×√6 and sides of length 1. Then the law of cosines gives you cos α = −1/3, as stated in the VSEPR article. No idea where the number −1/3 comes from. --Lambiam ^Talk 22:30, 25 September 2006 (UTC)[reply]

Things become easier if you consider that a tetrahedron can be embedded in a cube, each face of the cube has one edge of the tetrahedron across it. If the cube has sides of length 2 and is centered at the origin then the verticies of the cube will be (+/-1,+/-1,+/-1). Four of these will be verticies of the tetrahedron, say A (1,1,1), B (1,-1,-1), C (-1,-1,1), D (-1,1,-1). Consider the triangle OAB. This has sides a=√3, b=√3, c=2√2. The law of cosines gives

c^{2}=a^{2}+b^{2}-2ab\cos(\gamma )

so

8=3+3-2*3*\cos(\gamma )

so

\cos(\gamma )=-2/6

and

\gamma =109.471

degrees. --Salix alba (talk) 23:07, 25 September 2006 (UTC)[reply]

Or you can just take the dot product of OA and OB. Melchoir 00:11, 26 September 2006 (UTC)[reply]

Wow, this problem seems so easy now. Thanks! --JianLi 01:56, 26 September 2006 (UTC)[reply]

Should some of this be mentioned in the text of VSEPR? Before cos^-1(-1/3) is mentioned there now, there is nothing constraining the shape of the tetrahedron. Is there an argument showing that the tetrahedron should be one sixth part of a cube? --Lambiam ^Talk 15:34, 26 September 2006 (UTC)[reply]