Wikipedia:Reference desk/Archives/Mathematics/2012 September 8

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 8

"excessive" shuffling

One of the regulars in my weekly bridge game complains that I shuffle the deck too many times, leading to perverse distributions. Should I take it seriously? —Tamfang (talk) 05:53, 8 September 2012 (UTC)

Well, I suppose certain shuffling patterns might be self-reversing. Let's say you just cut the deck in half, then put the top half on the bottom. The next time you do that, you should reverse the cut, if you manage to cut it in exactly the same spot. However, the odds of you having such a self-reversing shuffle seem quite low. Otherwise, if your shuffle truly randomizes the cards, then repeating it shouldn't make them any less random, on average. StuRat (talk) 06:03, 8 September 2012 (UTC)

Disclaimer: What I'm about to relate was learned by word of mouth, so may be apocryphal. When bridge software was first being developed, the programmers initially thought they had a bug with their shuffling algorithm, because they kept getting very unusual distributions. So they went back and picked over the code, but there was no problem with it. It turns out that when shuffling by hand, most people do a very poor job of randomizing the deck, and so the distributions seemed odd because the programmers were all used to insufficiently randomized decks. So it's possible that your shuffling is leading to unusual distributions, but the fault lies with everyone else, not with you.--121.73.35.181 (talk) 06:34, 8 September 2012 (UTC)

Well a poorly shuffled deck is more likely to give interesting sequences in the cards and a more entertaining game. --Salix (talk): 09:20, 8 September 2012 (UTC)

Actually I think a poorly shuffled deck tends to give less distributional hands. You probably don't notice it except in the tails, which means you probably don't notice it — maybe you don't get as many nine-card suits, but then, how many do you expect?

(In the extreme case, say you don't shuffle at all. Then any trick in which everyone followed suit, results in one card of that suit to each player.) --Trovatore (talk) 10:26, 8 September 2012 (UTC)

Some expert bridge players can anecdotally do a perfect shuffle, which after a number of such shuffles (8, I think it was) I've heard can return the deck to its original state. Under the assumption of adequately unpredictable shuffling, the claim can be ignored as the distribution will become more random with each shuffle. Under the assumption of chosen shuffles (are you a card sharp?), the number of shuffles hardly matters: the shuffler can in principle predict (and control) the result. — Quondum 06:46, 8 September 2012 (UTC)

Here is a source for what 121.73.. wrote. Seven shuffles should be enough to mix a deck of cards thoroughly. Players may not like it because of odd distributions, or they may have another reason to prefer less shuffling ...

• "... These players had figured out that the cards were not being randomly shuffled, and that they could predict the distributions of cards by knowing what the deck looked like at the end of the previous hand." Ssscienccce (talk) 00:21, 9 September 2012 (UTC)

This is really interesting — led me to the Persi Diaconis article and his "seven shuffles" result. It says that after seven shuffles, the total variation distance falls below 0.5 and then is halved every shuffle. If I've correctly understood what that means (which I'm not certain), then in order to be sure you had about the right probability for a nine-card suit, you'd have to shuffle roughly 18 times.

According to our bridge probabilities article, the probability of a nine-card suit is 0.00037, which means 2700-to-1 against. I think I've had about three nine-card suits in my life, which you'd expect in about 5000 hands. I think I've played more than that but I'm not sure (it's been some time since I've played at all); anyway I can't claim that the number is too high or too low with any good statistical significance. --Trovatore (talk) 08:44, 9 September 2012 (UTC)

It could even be that the effect this player is noticing is that your shuffling is actually more random than other people's in the group. It's possible that by shuffling too few times, the suits get distributed more evenly than random (since they'll tend to be clumped after a hand and then spread out at regular intervals). These distributions might feel more random because there's less variance in hand strength, but aren't. I've heard of people complaining about the shuffling in online games (which should be much closer to random than human shuffling), because they have a false conception of what random should look like. That said, most likely everyone's shuffling is fine and it's just confirmation bias on the part of this other player. Rckrone (talk) 01:15, 9 September 2012 (UTC)

Sorry, didn't read carefully that 121.73.35.181 already made the same point. Rckrone (talk) 15:18, 9 September 2012 (UTC)

Tesseract

i am looking for information to help me better understand the tesseract and the 4D. — Preceding unsigned comment added by 205.142.178.36 (talk) 19:59, 8 September 2012 (UTC)

Rotation of a tesseract about a plane

See the article tesseract, it's great. You can also read Flatland by Abbott and watch Carl Sagan's Cosmos episode 10, "The Edge of Forever." available on line. μηδείς (talk) 20:09, 8 September 2012 (UTC)

As long as we're referencing works of fiction, check out —And He Built a Crooked House by Heinlein. In addition to being a very entertaining (well, at least entertainingly written) story in its own right, the action takes place in rooms comprising the (hyper)faces of a tesseract, and the description of how they are connected is meticulously accurate (I worked it out). (The opening passage about Americans, Californians, Angelenos, Hollywood residents, Laurel Canyon, Lookout Mountain Avenue, and finally the protagonist, is worth memorizing.) --Trovatore (talk) 21:41, 8 September 2012 (UTC)

Possibly of interest, one of my favorite Youtube movies shows the 120-cell (which is to the tesseract as the dodecahedron is to the cube) as a tiling of spherical 3-space. —Tamfang (talk) 04:37, 9 September 2012 (UTC)

Star Trek Special Effect

At time signature 18:12 on this Star Trek episode http://www.youtube.com/watch?v=hornvnjML88 you see the classic yellow-and black rotating interference band from the vintage Star Trek by Spock's head. I know it is caused by two interfering rotating patterns. What are those underlying patterns? Thanks. μηδείς (talk) 20:06, 8 September 2012 (UTC)

I think it's simply two offset radial patterns, as seen here. -- BenRG (talk) 04:07, 9 September 2012 (UTC) *

Exactly! Wonderful. I had been guessing two spirals, which I think would have been way more checkered. Great! μηδείς (talk) 04:21, 9 September 2012 (UTC)

Resolved

Can you give the url of the page in which that image was embedded? μηδείς (talk) 04:49, 9 September 2012 (UTC)

I updated the original link. It's an interesting web site and I hadn't even noticed since I just found the image in Google Image Search. -- BenRG (talk) 05:20, 9 September 2012 (UTC)

Extrapolating sums of powers

Let's say we define G(N, P) = {1^P + ... + N^P}. Now given that A = G(N, 1), B = G(N, 2), and C = G(N, 3) are easy to calculate, is there any way to extrapolate to get the value of D = (G(N, N) mod (N + 1)) using A, B, and/or C (by inspecting the differences between their respective values, or what have you)? If not, can we, at the very least, infer anything whatsoever about D?

76.25.96.107 (talk) 22:08, 8 September 2012 (UTC)

See Faulhaber's formula Dmcq (talk) 22:55, 8 September 2012 (UTC)

Sorry, I should have been clearer: I'm seeking an efficient method for any given N.

76.25.96.107 (talk) 23:04, 8 September 2012 (UTC)

This only works for a subset of N, but is very efficient for that subset (unless I've bungled it): if N+1 is a prime number, then D = N. This follows from Fermat's little theorem. — Quondum 23:32, 8 September 2012 (UTC)

An efficient method is to calculate the first few values and then look up the Encyclopaedia of Integer Sequences, but that is only for a limited number of values ;-) Sticking 1,2,0,4,3,6,0,6 into that gives A204187. Unfortunately except for the case of N+1 a prime the main reference seems to be 'R. K. Guy, Unsolved Problems in Number Theory, A17' which indicates anything simple may be a bit much to ask. Always worth a good look though if it has come up in some different context. Dmcq (talk) 08:56, 9 September 2012 (UTC)

According to the OEIS page, we can expand the "efficient" cases:

• If N+1 is prime, D = N
• If N+1 is a multiple of 4, D = 0
• Otherwise, there appears to be no known efficient way to calculate D.

— Quondum 09:38, 9 September 2012

Well it looks to me like there probably are some rules depending on the factorization of N+1. For instance for the table of values it looks like the value for p^2 is p(p-1) and for 2.(2n+1) is 2n+1 and for 3.p is 2.p. Though how one gets 52 from 65, I don't know - one would expect both factors 5 and 13 to enter if one does. Dmcq (talk) 15:43, 9 September 2012 (UTC)

N + 1 = p₁p₂ ⇒ D = p₁(p₂ – 1)? Err... It is looking vaguely reminiscent of the Euler totient function, with some unpredictable deviations. If N is quite small (< 2¹⁶ say), and one can afford a few milliseconds to calculate each D, I'd just do it on a computer using modulo arithmetic. — Quondum 20:32, 9 September 2012 (UTC)

Hmmmm, can't this be simplified by using that this is

${\frac {B_{n+1}(n+1)-B_{n+1}(0)}{n+1}}{\text{mod }}(n+1)$

The terms in the Bernoulli polynomial evaluated at n+1 are mostly divisible by n+1 and then also zero when reduced mod n+1, so it seems to me that you don't have many nonzero terms left... Count Iblis (talk) 21:40, 9 September 2012 (UTC)

How could that possibly lead to a simplification though - the Bernoulli numbers are notoriously inefficient to calculate, aren't they?

66.87.126.39 (talk) 03:35, 10 September 2012 (UTC)

You end up with one Bernoulli number. You can take Modulo n+1 in the entire polynomial, if the denominator is not a zero-divisor, you obviously get zero, if not then you still have a high enough power of n+1 left to make the term zero. This is true for all terms except the first term after the contant term. That term is proportional to a Bernoulli number and you need to evaluate this Modulo (n+1) (with the right convention if the re are zero divisors). I have to look into this in more detail, but it seems to me that the Von Staudt–Clausen theorem can be used to simply this. Count Iblis (talk) 04:28, 10 September 2012 (UTC)

So, we need to calculate the coefficient of the lowest nonzero power of x in $B_{n+1}(x)$, which for even N is the coefficient of x, and for odd N is the coefficient of x^2. Using the recursion relation:

${\frac {B_{n}(x)}{dx}}=nB_{n-1}(x)$

you find that for even n this is

$c_{\text{even}}=(n+1)B_{n}$

and for odd n this is

$c_{\text{odd}}=n{\frac {(n+1)}{2}}B_{n-1}$

For even n the summation is

$c_{\text{even}}{\text{ mod}}(n+1)=(n+1)B_{n}{\text{ mod}}(n+1)$

because multiplying with x and setting x = n+1 and then dividing by n+1 yields a factor 1. In case of odd n, the sumation is

$(n+1)c_{\text{odd}}{\text{ mod}}(n+1)=n{\frac {(n+1)^{2}}{2}}B_{n-1}{\text{ mod}}(n+1)$

because now the term must be multiplied by x^2 and divided by n+1 and setting x = n+1 yields a factor of n+1.

In both cases, the Bernoulli numbers can be reduced Modulo 1, as that shifts the terms by a number proportional to n+1 which is then zero as we're computing modulo n+1. The Von Staudt–Clausen theorem then yields for even n the expression

$-\sum _{p-1|n}(n+1)p^{-1}{\text{ mod}}(n+1)$

where the p in the summation are prime numbers. This has to be evaluated with the convention that P^(-1) multiples (n+1) before we reduce modulo (n+1). If p is not a divisor of n+1, this is the same as computing the inverse of p modulo n+1 first, but then we see that term becomes zero. So, the summation is equal to the above expression where we now only sum over the prime numbers that divide n+1.

For odd n, the summation can be written as

$-\sum _{p-1|n-1}n{\frac {(n+1)^{2}}{2}}p^{-1}{\text{ mod}}(n+1)$

Then as in the even case, primes that don't divide n+1 yield zero. But now also odd primes that divide n+1 yield zero, because you can then let p divide (n+1)/2 and the term will still be proportional to n+1 = 0 Mod(n+1). So, the only nonzero contribution can come from p = 2. If n+1 is divisible by 4, it will remain zero as p = 2 will divide (n+1)/2. Only if n + 1 is not divisible by 4, so when n = 4 k + 1 will the term be nonzero, it then becomes

${\frac {n+1}{2}}$

To see this, you can use the fact that n = -1 mod(n+1) and (n+1)^2/4 = (n+1)/2 (n+1)/2 = (n+1)/2 [(n+1)/2 - 1 + 1] = (n+1)/2 mod (n+1) because (n+1)/2 - 1 is an even number. Count Iblis (talk) 16:25, 11 September 2012 (UTC)

Cube: 2 Hypercube

I do not want to be a bother to Mathmatics but i was wondering how accurate is the movie Cube 2 Hypercube, i know its all about tesseracts and 4D? Can any one explain how it works to me? — Preceding unsigned comment added by 205.142.178.36 (talk) 23:34, 8 September 2012 (UTC)

|

A 3D projection of an 8-cell performing a double rotation about two orthogonal planes

Did you not find the above answers to your question helpful? μηδείς (talk) 00:29, 9 September 2012 (UTC)

No this is about the movie in general — Preceding unsigned comment added by 76.16.47.115 (talk) 02:46, 9 September 2012 (UTC)

It's a horror movie. You might do well to ask a specific mathematical question here, or a plot question on the entertainment desk. μηδείς (talk) 04:22, 9 September 2012 (UTC)

Explain how it would work in math — Preceding unsigned comment added by 76.16.47.115 (talk) 05:00, 9 September 2012 (UTC)

The surface of a cube consists of six squares, each of which is connnected via its four sides to four of the other five square that make up the surface of the cube. In the same way, the "hypersurface" of a tessaract consists of eight cubes, each of which is connected via its six faces to six of the other seven cubes that make up the "hypersurface" of the tessaract.

If you take a tour of the squares around a cube, always going straight on i.e. exiting each square on the opposite side that you entered it, then you go through four different squares before returning to where you started. In the same way, if you take a tour of the cubes around a tesseract, always going straight on i.e. exiting each cube on the opposite face that you entered it, then you go through four different cubes before returning to where you started. Gandalf61 (talk) 08:15, 9 September 2012 (UTC)

You really should read the tesseract article, read Flatland, and watch the Edge of Forever episode available all over the internet if you want to understand the fourth dimension. I would start with the cosmos episode: here at google. μηδείς (talk) 21:39, 9 September 2012 (UTC)