4
$\begingroup$

I don't understand what I found when calculating the expected value of a card game.

A deck contains 40 cards. 8 of them are red cards and 32 of them are blue cards. At the start of the game, 5 cards are drawn to be the starting hand. The question is to find the expected value of drawing red cards in the starting hand.

d = number of cards in deck

r = number of red cards in deck

b = number of blue cards in deck

s = number of starting hands

n = number of red cards drawn in starting hand

I believe the probability drawing n red cards in starting hand is something like this,

$P_n = \frac{C_n^r×C_{s-n}^{b}}{C_s^{d}}$

I believe the expected value of number of red cards drawn in starting hand should be like (and given that r>s),

$$E(n) = \sum_{n=0}^s n×P_n$$

So r=8 in this case, E(n) should be 1 if calculated correctly

After that, I modify the deck, so there will be 16 red cards and 24 blue cards. And the deck size remains unchanged. So r=16 and the returned value of E(n) is 2 if I calculated correctly.

At this moment, I noticed that to calculate E(n), I can just simply calculate this,

$\frac{r} {d}×s$

I don't understand why this is possible. I tried to simplify the expression of the equation from my original calculation but I failed. Could anyone kindly explain to me what happened?

Edit: Thank you very much for the first 2 responses, but I would like to ask if there is a way to simplify this,

$\sum_{n=0}^s n × \frac{C_n^r×C_{s-n}^{b}}{C_s^{d}}$ (where r>s)

Into this, $\frac{r} {d}×s$

$\endgroup$

4 Answers 4

3
$\begingroup$

Using the basic identity

$$ n× C_n^r=r C_{n-1}^{r-1}, \tag{1}$$

we have $$\sum_{n=0}^s n × C_n^r×C_{s-n}^{b}=\sum_{n=1}^s r C_{n-1}^{r-1}×C_{s-n}^{b}=\\r\sum_{i=0}^{s-1} C_{i}^{r-1}×C_{s-1-i}^{b}=r C_{s-1}^{b+r-1}=r C_{s-1}^{d-1}.$$

To compute the last sum, the Vandermonde's identity is used after the change of index $i=s-1$.

Thus, using the above and (1),

$$\sum_{n=0}^s n × \frac{C_n^r×C_{s-n}^{b}}{C_s^{d}}=\frac{rC_{s-1}^{d-1}}{C_s^d}=\frac{rs}{d}.$$

$\endgroup$
4
  • 1
    $\begingroup$ @tkf Thank you for the edit! $\endgroup$
    – Amir
    Apr 19 at 17:12
  • $\begingroup$ The three proofs of Vandermonde's identity on the wiki page are quite similar. I think the following proof is more in the spirit of this question: Let $$f_{r,b,s}=\sum_{n=0}^s C^r_n\times C^b_{s-n}.$$ Then noting that $s=n+(s-n)$ we have $$sf_{r,b,s}=rf_{r-1,b,s-1}+bf_{r,b-1,s-1}.$$ The result follows by induction. $\endgroup$
    – tkf
    Apr 19 at 17:55
  • $\begingroup$ @tkf Nice method, not seen before! Thanks! $\endgroup$
    – Amir
    Apr 19 at 19:58
  • $\begingroup$ @tkf to make it more visible, you may add the new proof as a new answer for this question: math.stackexchange.com/q/337923/1231520 $\endgroup$
    – Amir
    Apr 19 at 21:30
2
$\begingroup$

If you have 40 players with one card each, then all cards are dealt. The expected value of red cards handed to all players is r. Since each player is in an identical position, each has the same expected value of red cards, r/d.

If you look at the first s players, their total expected value is (r/d)*s. And if you divide these s players into groups, that doesn’t affect anything, and the expected value is still (r/d)*s.

$\endgroup$
2
$\begingroup$

An easier way to solve questions like these is with an Indicator Random Variable

$ X_i = \begin{cases} 1 & \text{if event } A \text{ occurs}, \\ 0 & \text{otherwise}. \end{cases} $

In this case $ X_i = \begin{cases} 1 & \text{if the ith card is red }, \\ 0 & \text{otherwise}. \end{cases} $

Something else you might want to look into is linearity of expectation and the fundamental bridge (as named by Prof. Blitzstein in this book https://projects.iq.harvard.edu/stat110/home)

$ \sum_{i=1}^{s} E(X_i)= \sum_{i=1}^{s} P(X_i) = \sum_{i=1}^{s} \frac{r}{d} =\frac{r}{d} * s $

$\endgroup$
2
$\begingroup$

For integers $r\geq 0$ and $n$, let $C^r_n=\frac{r!}{n!(r-n)!}$ if $n\in0,1,\cdots,r$ and $C^r_n=0$ otherwise. This satisfies:

$$nC^r_n= \frac{r!}{(n-1)!(r-n)!}=rC_{n-1}^{r-1}, $$

Let $$f_{r,b,s}=\sum_{n=0}^s C_n^r\times C_{s-n}^b.$$

Then $$ sf_{r,b,s}=\sum_{n=0}^s (n+(s-n))C_n^r\times C_{s-n}^b $$ $$ = \sum_{n=1}^s nC_n^r\times C_{s-n}^b +\sum_{n=0}^{s-1}C_n^r\times (s-n)C_{s-n}^b $$ $$ =\sum_{n=1}^s rC_{n-1}^{r-1}\times C_{s-n}^b +\sum_{n=0}^{s-1}C_n^r\times bC_{s-1-n}^{b-1} $$ $$ =rf_{r-1,b,s-1}+bf_{r,b-1,s-1} $$

At this point we could use the identity $sf_{r,b,s}=rf_{r-1,b,s-1}+bf_{r,b-1,s-1}$ to prove (by induction on $s$) that $f_{r,b,s}=C_s^{r+b}$, which @Amir uses to complete their excellent solution (+1).

Alternatively we could note Pascal's famous identity:

$$ C^r_n+C^r_{n+1}=\frac{r!}{(n+1)!(r-n)!}\left((n+1)+(r-n)\right) $$ $$ =\frac{(r+1)!}{(n+1)!(r-n)!}=C_{n+1}^{r+1} $$

Thus $$f_{r,b-1,s-1}=\sum_{n=0}^{s-1} C_n^r\times C_{s-1-n}^{b-1}$$ $$= \sum_{n=0}^{s-1} (C_{n-1}^{r-1}+C_n^{r-1})\times C_{s-1-n}^{b-1} $$ $$ =\sum_{n=0}^{s-1} C_{n-1}^{r-1}\times C_{s-1-n}^{b-1} + \sum_{n=0}^{s-1} C_n^{r-1}\times C_{s-1-n}^{b-1} $$ $$ =\sum_{n'=-1}^{s-2} C_{n'}^{r-1}\times C_{s-1-n'-1}^{b-1} + \sum_{n=0}^{s-1} C_n^{r-1}\times C_{s-1-n}^{b-1} $$ $$ =\sum_{n=0}^{s-1} C_{n}^{r-1}\times (C_{s-1-n-1}^{b-1}+C_{s-1-n}^{b-1})+0-0 $$ $$ =\sum_{n=0}^{s-1} C_{n}^{r-1}\times C_{s-1-n}^{b}=f_{r-1,b,s-1} $$

Combining our two results we get: $$sf_{r,b,s}=rf_{r-1,b,s-1}+bf_{r,b-1,s-1}$$ $$ =rf_{r-1,b,s-1}+bf_{r-1,b,s-1}=(r+b)f_{r-1,b,s-1} $$

That is $$\frac{f_{r-1,b,s-1}}{f_{r,b,s}}=\frac{s}{r+b}.$$ This is exactly what we need to answer the original question. The expected number of reds in the starting hand is: $$ \frac1{f_{r,b,s}}\sum_{n=0}^s nC_n^r\times C_{s-n}^b $$ $$ =\frac1{f_{r,b,s}}\sum_{n=1}^s rC_{n-1}^{r-1}\times C_{s-n}^b $$ $$ =\frac1{f_{r,b,s}}\sum_{n'=0}^{s-1} rC_{n'}^{r-1}\times C_{s-1-n'}^b $$ $$ =r\frac{f_{r-1,b,s-1}}{f_{r,b,s}} =\frac{rs}{r+b}, $$ as desired.

I realise this is very long-winded, but I got the impression the OP was looking for a purely computational argument for a result that is conceptually is to see.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .