Ok. I think part of the issue [ETA: with our mutual understanding of each other, not with you] is that you're focused on the "You're lying" part of the conversation.
I'm considering it in the context of this: "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?"
Granted, his observations have N bits of information (at least), the same as the situation with cheating, and it's at least as improbable that he'd observe a given sequence of length N when something else entirely happened, than that the given sequence of length N itself happened, so in practice, it's still -certainly- more likely that he actually observed the observation he observed.
The paradox isn't there. The paradox is that we would, in fact, find some sequences unbelievable, even though they're exactly as likely as every other sequence. If the sequence was all heads 100 times in a row, for instance, that would be unbelievable, even though a sequence of pure heads is exactly as likely as any other sequence.
The paradox is in the fact that the sequence is undefined, and for some sequences, we'd be inclined to side with Alice, and for other sequences, we'd be inclined to side with Bob, even though all possible sequences of the same length are equally likely.
ETA:
This is what I was getting at with the difference between the reference classes of "distinguished" and "undistinguished".
if you make an event improbable enough, why shouldn't I be skeptical even if I think I observed it?
You should. You should be aware that you might e.g. have made a mistake and slightly misremembered (or miscopied, etc.) the results of the coin flips, for instance.
we would, in fact, find some sequences unbelievable
We might say that. We might even think it. But what we ought to mean is that we find other explanations more plausible than chance in those cases. If you flip a coin 100 times and get random-looking results: sure, those particular results ar...
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.