Wikipedia:Reference desk/Archives/Mathematics/2007 September 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.

September 3

Random walk

Are you able to explain, in a way that I can understand, why the following, from the article Random walk, is true?

"Imagine now a drunkard walking randomly in a city. The city is infinite and arranged in a square grid, and at every intersection, the drunkard chooses one of the four possible routes (including the one he came from) with equal probability. Formally, this is a random walk on the set of all points in the plane with integer coordinates. Will the drunkard ever get back to his home from the bar? It turns out that he will (almost surely). This is the high dimensional equivalent of the level crossing problem discussed above. However, in dimensions 3 and above, this no longer holds. In other words, a drunk bird might forever wander the sky, never finding its nest. The formal terms to describe this phenomenon is that a random walk in dimensions 1 and 2 is recurrent, while in dimension 3 and above it is transient. This was proven by Pólya in 1921." A.Z. 03:16, 3 September 2007 (UTC)

Well, one-dimension is easy -- a random walk in one dimension will "always" get you to any point along that line -- Think of moving left as getting heads when flipping a coin, and moving right as getting tails. You being x units from where you started is equivalent to having x more heads flipped than tails -- or vice versa in the other direction... and the chance that during an infinite coin flipping sequence you will have x more heads than tails at some point is 1.

As for higher dimensions -- you'll need someone who understands this a little better than I do. Gscshoyru 03:42, 3 September 2007 (UTC)

Thank you. Isn't the two dimension relatively easy as well, if there is a grid and only four possible routes, like in that infinite city? The coin would be a dice with four sides (for instance, 1 means up, 2 means down, 3 means right and 4 means left, relatively to the grid), and your vertical position would depend on how many 1s there there have been more than 2s and your horizontal position would depend on how many 3s there have been more than 4s. Can you now prove that I'm going to eventually occupy all infinite places on the grid? A.Z. 03:51, 3 September 2007 (UTC)

I see that the chance that I'll occupy all infinite vertical positions and all infinite horizontal positions after an infinite dice throwing sequence is 1. I still don't know how the chance that I'll occupy all positions equals 1. A.Z. 04:00, 3 September 2007 (UTC)

I'd say it's not. The chance of occupying any particular grid point is the chance of occupying the X coord times the chance of occupying the Y coord (at the same time). If we had finite probabilities, then a 1/10 chance of ever occupying an X coord and an independent 1/10 chance for the Y coord would give a 1/100 chance of hitting that grid point. Why, then, does the drunk find it home ? I'd speculate the probabilities go up dramatically if the target grid point is near the starting grid point, which must be the assumption for this problem. StuRat 13:48, 3 September 2007 (UTC)

That's not the assumption for this problem. In two dimensions it has been proven that an infinite random walk will get you everywhere on the grid at some point. However, I don't really understand why, or why it isn't true for 3 dimensions. The probability you get to any horizontal position is 1, the probability you get to any vertical position is 1, so that would imply the probability of 1 for 2 dimensions... but it's also a probability of 1 you will get to a certain height in three dimensions, which would seem to imply that the probability of getting home in 3 is also 1, but it isn't. Gscshoyru 13:54, 3 September 2007 (UTC)

Okay, I didn't know if to comment about this, since I don't remember the exact proofs, but seeing as there is some confusion here... Gscshoryu's argument is certainly not the reason why 2D random walk is recurrent. Yes, the probability to reach any horizontal position at least once is 1, the same for vertical, but to reach a certain point you must be at the specified horizontal and vertical position at the same time, which is not a priori guaranteed. However, it does end up to be 1, and I think the proof goes something like: Consider first a "restricted" random walk, which takes place only on an N*N square, and stops when an edge of the square is reached; estimate the probability that you will ever land on a given point (with known methods such as conditioning on first move); calculate the limit as N goes to infinity (it is 1). For 3D, however, when we do the same thing, it is just as easy to go astray (move N steps in any direction) but harder to reach a specified point (since there are more points), and when you do the calculations the probability doesn't tend to 1.

Of course, any good book about Markov chains, stochastic processes etc. should be able to provide more details. -- Meni Rosenfeld (talk) 15:31, 3 September 2007 (UTC)

Oops... yeah I totally didn't mean what I said there. Somewhere in my paragraph there should be an "according to your logic" (having to do with the 1/10 * 1/10 be 1/100). My argument was meant to show that if that argument was true for 2 dimensions, it'd be true for 3 and beyond, which isn't true, as stated in the article. I just didn't phrase what I was doing properly. Thanks for catching that, Meni. Gscshoyru 15:43, 3 September 2007 (UTC)

Do we have to hand a probability for 3D? It would be quite interesting if it were neither 0 nor 1. (Pólya's paper doesn't seem to give one, although I can read only the math in it!) --Tardis 17:17, 4 September 2007 (UTC)

But we know that it is neither nor 0 nor 1. I see no reason why calculating the exact probability should be a problem. -- Meni Rosenfeld (talk) 18:18, 4 September 2007 (UTC)

Yeah, if I had read the comments more carefully, I would have understood that was your intention, sorry. -- Meni Rosenfeld (talk) 16:21, 3 September 2007 (UTC)

Just an observation. Not only the drunkard will intersect any d-1-hyperplane in $\mathbb {Z} ^{d}$ with probability 1, but he will intersect it infinitely many times with probability 1. (Igny 16:48, 3 September 2007 (UTC))

So drunk he don't even know when he is home. —Bromskloss 19:54, 3 September 2007 (UTC)

I have edited Igny's post so that it looks less like $2^{d}$. -- Meni Rosenfeld (talk) 21:56, 3 September 2007 (UTC)

(outdent) I do not have my notes anymore about this, but at one time I had a proof for almost surely returning to the origin in 1D and 2D, and that the prob for doing so in 3D was less than 1. I remember that one of the key ideas, if not the key idea, was using Stirling's expansion of the Gamma function. Not sure if this jogs anyone else's memory, but hope it helps. Baccyak4H (Yak!) 14:21, 4 September 2007 (UTC)

Stirling's expansion? That doesn't ring a bell. I recall it having something to do with the divergence of $\sum 1$ (for 1D) and $\sum {\frac {1}{n}}$ (for 2D), compared to the convergence of $\sum {\frac {1}{n^{2}}}$ (for 3D).

Anyway, this is ridiculous, I will go to the library tomorrow and take a look at a relevant book. -- Meni Rosenfeld (talk) 18:18, 4 September 2007 (UTC)

More likely the convergence or divergence of Σ n^−d/2, where d is the dimension.  --Lambiam 22:36, 4 September 2007 (UTC)

Looking at the page, it was Stirling's series that I meant. The one with (f(n)) * (1 + 1/(12n) + ...). And I do think that after playing around with it in the right contexts, one does come up with Zeta function-like expressions as you have. Baccyak4H (Yak!) 18:33, 4 September 2007 (UTC)

Yes, I think Stirling's series and expansion are synonyms - I linked to Stirling's approximation only because, well, that is the article the information is in. In any case, since I know of no direct connection between the series I mentioned and Stirling's series, I wonder if you are now saying that both appear, any one of them, or just the Zeta. Unless it is the latter, this must be a different proof from what I was taught. -- Meni Rosenfeld (talk) 18:40, 4 September 2007 (UTC)

Surely the probability in 3D depends on how far apart the starting point and target points are. If they were in adjacent nodes, for example, we would have:

Steps  Walks leading  Total walks   
taken  to the target  possible        P
-----  -------------  -----------   ------
  1         1              6        0.1667
  2         0             36        0.0000
  3         4            216        0.0185

So, just for the first 3 steps I get a total P of 0.1852. For a starting node and ending node a million units apart, I suspect the total P is much lower. StuRat 21:32, 4 September 2007 (UTC)

Yes, indeed. My usage of singular "probability" may have been confusing; what I meant is, the probability for a given target coordinate -- Meni Rosenfeld (talk) 21:52, 4 September 2007 (UTC)

Apparently, my memory is playing tricks on me. The proof found in "Markov Chains" by J R Norris is nothing like what I remember, and virtually none of my observations above hold for it. Baccyak4H and Lambiam had more truth in their comments.

First, some theory: For a connected (in the sense that any state can lead to any other) Markov chain, denote by $p_{n}$ the probability of being back at the starting point after n moves. Then exactly one of the following possibilities hold:

1. The chain is recurrent; For any state, the probability of visiting it infinitely many times is 1; $\sum p_{n}=\infty$.
2. The chain is transient; There are states (for a random walk, this is any state other than the origin) for which there is a positive probability for never visiting; $\sum p_{n}<\infty$. (note: The usage of "never" instead of "only finitely many times" is a part of the theorem.)

Now, the outline of the proof is: For a random walk in d dimensions, a simple combinatorial argument, followed by an application of Stirling's approximation (no need for the series), shows that $p_{n}$ is roughly proportional to $n^{-d/2}$ (in fact, it is 0 for any odd n, but that is inconsequential). So for $d\leq 2$, $\sum p_{n}=\infty$ and the chain is recurrent; for $d\geq 3$, $\sum p_{n}<\infty$ and the chain is transient. -- Meni Rosenfeld (talk) 11:19, 5 September 2007 (UTC)

Now please explain this in a way that the OP can understand.  --Lambiam 17:30, 5 September 2007 (UTC)

Well, if the OP is interested in a proof he can understand, then I cannot do that without reconstructing here the theory of Markov chains from scratch. If he is interested in an intuituve explanation, then the best one I can give is that 3D space is much bigger than the 2D plane, so it is easy to get lost. -- Meni Rosenfeld (talk) 18:02, 5 September 2007 (UTC)

For anyone who wants it, the entire relevant chapter of Norris's book mentioned above is available on his website: [1]. Algebraist 17:43, 6 September 2007 (UTC)

Approximation of manifolds by tangent spaces

Friends told me that the tangent space T at a point m of a manifold M is the first order LOCAL approximation of M at m. In what way and in what sense that this is true based on the definition of Tangent_space#Definition_as_directions_of_curves? Thank you in advance. twma 08:35, 3 September 2007 (UTC)

This is a bit much to explain here. Briefly, consider the torus defined by the following parametric equations.

${\begin{aligned}x&=(R+r\cos v)\cos u\\y&=(R+r\cos v)\sin u\\z&=r\sin v\end{aligned}}$

For any (u,v) pair we have a point on the surface, and for any curve in the uv plane we have a curve on the surface. If the uv curve goes through (^π⁄₂,^π⁄₃) then the surface curve goes through (0,^r⁄₂+R,^r⁄₂√3). One of these curves varies u while holding v fixed; as it passes through the point in question its tangent is −(^r⁄₂+R,0,0). Another curve varies v while holding u fixed; as it passes through the point in question its tangent is (0,−^r⁄₂√3,^r⁄₂). These two tangent vectors happen to be perpendicular to each other, and every other tangent vector at that point is a linear combination of them. (Experiment!) Thus we have a plane tangent to the torus at the chosen point, which is something like what we mean by a tangent space. Since our example manifold is two-dimensional (the torus is a surface), each of its tangent spaces is a two-dimensional vector space. In formal theory, the tangent space is an abstract vector space that is not a part of some ambient space in which the manifold is embedded; but for this example it is convenient to visualize both the manifold and the tangent space within three-dimensional space. However, the "intrinsic" approach is essential when dealing with abstract differentiable manifolds.

For comparison, we can write an implicit equation for the torus.

$0=(x^{2}+y^{2}+z^{2}+R^{2}-r^{2})^{2}-4R^{2}(x^{2}+y^{2})\,\!$

The right-hand side is a function of x, y, and z, and at any point of the surface the gradient of the function will be a vector perpendicular to the surface. At the point we have examined, the gradient is (0,1,√3) times 2rR(r+2R). We can easily verify that all our tangent vectors will, indeed, be perpendicular to this, as expected. This may help build our intuition, even though it is a less powerful approach. As well, a computer graphics rendering of the torus will bounce light off the surface at each point by, in effect, approximating the surface there with its tangent plane. The fact that such images have the shading of a physical torus confirms the mathematics of tangent planes as local linear approximations. --KSmrq^T 17:34, 3 September 2007 (UTC)

Thank you very much for the explanation which is outside the framework of the formal definition of Tangent_space. Suppose that a point x in M is near the base point m. How do we find two cuves p,q in the tangent space such that m,x are approximated by p,q respectively. Why we say that the approximation is of first order in terms of Tangent_space? Thank you in advance. twma 03:21, 4 September 2007 (UTC)

Your follow-up question suggests a misunderstanding. I described a map from the (u,v) plane to the torus. The tangent plane is not the (u,v) parameter plane. My curves are curves on the surface, parameterized by u and v. The tangent space consists of tangents to such curves. Each point of the manifold has its own separate and unique tangent space. For the torus, we considered just one parameter plane for the whole surface. For most manifolds, we require multiple parameter spaces, and any point of the manifold is likely to have more than one parameter space covering it. Fortunately, the tangent space is well-defined and independent of which parameter space we happen to be using. As a simple example, suppose we parameterize the torus by a unit square, but then use 2πu and 2πv in the mapping; the space of all possible tangent vectors at a point does not change.

We do have a clever gadget called the exponential map that allows us to convert a given tangent vector into a point of the manifold. Essentially, it uses the tangent vector to say what direction to go and how fast to go for a fixed unit of time. For example, on the Earth standing at Greenwich, England we could say "go southeast at 35 km/h for one hour". As we choose different directions and speeds, we arrive at different points.

Personally, I would say that a tangent plane (embedded in 3D) is a first-order approximation to the surface, but I would carefully avoid saying such a thing about the abstract tangent space. The plane consists of points; the space consists of vectors. The points of the tangent plane are embedded in the same ambient space as the surface; the vectors of the tangent space have a separate, abstract existence. As for the meaning of "first-order", that simply means we considered only first derivatives. If we considered second derivatives as well, the tangent plane would be replaced by a tangent quadric, perhaps a one-sheeted hyperboloid or perhaps an ellipsoid, depending on which point of the torus we are approximating. That doesn't work for abstract manifolds, where instead we introduce the idea of a curvature tensor. Let's save that conversation for another day. :-) --KSmrq^T 15:37, 4 September 2007 (UTC)

To keep things simple, let's look at the case of a curve in 2-dimensional Euclidean space, specifically a function $f:x\rightarrow y$, under the assumption that the function is smooth enough that its image forms a 1-dimensional manifold. Then, at a given point $x_{0}$, the function can be written as a Taylor series, as follows:

$f(x)=f(x_{0})+f'(x_{0})(x-x_{0})+{\frac {f''(x_{0})}{2}}(x-x_{0})^{2}+{\frac {f'''(x_{0})}{3!}}(x-x_{0})^{3}+\ldots$

Where a dash represents a differentiation with respect to x. Then we can also write this as a polynomial of order n and an error term of order O(xⁿ) (yes I know the word "order" is being used in two slightly different ways). Because the second part is asymptotically zero as $x\rightarrow x_{0}$, we can consider the polynomial part to be an "nth-order approximation" to f near $x_{0}$, and in particular the first order approximation is

$f(x)=f(x_{0})+f'(x_{0})(x-x_{0})+{\mathcal {O}}(x^{2})$, or just

$f(x)\approx f(x_{0})+f'(x_{0})(x-x_{0})$

where the right-hand side is the equation of the tangent line to f at $x_{0}$. We use the term "first order", or "nth order" in the more general case, because the result is an "nth order" polynomial, i.e. one of degree 1. If you then generalise the above into functions of vectors, then you get equivalent results involving tangent planes and higher dimensional concepts. Confusing Manifestation 06:06, 4 September 2007 (UTC)

I have a problem understanding the definition given at Tangent space#Definition as directions of curves, which I've registered on the talk page of the article.  --Lambiam 07:50, 4 September 2007 (UTC)  Issue resolved.  --Lambiam 13:37, 4 September 2007 (UTC)

Suppose that a point x in M is near the base point m. How do we find two cuves p,q in the Tangent_space such that m,x are approximated by p,q respectively? How do we express the nearness between p,q as a first order approximation in term of the nearness between m,x? Please stick with the ABSTRACT framework of Tangent_space. In particular, there is no embedding space of M. As a result, the higher dimensional tangent PLANE at m is not defined. Thanks for the enthusiasm but I do not believe that my questions have been answered. Looking forward to hearing more satisfactory explanation from you soon. Thank you in advance. twma 07:02, 5 September 2007 (UTC)

I have already told you that you are asking a question based on a misunderstanding. And I have told you about the exponential map, which you can use to map tangent vectors to points. If we use the tangent space at m, the tangent that exponentially maps to m is the zero vector. This should be obvious by now, and the fact that you keep asking for curves suggests you are stuck in a mental framework that you must first discard before you truly grasp the correct way of seeing things.

My guess is that you are looking at the idea of defining tangent vectors as equivalence classes of curves; but the tangents are not the curves, and the curve points are points of the manifold (in the version I see in the article as I write). We can easily define a curve giving us a zero vector, namely γ₀(t) = m; but this is only one of many possible curves in the desired equivalence class.

For comparision, think about real numbers. We can define these using Dedekind cuts or Cauchy sequences or simply using axioms, but in ordinary practice we discard the scaffolding and just work with the reals as things in themselves. The tangent space article explains three different ways to approach the idea of a tangent space, but when we work with tangent spaces we usually don't need to refer to any particular construction.

We have seen a curve of M that passes through m and is in the equivalence class that we may call a zero vector in the tangent space. Now suppose x is a point sufficiently near m, and let γ₁ be a geodesic curve such that γ₁(0) = m and γ₁(1) = x. This will serve as a representative curve in that class of curves that we call v, where v is a tangent vector in the tangent space at m such that exp(v) = x.

Do you now see the problem with your question? If not, I think it's time you picked up a proper textbook instead of trying to learn differential geometry from a brief Wikipedia article or two. A wonderful readable survey is Marcel Berger's recent book, A Panoramic View of Riemannian Geometry (ISBN 978-3-540-65317-2); however, it's not really intended as a textbook. You could try something like Bishop and Goldberg's Tensor Analysis on Manifolds (ISBN 978-0-486-64039-6), Spivak's more challenging Calculus on Manifolds (ISBN 978-0-8053-9021-6), or do Carmo's Riemannian Geometry (ISBN 978-0-8176-3490-2). But don't expect an answer to your question; for an abstract Riemannian manifold the tangent space is used for many things, but not really as a "first-order approximation" to the manifold itself, an idea makes little sense in that setting. --KSmrq^T 23:00, 5 September 2007 (UTC)

Thanks to KSmrq^T that "are asking a question based on a misunderstanding" and that "don't expect an answer to your question". So my conclusion is that there is no suitable answer to the question that people claim. By the way, when I wrote p, I mean the equivalent class [p] containing p. Thanks again. twma 06:19, 6 September 2007 (UTC)

Commonwealth Star - Australian National Flag

I need to know the area of the Commonwealth Star in the above diagram, in terms of A, where A is the length of the flag:

• The star has 7 points, the vertices of which are on a circle whose diameter is 3/20 of A
• the inner diameter is 4/9 of the outer diameter.

I want an answer that I could easily generalise to calculate the areas of the smaller stars on the flag as well. Thanks. -- JackofOz 14:07, 3 September 2007 (UTC)

Divide the star into 7 rhombi kites, each with a vertex at the common centre of the two circles. If the radius of the larger circle is r₁ and the radius of the smaller circle is r₂ then the diagonals of each rhombus kite are r₁ and 2r₂sin(180/7), so the total area of all 7 rhombi kites is

$A=7r_{1}r_{2}\sin(180/7)\approx 3.04r_{1}r_{2}$

Gandalf61 14:31, 3 September 2007 (UTC)

Is each shape a rhombus or more generally are they Kite (geometry)? It seems that they would only be rhombi for a particular ratio of r1 and r2. This does not affect the area formula though. --Salix alba (talk) 14:58, 3 September 2007 (UTC)

Yes, they are indeed kites, not rhombi. Fixed above. Gandalf61 15:22, 3 September 2007 (UTC)

Thanks for that. Now, why is the smaller diagonal = 2r₂sin(180/7)? The angle subtended by the centre is 360/7, isn't it?-- JackofOz 07:22, 4 September 2007 (UTC)

The easiest way I see to analyze this (I'll give the case for an n-pointed star) is to draw the n lines connecting the centre to each of the n "inner" vertices, as well as the n lines from the centre to the n "outer" vertices (the points). This dissects the star into 2n congruent triangles, so the total area is 2n times that of an individual triangle. A kite is two mirrored triangles pasted together. Pick any of these triangles, and let C be the centre, A the inner vertex and B the outer vertex. Then |CA| = r_i, the radius of the inner circle, and |CB| = r_o, the radius of the outer circle. Putting φ = 360°/(2n) = π/n, the angle ∠ACB at vertex C then equals φ. If h is the distance from A to the line CB (the length of the perpendicular, and half the size of the transverse kite diagonal), then the triangle's area is given by ¹/₂h·|CB|. Now h = |CA|·sin φ. Putting everything together, you get a total are of 2n × ¹/₂h·|CB| = n·r_i·r_o·sin (π/n).  --Lambiam 08:23, 4 September 2007 (UTC)

Thanks, Lambiam. -- JackofOz 02:03, 5 September 2007 (UTC)

Could it not also be done by dividing the star into a heptagon and seven triangles? — Michael J 01:34, 5 September 2007 (UTC)

Sounds like an elegant approach. What would be the formulae for the heptagon and a triangle? -- JackofOz 02:03, 5 September 2007 (UTC)

Let's see now... By the diagram, the inner radius is ⁴/₉ of the outer. So if R_i = ⁴/₉ R_o, then R_o = 2.25 × R_i. If we assume an inner diameter of 1, then the outer diameter is 2.25. A heptagon inscribed inside the unit circle would have sides of S_hep ≈ 0.4316. According to the heptagon article, A_hep ≈ 3.63391 S_hep². Thus, the area of the heptagon A_hep ≈ 0.677 units².

Now onto the triangles. The base of each triangle is the same as each side of the heptagon, B_tri ≈ 0.4316. As for the altitude of each triangle, it is the distance from the edge of the inner circle to the edge of the outer circle, or 0.625. Calculating the area of each triangle, A_tri ≈ ½(0.625 × 0.4316) ≈ 0.1349 units².

The total area of all the triangles, therefore, is A_tri ≈ 7 × 0.1349 ≈ 0.944 units². Add that to the area of the heptagon to get the total area, thus: A_star ≈ 0.944 + 0.677 ≈ 1.621 units².

— Michael J 03:41, 5 September 2007 (UTC)

You lost me at "A heptagon inscribed inside the unit circle would have sides of $S_{hep}\approx 0.4316$." Where does that info come from? I'm more interested in the formulae than the numerical values, but thanks anyway. -- JackofOz 03:50, 5 September 2007 (UTC)

It's getting a bit complicated for me, too. — Michael J 04:27, 5 September 2007 (UTC)

I haven't really followed the discussion, but regarding the last point: The side of a regular heptagon inscribed in the unit circle is the base of an isoceles triangle with sides 1, 1 and an angle between them ${\tfrac {2\pi }{7}}$. By the cosine law, the side of the heptagon will be ${\sqrt {1^{2}+1^{2}-2\cos {\tfrac {2\pi }{7}}}}\approx 0.8678$. -- Meni Rosenfeld (talk) 21:10, 5 September 2007 (UTC)

which is equal to $2\sin {\tfrac {\pi }{7}}$.  --Lambiam 21:33, 5 September 2007 (UTC)

Kite Prism

Does a "kite prism" have a special name, or is this name correct? For some reason it just doesn't sound right. Thanks. Ben Tillman 17:37, 3 September 2007 (UTC)

With about 3,000 Google hits, it seems to be the name of a common kind of chandelier crystals. ←Ben^B4 02:45, 4 September 2007 (UTC)

I seem to remember hearing the Gyrobifastigium descibed as a kite prism, or maybe I imagined that?87.102.81.184 16:13, 4 September 2007 (UTC)

A gyrobifastigium isn't a prism at all. It's a Johnson solid (which specifically doesn't include prisms). — Daniel 22:57, 4 September 2007 (UTC)