September 15 Information

We randomly pick 3 points inside the n-dimensional unit ball. What is the expectation value of the area of the triangle that has the 3 points as its vertices? Count Iblis ( talk) 02:42, 15 September 2011 (UTC) reply

http://mathworld.wolfram.com/BallTrianglePicking.html Naraht ( talk) 04:10, 15 September 2011 (UTC) reply

(ec)

This problem consists of parts.

1. compute the coordinates to a randomly chosen point inside the n-dimensional unit ball.
2. compute the area of a chosen triangle.
3. compute the average of a million such areas.

The easier way to do part one is to take n random numbers from the uniform distribution in the interval from −1 to 1. If the sum of squares of those numbers exceeds 1, then try again.

Part two can be done either by Heron's formula, or by linear algebra.

Part three is standard statistics. Also compute the standard deviation of the areas in order to estimate the statistical uncertainty of the computed mean value.

You are probably requesting an analytical expression for the expected value, but that is a later development. Good luck! Bo Jacoby ( talk) 04:15, 15 September 2011 (UTC). reply

The Mathworld link doesn't give results for ${\displaystyle n>3}$.

Bo's method for step 1 isn't tractable for large n. My preferred method: Pick a unit vector by sampling n normal variables, and normalizing; Pick a distance from center by sampling a uniform variable and taking the nth root. Multiply.

My simulation confirms Mathworld's results for ${\displaystyle n=2,3}$; and gives ${\displaystyle \approx 0.455}$ for n=4, ${\displaystyle \approx 0.517}$ for n=5, and ${\displaystyle \approx 0.666}$ for n=10. -- Meni Rosenfeld ( talk) 05:16, 15 September 2011 (UTC) reply

Interesting, Meni! Your method is nice, but doesn't sampling normal variables require much more computation than sampling uniform variables? How large must n be before your method is faster? Bo Jacoby ( talk) 09:17, 15 September 2011 (UTC). reply

Sampling a normal variable is more expensive, but my method scales linearly. While the proportion of points in the unit cube that are also in the unit ball decreases exponentially in the dimension. For ${\displaystyle n=20}$ you'll already need to sample more than a million points to get a single point in the ball. The exact crossover point depends on the details of the computing environment, but assuming a normal variable is 10 times the cost of a uniform variable (made up number), then for ${\displaystyle n=6}$ you'll already see improvement. -- Meni Rosenfeld ( talk) 11:08, 15 September 2011 (UTC) reply

Yes, the proportion of points in the cube that are also in the ball is the ratio between the ball volume ${\displaystyle {\frac {\pi ^{\frac {n}{2}}}{{\frac {n}{2}}!}}}$ and the cube volume ${\displaystyle 2^{n}}$. That is ${\displaystyle {\frac {({\frac {\sqrt {\pi }}{2}})^{n}}{{\frac {n}{2}}!}}}$ which actually decreases even faster than exponentially! The mean number of shots needed to hit inside the ball is the reciprocal value ${\displaystyle \textstyle ({\frac {2}{\sqrt {\pi }}})^{n}\cdot {\frac {n}{2}}!}$. Meni's method requires 10n operations. The J expression (,.(4p_1&^*!)@-:,.10&*)2+i.16 computes the table below.

      2 1.27324  20
      3 1.90986  30
      4 3.24228  40
      5 6.07927  50
      6 12.3846  60
      7 27.0913  70
      8 63.0742  80
      9 155.222  90
     10 401.543 100
     11 1086.99 110
     12 3067.56 120
     13 8995.98 130
     14 27340.2 140
     15 85905.3 150
     16  278485 160
     17  929713 170

Meni's method is faster when n is at least 9. Bo Jacoby ( talk) 21:37, 15 September 2011 (UTC). reply

I think you didn't take into account the fact that with the cube method you need to sample n uniform variables per attempt. But of course this doesn't matter since it's all rough anyway. -- Meni Rosenfeld ( talk) 05:07, 16 September 2011 (UTC) reply

I think you are right. I should compare to 10 rather than to 10n, and the crossover is at n=6. Bo Jacoby ( talk) 12:12, 16 September 2011 (UTC). reply

Oh, and as ${\displaystyle n\to \infty }$, this will go to ${\displaystyle {\sqrt {3}}/2}$, since two random vectors in high-dimensional space are orthogonal, so this is an equilateral triangle with side ${\displaystyle {\sqrt {2}}}$. -- Meni Rosenfeld ( talk) 17:16, 17 September 2011 (UTC) reply

I see, so this has to be investigated using numerical methods. Is an asymptotic expansion around n = infinity also possible? Count Iblis ( talk) 15:11, 20 September 2011 (UTC) reply

I don't know about "has to". Mathworld gives exact results as a rational multiple of π for ${\displaystyle n=2,3}$ and I guess these exist for any other n, too. I don't think there's an elementary closed-form solution for a general n, but there should be an expression with special functions and someone smarter than myself may be able to find it.

There should also exist an expansion around ∞ but I'm unable to find it. It looks like the first term is ${\displaystyle {\frac {\sqrt {3}}{2}}\left(1-{\frac {c}{n}}\right)}$ where c is around 3. -- Meni Rosenfeld ( talk) 11:23, 21 September 2011 (UTC) reply

Greetings one and all. I have a problem to do with an assignment I am working on, and it is to do with variation of parameters with respect to differential equations. I was given the following equation  : t²y′′ - t(t+2)y′ + (t + 2)y = 2t³, the homogenenous solution to which is y1 = t and y2 = te^t , where e is e, the exponential function exp(t), and both of these do work. We are asked to work out the non homogeneous equation for y1 and y2 whose derivatives combine in the way given in the equation to equal 2t³.

I carried out a general equation, calling my terms v1y1 and v2y2, such that my y = v1y1 + v2y2 , differentiating them using the product rule, then again for the second derivative.

I found that  : (v1y1 + v2y2)′ = v1′y1 + v1y1′ + v2′y2 + v2y2′, but in the lecture notes for such exercises we are told that we can allow v1′y1 + v2′y2 to equal zero, as that is a representation of the complementary, homogeneous equation, meaning now that (v1y1 + v2y2)′ = v1y1′ + v2y2′, and this we now differentiate to get y′′, which then equals v1′y1′ + v1y1′′ + v2′y2′ + v2y2'′.

This we put in a general formula for differential equations of this kind which is y′′ + p(t)y′ + q(t)y = r(t), and we get  :

v1′y1′ + v1y1′′ + v2′y2′ + v2y2′′ + p(v1y1′ + v2y2′) + q(v1y1 + v2y2)= r(t).

From this our notes tell us we can rearrange this into v1′y1′ + v2′y2′ + v1(y1′′ + py1′ + qy1) + v2(y2′′ py2′ + qy2)= r(t), but are informed that both the coefficients of v1 and v2 will vanish since the differential y1′′ + py1′ + qy1 is the general equation that equals zero, so now this means that v1′y1′ + v2′y2′ = r(t).

To solve in order to find out what v1 and v2 are, we can turn this into a matrix equation as such :

[y1 y2 ; y1′ y2′ ] [v1′;v2′] = [0;r(t)]

imagine the y terms are in a 2 by 2 matrix, and the other two are 2 by 1 matrices. Here they are written as they would be to be entered into MatLab.

Specifically, for this particular exercise, the matrix equation would be

[t te^t ; 1 e^t(t+1) ] [v1′;v2′] = [0;2t³]

and I find the inverse matrix and get

v1′ = -2t² and v2′ = 2t²e^-t

Now when I plug these into v1′y1′ + v2′y2′ = r(t), it works, but only -2t² seems to work when I put it into the original non homogenenous equation. If I try to find v1 and v2 by integration, I get answers that do not seem to work either, so I wonder what it is I am doing wrong. Any help and advice on this would help very much, thank you. Chris the Russian Christopher Lilly 12:07, 15 September 2011 (UTC) reply

I replaced all the quotes with primes symbols since wiki syntax was interpreting them not the way you intended.-- RDBury ( talk) 12:17, 16 September 2011 (UTC) reply

You're going wrong at the expression immediately after "From this our notes tell us we can rearrange this into...". Keep in mind the professors often put in these little intentional mistakes to make sure people are paying attention. When I expand out the expression I get v1′′y1+2v1′y1′+pv1′y1+v2′′y2+2v2′y2′+pv2′y2=r. In any case, perhaps variation of parameters isn't the best way of doing this since undetermined coefficients works as well. Try putting y=at²+c into the equation and solving for a and c. I get a=-2, c=0 which gives the solution y=-2t².-- RDBury ( talk) 13:35, 16 September 2011 (UTC) reply

This is very interesting. I cannot see how they expect us to learn the stuff if they are trying to trip us up. The thing is, if they have not taught me properly how to do this, and sure, it is also up to me to learn, which is what I am trying to do, and then instead of showing us how and what to do properly, what do they expect ? Would anyone leave a five year old alone in a room with a maths book and expect them to figure it out all on their own ? It may take a while. After all, sure I am at a much higher level, but by own admission, I came here to learn, and I know I do not know it all and rely on the teachers to show me how to do something new, then I can also learn how to think for myself.

But your answer is interesting, because of course that was one of the v'₁ answers I had, and alone it is a solution to the non homogeneous equation. Now if I integrate this v'₁ = -2t², and the v'₂ I got, which is 2t²e^-t, I get a v₁ equals -(2/3)t³, and a v₂ that equals -2t²e^-t - 4te^-t - 4e^-t. I thought then I was supposed to multiply y₁ by v₁ which would give me t × -(2/3)t³ = -(2/3)t⁴ and y₂ by v₂ which is te^t × [ -2t²e^-t - 4te^-t - 4e^-t ] = -2t³ - 4t² - 4t, since the e^-t would multiply by the e^t, and cancel out to equal one.

But when I did all this, such that my y ended up being v₁y₁ + v₂y₂ = -(2/3)t⁴ -2t³ - 4t² - 4t, then derived it to get y' = -(8/3)t³ -6t² - 8t - 4, and again for y = -8t² -12t - 8, and put them all back into the original equation where t²y - t(t+2)y' + (t+2)y was supposed to equal 2t³ , and went over this again and again, I got the same answer of 2t⁵, and could not understand what I had done wrong. Am I to suppose then that the answer is only y= -2t², and nothing else, because for all I know, it is the only one that seems to work. Also, I am sorry, but how is it you say you get v₁′′y₁ + 2v₁′y₁′+pv₁′y₁+v₂′′y₂+2v₂′y₂′+pv₂′y₂=r, as I am sure I checked the thing myself to see if what they had put down was right. Normally as I say I like to presume they are not putting us crook, but I do try to check things as much for typos as for deliberate errors, which themselves may not be entirely unreasonable if they are ones we should know better about. All I see in the expression is one each of v₁′ and v₂′, but if this is crucial, I should like to understand that. Thank You. Chris the Russian Christopher Lilly 06:50, 17 September 2011 (UTC) reply

I was wrong earlier about the location of the mistake. You first need to put the equation in the standard form y′′+py′+qy=r, so you need to divide by the coefficient of y′′ before you start. That make p=−(t+2)/t, q=(t+2)/t², r=2t. Thant means you need to solve the system u₁′t+u₂′te^t=0, u₁′1+u₂′(t+1+e^t=0. The solution is u₁′=−2, u₂′=−2e^−t, so take u₁=−2t, u₂=−2e^−t. Plug that in to get y=−2t²−2t. But the −2t can be absorbed into the homogeneous solution, so the general solution is y=−2t²+at+bte^t.-- RDBury ( talk) 12:21, 17 September 2011 (UTC) reply

Thank You, now I get it. This has been quite a trying exercise, as all these seem to be, but even so, now I feel I becoming battle hardened so to speak, and beginning to get the idea that we need challenges to keep us on our toes and get us thinking for ourselves. I certainly do not want to be given the answers, and am glad of the chance to work this out for myself, but just more the guidance to show if I am on the right track, and if not, where I have gone wrong. I also see in my notes that hidden in there is a mention of allowing a like term from the particular to be absorbed into the constant of the like term of the homogeneous, because if it is c₂, who is to say that does not contain that part of the y₂ term  ? So I shall give that a go. Thanks Again. Chris the Russian Christopher Lilly 17:36, 17 September 2011 (UTC) reply

Hi. I'm working through a book, and stuck on an exercise. I'm supposed to show that, if ${\displaystyle \theta }$ is an irrational number, then there exist infinitely many degree 1 polynomials ${\displaystyle P\in \mathbb {Z} \left[x\right]}$ satisfying ${\displaystyle |P(\theta )|<{\frac {1}{H(P)}}}$, where ${\displaystyle H(P)}$ is the height of P: the maximum absolute value of coefficients of P.

I know that, for any irrational ${\displaystyle \theta }$, we have infinitely many ${\displaystyle {\frac {p}{q}}\in \mathbb {Q} }$ satisfying ${\displaystyle |\theta -{\frac {p}{q}}|<{\frac {1}{{\sqrt {5}}q^{2}}}}$. I can multiply through by ${\displaystyle q}$ (which I can assume to be positive), obtaining ${\displaystyle |q\theta -p|<{\frac {1}{{\sqrt {5}}q}}<{\frac {1}{q}}={\frac {1}{H(qx-p)}}}$, but that last equality only holds if ${\displaystyle p\leq q}$, which we can get away with as long as ${\displaystyle \theta <1}$. If ${\displaystyle p>q}$, then I get an inequality pointing the wrong way.

Has anyone got an idea how I can generalize this argument for an arbitrary irrational ${\displaystyle \theta }$? Thanks in advance for any hints or suggestions. - GTBacchus^{( talk)} 23:50, 15 September 2011 (UTC) reply

It appears to me that your analysis is correct and there are counter examples with ${\displaystyle \theta >1}$. Try looking at ${\displaystyle \theta =k+\varphi }$ there k is a large integer and ${\displaystyle \varphi }$ is the golden ratio. Then the best rational approximations of ${\displaystyle \theta }$ have the form ${\displaystyle k+{\frac {F_{n+1}}{F_{n}}}}$ where ${\displaystyle F_{n}}$ are Fibonacci numbers. But it appears the inequality required will fail if k is large enough.-- RDBury ( talk) 03:44, 16 September 2011 (UTC) reply

Huh. That's unsettling. I mean, all books have mistakes, but this is kind of a surprising one. I'll work on establishing a counterexample, I guess, and then maybe write to the author. - GTBacchus^{( talk)} 15:01, 16 September 2011 (UTC) reply

I could be wrong, have been before and will be again. My understanding though is the the √5 in the denominator is the best you can do, with φ being the number the disproves you can do any better. And my informal calculation say that if the inequality given is true then applying it to k+φ would give a rational approximation u/v of φ which is as close as approximately 1/kv².-- RDBury ( talk) 17:35, 16 September 2011 (UTC) reply

Yes, that makes sense. I'm confident there's either a proof or a counterexample, anyway, and if it's the latter, it should just be a matter of rolling up my sleeves and doing it. I'll post here when I've got something definitive. - GTBacchus^{( talk)} 19:17, 16 September 2011 (UTC) reply

I now think that the error in the book is this: Instead of ${\displaystyle {\frac {1}{H(P)}}}$, it should read ${\displaystyle {\frac {c}{H(P)}}}$, where ${\displaystyle c}$ is a constant that depends on ${\displaystyle \theta }$. - GTBacchus^{( talk)} 15:38, 18 September 2011 (UTC) reply