Ides of March
I didn't beware them last year. Does that
admonition apply only
to Caesar, or to the general public, too?
Cards
jauderho:
Assuming even shuffling, how many shuffles on average would return
a deck to it's original order?
If by "even shuffling", you mean
- perfect faro shuffling: 30, if you're consistent about always
in-shuffling or out-shuffling, but you don't care which.
- shuffling well, but not in precisely the same way every time:
probably 52!/2, because good shuffling actually has a genuine
randomizing effect, and correlations and patterns will tend to
disappear; you'll come around to the original order only by chance.
- shuffling well, always breaking the deck 26 and 26: probably
still 52!/2.
- shuffling in a randomly-chosen but consistent way: this is a
very good question, maybe harder than my old question about
permutations; the answer is probably less than 90090.
jmg, thanks for your suggestions. I think we
can assume that runs always contain at least one card, by
definition; if a shuffler misses an attempted run, it
just makes the older run continue longer (although I guess the
idea is that the probabilities should be different: there's a
higher probability of some much longer runs in that
case).
Your point about the difference between the (remaining?) size
of the two halves is something I actually addressed yesterday,
before I read your note. I don't have a good solutions to it.
Do people compensate to try to keep the absolute sizes
of the halves equal? Or are they trying to keep the rates
at which the halves are exhausted equal? These lead to very
different models!
I've been thinking that people are trying to keep the rates even,
which doesn't require any adjustment when they notice that the
halves have different numbers of cards (because they don't care
about that). Your suggestion seems not to be that the average
run length should be larger from the side which has more cards,
but rather that, when the shuffler notices a significant
discrepancy, he will probably try to correct for it by causing
a single long run then and there, to even out the two halves.
Is that correct?
How much control do shufflers normally exert over the rates at
which they let cards full? Not how much control they are
capable of (for some extremely adept shufflers, that's
perfect control!), but how much control they actually bring to bear
after they've started to riffle the cards. In my case, as a poor
shuffler, I find it very hard to slow down at all once the cards
have begun to fall.
Applications? (A story about a conversation about a
card trick)
So, way back in 1995 I was once talking with this physics student about
a card trick in the lounge of a college dorm (which happened to
be in Haifa, Israel). When we had talked about it for twenty minutes,
a friend wandered by and said "You're still talking about that card
trick?" "Yep", we said. They said "Well, we're going to dinner."
When they came back from dinner, we were still sitting at that same
table. "You're not still talking about that card trick?"
But the pad of paper with sketches of hypothetical patterns of
shuffles interleaving told the tale. "You're actually still talking
about it. OK, we're going off to do some work." So they went off
and studied a bit.
Of course, we were unperturbed, and continued our conversation, so
that when those people came by again and said "We're on
our way out to a movie -- I bet you'll still be talking about that
card trick when we get back", we just kind of nodded sagely. And
off they went to a movie, and we kept on scribbling and arguing
about runs and sequences and ambiguities and averages.
When the movie ended, of course, we were discovered not to have
moved an inch, although we had consumed several more sheets of
paper, which were scattered around the table. They talked about
chains and immunity to cuts and about cyclic order and cyclic
chaining and abitrary cut-points and probably something like "true
effective cyclic chain length". The deck of cards we'd had was
stacked into eight neat little piles, and we were still trying to
make consensus estimates of some probabilities.
"You're still talking about that card trick! Look, everybody,
Seth and Uri have been here since before dinner talking
about a card trick." And it was true. Four hours, all told, if I
remember correctly, and four very pleasant hours they were, too.
So there actually is a connection to the program I'm writing. The
card trick in question is one I've already mentioned in my Advogato
diary (July 17 of last summer); Knuth actually mentions it in an
exercise in
The Art of Computer Programming. The basic application
is that, if I can actually get a realistic model of how people
shuffle, I can find out how likely there is to be exploitable
non-randomness in a deck after a small number of shuffles.
You know, it's kind of like TCP sequence prediction attacks, only
more useless.
Anyway, I'm working on a simulation that tries to undo small numbers
of shuffles.