Alice and Bob are playing the following game. There are two identical decks of cards. Each of them has one of them, and both decks are shuffled randomly. Alice and Bob then reveal one card at a time from their respective decks. If any pairs of cards newly revealed from different hand ever match, Alice wins. If no match were ever encountered after they got through the whole decks, Bob wins. Consider the number of cards to be $2^n$. Let's say there are at least more than five cards in each deck.
I am wondering what is the probability of Alice is going to win this game?
This should be P(Alice wins in 1st round) + P(Alice wins in 2nd round) + ...
and P(Alice wins in 1st round) should be $\frac{1}{2^n}$, but what about P(Alice wins in 2nd round)?
Also, how can we discuss the significance of the above result in cryptography? I totally have no idea about it.
Let number cards by numbers $1, \ldots, N$ ($N = 2^n$, but it really doesn't matter). Without loss of generality we can suppose that cards in the first deck follow in ther order of increasing their numbers. Then the order in the second deck is some permutation $P$ of $1, \ldots, N$. Bob wins if and only if $P$ is derangement. Number of derangements is $!N = \left\lfloor \frac{ N !}{e} + \frac12\right\rfloor$, while total number of permutations is $N!$. So $P\{\text{Bob wins}\} = \frac{!N}{N!} \stackrel{N\to\infty}{\longrightarrow}\frac1e$.