I didn't beware them last year. Does that admonition apply only to Caesar, or to the general public, too?
Cards
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.