Wikipedia:Reference desk/Archives/Mathematics/2009 March 15

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 15

Hilbert curve

It is clear (by a self-similarity argument) that the Hausdorff dimension of the Hilbert curve is 2. But what is its topological dimension ? Is it 1 because it is the limit set of a series of curves each of which has topological dimension 1 ? Or is it 2 because it is space-filling ? A reliable source would be useful - I can find not-necessarily-reliable sources for both answers ! Gandalf61 (talk) 09:19, 15 March 2009 (UTC)

As far as I know these concepts (Hausdorff dimensions and the various definitions of topological dimension) are attached to subsets rather that maps; in this case, the subset is just the image of the map, a square; so it's 2.--pma (talk) 09:39, 15 March 2009 (UTC)

That's what I thought. But this on-line textbook, talking about a minor variation on the Hilbert curve, says "Even though its Hausdorff-Besicovitch dimension is a whole number (D = 2) its topological dimension (DT = 1) is strictly less than this". Gandalf61 (talk) 12:08, 15 March 2009 (UTC)

I didn't find (after a very quick search) a definition of (top or HB) dimension for a curve in that on-line book; another possibility is that they mean the dimensions of the graph. In this case, the topological dimension of the graph of the Hilbert curve is 1, for it is a topological invariant, while the Hausdorff dimension is at least 2 (I guess 2 in fact), since in general for a Lipshitz map F we have $\scriptstyle \dim _{HB}(F(A))\leq \dim _{HB}(A)$; here the projection is 1 Lipschitz and maps the graph onto the square; so it's all right if the point was just exibiting a compact subset of an euclidean space with different topological and Hausdorff-Besicovitch dimensions. Nice book by the way; it may still contain some imprecisions. It says:

"This curve twists so much that it has infinite length. More remarkable is that it will ultimately visit every point in the unit square. Thus, there exists a continuous, one-to-one mapping from the points in the unit interval to the points in the unit plane."

Of course the Hilbert curve is definitely not 1-1 from the closed interval [0,1] to the unit square [0,1]x[0,1], and there is no such a curve, for it would be an homeomorphism.--pma (talk) 14:25, 15 March 2009 (UTC)

To be a homeomorphism it would need to have a continuous inverse, which it quite obviously doesn't. I think the map is bijective (the cardinalities are certainly the same, so it's not hard to believe). --Tango (talk) 14:33, 15 March 2009 (UTC)

I don't understand your comment, you are just repeating what I said. Sorry I did not read carefully what you wrote. I repeat: it is not bijective, otherwise it would be a homeomorphism, which is impossible as you are saying--pma (talk) 14:39, 15 March 2009 (UTC)

You are not reading what I said. A homeomorphism is not a "continuous bijection", it is a "continuous bijection with continuous inverse". The Hilbert curve is a continuous bijection without a continuous inverse. --Tango (talk) 14:48, 15 March 2009 (UTC)

Well, no, as you certainly know but are forgetting for a moment, a continuous bijective map between Hausdorff compact topological spaces is always a homeomorphism. The Hilbert curve is not 1-1, although the approximating curves are.--pma (talk) 14:56, 15 March 2009 (UTC)

You're right, I had forgotten that (assuming I ever knew it, which I probably did). After refreshing my memory of the subject, I can confirm you are entirely correct. I think my problem was caused by trying to use intuition to work with limits - never a good plan! The approximating curves are all injective, but the limiting curve is not (although it doesn't actually cross anywhere, just touches tangentially). --Tango (talk) 15:06, 15 March 2009 (UTC)

(rmv indent) Like pma, I don't think the Hilbert "curve" is even bijective. Be that as it may, we all seem to be agreed that the it is not a homeomorphism. So the argument that its image must have topological dimension 1 because the line has topological dimension 1 does not hold. However, I am not certain that I follow the distinction between the image of the Hilbert curve function and its graph. Is the graph the set of points {(t, f(t): 0 ≤ t ≤ 1}, where each f(t) is a point in R², whereas the image is the projection of that set onto the plane t=0 ? Gandalf61 (talk) 15:08, 15 March 2009 (UTC)

Exact; so the image is the square, and the graph is a compact in R³ homeomorphic to the interval [0,1] (again because the map $\scriptstyle [0,1]\ni t\mapsto (t,f(t))$ is continuous and bijective onto the graph, or even simplier, because the projection on the t component is a continuous inverse to it). That the Hilbert curve is not 1-1 can also be seen directly.--pma (talk) 15:38, 15 March 2009 (UTC)

How do I calculate probability of an event occurring consecutively over many repetitions?

I have an event with a 25% chance of occurring, and a 75% chance of NOT occurring. I'm trying to figure out the correct way to find out the odds/% chance of the event NOT occurring 65 times consecutively (or more, let's say 300 times). What is the name of what I'm trying to do, and more importantly, what is the correct formula for accomplishing this?

Sorry for such a simple question, but I was a music major, so math and I just aren't friendly. 74.163.76.31 (talk) 11:34, 15 March 2009 (UTC)

Don't be sorry; the relevant article is binomial distribution. Hope this helps. If you just need the result, the formula is:

P (the event not occurring x times consecutively) = (0.75)^x

--PST 13:32, 15 March 2009 (UTC)

Note that this formula gives the result as a decimal (where 0 means it will never happen and 1 means it will always happen). Multiply the result by 100 to make it into a percentage. StuRat (talk) 14:39, 15 March 2009 (UTC)

Thanks for the informative answer. One tiny problem, though. I've read the article (as well as every other one relevant to probability/statistics, it seems). While I understand the concept, I'll be honest, math and I not being friendly was an understatement. I have no earthly idea whatsoever how to apply the formula to find the answer. It looks simple enough to me, but I have no idea what to do with it.

If I understand you correctly (unlikely), I'm just looking for P = (0.75)⁶⁵ ? Is that right, and if so, how would one enter that on your average scientific calculator? Got a little more insight? :) 74.163.76.31 (talk) 22:14, 16 March 2009 (UTC)

I don't know what calculator you use, but I use Google. Algebraist 22:22, 16 March 2009 (UTC)

On your typical scientific calculator: .75x^y65×100, then hit the equals sign ("="), to get the answer as a percentage. One problem is that this will give a very small number, and it is likely to be in scientific or engineering notation. For example, I got 7.568e-7. This means you need to move the decimal point 7 places to the left. I get .000000768% when I do this. This works out to be so rare that it will only happen once in over 132 million trials of 65 events. For 300 events, the number rises to one so large I don't even know a name for it. StuRat (talk) 03:26, 17 March 2009 (UTC)

For 300 events, it's about one chance in thirty undecillion. Algebraist 13:13, 17 March 2009 (UTC)

Probability in Rummikub

For the benefit of those who don't know the game, I will restate it in more common terms. I have 2 decks of cards, each deck containing one joker, giving a total of 106 cards. I shuffle them together and keep on shuffling until they are randomized.
If I draw 14 cards, what is the probability that I will have exactly 1 pair (same suit and rank). Same for 2 pairs ... up to 7 pairs. Phil_burnstein (talk) 12:23, 15 March 2009 (UTC)

You have to count out the different possibilities. For example, to have ZERO pairs, you need one of each of the 13 ranks, plus one joker. How many ways can that happen? Well, there's 4 possible suits for each non-joker, plus 2 jokers. Then for one pair, look at how to get 13 cards with no pairs, plus a 14th card paired with one of the earlier 13, etc. Divide each of those by the ${104 \choose 14}$ possible deals. —Preceding unsigned comment added by 207.241.239.70 (talk) 02:12, 17 March 2009 (UTC)

Assuming that the deck consists of 53 pairs (52 pairs same suit, same rank plus 1 pair of jokers) I get:

Probability of 0 pairs ... 37.26%

Probability of 1 pair ..... 42.38%

Probability of 2 pairs ... 17.06%

Probability of 3 pairs ... 3.05%

Probability of 4 pairs ... 0.25%

Probability of 5 pairs ... approx 1 in 12,000

Probability of 6 pairs ... approx 1 in 10⁶

Probability of 7 pairs ... approx 1 in 7 × 10⁸

So you are 50 times more likely to guess all six numbers in the UK National Lottery than you are to get seven pairs in a Rummikub hand. Gandalf61 (talk) 09:13, 17 March 2009 (UTC)

A more complete answer: Lets solve the problem of calculating the probability of getting $s\,$ pairs in $(2n)\,$ cards drawn out of $m\,$ pairs of cards (a total of $(2m)\,$ cards). Your question would be the case $m=53\,$, $n=7\,$, and $s=0,1,\dots 6,7\,$. Lets begin with the simpler case $s=0\,$. What's the number $n_{0}^{m,n}\,$ of different ways can we do that? That's simmilar to computing how many ways we can draw $2n\,$ cards out of a deck with $m\,$ different cards (since no repeats are allowed) which is given by ${m \choose 2n}$, but with the aditional caveat that each card could belong to either one of the two decks (of $m\,$ cards each). That gives us an extra factor of $2^{2n}\,$, and we get $n_{0}^{m,n}=2^{2n}{m \choose 2n}\,$, and the probability $p_{0}^{m,n}={\frac {n_{0}^{m,n}}{N}}\,$ where $N={2m \choose 2n}$ is the total number of possible ways we could have drawn the cards.

$p_{0}^{m,n}=2^{2n}{m \choose 2n}{2m \choose 2n}^{-1}={\frac {2^{2n}m!(2m-2n)!}{(m-2n)!(2m)!}}\,$.

Now for the general case, the number $n_{s}^{m,n}\,$ is given by the number of ways we can get $s\,$ pairs out of $m\,$ possible times the number $n_{0}^{m',n'}\,$ of drawing the remaining $2n'=2n-2s\,$ out of the remaining $2m'=2m-2s\,$ deck without any extra pairs.

$n_{s}^{m,n}={m \choose s}n_{0}^{m-s,n-s}={m \choose s}2^{2n-2s}{m-s \choose 2n-2s}$,

and the probability $p_{s}^{m,n}$ is given by

$p_{s}^{m,n}={\frac {n_{s}^{m,n}}{N}}={m \choose s}2^{2n-2s}{m-s \choose 2n-2s}{2m \choose 2n}^{-1}={\frac {2^{2n-2s}m!(2n)!(2m-2n)!}{s!(2n-2s)!(m+s-2n)!(2m)!}}$.

That formula can be used to reproduce Gandalf's table. Dauto (talk) 00:22, 18 March 2009 (UTC)