A-SHUFFLE PROBABILITY HELP!! MATHEMATICIANS PLEASE!!

[DcifrThs]

i think its called an "a-shuffle" but i'm a little hazy so here it goes...

i was shuffling 6 blue $1 mirage chips and 6 white $1 st. tropez chips and i noticed that after 6 PERFECT A SHUFFLES i turned and counted each time many many times over, the stacks invariably returned to 6blue 6white...i then tried it with 2, 3, 4, 5, 7, 8 (had to do it one chip at a time), same with 9 and 10 but i did it anyway to see 'cause i was curious and i recorded all results:

N (#total chips) #A-Shuffles to return to original
4- 2
6- 3
8- 3
10- 5
12- 6
14- 4
16- 4
18- 9!!!! (checked this one about a million times)
20- 6

This got me thinking about how to write an equation (or what is the equation if a relationship exists) for the relationship between # of total chips and # of perfect shuffles needed to return them to original 2 stacks of uniform colors...

SOOO thats my question. math and probability professors and statisticians, please let me have it!

-Barron

[DcifrThs]

FURTHER:

i would like to know a few other odd aspects of this problem.

1) if one chip is misplaced by one position aaaaaa, bbbbbb----> ababababBAab ... will it ever return to original aaaaaa, bbbbbb? i never shuffled enough to find out

2) if we start with random sorts, abaababbabab or the like, what is P(aaaaaa,bbbbbb|random sort, but perfectshuffles from then on in)

3) what is general notation for this stuff?

thanks
-Barron

[bigpooch]

What's an A-shuffle?

The most common terms for a "perfect shuffle" are in-shuffle
and out-shuffle, so let me illustrate each based on a deck
of 8 cards:

An in-shuffle on a deck of 1 2 3 4 5 6 7 8
results in 5 1 6 2 7 3 8 4
whereas
an out-shuffle on a deck of 1 2 3 4 5 6 7 8
results in 1 5 2 6 3 7 4 8.

Suppose the deck has 2n elements where n is an integer.
The results of in-shuffles and out-shuffles have been
examined before. In the case of in-shuffles, the first
element is considered the 1st place and in-shuffling is just
the same as multiplication by 2 modulo (2n+1) whereas for
outshuffles, the first element is considered the 0th place
and out-shuffling is multiplication by 2 modulo (2n-1).
By that, I mean that the kth place goes to the (2k)th place
after one shuffle.

Note: modular arithmetic is just "remainder" arithmetic or
"clock" arithmetic where the only allowed results are 0, ...
(m-1) where m is the modulus.

Thus, the lowest exponent k for which 2^k is congruent to 1
mod 2n+/-1 gives the least number of shuffles returning the
deck to its original state. Also, it will take at the very
most 2n in-shuffles or 2n-2 out-shuffles to return to the
original state (this comes from a theorem by Euler, a
generalization of Fermat's Little Theorem that if a and m
are coprime, a^phi(m) is congruent to 1 mod m). Actually,
the biggest it could be is phi(m) shuffles where m is the
modulus in question and phi is the Euler totient function
(phi(m) is the same as the number of integers between 0 and
m-1 inclusive that are coprime with m). In any case, the
actual least number of shuffles to return to the original
state must divide exactly into phi(m).

Since the number 53 is prime, and 2 is a primitive root
modulo 53 (or 2 is a generator of the multiplicative group
of nonzero congruence classes modulo 53) it takes 52
in-shuffles for a deck of cards to go back to its original
state and similarly 8 out-shuffles (since 2^8 is congruent
to 1 mod 51 and no smaller exponent of 2 is congruent to 1).


At first, I thought you were talking about out-shuffles, but
your data doesn't coincide with what would be the data for
out-shuffles.

[DcifrThs]

well i got to the first paragraph and will ask you one question before i slog through the rest because it will take me some effort (that i'm willing to put in) but not if the premise is faulty.

for the in shuffle you demonstrate (and out for that matter) it seems as if neither is what i would call a "perfect shuffle" nor the one that occurs w/ my little baby chips.

taking 12345678 and LOL. ok, i'll stop here. funny [censored]. clearly we're lookin at an inshuffle of 51627384. i thought were were taking 12345678 and 12345678. clearly thats wrong and i will now go back to slogging. ty VERY much for your time and effort for this post!

-Barron

[DcifrThs]

ok, heres my problem.i love math and stat. i'm an economist for the dept. of laber (not many 23 year olds that have that job...)

but i do not know to what you refer with many of the words you are using. it is like looking up words in the definition of the word you just looked up. plus, being a statistics guy, i see phi(m) and take a while guess what i think of...thats right our favorite buddy the normal distribution for m. so i really am lost here.

if you would be so kind (and i really would appreciate this) would you please either private message me or post the same exact proof in language i can at least slog through lol. further, what would REALLY be great, although i'm sure its in that post somewhere, is how to derive the formula for how many shuffles does it take to return a set of n elements of x (x=2 in this example) variety to original order m. that would be fantastic!

thanks again!
-Barron

[BruceZ]

You can lookup explanations of all these terms at www.mathworld.wolfram.com (http://www.mathworld.wolfram.com.).

[bigpooch]

Actually, you don't need the same chip to go back to the
original place, right? You simply require that the same
"pattern" of alternating chips as the start is reinstated.

As per my previous post then, if you have 2n elements (chips
or that are alternating in exactly 2 or g different colors
where g divides into 2n), then the least positive number of
shuffles to get back to the original pattern must divide
into phi(2n+1).


Here, phi(k) is a number-theoretic function:

Again, it is simply the number of elements of {0,1,...,m-1}
that are relatively prime to m. [Two numbers n1 and n2 are
relatively prime if there is no common divisor other than 1
that divides both n1 and n2.]. Also, m and n are coprime
means the same as m and n are relatively prime.

For example, if p is a prime, phi(p)= p-1.
For nth powers of primes, phi(p^n)= (p-1)p^(n-1).

Also, phi is multiplicative, i.e., if m and n are coprime,
phi(mn)=phi(m)phi(n). Since we know every positive integer
greater than 1 has a unique factorization as a product of
primes, phi(m) can be easily determined from the above.

Now, as to the question about EXACTLY how many times you
need to shuffle k chips, that seems a bit more difficult,
but I'll see what I can do!

This brings a completely new meaning to "pattern mapping"
that I didn't intend! LOL!
/images/graemlins/smile.gif

[bigpooch]

Also, your data isn't quite right: for example, you consider
the pattern abab equivalent to baba which is not quite so.
You have been taking the number of shuffles to get to the
"inverse" as well!

Your data should be:

2n: min # of shuffles to original , min # to inverse

4: 4, 2
6: 3
8: 6, 3
10: 10, 5
12: 12, 6
14: 4
16: 8, 4
18: 18, 9
20: 6

[bigpooch]

My apologies for not having worked sufficiently more on this
problem!

Since the shuffle you are dealing with is an inshuffle and
it is known that the state of the deck will return in r
shuffles where r is the lowest positive exponent of 2 which
is congruent to 1 modulo (2n+1) (where 2n = number of
objects that are shuffled), the actual least number of
shuffles to return to the original pattern must divide r.
Call this least number of shuffles s (clearly, s >=2 and s divides r).

I suppose someone could check this out if they had adequate
computing resources and the inclination: to see if the
pattern only returns after r shuffles for the first few
thousand values of 2n (I am basically quite lazy at times
especially when it comes to coding and try to solve these
kinds of problems analytically).

Suppose the set of objects starts off as:

1 2 3 ... 2n

And suppose that after s shuffles, the same pattern occurs,
i.e., the odd placed spots are filled with odd numbers and
the even placed spots have even numbers.

My argument to suggest that r is the answer is this: since
the positions of the objects for each shuffle is equivalent
to multiplying by 2 modulo (2n+1), for the same pattern to
develop after s shuffles, all the even numbers above must
go the even-numbered positions and therefore after s-1
shuffles, the objects would be ordered like this:

{even objects in first half} {odd objects in last half}

{2, 4, .., 2n in some order} {1, 3, .. ,2n-1 in some order}

for then after another shuffle, the even objects get thrown
into the even-numbered positions. What does this actually
mean? Well, the even objects are really numbers of the
form 2m where 1 <= m <= n, so this just means that

2m.2^(s-1) is congruent to a number m0 where 1 <= m0 <= n

because these even numbers are in the first half of the
deck after (s-1) shuffles. This is true for all m, so
(using =/= as the congruence symbol),

2m.2^(s-1) = m.2^s =/= m0 where 1 <= m0 <= n

or m goes to m0 after s shuffles where both m and m0 are
between 1 and n inclusive.

but m.2^s being in the first half just means the first half
of the deck goes to the first half of the deck after s
shuffles. Thus, the last half of the deck also goes to the
last half after s shuffles. So this highly suggests that
this will only happen when 2^s =/= 1 (also, even numbers
go to even placed spots and odd numbers...).

So my "guess" is that s would have to be r.


Any comments from the peanut gallery?

[bigpooch]

As highly suggested from my "guess", the answer must be the
order of 2 in the multiplicative group generated by 2 mod
(2n+1) where there are 2n objects; i.e., the answer is r
where r is the least positive integer such that 2^r is
congruent to 1 modulo (2n+1).

Does anyone see why? It's actually not hard to deduce from
the text in the post "MY EDUCATED GUESS".

In other words, the pattern only repeats after the chips
return to their original positions; this is not a very
obvious result!

[bigpooch]

As nobody posted a proof based on the "ANSWER" post which is
easily seen from the "EDUCATED GUESS" post, here's a proof
that the pattern only returns in the same number of
in-shuffles required to reinstate a deck of 2n objects:

Denote s as the minimum number of in-shuffles to reinstate
the 2n objects to their original positions.

By the number theoretic argument from the "EDUCATED GUESS"
post, the even numbers will go to the even numbered spots
after s shuffles and similarly, the first half of the deck
goes to the first half of the deck after s shuffles. Thus,
the first half of even numbers will go to the first half of
even numbered spots in the deck.

From the same algebraic argument as before, but with the
upper bound now reduced to integer[n/2] for m0, the first
quarter of numbers (roughly) go to the first quarter of the
deck after s shuffles.

Continuing in this manner, eventually, a small enough
starting portion of the deck goes to the same portion so
that:

1.2^s =/= 1
2.2^s =/= 2
and thereby 2^s =/= 1 (mod 2n+1).


Included is a table for the number of shuffles to get back
to the original pattern for 2n<100. To get to the "reverse
pattern", one simply needs to find the smallest t>1 such
that 2^t =/= -1 (mod 2n+1). Here, I denote =/= to mean "is
congruent to", the equivalence relation on integers modulo
2n+1. [This is just the smallest t such that 2^t leaves a
remainder of 2n when divided through by (2n+1); then, s=2t.]

For the following table, the first entry divides into
phi(2n+1) where phi is the Euler totient function.

TABLE:
2n: number of in-shuffles to restore original pattern,
number to get to reverse pattern (if any)

[There is an asterisk if the first number = phi(2n+1); then,
t must exist and is s/2.]

4: 4*, 2
6: 3
8: 6*, 3
10: 10*, 5
12: 12*, 6
14: 4
16: 8, 4
18: 18*, 9
20: 6
22: 11
24: 20*, 10
26: 18*, 9
28: 28*, 14
30: 5
32: 10, 5
34: 12
36: 36*, 18
38: 12
40: 20, 10
42: 14, 7
44: 12
46: 23
48: 21
50: 8
52: 52*, 26
54: 20
56: 18, 9
58: 58*, 29
60: 60*, 30
62: 6
64: 12, 6
66: 66*, 33
68: 22
70: 35
72: 9
74: 20
76: 30
78: 39
80: 54*, 27
82: 82*, 41
84: 8
86: 28
88: 11
90: 12
92: 10
94: 36
96: 48, 24
98: 30, 15