Predicting cards color

[lostdummy]

Another one that looked simple at first :

Deck of 52 cards is shuffled, and then you predict color of each next card to be drawn. If you would guess at random black or red, expected number of correct guesses would be 26. But what would be expected number if you would guess color that has more cards remaining in deck (and random if even)?

I'm still working on this one, although it shows certain similarities to one of previous problems ;p

[ralphmerridew]

I get 3724430600965475/123979633237026
(def-auto avg-sum (r b) (cond ((= r 0) b) ((= b 0) r) ((>= r b) (/ (+ (* r (+ 1 (avg-sum (- r 1) b))) (* b (avg-sum r (- b 1)))) (+ r b))) (t (avg-sum b r))))
(avg-sum 26 26)

Takes about .01s on my computer.

[Zag]

I'm pretty sure you end up with a positive score (that is, greater than 26). Consider every sequence from the point that the count is even to when it is even again. Say the first card is black, so the deck is now +1, you are going to continue guessing red until the deck at zero again, which will net you one point.

If we change the scoring so that you get +1 for a correct guess, -1 for an incorrect guess, and 0 if you choose not to guess (which you do whenever the count is zero). It is clear that you can guarantee a positive number. I don't see any way, other than simulation, to work this out, but my gut says that you will average about between 4-7 points.

[ralphmerridew]

If I didn't make any mistakes in my algebra:

Avg-sum(r,b) = sum (i = 0 to r+b-1: P(get i'th card correct))
Avg-sum(r,b) = sum (i = 0 to r+b-1: sum (j = 0 to i: P(get i'th card correct & exactly j red cards have been removed)))
Avg-sum(r,b) = sum (i = 0 to r+b-1: sum (j = 0 to i: P(get i'th card correct | exactly j red cards have been removed) * P(exactly j red cards have been removed)))
Avg-sum(r,b) = sum (i = 0 to r+b-1: sum (j = 0 to i: (max(r-j, b+j-i)/(r+b-i)) * (C(j,r)*C(i-j,b)/C(i,r+b))))

[Zag]

Nice simulpost. You LISP guys kill me -- a write-only language.

[ralphmerridew]

Regarding Zag's alternate problem, I analyzed that (except this code will guess on an even split, but gets the same average result):

[lostdummy]

Nice work - I got same result, although this time for a change I solved it symbolically (without program):


1) "pk" is probability that after "m" draws we had "k" in specific color
pk(m,k):= C(m,k)*C(52-m,26-k)/C(52,26) , or 0 if (k>m) or (m>26+k)

2) "pg" is probability to correctly make single guess, if "m" cards were previously drawn

pg(m):=sum(k=0..26)[ pk(m,k)* (26-min(k,m-k))/(52-m)]

3) "Ec" is expected number of correct guesses

Ec:= sum(m=0..51)[ pg(m) ]

And it result in Ec=30.0406648


BTW, I started working on extension of this problem, which proved to be separate problem in itself:

If person A use above approach (guess color that remained most) , and person B just guesses randomly, how often will person A win match after whole deck is dealt?

So far I have solution for this by program calculation, but not sure if it is correct since I have no idea how to solve this one symbolically and I prefer waiting for someone else to solve to compare numbers over writing simulation to compare ;p

[ralphmerridew]

(def-auto a-gets-n (n r b) (cond ((= b 0) (if (= r n) 1 0)) ((> b r) (a-gets-n n b r)) (t (/ (+ (* r (a-gets-n (- n 1) (- r 1) b)) (* b (a-gets-n n r (- b 1)))) (+ r b)))))
(def-auto b-gets-n (n ct) (cond ((= ct 0) (if (= n 0) 1 0)) (t (/ (+ (b-gets-n (- n 1) (- ct 1)) (b-gets-n n (- ct 1))) 2))))
(defun a-wins (r b) (loop for a-n from 0 to (+ r b) sum (loop for b-n from 0 below a-n sum (* (a-gets-n a-n r b) (b-gets-n b-n (+ r b))))))

(a-wins 26 26)
4558408532693194411385847/5750778952414215943487488
0.7926593197917203d0

[lostdummy]

I get similar number as result, although not exactly same:

1) chance for "optimal" strategy to guess correctly
I use same formula for "pg" as posted in previous post - probability to correctly make single guess, if "m" cards were previously drawn , and if used "optimal" strategy (one with guessing color that most remained).

2) chance for "optimal" strategy to win k-th deal
Probability that at k-th deal (any of 52 deals) "optimal" player will win over "random" player is half of his chances to guess right at that point (since one who guess random will in half of his correct guesses also guess correctly):
wo(k)= pg(k-1)/2

Also, chance for "random" player to win any deal is half of cases when "optimall" guess wrong, ie:
wr(k)= (1-pg(k-1))/2

BTW, chance that they are even (bot correct or both wrong) at every step is 1/2.

3) Probability of each possible score at each of 52 draws:
Ps[s,d]= probability that after d-th deal we have score "s", such that sum(s=all s) Ps[s, d]=1

Ps[0,0]=1
for (d=1..52); for(s= -d+1 .. d-1);
pold=Ps[s,d-1] // chance of this score (s) after previous deal
Ps[s,d] += 1/2*pold // in half cases it is even, so score remains same
Ps[s+1,d] += wo(d)*pold // if optimal win, score++
Ps[s-1,d] += wr(d)*pold // if random win, score--

4) chance for "optimal" to win after 52 deals:

pW = sum (s=1..52) Ps[s,52]

When calculated above, pW= 0.75931

But after I did that, I saw potential problem with solution: chance for optimal player to win k-th deal is not independent of current score before k-th deal.

[extropalopakettle]

[Thok]