by naive analysis, it's -always- more likely that Alice cheated than that this particular sequence came up by chance.
Why? I agree that Pr(Alice cheated) is likely higher than Pr(these coin-flip results on this occasion), but that's the wrong comparison. Pr(Alice cheated to produce these coin-flip results) is typically about 2^-n times Pr(Alice cheated), and in particular is generally smaller than Pr(Alice got these coin-flip results fairly).
Wait. Are you arguing that, given two possibilities: Alice cheated to produce (random sequence), and Alice produced (random sequence) randomly, given that it requires the same amount of information to produce the sequence in both cases (n bits), Alice cheating to produce a given sequence is just as unlikely, for a sufficiently random sequence, as arriving at the random sequence randomly?
Alice: "I just flipped a coin [large number] times. Here's the sequence I got:
(Alice presents her sequence.)
Bob: No, you didn't. The probability of having gotten that particular sequence is 1/2^[large number]. Which is basically impossible. I don't believe you.
Alice: But I had to get some sequence or other. You'd make the same claim regardless of what sequence I showed you.
Bob: True. But am I really supposed to believe you that a 1/2^[large number] event happened, just because you tell me it did, or because you showed me a video of it happening, or even if I watched it happen with my own eyes? My observations are always fallible, and if you make an event improbable enough, why shouldn't I be skeptical even if I think I observed it?
Alice: Someone usually wins the lottery. Should the person who finds out that their ticket had the winning numbers believe the opposite, because winning is so improbable?
Bob: What's the difference between finding out you've won the lottery and finding out that your neighbor is a 500 year old vampire, or that your house is haunted by real ghosts? All of these events are extremely improbable given what we know of the world.
Alice: There's improbable, and then there's impossible. 500 year old vampires and ghosts don't exist.
Bob: As far as you know. And I bet more people claim to have seen ghosts than have won more than 100 million dollars in the lottery.
Alice: I still think there's something wrong with your reasoning here.