Wikipedia:Reference desk/Archives/Mathematics/2010 September 11

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.

September 11

Markov chains

I am a bit confused about part of the article on Markov chains.

For the chain with transition matrix $P$, the limiting distribution $\pi$ is the solution to $\pi =\pi P$.

Is the stationary distribution simply an initial distribution that is equal to the limiting distribution? Is it possible for there to be a stationary distribution that is not also a limiting distribution? I'm not sure of the distinction. —Preceding unsigned comment added by 118.208.141.67 (talk) 02:55, 11 September 2010 (UTC)

I'm not sure about the exact terminology, but I'd say a "stationary distribution" is one satisfying $\pi =\pi P$, and a "limiting distribution" is one to which the chain always converges. A chain can have many stationary distributions but has either a single or no limiting distribution. The limiting distribution, if it exists, must be stationary, but the converse doesn't hold (unless additional conditions are assumed). Consider the transition matrix ${\begin{bmatrix}0&1\\1&0\end{bmatrix}}$, which has a stationary distribution $(0.5\ 0.5)$ but no limiting distribution. -- Meni Rosenfeld (talk) 17:19, 11 September 2010 (UTC)

basic probability / stats question

There is an big jar containing 1000's of very expensive diamonds and rubies, say $1000 each (i.e. it costs $1000 to draw one sample, so I don't want to draw too many). I want to know the approximate mix in the jar. I hand over $5000 to draw 5 stones, and I get 2 diamonds and 3 rubies. So the immediate guess that the jar has 40% diamonds. But how do I estimate the probability that the jar has more than 20% diamonds, based on this limited experiment? What if I go up to 10 samples? Thanks. 75.62.3.153 (talk) 03:59, 11 September 2010 (UTC)

This sounds like Bayesian inference but you need an initial probability distribution of the ratio for it to work. In statistics you generally ask the question the other way around: What is the probability of getting 2 diamonds and 3 rubies if the jar has 20% diamonds.--RDBury (talk) 05:20, 11 September 2010 (UTC)

Thanks. Good point about needing a prior distribution-- that should make this easier to think about. I'm getting sleepy but the beta distribution article looks relevant. I'll see if I can figure it out for that and for the uniform distribution on [0,1]. 67.119.12.106 (talk) 06:03, 11 September 2010 (UTC)

Maybe I should draw the samples one by one and use the rule of succession to get new estimates after each sample. I could average the result over all permutations of the samples, etc. Hmm. 67.119.12.106 (talk) 06:15, 11 September 2010 (UTC)

The jar contains $\scriptstyle N$ stones of which $\scriptstyle K$ are diamonds and $\scriptstyle N-K$ are not. You buy $\scriptstyle n$ stones of which $\scriptstyle k$ are diamonds and $\scriptstyle n-k$ are not. If you know $\scriptstyle N,n,K$, then $\scriptstyle k$ has the hypergeometric distribution $\scriptstyle p(k|N,n,K)={\frac {{\binom {K}{k}}{\binom {N-K}{n-k}}}{\binom {N}{n}}}$. If you know $\scriptstyle N,n,k$, then $\scriptstyle K$ has the conditional probability distribution $\scriptstyle p(K|N,n,k)$ $\scriptstyle =p(k|N,n,K){\frac {p(K|N,n)}{p(k|N,n)}}$ $\scriptstyle ={\frac {{\binom {K}{k}}{\binom {N-K}{n-k}}}{\binom {N}{n}}}{\frac {\frac {1}{N+1}}{\frac {1}{n+1}}}$ $\scriptstyle ={\frac {{\binom {K}{k}}{\binom {N-K}{n-k}}}{\binom {N+1}{n+1}}}$. Bo Jacoby (talk) 09:18, 11 September 2010 (UTC).

Yes, the beta distribution is great for this problem because it's very easy to update. It has parameters α and β where ${\frac {\alpha }{\alpha +\beta }}$ is your current estimate for the proportion of diamonds, and $\alpha +\beta$ is your level of confidence. Each diamond drawn increases α by 1, each ruby increases β by 1. A uniform distribution is a special case of beta with $\alpha =\beta =1$.

All this assumes there are so many gems in the bag that drawing some doesn't change the proportion. -- Meni Rosenfeld (talk) 17:26, 11 September 2010 (UTC)

The mean value of $\scriptstyle p(k|N,n,K)$ is

$\scriptstyle \mu =nKN^{-1}$

and the standard deviation is

$\scriptstyle \sigma ={\sqrt {nKN^{-1}(1-nN^{-1})(1-KN^{-1})(1-N^{-1})^{-1}}}$.

This is written

$\scriptstyle k\approx nKN^{-1}$$\scriptstyle \pm {\sqrt {nKN^{-1}(1-nN^{-1})(1-KN^{-1})(1-N^{-1})^{-1}}}$.

The mean value and standard deviation of the distribution $\scriptstyle p(K|N,n,k)$ happens to be the same formulas when $\scriptstyle (N,n,K,k)$ is substituted by $\scriptstyle (-n-2,-N-2,-k-1,-K-1)$.

That is

$\scriptstyle K\approx -1-(-N-2)(-k-1)(-n-2)^{-1}$$\scriptstyle \pm {\sqrt {(-N-2)(-k-1)(-n-2)^{-1}(1-(-N-2)(-n-2)^{-1})(1-(-k-1)(-n-2)^{-1})(1-(-n-2)^{-1})^{-1}}}$.

For $\scriptstyle N$=1000 stones in the jar, $\scriptstyle n$=5 stones bought, $\scriptstyle k$=2 diamonds bought, you get $\scriptstyle K$ ≈ 428.429±174.700 diamonds in the jar. The probability p($\scriptstyle K$>200) = p(428±175>200) = p(228>±175) = p(1.3>±1) = 0.8, assuming that the distribution is approximately normal.

The frequency of diamonds among the stones in the jar is

$\scriptstyle KN^{-1}\approx -N^{-1}-(-1-2N^{-1})(-k-1)(-n-2)^{-1}$$\scriptstyle \pm {\sqrt {(-1-2N^{-1})(-k-1)(-n-2)^{-1}(N^{-1}-(-1-2N^{-1})(-n-2)^{-1})(1-(-k-1)(-n-2)^{-1})(1-(-n-2)^{-1})^{-1}}}$

which in the limiting case $\scriptstyle N^{-1}=0$ reduces to the beta distribution formula

$\scriptstyle {\frac {K}{N}}\approx {\frac {k+1}{n+2}}$ $\scriptstyle \pm {\sqrt {\frac {(k+1)(n-k+1)}{(n+2)^{2}(n+3)}}}$.

Bo Jacoby (talk) 21:33, 11 September 2010 (UTC).

Thank you! I tried thanking you earlier with three exclamation points instead of just one, but some silly robot thought that was vandalism ;-).[1] 67.119.12.29 (talk) 01:24, 12 September 2010 (UTC)

Graph of x^2 + y^2 = 1

The graph of x^2 + y^2 = 1 over R is a circle. It's 1 dimensional because R is 1 dimensional. But ... it's natural to think of the graph of x^2 + y^2 = 1 over C = complex plane. I'm guessing it's 2 dimensional since C is 2 dimensional (my prof. says C is 1 dimensional in other math though I don't get that can someone explain?). Anyway if it's 2 dimensional I can see it though I don't know how to prove it. Now my guess was that it's the sphere since a 2 dimensional circle is a sphere. But my prof. tells me it's actually a sphere with 2 points deleted ... But no matter how hard I try (banging my small head against the wall!) I just can't see this. So two questions.

(a) How do you see it visually? (b) How do you PROVE it formally?

And how can you imagine such math because C X C is 4 dimensional so how can you imagine it? Thanks and please take pity on the math illiterate = me! —Preceding unsigned comment added by 203.129.47.43 (talk) 07:22, 11 September 2010 (UTC)

I think you are using "dimension" in several meanings here. The easiest concept of dimension is for vector spaces. The graph of x² + y² = 1 is a subset of R², which is a vector space of dimension 2 over R. If you use the complex representation, |z| = 1 (or (Re z)² + (Im z)² = 1), then the graph is a subset of C, which is also a vector space of dimension 2 over R, albeit with a few extra algebraic properties defined. As far as the vector space properties go, the two are indistinguishable, so the two representations of the unit circle are not different at all. The thing about C having dimension 1 is that you can define vector spaces over any base field, not only over the real numbers. Any field is a vector space over itself, and as such has dimension 1. So as a vector space over C, the dimension of C is 1. It is very important when dealing with vector spaces to know what the base field is, because it can change things like this.

Now, as for the circle (a subset of R²) being 1-dimensional, we're into dimensions of manifolds, which is a different topic, from topology. The circle is a 1-dimensional manifold because, loosely speaking, it locally resembles a line, like the real number line R, which has dimension 1 as a vector space over R. As far as I know, manifolds are only studied in the vector spaces Rⁿ, so the thing about vector spaces taken over C affecting the dimension does not come into play here. I don't know much about topology, but if you are interested, this refdesk has several very knowledgeable people in the area, who will probably be happy to answer your questions. (There are also other concepts of dimension which are useful when describing weirdly-behaving objects like fractals.)

Finally, imagining objects in more than 3 (real) dimensions is of course difficult, and one of the major obstacles for understanding these things. You can visualize a fourth or fifth dimension by animating the object as time progresses, or by using colours, or similar things, but it will never be a really fair depiction of objects in R⁴, C² or similar spaces. Cosmologists, for instance, have to deal with these problems. Often they can enhance the understanding by doing an analogy with a lesser-dimensional space (the actual Minkowski space is 3 spacelike dimensions and 1 timelike, but it is often depicted as 2 spacelike dimensions and 1 timelike, enabling light cones and other interesting phenomena to be visualized). Note that someone living in a 2-dimensional world would have the same trouble depicting the "third dimension", as explored in the classic book Flatland and in the Simpsons episode "Treehouse of Horror VI". 85.226.205.1 (talk) 08:57, 11 September 2010 (UTC)

OK. But can you answer part (a) and (b) of my question? I'm not interested in irrelevant remarks thanks. —Preceding unsigned comment added by 203.129.47.43 (talk) 09:38, 11 September 2010 (UTC)

All right, I might have jumped to conclusions when I assumed that x and y were the real and imaginary parts of a complex number. Are you rather saying that x and y themselves are complex numbers? So that we are defining an object in the vector space C²? Then much more of these questions make sense. 85.226.205.1 (talk) 09:59, 11 September 2010 (UTC)

Yes exactly. Thanks. That's what the interpretation would be over any field wouldn't it so I don't see how the confusion would arise? Why would you consider imaginary and real parts? —Preceding unsigned comment added by 203.129.47.43 (talk) 13:35, 11 September 2010 (UTC)

Because the variables x and y were used. The standard representation of a complex number z is given by z = x + iy where x is the real part of z, and y is the imaginary part of z. In addition to that, your original question said that "it's natural to think of the graph of x^2 + y^2 = 1 over C = complex plane". If x and y are complex variables then you are not considering the complex plane; you have C². — Fly by Night (talk) 20:30, 11 September 2010 (UTC)

Don't insult me. You know what I meant. You now know what I meant. So please answer my question. If you don't know admit you don't know instead of pretending that you're so intelligent thinking you can lecture me like I'm a baby. Please answer my question! —Preceding unsigned comment added by 203.129.47.43 (talk) 00:18, 12 September 2010 (UTC)

Please remember that Reference Desk queries are answered by volunteers. You will get better and quicker answers if you are polite. Throwing out insults like this to a well-meaning editor simply discourages other editors who might have been able to answer your question from responding.

Anwyay, to return to your question: you have a surface or complex manifold defined by

$x^{2}+y^{2}=1$

where x and y are complex numbers. This is a surface with one complex dimension or two real dimensions i.e. it can be parameterised by one complex number or, equivalently, by two real numbers. One possible parameterisation is

$x=\sin(w)$

$y=\cos(w)$

or

$x=\sin(u)\cosh(v)+i\cos(u)\sinh(v)$

$y=\cos(u)\cosh(v)-i\sin(u)\sinh(v)$

where

$w=u+iv$

In the complex w-plane, sin(w) and cos(w) are periodic functions with a single real period of 2π. So this parameterisation wraps the w-plane into a cylinder embedded in C² (this is analogous to how the equivalent real paramaterisation (sin(θ), cos(θ)) wraps the real line into a circle). This cylinder - which is topologically equivalent to a sphere with two points removed - is your manifold. Gandalf61 (talk) 10:56, 12 September 2010 (UTC)

Please note that the OP has been blocked for three months. — Fly by Night (talk) 16:47, 12 September 2010 (UTC)

Evaluating a sum

How do you evaluate $\sum _{r=1}^{n}{\frac {r+1}{(r+2)(r+3)(r+4)}}?$ I think you're meant to convert it to a telescoping series somehow. Wikinv (talk) 07:35, 11 September 2010 (UTC)

Partial fraction decomposition? 67.119.12.106 (talk) 07:51, 11 September 2010 (UTC)

I only have a rudimentary ability to do partial fraction decomposition, and unfortunately I don't see how to do it here. Wikinv (talk) 09:23, 11 September 2010 (UTC)

I suggest putting your rudimentary ability to work on that fraction and seeing what happens. Rckrone (talk) 16:15, 11 September 2010 (UTC)

What you want to do is set ${\frac {r+1}{(r+2)(r+3)(r+4)}}={\frac {A}{r+2}}+{\frac {B}{r+3}}+{\frac {C}{r+4}}$ and then solve for A, B and C (which are constants). Rckrone (talk) 20:16, 11 September 2010 (UTC)

A non-"mathematical" way to get A,B,C is rather than solving the equation, just guess them. Then back-substitute them to see if they fit. If your guess was wrong, the back-substitution will immediately tell you the right values. It's kind of hard to explain but you'll see it if you try it. 67.119.12.29 (talk) 01:26, 12 September 2010 (UTC)

To solve ${\frac {r+1}{(r+2)(r+3)(r+4)}}={\frac {A}{r+2}}+{\frac {B}{r+3}}+{\frac {C}{r+4}}$ for A, B and C, multiply by the denominator getting r + 1 = A(r + 3)(r + 4) + B(r + 2)(r + 4) + C(r + 2)(r + 3) and then be naughty and substitute the forbidden values r = −2, r = −3 and r = −4 to get the easy equations −2+1 = A(−2+3)(−2+4), −3+1 = B(−3+2)(−3+4), and −4+1 = C(−4+2)(−4+3). Bo Jacoby (talk) 08:36, 13 September 2010 (UTC).

A Simple Random Walk

I know I might be pushing my luck asking for help with this question, but it's been driving me crazy for several days now.

I am given a simple random walk, starting at zero, with $S_{n+1}=S_{n}+2X_{n}-1$, with $X_{1},X_{2},\ldots$ a Bernoulli process. So at each step I can move up with probabiliy $p$ or down with probabiliy $1-p.$

If $D_{n}$ is the number of distinct values that the random walk takes on in its first $n$ steps, what is $\mathbb {E} (D_{n})$

I have spent hours drawing up graphs and counting paths, but I cannot get the pattern out. —Preceding unsigned comment added by Damian Eldridge (talk • contribs) 08:45, 11 September 2010 (UTC)

From [2] he shows that for a simple random walk, S_n with equal chance of increasing or decreasing at each step then if $M_{n}=\max _{0\leq i\leq n}S_{i}$ then $E(M_{n})={\sqrt {\frac {2n}{\pi }}}$.--Salix (talk): 17:46, 11 September 2010 (UTC)

Surely it should be $E(M_{n})\sim {\sqrt {\frac {2n}{\pi }}}.$

Anyway, I haven't read the linked paper so I don't know how much of this was already covered, but what I'd do is let $f(n,m,M)$ be the expectation of D given that the range we have already visited is from m to M and we have n steps left. Then it's easy to write recurrence relations for f. Solving them might be harder, but for $p=1/2$ I got empirically that $2^{n}f(n,0,0)=2^{n}\mathbb {E} [D_{n}]$ is OEIS A152548. -- Meni Rosenfeld (talk) 18:14, 11 September 2010 (UTC)

Special Orthogonal Group

OK, so I am having a rather tough time showing that an element of the special orthogonal group for 3x3 matrices must have an eigenvalue of +1. By saying that Ax=tx and taking the modulus of both sides, you can show that |t|=1. Now I have considered the characteristic equation of A and split this into two cases, where ones root is real and two are complex conjugates and another where they're all real. The first case was easy to show that one of the roots must be +1 but I cannot for the life of me work out how to do it for the case where all roots are real. I imagine I want to focus on one approach out of showing all the roots are integers, a root of -1 implies a root of +1 or a root of -1 implies another root of -1, which in turn implies a root of +1 but I can't decide which is best and am getting nowhere. Any offers? Thanks. asyndeton talk 12:27, 11 September 2010 (UTC)

All eigenvalues have modulus 1, so if they are real then they are +1 or -1. If none is +1, then all three are -1. But then the determinant of the matrix is (-1)^3=-1, and it's not in the special orthogonal group. Algebraist 12:43, 11 September 2010 (UTC)

I can't believe I missed that when it's so simple. To think of the hours I wasted... Many thanks. asyndeton talk 17:05, 11 September 2010 (UTC)

Divergence Theorem

I'm using the divergence theorem to calculate the radiation flux through a quadrant of the unit spherical shell, which gives an open surface. I am presented with two options. The first is to close the surface, which seems like hard work, and the second is to just consider the flux through the entire unit spherical shell and divide by four. Is the second approach allowed or is the divergence theorem not linear in that sense? Thanks asyndeton talk 17:09, 11 September 2010 (UTC)

It's just about the integrals - it should be fine provided you can reasonably expect both the quadrant integrals to be a quarter of the whole integrals (i.e. if the function is appropriately symmetric). 95.150.23.75 (talk) 20:34, 11 September 2010 (UTC)

Tabular method of integration by parts

I know how to do this. My question is, do all you know this method? I learned it in high school. But, I am at a Tier II grad school in the US that's pretty good, not amazing or anything, and I just mentioned today to 4 grad students that the calc book we use doesn't have the tabular method in the section on integration by parts, but apparently none of the 4 grad students had ever heard of this method, which I thought was weird. I also told another grad student about it this summer during one of my stat classes and he had never heard of it. The thing is, this method is faster/easier even when I only have to do 1 iteration of integration by parts, let alone 2 or 3 or 4, so it's weird it's not taught. I will be teaching it to my students. StatisticsMan (talk) 23:45, 11 September 2010 (UTC)

I've never heard of it either, at least by that name, but maybe it's a standard technique normally given some other name? 67.119.12.29 (talk) 01:30, 12 September 2010 (UTC)

OK, Integration by parts#Tabular_integration_by_parts. No I'd never seen that technique either, but it doesn't look that useful unless you're treating the AP exam like a sporting event (which I guess is what Stand and Deliver was about). The usual method is conceptually obvious once seen, though a bit slower. The tabular method is just more cruft to remember unless one has reason to be doing such integrals all day long. 67.119.12.29 (talk) 01:57, 12 September 2010 (UTC)

I know I found it very useful recently when I took a couple probability courses where I had to find expected values of X^2 or X^3 or X^4 of some random variable, say exponential random variable. It saves you several minutes of time per problem, and it makes errors much less likely. As I said above, I believe, I think it's even faster just for a one-time integration by parts like $\int _{0}^{\infty }xe^{-x}\,dx$. I also just found a paper that talks about many other reasons it is useful (and also shows that it is not restricted to the case where one of the parts is a polynomial, in fact this is part of what makes it so useful): [3] StatisticsMan (talk) 02:12, 12 September 2010 (UTC)

So, you're looking for a loose poll of Wikipedians? I've learned it in the past, but forgotten exactly how to do it off-hand. I have a Ph.D in applied math from a good state school.SemanticMantis (talk) 01:57, 12 September 2010 (UTC)

I am another math grad student who has never seen this before. Rckrone (talk) 06:19, 12 September 2010 (UTC)

I taught integration by parts for many years, but never by this method, and it wasn't in any of the text books that I used. On reflection, it might have been useful to some students. Dbfirs

Undergrad here; never seen it before. I don't know how anyone can possibly suggest that it isn't useful when multiple applications of integration by parts are required, knowing how long and tedious integration by parts is and how easy it is to make a mistake in the process. This method also allows one to look ahead see much sooner whether the particular track one is taking will lead anywhere. --COVIZAPIBETEFOKY (talk) 13:06, 12 September 2010 (UTC)

2 cents from another math PhD & professor: I had never seen that method until a student showed it to me (they learned it in high school). I still don't teach it in my calculus class, because the pace of the typical university level calculus course doesn't allow it. I spend one lecture (maybe 1.5) on integration by parts, and that's all I can afford. I assume this is why I never learned it in college. Probably also why it works fine for an advanced high-school course, where they typically can spend a whole year doing what I do in a semester, and high school students (and teachers?) absolutely love tricks like this where you can totally forget what you're doing and still get the right answer- thinking just slows you down! Staecker (talk) 01:03, 13 September 2010 (UTC)

I have heard of this, but my experience is that when you have to do repeated partial integrations, it is time to think of using other methods like differentiation w.r.t. a suitably chosen parameter, or defining a suitable generating function. E.g. suppose we want to compute:

$I_{n}=\int x^{n}\exp(x)dx$

Then it makes sense to define:

$F(x,y)=\sum _{n=0}^{\infty }I_{n}{\frac {y^{n}}{n!}}=\int \exp \left[x\left(y+1\right)\right]dx={\frac {1}{1+y}}\exp(xy)\exp(x)$

We can then directly read-off the coefficient of y^n and find the result:

$I_{n}=\exp(x)\sum _{k=0}^{n}(-1)^{n-k}{\frac {n!}{k!}}x^{k}$ Count Iblis (talk) 20:53, 14 September 2010 (UTC)

That's a method I've never seen before, and it seems like it would be very useful. Thanks. StatisticsMan (talk) 15:35, 16 September 2010 (UTC)