Possible Duplicate:
Game Theory Matching a Deck of Cards
Suppose we take a blank deck of $52$ cards, write the number $1$ on the first card, $2$ on the second card, and so on until we write $52$ on the final card. Then we shuffle this deck of cards and stack it. Then two people take turns switching the positions of any two consecutive cards in the deck. No order of cards can be repeated. The player who first gets the deck back to the order $1,2,3...52$ wins, unless the shuffled deck is already in that order, in which case the second player wins. If a player can show that there is no way to get to the $1,2,3,...52$ ordering without repeating any arrangement previously made then that player wins.
I can see from this set-up that any given order of cards is predisposed to being transformed to the $1,2...52$ order in either an even or an odd number of moves(though I am not certain precisely why). Hence the probability, given a random shuffled ordering, of either player winning, should be $\frac{1}{2}$.
Now suppose that the game is being played in Vegas! The mediator of the game holds a winning value dependent on how many turns the game takes. Every turn, the mediator increases the winning prize amount by a factor $p$. If the game takes no turns, the second player wins a dollar. However the mediator can only award the prize if all moves made are the smallest possible path from the shuffled ordering to $1,2,3,..52$. For instance, the second player would not get any winnings if(for the sake of example I will play the game with 3 cards, with the initial ordering $231$,the game was played as $231\rightarrow321\rightarrow312\rightarrow132\rightarrow123$ as opposed to $231\rightarrow 213\rightarrow123$, in which case player 2 will win $p^2$ dollars- he/she can't win $p^4$ dollars. So instead, I suppose we can simply say that for a given starting ordering the game is always played such that the fewest number of turns possible are taken(anyways we know who is going to win!) How can we find the expected number of turns? How can we find the expected winning prize?