Wikipedia:Reference desk/Archives/Mathematics/2012 March 3

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 3

Can't figure out probability mistake

Hello. I recently came across this puzzle: "Alice, Bob, and Camille are playing a dice game. Alice rolls a 10-sided die; if she gets a 1 she wins, if not Bob rolls a 6 sided die; if he gets a 1 he wins, if not Camille rolls a 4 sided die, if she gets a 1 she wins. The game continues until one player wins What is the probability that Alice wins the game?" I set it up like this: call P(A) the probability that Alice wins. Then $P(A)={\frac {1}{10}}+{\frac {9}{10}}({\frac {5}{6}}\cdot {\frac {3}{4}}\cdot {\frac {1}{10}}+{\frac {9}{10}}({\frac {5}{6}}\cdot {\frac {3}{4}}\cdot {\frac {1}{10}}+...$ I observed that this expression exhibits self-similarity; I define $q=P(A)-{\frac {1}{10}}$ so that $q={\frac {9}{10}}({\frac {5}{6}}\cdot {\frac {3}{4}}\cdot {\frac {1}{10}}+q)$. Solving for q I have ${\frac {1}{10}}q={\frac {9}{160}}\implies q={\frac {9}{16}}$, then solving for P(A) I get P(A)=9/16 + 1/10 = 53/80. I was congratulating myself on how elegant my solution was when I finally had that d'oh moment that it makes no sense that Alice who has only a 1/10 chance of rolling a 1 would have a greater than 50% chance of winning, even if she goes first. Where is my reasoning wrong? Thanks. 24.92.85.35 (talk) 01:43, 3 March 2012 (UTC)

You only need to look at the relative probabilities for one cycle, as they will be the same for each subsequent cycle. So, Alice has a 1/10 chance of winning during a cycle, and Bob has a (9/10)(1/6) = 9/60 = 3/20 chance of winning in a cycle, and Camille has a (9/10)(5/6)(1/4) = 45/240 = 3/16 chance of winning in a cycle. Let's give those chances common denominators: A = 8/80, B = 12/80, C = 15/80. So, these add up to 35/80 chance that there will be a winner in the first cycle. Thus, Alice has an 8/35 chance of winning the first cycle (and each subsequent cycle), Bob has a 12/35 chance, and Camille a 15/35 chance. These are therefore the probabilities of winning the game. StuRat (talk) 01:59, 3 March 2012 (UTC)

(edit conflict) Try $P(A)={\frac {1}{10}}+{\frac {9}{10}}({\frac {5}{6}}\cdot {\frac {3}{4}}({\frac {1}{10}}+{\frac {9}{10}}({\frac {5}{6}}\cdot {\frac {3}{4}}({\frac {1}{10}}+...$ PrimeHunter (talk) 02:01, 3 March 2012 (UTC)

Getting my head around tensors

Two successive orthogonal transformations are given by ${\bar {\mathbf {x} }}=\mathbf {A} \mathbf {x}$ and ${\bar {\bar {\mathbf {x} }}}=\mathbf {B} {\bar {\mathbf {x} }}$. Relative to each of these $T_{ij}$ transforms as a second rank tensor. Show that $T_{ij}$ also transforms as a tensor relative to the resulting transformation ${\bar {\bar {\mathbf {x} }}}=\mathbf {B} \mathbf {A} \mathbf {x}$. Widener (talk) 05:07, 3 March 2012 (UTC)

A tensor of order/rank 2 can be written as the sum of tensor products of pairs of vectors. Each of the vectors get transformed by A and the B. One can then see that the collective transformation will be BA applied directly each vector in the product. It may be simpler to see by writing the vectors and tensors in terms of their components with respect to some basis, remembering to distinguish between vectors and covectors (I have assumed upper indices for T for simplicity):

${\bar {\bar {x}}}^{i}={B^{i}}_{j}{A^{j}}_{k}x^{k}$

${\bar {\bar {T}}}^{ij}={B^{i}}_{p}{B^{j}}_{q}{A^{p}}_{m}{A^{q}}_{n}T^{mn}$

— Quondum^☏✎ 13:30, 3 March 2012 (UTC)

But we aren't told that T is a tensor, only that it transforms as a tensor relative to A and B. And the fact that A and B are orthogonal is presumably significant. Gandalf61 (talk) 18:46, 3 March 2012 (UTC)

Thanks Quondum. The reason why orthogonality is mentioned is because the next part of the question asks to show that the composition of orthogonal transformations is itself orthogonal (WITHOUT the use of matrix algebra). I think that must mean to go through it component by component again, as Quondum did. How do you do that? Widener (talk) 05:02, 4 March 2012 (UTC)

Gandalf61 has pointed out a subtlety that may render my original argument worthless; it would depend I suppose on exactly what is meant by "relative to A and B" (separately or in succession?), and for that matter, "orthogonal" (I would assume it means they are elements of the orthogonal group, and hence we cannot use commutivity). I'll have to leave this to others to answer... — Quondum^☏✎ 08:22, 4 March 2012 (UTC)

I think I've figured out how to show that the composition of orthogonal transformations is orthogonal myself, actually, so I don't need help for that part of the question. Widener (talk) 10:37, 4 March 2012 (UTC)

The notation they use actually is ${\bar {x_{i}}}=A_{ip}x_{p}$ and ${\bar {\bar {x_{i}}}}=B_{iq}{\bar {x_{q}}}$ rather than ${\bar {\mathbf {x} }}=\mathbf {A} \mathbf {x}$ and ${\bar {\bar {\mathbf {x} }}}=\mathbf {B} {\bar {\mathbf {x} }}$. I'm pretty sure they're using Einstein notation which I find a bit alien. Widener (talk) 09:21, 4 March 2012 (UTC)

Yes, that looks like the variant of the Einstein summation convention where all indices are left as subscripts.

Looking a bit more closely, I think "transforms as a second rank tensor" in this case essentially means that when it (T) acts on a vector, we have $y_{k}=T_{kj}x_{j}\Rightarrow {\bar {y}}_{i}={\bar {T}}_{ij}{\bar {x}}_{j}$ (this does not match my previous interpretation). Then, with a bar indicating transformation with respect to A and a hat to mean transformation with respect to B,

${\bar {y}}_{i}=A_{ik}y_{k}=A_{ik}T_{kj}x_{j}=A_{ik}T_{kj}(A^{-1})_{jm}{\bar {x}}_{m}$

For this to hold for all ${\bar {x}}_{m}$, we must have the transformation rule

${\bar {T}}_{im}=A_{ik}T_{kj}(A^{-1})_{jm}.$

Then we have by substition using the above identities,

${\hat {\bar {y}}}_{j}=B_{ji}{\bar {y}}_{i}=B_{ji}A_{ik}y_{k}=B_{ji}A_{ik}T_{kj}x_{j}=B_{ji}A_{ik}T_{kj}(A^{-1})_{jm}{\bar {x}}_{m}=B_{ji}A_{ik}T_{kj}(A^{-1})_{jm}(B^{-1})_{mn}{\hat {\bar {x}}}_{n}=B_{ji}{\bar {T}}_{im}(B^{-1})_{mn}{\hat {\bar {x}}}_{n}.$

Looking at the transformation rule for A, we see that if we need to interpret T as transforming as a second rank tensor as applying not only to $T_{ij}$ itself, but also to any transformed versions, in this instance transforming with respect to B the already transformed version ${\bar {T}}_{ij}$. We can then deduce that we must have

${\hat {\bar {T}}}_{jn}=B_{ji}{\bar {T}}_{im}(B^{-1})_{mn},$

similarly to the equivalent deduction in relation to A. We then have that

${\hat {\bar {T}}}_{jn}=(B_{ji}A_{ik})T_{kj}((A^{-1})_{jm}(B^{-1})_{mn}),$

which is a direct transformation with respect to C, where C=BA (or $C_{jk}=B_{ji}A_{ik}$).

That $(C^{-1})_{jn}=(A^{-1})_{jm}(B^{-1})_{mn}$ is particularly easy to show in the case of orthogonal transformations A and B, because then throughout use the identity $(A^{-1})_{jm}=A_{mj}$ (in an orthonormal Euclidean basis) and similarly for B (i.e. swapping the indices of an orthogonal transformation inverts it). I hope I haven't made too much of a mess of it this time and that it is of some use to you. — Quondum^☏✎ 15:10, 4 March 2012 (UTC)

Rotation vs. orbit

Is there a mathematical difference between an orbit and a rotation? 58.111.91.182 (talk) 08:29, 3 March 2012 (UTC)

I'm not sure I understand exactly what you're asking, but here goes. I'll assume 3D space. A rotation usually refers to a specific angle of movement around a defined axis, whereas an orbit refers to the path an object follows around a point, including its position as a function of time. A rotation would include the rotation of the body itself, and orbit would normally only refer to the position of the object and would say nothing about its rotation about its "position" (e.g. its centre of mass). An orbit would normally require other parameters – eccentricity, precession, etc. Thus the two concept are quite distinct. — Quondum^☏✎ 13:05, 3 March 2012 (UTC)

One can have orbits which aren't circles, I particularly like one where three bodies follow a figure of eight orbit under the influence of gravity, not that that's liable to happen in practice! Dmcq (talk) 13:39, 3 March 2012 (UTC)

Thank you both. It is correct then to talk about Earth rotating around the sun? Which would be different to its orbit (path?). Basically, I'm just trying to properly distinguish the two terms in my mind. 58.111.91.182 (talk) 13:59, 3 March 2012 (UTC)

You wouldn't normally talk about the earth rotating about the sun, only about its axis. The earth orbits the sun. A line connecting the sun to the earth would rotate around the sun. In general a rotaton is a geometric movement through an angle whereas an orbit is a movement according to some equation and in particular it normally means under gravity. Dmcq (talk) 14:24, 3 March 2012 (UTC)

Ok, what if we consider a unit circle centred at 2. I can 'rotate' that circle about the origin. Am I using the wrong term in that case? If not, then I'm failing to distinguish that example and the Earth about the sun example above. Thanks again for your time. 58.111.91.182 (talk) 16:25, 3 March 2012 (UTC)

Yes, you could speak about rotating a circle, or any other figure, about the origin. It may be more instructive to consider a figure with more detail, such as a triangle. To specify the rotation, in 2D you would need to specify the centre of rotation (you specified the origin), plus the angle of rotation, say 10° anticlockwise. Imagine tracing the figure (the circle or triangle) on tracing paper, putting a pin through the tracing paper at the specified centre of rotation, and rotating the tracing paper around the pin as specified through 10°. The position of the traced figure is the original figure as rotated. Notice that the sides of the triangle will be at 10° from their original orientations, and every point on the figure (e.g. circle centre, triangle vertices etc.) are at 10° from their original positions as measured from the centre of rotation. The distinction is partly about the detail about what is described (e.g. specifying the orbit does not constrain the rotation of the earth about its axis), and partly is like the semantic difference between trajectory and change of position. One (trajectory and orbit) describes the path it follows, generally as a function of time, and the other (change of position or rotation) says how much it has moved (generally including orientation) between two cases, e.g. points in time. Note that in general, the earth will not ever be purely rotated with respect to the sun at some future another time: its motion is too complex to be described by a single rotation about the sun, even ignoring intermediate positions. — Quondum^☏✎ 07:35, 4 March 2012 (UTC)

Dividing by 3, 6, prime or odd numbers other than 5, 25, 125 etc.?

So no matter what I do, if I divide a number not divisible by three or six by three or six, the quotient always ends with repeating digits. Are there any numbers that, even if they are not divisible by three, the quotient doesn't have repeating digits? And are there any prime numbers other than 5 that, when they divide, the quotient will not always end in repeating digits? I'm not sure about 7 or 9 but feel free to check. Narutolovehinata5 ^tccsdnew 10:57, 3 March 2012 (UTC)

If an integer is not divisible by three, it can be written as $3n+1$ or $3n+2$ for some integer n. If you divide this by the three you get $n+{\frac {1}{3}}$ or $n+{\frac {2}{3}}$ respectively. ${\frac {1}{3}}$ and ${\frac {2}{3}}$ have repeating digits, so the answer to your first question is "no". Widener (talk) 12:04, 3 March 2012 (UTC)

The answer to your second question is "yes". 2 is a prime number, but ${\frac {3}{2}}$ does not have repeating digits, for example. 9 is not a prime number by the way. Widener (talk) 12:07, 3 March 2012 (UTC)

Oops, I meant odd numbers. Narutolovehinata5 ^tccsdnew 12:16, 3 March 2012 (UTC)

The decimal representation of a fraction terminates if and only the denominator (with the fraction expressed in its lowest terms) has no prime factors other than 2 and 5. See Decimal_representation#Finite decimal representations. Of course, strictly speaking it ends with the repeating digit zero, and also as a technicality a terminating decimal also has a representation with repeating nines - e.g. 1.5 = 1.499999... AndrewWTaylor (talk) 12:42, 3 March 2012 (UTC)

Any multiple of 5 can be an example, not just the powers of 5. For example, 27/15 = 1.8. The important point is that all the prime factors other than 5 occur in the numerator in sufficient quantity to be cancelled out.--121.74.97.164 (talk) 20:57, 3 March 2012 (UTC)

Note that the only reason 2 and 5 are special here is that they divide 10, the base of the decimal number system. For any base b, the irreducible fractions without repeating digits in base b are those where all prime factors of the denominator are also prime factors of b. PrimeHunter (talk) 21:33, 3 March 2012 (UTC)

The problem lies in the fact that the number we chose as our base system (10) has no real mathematical significance, being of course said to be chosen for no other reason than because it's the number of digits we have on our hands, so it is not actually "designed" to deal with decimals. Primorial base systems such as base 30 would avoid problems with repeating decimals like the ones here bing discussed and highly composite number bases such as base 12 and base 60 would also work to a degree and simplify them up a bit. Robo37 (talk) 19:42, 4 March 2012 (UTC)

Narutolovehinata5, do you consider a number like 1.78234234234... to have "repeating digits"? 96.46.204.126 (talk) 03:58, 7 March 2012 (UTC)

Formal proof that the number of arcs in a tree is one less than the number of nodes.

I understand intuitively why this is the case; for every node other than the one at the top, there is exactly one arc connecting it to its parent. How does one formulate this into a formal proof? Widener (talk) 12:11, 3 March 2012 (UTC)

What you said is the central idea of the proof. Let P be the set of nodes other than the one at the top, and let A be the set of arcs. Then the function which assigns each node to the arc from its parent is a bijection from P to A. Therefore P and A have the same size, so the number of arcs is the same as the number of nodes other than the one at the top. Staecker (talk) 13:01, 3 March 2012 (UTC)

Thanks. The question is actually very technical; it took me a while to figure out what they were really asking. Let $V$ be a nonempty finite set and $E\subset V\times V$ be a symmetric relation such that the following conditions hold: $\forall x\in V,(x,x)\notin E$, $\forall x,y\in V$ there exists a unique sequence $(x_{j})_{j=0}^{k}$ such that $x_{0}=x,x_{l}=y$, $(x_{k},x_{k+1})\in E$ for all k=0,...,l-1, and $\forall i\in \{0,...,l-1\},(x_{i},x_{i+1})\notin \{(x_{j},x_{j+1});j\in \{0,...,l-1\}\setminus \{i\}\}\cup \{(x_{j+1},x_{j};j\in \{0,..,l-1\}\setminus \{i\}\}.$. Prove that ${\bar {\bar {E}}}=2{\bar {\bar {V}}}-2$. Here ${\bar {\bar {A}}}$ means the cardinality of set A. Do you think I could pick one node without loss of generality and call it the node at the top, and then use your method? I still may have a lot of trouble with the technical details (just look at the problem statement!). Widener (talk) 23:43, 3 March 2012 (UTC)

If you have a tree, you can always choose any vertex to be the root, and then have a rooted tree, but this seems like unnecessary work from the construction of a tree that you're given. I think a more straight forward way to go is as follows. First prove that every tree with more than 1 vertex has a leaf (if not then you get either an infinite length path, or a cycle which gives you two distinct paths between two vertices). Then do induction on the number of vertices in your tree by deleting a leaf and its corresponding edge to get a smaller tree. Rckrone (talk) 02:28, 4 March 2012 (UTC)

Actually I take it back. The idea you mentioned originally can be made into a nice argument. Fix any vertex x, and then for each other vertex y, there's a unique trail from y to x. Let f:V\{x} → E map each vertex y to the first edge along the trail to x. Showing that f in injective is pretty easy. To show it's surjective, note that if some edge (u,v) is not in the image, then using that edge gives you a second trail from u to x, which is a contradiction. Rckrone (talk) 05:34, 4 March 2012 (UTC)

That looks good. You have to be a bit careful though. That map you described is not actually surjective; it maps on to exactly half of the elements in E. Still, I think the argument can be modified a bit to work. Widener (talk) 06:26, 4 March 2012 (UTC)

Yeah, I didn't feel like dealing with that. Rckrone (talk) 16:08, 4 March 2012 (UTC)

Standard Deviation and Excel/SPSS

Today I was using Excel for some coursework when I noticed that it was returning a value for standard deviation for three identical numbers, 0.048,0.048 and 0.048. I checked it again with 1,1,1 and it returned a 0 this time, so I tried once again with 0.048 in different cells and still got the same answer: 8.49837E-18. Confused I ran it through SPSS and still received a value for standard deviation. Can anyone please tell me why this is? — Preceding unsigned comment added by 194.82.172.24 (talk) 16:27, 3 March 2012 (UTC)

8.49837E-18 means 0.00000000000000000849837. That is zero, with a slight numerical error due to Excel's algorithm not being perfect. --Tango (talk) 17:36, 3 March 2012 (UTC)

There's a rather good essay on the subject to be found here, including the rather telling line "The most important flaw in basic statistical functions is the way Excel calculates the standard deviation and variance". The maths is a little heavy, but it seems a good read if you're interested in WHY Excel makes errors of this sort. If you're not, the summary is: "My overall assessment is that while Excel uses algorithms that are not robust and can lead to errors in extreme cases, the errors are very unlikely to arise in typical scientific data analysis. However, I would not advise data analysis in Excel if the final results could have a serious impact on business results, or on the health of patients. For students, it’s my personal belief that the advantages of easy-to-use functions and tools counterbalance the need for extreme precision". That is, Excel is normally adequately accurate, but if you need absolute accuracy, use something else. - Cucumber Mike (talk) 22:39, 3 March 2012 (UTC)

The particular issue with the computational formula for the variance was fixed in Excel 2003 and later versions: http://support.microsoft.com/kb/826112 . Qwfp (talk) 11:58, 4 March 2012 (UTC)

I got the same result as the OP using Excel 2010, so whatever specific issue is causing this hasn't been fixed. --Tango (talk) 01:23, 5 March 2012 (UTC)

There's a more fundamental problem in addition to Excel's algorithm being bad. Computers don't use exact real numbers - instead they use limited precision floating point representations. This leads to small "errors". (See Floating point#Accuracy problems) Typical IEEE 754 standard floating point numbers have ~53 digits of precision, or around ± 1×10^-16 for values near unity magnitude. The absolute error should be consistent for values created in a consistent fashion, but may vary based on how the variable is constructed. For example, even a "simple" calculation of "0.33 * 10 - 3.3" in a Python shell results in an answer of 4.44e-016, rather than exactly zero - this isn't a failing of Python, but rather a limitation of how computers store and process reals. -- 71.35.120.88 (talk) 07:34, 4 March 2012 (UTC)

This has been helpful thanks. 194.82.172.24 (talk) 02:30, 8 March 2012 (UTC)

are consistent self-references usually allowed

if you can reach a consistency either way, then is the sentence true:

for example, is "if a t and period is addended to it in case this consistently COMPLETED sentence is true, and F and period is addended to it in case this consistently COMPLETED sentence is false, then this sentence, with its addendum, will contain 18 t's:"

naively, we can count the t's, see there ar 17 in them, which is not 18, and therefore put an F. after the : (the f obviously does not change the total number of T's). Thus the sentence will read: "if a t and period is addended to it in case this consistently COMPLETED sentence is true, and F and period is addended to it in case this consistently COMPLETED sentence is false, then this sentence, with its addendum, will contain 18 t's:F."

On the other hand, we can also consistently complete the sentence thusly: "if a t and period is addended to it in case this consistently COMPLETED sentence is true, and F and period is addended to it in case this consistently COMPLETED sentence is false, then this sentence, with its addendum, will contain 18 t's:T."

so we have a self-referential statement that can be evaluated correctly as either True or False, consistently, and you can check it and obviously it works out. Are self-referencing sentences of this nature allowed in mathematics, or are the above sentences, for some reason, not mathematical? (or not allowed). Even though, to me, they seem straightforward and mathematical.

If they are not mathematical or not allowed, can you "fix" one or both and make them allowed, while retaining the self-referential nature? — Preceding unsigned comment added by 80.99.254.208 (talk) 19:50, 3 March 2012 (UTC)

First, let me point out that you can get a much simpler example: "This sentence is true.". Allowing sentences that refer to themselves tends to create paradoxes (for example, Russel's paradox), so when formalising mathematics, mathematicians tend to take great pains to avoid them. It can still be possible to sneak them in, though. Godel's incompleteness theorem basically relies on this, and Kleene's recursion theorem tends to allow it.--121.74.97.164 (talk) 21:13, 3 March 2012 (UTC)

Actually it's not so much that mathematicians avoid self-reference, as it is that the natural way of formalizing the truth of a sentence of first-order logic does not support self-reference. See for example Tarski's undefinability theorem.

As for the Goedel construction, it's important to distinguish: The Goedel sentence, to the extent that it self-refers, refers to its provability, not to its truth. In some sense the most important takeaway from the Goedel theorems, at a philosophical level, is that provability and truth are different things. --Trovatore (talk) 21:19, 3 March 2012 (UTC)

It's also important to note that even the Godel sentence does not self-refer directly. The Godel construction amounts to assigning a number to every well-formed statement of a mathematical language, and then finding a statement numbered N that makes the assertion: Statement N is not provable. Looie496 (talk) 23:32, 3 March 2012 (UTC)

So whether this indirect Goedel-number-based procedure constitutes true self-reference is perhaps debatable. Still, if it were possible to do the Goedel-number-based thing, but with truth instead of provability, we would have a real problem. That would then mean the sentence would be true if and only if it was false, so we would be able to genuinely embed the liar paradox into mathematics.

But because it's provability, and not truth, there is no such contradiction. To a mathematical realist (aka "Platonist"), the Goedel theorems represent a limitation on the inferential strength of first-order logic, but pose no problem whatsoever to the coherence of mathematical semantics. --Trovatore (talk) 22:15, 4 March 2012 (UTC)