Mathematics desk
< May 14	<< Apr \| May \| Jun >>	May 16 >

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.

May 15

Dijkstra's algorithm

Does the tree produced by Dijkstra's algorithm contain the shortest path between any two vertices or only between the starting vertex and another vertex? --107.207.240.197 (talk) 00:10, 15 May 2013 (UTC)[reply]

From a single source to all other vertices, but see the Floyd–Warshall algorithm. 2602:306:33A0:D150:226:8FF:FEE2:4E6A (talk) 01:14, 15 May 2013 (UTC)[reply]

In a triangle the shortest path between two vertices is the line between them. And all three shortest paths together don't form a tree. Dmcq (talk) 13:08, 15 May 2013 (UTC)[reply]

Decomposing a simply-connected space

Say I can produce a simply-connected space Y by gluing together finitely many copies of a space X in some way. Am I able to conclude that X is simply-connected? This seems far too good to be true -- I imagine I am just lacking the imagination to come up with a counter-example. Does anyone have a good one? (...or a proof of the contrary!) Thanks, Icthyos (talk) 17:50, 15 May 2013 (UTC)[reply]

Found a counter-example: take X to be the wedge of a 2-sphere with a 1-sphere. Glue two of them together by sticking the 1-sphere of one copy around a great circle on the 2-sphere of the other copy, and vice versa. Icthyos (talk) 19:04, 15 May 2013 (UTC)[reply]

You can get the fundamental group of a nice union of subspaces by the Seifert-van Kampen Theorem, as the free product of the groups of the subspaces, amalgamated by the fundamental group of their intersection. For your example, you get the trivial group as a free product of two free groups on one letter, amalgamated by the group of a figure 8, their intersection, which is a free group on two letters. Another similar example is gluing two solid tori to get a 3-sphere, as described here, for example. John Z (talk) 05:37, 16 May 2013 (UTC)[reply]

Expected value convergence question

Suppose $X_{1},X_{2},X_{3},\dots$ are identical independent variables that take take value 0 with probability .5 and take value 1 with probability .5. Consider the following: $\lim _{n\to \infty }{\frac {n/2-\sum _{i=1}^{n}X_{i}}{n^{\delta }}}$ . For $\delta =1$ , the law of large numbers tells us this limit almost surely exists (and equals 0). For $\delta =0$ , the limit almost surely does not exist. What's the cut-off value for $\delta$ where the limit ceases to almost surely exist?--80.109.106.49 (talk) 19:16, 15 May 2013 (UTC)[reply]

It seems to me that the Law of the iterated logarithm answers this question - the answer is δ > 1/2. 96.46.198.58 (talk) 21:06, 15 May 2013 (UTC)[reply]

That will do it. Thanks.--80.109.106.49 (talk) 09:34, 16 May 2013 (UTC)[reply]