Wikipedia:Reference desk/Archives/Mathematics/2008 March 12

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.

March 12

Least Squares Question

Let $v_{1}={\begin{bmatrix}1\\1\\0\\1\end{bmatrix}}$ and $v_{2}={\begin{bmatrix}0\\0\\1\\0\end{bmatrix}}$ and $b={\begin{bmatrix}0\\1\\0\\-1\end{bmatrix}}$. Let $V=span\{v_{1},v_{2}\}$. I am trying to find the vector in V that is closest to the vector b. Now, my questions is that I am trying to solve the system Ax=b and I know that b is my b above and $x={\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\end{bmatrix}}$ is a four dimensional vector but what would my matrix A be? Would it be just $A={\begin{bmatrix}1&1&0&1\\0&0&1&0\end{bmatrix}}$? But then I can't multiply both sides by transpose of A and them multiply by the inverse of (Transpose(A)*A)? Basically I want to have that $x=(A^{*}A)^{-1}*A^{*}$ but I can't figure out what my A will be. Any help would be appreciated! Thanks!A Real Kaiser (talk) 05:27, 12 March 2008 (UTC)

Because you're searching for the best approximation in V, you want the range of A to be V. The range of a matrix is the span of its columns, and so A is the 4 x 2 matrix with $v_{1}{\mbox{ and }}v_{2}$ as columns. Your x is actually a length 2 vector, representing the coefficients of $v_{1}{\mbox{ and }}v_{2}$. In this case, $A^{*}A$ will be square, and invertible. Check out Moore-Penrose inverse. 134.173.93.127 (talk) 07:46, 12 March 2008 (UTC)

Ironically, I can see by inspection that b is orthogonal to the vs. So the closest vector is just the zero vector. Baccyak4H (Yak!) 18:41, 12 March 2008 (UTC)

Actually, that was my intuition also that zero would be the answer (because that is the one and only point both spaces share so obviously it is the closest one). My I just couldn't understand how to setup my matrix A. And when I tried to do it (the way you basically said), I was wondering as to why my matrix x was only two dimensional. Now it makes sense the the entries of matrix x represent the coefficients for linear combination of v1 and v2. So this means that the x1v1+x2v2 would be the vector that I am looking for, right? In span{v1,v2}?A Real Kaiser (talk) 04:50, 13 March 2008 (UTC)

That's right. 134.173.93.127 (talk) 07:41, 13 March 2008 (UTC)

Which two spaces? There's the space V, and the vector b which is not in it. You may have meant span{b}, which indeed intersects V only at 0. But this is not enough for the closest vector to be zero - for this you need orthogonality. Consider v1 = {1, 0, 0}, v2 = {0, 1, 0} and b = {1, 1, 1}. Only {0, 0, 0} is common to span {v1, v2} and span {b}, but the closest vector in V to b is {1, 1, 0}. -- Meni Rosenfeld (talk) 14:36, 13 March 2008 (UTC)

Probabilities and this year's Champions League quarter finals

OK, I wasn't too shabby at Maths when I last studied it, but I always struggled with Probabilities. I thought of a nice bunch of Probabilities questions based on the forthcoming Champs Lg draw. Can you help me understand how to solve them, and thereby make up for either a duff teacher all those years ago, or, more likely, my inattention in class at crucial moments:

• There are 8 remaining teams in the competition
• 4 are English
• The draw will put them into 4 pairings that will decide the semi-final line up
• Assume all teams are of equal ability and AGF that UEFA don't rig their draws!

Q1 What's the probability of exactly 1 all-English quarter-final?
Q2 What's the probability of exactly 2 all-English quarter-finals?
Q3 What's the probability of at least 1 all-English quarter-final?
Q4 What's the probability of exactly 1 all-English semi-final?
Q5 What's the probability of exactly 2 all-English semi-finals?
Q6 What's the probability of at least 1 all-English semi-final?
Q7 What's the probability of an all-English final?

Oh, and leaving my probability of inattention in class aside (which, frankly is nearly 100%), if my maths teacher had used problems like this, instead of boys choosing socks in the dark (when they could just switch a ruddy light on) I might be able to do this without your help!

Cheers, --Dweller (talk) 12:23, 12 March 2008 (UTC)

Well, I will try to provide some of the answers, but I don't guarrantee that they are right :)

First, let's count how many combinations of quarter-final ties there are (only accounting that Team1 will be drawn against Team2, without accounting who is drawn to host the first leg). It should be $C_{2}^{8}={\frac {8!}{2!(8-2)!}}=28$.

A1. Out of these there is a $C_{2}^{4}={\frac {4!}{2!(4-2)!}}=6$ possibilities that exactly 2 English clubs are drawn together, thus making a probability of ${\frac {6}{28}}={\frac {3}{14}}\approx 0.21$, i.e. 21%.

A2. I suppose, therefore, that the probability of 2 all-English quarter-finals should be $({\frac {3}{14}})^{2}={\frac {9}{196}}\approx 0.05$, i.e. 5%.

A3. And, therefore, the probability of at least 1 all-English quarter-final should be the sum of above two probabilities, i.e. ${\frac {3}{14}}+{\frac {9}{196}}={\frac {51}{196}}\approx 0.26$, i.e. 26%.

It's hard to go on from here because we have to account for different cases.

A5. Of course, there can't be exactly 2 all-English semi-finals if there's at least 1 all-English quarterfinal. The probability that no English teams will be drawn together in the quarter-finals should be, according to the above information, $1-{\frac {51}{196}}={\frac {145}{196}}\approx 0.74$, i.e. 74%. Assuming that all clubs are of equal ability to qualify for the semi-finals, the probability that all English teams will win their ties in this case is $({\frac {1}{2}})^{4}={\frac {1}{16}}=0.0625$, i.e. 6.25%. Multiplying these two would give us the answer: ${\frac {145}{196}}\times {\frac {1}{16}}={\frac {145}{3136}}\approx 0.05$, i.e. 5%.

Well, the other questions are more complicated than these, maybe I will come back to them later... maybe not :). Again, I'm not sure if what I did above is right, but it sure makes sense. To me at least! Hope that helps!  ARTYOM  13:18, 12 March 2008 (UTC)

Urk. Sorry to be picky after you've done all that work, but you'll need to slow down. I think I remember what the ! is (but can't remember what it's called - is it "factorial" or something?) but haven't a clue what the big C thingy is, nor how/why you populate the first equation that leads to 28. Remember, I want to understand how to do this, not just learn the answers! --Dweller (talk) 13:47, 12 March 2008 (UTC)

For the benefit of people similarly mathematically illiterate to me who come here (I advertised this thread at WT:FOOTY) the ! is indeed Factorial --Dweller (talk) 13:52, 12 March 2008 (UTC)

Yes, it is, and the C stands for choose. $C_{2}^{8}$ is the number of ways of choosing 2 members from a set of 8 elements. --Tango (talk) 14:43, 12 March 2008 (UTC)

Thanks for that. So remembering about ! and learning that C notation means I've already learned something. --Dweller (talk) 15:10, 12 March 2008 (UTC)

I don't think that's right - only a 26% chance of an all-England matchup doesn't sound right at all. Your ${\frac {6}{28}}$ is the probability that any given tie, taken independently of the others, will be an all-England clash. But you can't just square that to get the probability of two, because the ties are not independent.

By my reasoning the probability that there are no all-English quarter-finals is given by placing the English teams into the draw first; so the first team can be placed in any of the 8 spots, the second in 6 of the remaining 7 spots (i.e. not against the first), the third in 4 of 6, and the last in 2 of 5, giving ${\frac {8}{8}}\times {\frac {6}{7}}\times {\frac {4}{6}}\times {\frac {2}{5}}={\frac {8}{35}}\approx 22.86\%$. So the probability of at least one all-English tie is the remainder, $\approx 77.14\%$. I can't think how to do the rest right now but I'll get back to you! — sjorford++ 14:53, 12 March 2008 (UTC)

In these things, it is often helpful to do the extreme cases first:

• Question 3 is easiest to answer, since we just want to find the probability of NOT having an english QF. As above, this is ${\dfrac {8}{8}}\times {\dfrac {6}{7}}\times {\dfrac {4}{6}}\times {\dfrac {2}{5}}={\dfrac {8}{35}}$, and thus P(at least 1 english QF) = ${\dfrac {27}{35}}$.
• Question 2. EXACTLY TWO english QF. Let us pick the english teams first. We can choose any position for the first team, so that is irrelevant. Let the 2nd team be a match (1/7). Then 6 choices for the 3rd, and 1 for the 4th. Thus we have ${\dfrac {8}{8}}\times {\dfrac {1}{7}}\times {\dfrac {6}{6}}\times {\dfrac {1}{5}}={\dfrac {1}{35}}$ chance of this. Now, suppose the 2nd team does not get a match (6/7), then the 3rd team has 2 options, and the 4th team just 1. Thus chances of 2 matches is ${\dfrac {1}{35}}+{\dfrac {8}{8}}\times {\dfrac {6}{7}}\times {\dfrac {2}{6}}\times {\dfrac {1}{5}}={\dfrac {1}{35}}+{\dfrac {2}{35}}={\dfrac {3}{35}}$
• Question 1. Now, there were 3 possible cases with 4 teams - 1 match, 2 matches, or no matches. So, now $P(1)=1-{\dfrac {3+8}{35}}={\dfrac {24}{35}}.$
• Question 5. For 2 english semi-finals, we require that the english teams all have different matches (8/35), and that they all win (1/2). Thus, P(2 E SF) = ${\dfrac {8}{35}}\left({\dfrac {1}{2}}\right)^{4}={\dfrac {8}{35}}\times {\dfrac {1}{16}}={\dfrac {1}{70}}$.
• Question 4. Here it gets difficult, as we need to consider many cases.
  • The easiest is if there are 2 english QFs (3/35) - then we can guarantee exactly two english teams in the SFs. The chance of them facing each other is ${\dfrac {1}{3}}$, which when combined with the probability of 2 english QFs is ${\dfrac {1}{35}}$.
  • Now suppose that there are no english QFs (8/35). Then to get 1 english QF we require at least 2 teams to win.
    • Suppose exactly 2 do win - there are $^{4}C_{2}=6$ ways to do this, each of which has a probaility of $\left({\dfrac {1}{2}}\right)^{4}={\dfrac {1}{16}}$ (2 teams must win, 2 lose). Now, we require that the 2nd team face the 1st team. This has a chance of 1/3 as above. Thus here we have ${\dfrac {8}{35}}\times {\dfrac {6}{16}}\times {\dfrac {1}{3}}={\dfrac {1}{35}}$
    • Suppose 3 English teams win - $^{4}C_{3}=4$ ways, each with P = 1/16. Any draw we are bound to have 2 english teams facing off, thus we have ${\dfrac {8}{35}}\times {\dfrac {4}{16}}\times {\dfrac {1}{1}}={\dfrac {2}{35}}$
  • Now, suppose there is one english QF (24/35). We are bound to have 1 english team in the SF.
    • Suppose both other english teams win (P = (1/2)^2 = 1/4). Then we have 3 teams and 4 spots - there's bound to be an english SF, with $P={\dfrac {24}{35}}\times {\dfrac {1}{4}}={\dfrac {6}{35}}$
    • Now, suppose that only one of the other enlish teams win. There are 2 ways to do this, each with probability 1/4. Now the chances of them facing each other in the SF is 1/3. Thus $P={\dfrac {24}{35}}\times {\dfrac {2}{4}}\times {\dfrac {1}{3}}={\dfrac {4}{35}}$
  • Thus, we now sum these probabilities: $P={\dfrac {1+1+2+6+4}{35}}={\dfrac {14}{35}}={\dfrac {2}{5}}$
• Question 6 - this is now easy, we just sum the probabilities of 1 and 2 english SFs. $P={\dfrac {2}{5}}+{\dfrac {1}{70}}={\dfrac {29}{70}}$
• Question 7 - Almost there, but again several cases to consider.
  • The most obvious place to start is with 2 all-english SFs. We know this had probability 1/70. We must have an all-english final here.
  • Next consider there are exactly 3 english teams in the SFs. This happens if either there is one english QF and both other teams win (P = 6/35), or no english QFs and 3 teams win (P=2/35). Thus we have a total P=8/35. We're bound to have 1 english team in the final, and the other has a 0.5 chance. Thus we have a 4/35 chance from this case.
  • We could take forever finding the probability of 2 english teams in the semis. However, note that there are an equal number of english and foreign teams, and that they all have equal chances of winning. Thus, the chances of two no-english SFs is 1/70, and the chance of only one english team in the SFs is 8/35. Thus, we have used up 17/35 options, and the remaining 18 must be exactly 2 teams facing each other, of which 1/3 are going to have the english teams facing each other and thus can be discarded. So we have a 12/35 chance of having exactly 2 english teams in different matches. Now, we require that both win. This has P = 1/4. Thus the chance of an english final here is ${\dfrac {12}{35}}\times {\dfrac {1}{4}}={\dfrac {3}{35}}$.
  • Now, sum these: $P={\dfrac {1}{70}}+{\dfrac {4}{35}}+{\dfrac {3}{35}}={\dfrac {3}{14}}$

Damn that was a lot of work. We'd better fkn win. -mattbuck (Talk) 16:16, 12 March 2008 (UTC)

Simpler approach for Q7: Forget the route to the final - there are (8x7)/2=28 possible pairs of teams in the final, of which (4x3)/2=6 consist of a pair of English teams. So probability of an all-English final is 6/28, which is 3/14. Gandalf61 (talk) 16:32, 12 March 2008 (UTC)

Damn my looking for the complicated route. I thought there should be an easy way to do it. -mattbuck (Talk) 16:46, 12 March 2008 (UTC)

Math: real-life examples of polynomial division?

what are some examples from real life in which you i might use polynomial division? —Preceding unsigned comment added by Lighteyes22003 (talk • contribs) 13:38, 12 March 2008 (UTC)

Finding roots of polynomials is the obvious one. It comes up all the time in various disciplines, since lots of things are described (at least approximately) by polynomials and it's often useful to know when they are zero. --Tango (talk) 13:45, 12 March 2008 (UTC)

See Linear response function for one example. It is used in radio and television design. Bo Jacoby (talk) 13:56, 12 March 2008 (UTC).

I saw your previous question and felt I should answer it, but it's hard to come up with an answer at what I think is your level of understanding. As others have mentioned, it's used to find roots of polynomials (e.g. to find more roots after the first is known). I doubt you are familiar with eigenvalues or root locus plots, but those require polynomial roots. Let's say I'm designing a control system for an aircraft. I've taught this using the roll control system of an F-18 as one example. First, you write out the equations of motion of the aircraft. The result is a system of differential equations. You then apply a Laplace transform to that system, so you get a system of polynomial equations in 's' (the Laplace variable). If you can find one root, by numerical or other means, you can use polynomial division to simplify the equation, getting the entire set of real and complex roots. Depending on those roots (are they real or complex? are their real parts negative or positive? how close to the origin are they?) you can tell a lot about the behaviour of the aircraft. For instance, if the real parts are negative, the aircraft is stable, otherwise it is unstable. Adding a control system to the loop modifies the set of differential equations and allows us to set the roots where we want them, ensuring the behaviour of the aircraft is how we want it, and that the aircraft is stable, maneuverable, and other desirable properties. moink (talk) 14:37, 12 March 2008 (UTC)

And the reference desk serves its function of helping us improve articles: Root locus needs some serious work. moink (talk) 14:44, 12 March 2008 (UTC)

One thing is for sure - polynomial division is a much less important mathematical skill for an average individual than others which are unfortunately not studied enough (or at all) in school, such as logic and probabilistic thinking. -- Meni Rosenfeld (talk) 15:08, 12 March 2008 (UTC)

That's for sure -- I agree 100%. Logic especially needs to be taught more. It is completely foreign to most students, unfortunately. (Joseph A. Spadaro (talk) 08:18, 13 March 2008 (UTC))

Chi-square test

When calculating a chi-square test what are the steps between calculating the differences between the expected and observed values and obtaining the chi-square value? Then, knowing the degrees of freedom, how is the p-value of the chi-square obtained (other than by looking it up in a table)? Thanks. The chi-square test article does not explain these points. Itsmejudith (talk) 15:47, 12 March 2008 (UTC)

If you are talking about a contingency table, then the expected value for each entry is

(column total / table total) × (row total / table total) × table total.

I know this expression can be simplified, but in this form it is easier to see conceptually what is being estimated. Subtract this from the observed value, square the difference, and divide by this expected value again. The sum over all the table is the value of the χ² statistic. Call that value X. Then the p-value is just the probability that a χ² distribution with the appropriate degrees of freedom is at least X (that is, one minus the CDF of the χ² distribution, at X). Baccyak4H (Yak!) 18:33, 12 March 2008 (UTC)

Can this detail be added to the worked example in the article? Thanks. Itsmejudith (talk) 08:50, 13 March 2008 (UTC)

OK, done. Although I can see the point someone might make that it is too much "How to...". Baccyak4H (Yak!)