Indexed on: 01 Jun '06Published on: 01 Jun '06Published in: Mathematics - Probability
This paper is about the following question: How many riffle shuffles mix a deck of card for games such as blackjack and bridge? An object that comes up in answering this question is the descent polynomial associated with pairs of decks, where the decks are allowed to have repeated cards. We prove that the problem of computing the descent polynomial given a pair of decks is $#P$-complete. We also prove that the coefficients of these polynomials can be approximated using the bell curve. However, as must be expected in view of the $#P$-completeness result, approximations using the bell curve are not good enough to answer our question. Some of our answers to the main question are supported by theorems, and others are based on experiments supported by heuristic arguments. In the introduction, we carefully discuss the validity of our answers.