Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The game goes like this:

There are 20 cards to begin with, among which, 12 cards are marked with $1, 3 cards are marked with +2 picks, 2 cards are marked with +3 picks, 2 cards are marked with x2, and the last card is marked with x3.

  So, it is: $1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1,+2,+2,+2,+3,+3,x2,x2,x3

A player is allowed to randomly pick 5 cards from the shuffled deck. And if he picks the card such as +2, he is allowed to pick an extra 2 cards from the deck without replacement. And if he gets +2 or +3 again, he picks again, over and over. The overall prize a player can get is the product of cash prize sum and multiplier product.

  e.g.  a player might get this:  $1,$1,$1,$1,+2,x2,x2 So he gets $4 x2 x2 = $16 (multipliers applied multiplicatively)

SO, what's the expected prize he can get?

This game cannot be modeled as a time homogeneous markov chain. Is there any model or any idea to solve this kind of problem rather than do a recursive dynamic programming on a pc?

share|improve this question
    
After reading the post below I have one question: does the multiplier cards apply to the pot or to the total? What I mean by this is: Is the drawing (x2 $1 $1 $1 $1 ) equal to ($1 $1 $1 $1 x2)? Notice that if the 'times two' card is applied to the pot, the first drawing would be a total of 4$, while the second one would be $8. Because if they are indeed equal then his final statement is correct. If they are not, the problem is even harder. –  Damieh Jun 15 '12 at 1:02
    
@Damieh Multiplier always apply to the final total. Btw, do u know how to make comments friendly for dollar sign? –  colinfang Jun 15 '12 at 12:35
    
No I don't =(. How do you do it? Also, if the multiplier cards apply to the total and not the current stack, upvote bgins's answer! It's pretty neat! =) –  Damieh Jun 15 '12 at 13:26

1 Answer 1

Here's my two cents, which is perhaps only stating the obvious.

Let $a_k$ be expected and $A_k$ the actual number of ${\$}1$, and similarly $b_k$ the number of $+2$, $c_k$ the number of $+3$, $d_k$ the number of $\times2$ and $e_k$ the number of $\times3$ cards drawn in the $k^\text{th}$ round, starting with $5$ cards being drawn in round $k=1$. Then we have the following marginal probabilities: $$ \begin{align} P(A_1=x)=\frac{{12\choose x}{ 8\choose5-x}}{20\choose5}\\ P(B_1=x)=\frac{{ 3\choose x}{17\choose5-x}}{20\choose5}\\ P(C_1=x)=\frac{{ 2\choose x}{18\choose5-x}}{20\choose5}\\ P(D_1=x)=\frac{{ 2\choose x}{18\choose5-x}}{20\choose5}\\ P(E_1=x)=\frac{{ 1\choose x}{19\choose5-x}}{20\choose5}\\ \end{align} $$ Let $N_k$ be the cumulative number of cards drawn from round $1$ up to and including round $k$. Then $N_1=5$ and, for $k>1$, $N_k=5+\sum_{i=1}^{k-1}\left(2B_i+3C_i\right)$ since the number of cards drawn in round $k+1$ will be $2B_k+3C_k$. Note that we need not worry about imposing the upper limit of $20$, since in total at most $5+3\cdot2+2\cdot3=17$ cards can be drawn. This in fact then gives a clue about how to efficiently model the expected outcome. All we really care about is how many cards ultimately get drawn (in total) of the numeric and multiplier types. Let us denote these values (random variables in uppercase and expectations in lowercase) by the corresponding un-subscripted letters. Let us first try to solve for the probability distributions of $B$ and $C$. After the first round, we have $$ p_{ij}^1=P(B_1=i,C_1=j)=\frac{{3\choose i}{2\choose j}{15\choose5-i-j}}{{20\choose5}}\,. $$ Another way of looking at it is with the generating functions $$ F_1(x,y)= \sum_{i=0}^3\sum_{j=0}^2p_{ij}^1x^iy^j= \left(\matrix{1\\x\\x^2\\x^3}\right)^{T} \left(\begin{array}{rrr} \frac{1001}{5168} & \frac{455}{2584} & \frac{455}{15504} \\ \frac{1365}{5168} & \frac{455}{2584} & \frac{105}{5168} \\ \frac{455}{5168} & \frac{105}{2584} & \frac{15}{5168} \\ \frac{35}{5168} & \frac{5}{2584} & \frac{1}{15504} \end{array}\right) \left(\matrix{1\\y\\y^2}\right) $$ $$ G_1(t)=F_1(t^2,t^3) =\tfrac{ 1}{15504} t^{12} +\tfrac{ 15}{ 5168} t^{10} +\tfrac{ 5}{ 2584} t^9 +\tfrac{ 105}{ 5168} t^8 +\tfrac{ 105}{ 2584} t^7 +\tfrac{ 35}{ 969} t^6 +\tfrac{ 455}{ 2584} t^5 +\tfrac{ 455}{ 5168} t^4 +\tfrac{ 455}{ 2584} t^3 +\tfrac{1365}{ 5168} t^2 +\tfrac{1001}{ 5168} $$ where the monomial coefficients and exponents for $x,y,t$ represent respectively the probabilities of obtaining given multiplicities of $+2$ cards in round $1$, $+3$ cards in round $1$, and total number of new cards to draw in round $2$. Now the fundamental "driving force" of this system is the matrix $P^1=(p_{ij}^1)$, whose superscript $1$ indicates the first round and whose subscripts represent the case of obtaining $i$ cards $+2$ and $j$ cards $+3$ (the corresponding probability is in row $i$ and column $j$, each starting with $0$). If we let $P^k=(p_{ij}^k)$ and $Q^k=(q_{ij}^k)$ represent the respective probabilities of iteratively and cumulatively obtaining $i$ $+2$ and $j$ $+3$ cards in/by the $k$ round (which are identical for $k=1$ and given in the middle $4\times3$ matrix factor above), then we could use these to compute our answer. But what we really care about are the ultimate cumulative probabilities (regardless of the number of rounds), after no more $+$ cards are drawn, which can be used to calculate the distribution of the ultimate number of non-$+$ cards drawn. Is there perhaps an even easier way of calculating these?

Clearly the probability of drawing no plus cards ultimately and initially is identical: $p_{00}=\frac{1001}{5138}=p_{00}^1$. Other entries of the matrix $P^1$ tend to donate some of their value to higher-indexed entries, within their total index dispersement range ($2i+3j$) and according to a state change graph (Markov chain). If we were lucky enough to draw all five plus cards in the first round (beating the one to $15503$ odds), then the second round will give us twelve non-plus cards. Both of these extreme cases has an easily calculated conditional expected win, $$E(W|B_1=C_1=0)=\sum_{x+y+z=5}x\cdot2^y\cdot3^z\cdot \frac{{12\choose x}{2\choose y}{1\choose z}}{{15\choose 5}}$$ $$E(W|B_1=3,C_1=2)=\sum_{x+y+z=12}x\cdot2^y\cdot3^z\cdot \frac{{12\choose x}{2\choose y}{1\choose z}}{{15\choose 5}}$$

where I am assuming that the final win depends only on the total amount of cards drawn in all rounds, independent of the order and in which round they are drawn: $$ \text{Final Win}=W=A\cdot2^D\cdot3^E\,. $$ So the trick would be figuring out an elegant way to determine the probability distribution for the total number non-plus cards drawn. Then we could condition on this similar to the extreme cases above to solve the problem.

share|improve this answer
    
Hats off!!!!!!!!!!! I have doubts with those lasts statements though. The OP didn't state if the order of the multiplier cards mattered. i.e. if picking ($1 $1 $1 $1 x2) is the same as ($1 $1 $1 x2 $1). –  Damieh Jun 15 '12 at 1:04
1  
@Damieh: thanks, I made that assumption explicit; I suspect that it reflects the original intent. –  bgins Jun 15 '12 at 7:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.