2
$\begingroup$

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?

  • 0
    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! =)2012-06-15

1 Answers 1

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.

  • 1
    @Damieh: thanks, I made that assumption explicit; I suspect that it reflects the original intent.2012-06-15