Câu trả lời "hiển nhiên" là phát bất cứ khi nào có nhiều đồng tiền xanh hơn đồng tiền màu xanh lam. Trong thực tế, điều này là sai. Ví dụ, nếu có 999 đồng tiền màu xanh lá cây và 1000 tiền xu màu xanh, đây là một chiến lược mà phải mất một lợi nhuận dự kiến:
Take 2 coins
If GG -- stop with a profit of 2
if BG or GB -- stop with a profit of 0
if BB -- take all the remaining coins for a profit of -1
Kể từ khi các khả năng đầu tiên và cuối cùng cả hai xảy ra với gần 25% xác suất, kỳ vọng tổng thể của bạn là xấp xỉ 0,25 * 2 - 0.25 * 1 = 0.25
Đây chỉ là một chiến lược đơn giản trong một ví dụ cực đoan cho thấy vấn đề không đơn giản như lần đầu tiên.
Nói chung, sự mong đợi với g đồng tiền màu xanh lá cây và màu xanh b đồng tiền được đưa ra bởi một mối quan hệ tái phát:
E(g, 0) = g
E(0, b) = 0
E(g, b) = max(0, g(E(g-1, b) + 1)/(b+g) + b(E(g, b-1) - 1)/(b+g))
Các max ở hàng thức xảy ra bởi vì nếu nó -EV để chơi, sau đó bạn dừng lại tốt hơn.
Các mối quan hệ lặp lại này có thể được giải quyết bằng cách sử dụng lập trình động trong thời gian O (gb).
from fractions import Fraction as F
def gb(G, B):
E = [[F(0, 1)] * (B+1) for _ in xrange(G+1)]
for g in xrange(G+1):
E[g][0] = F(g, 1)
for b in xrange(1, B+1):
for g in xrange(1, G+1):
E[g][b] = max(0, (g * (E[g-1][b]+1) + b * (E[g][b-1]-1)) * F(1, (b+g)))
for row in E:
for v in row:
print '%5.2f' % v,
print
print
return E[G][B]
print gb(8, 10)
Output:
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
1.00 0.50 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
2.00 1.33 0.67 0.20 0.00 0.00 0.00 0.00 0.00 0.00 0.00
3.00 2.25 1.50 0.85 0.34 0.00 0.00 0.00 0.00 0.00 0.00
4.00 3.20 2.40 1.66 1.00 0.44 0.07 0.00 0.00 0.00 0.00
5.00 4.17 3.33 2.54 1.79 1.12 0.55 0.15 0.00 0.00 0.00
6.00 5.14 4.29 3.45 2.66 1.91 1.23 0.66 0.23 0.00 0.00
7.00 6.12 5.25 4.39 3.56 2.76 2.01 1.34 0.75 0.30 0.00
8.00 7.11 6.22 5.35 4.49 3.66 2.86 2.11 1.43 0.84 0.36
7793/21879
Từ đây bạn có thể thấy rằng sự kỳ vọng là tích cực để chơi với 8 màu xanh lá cây và 10 đồng tiền xanh (EV = 7793/21879 ~ = 0,36), và thậm chí bạn có kỳ vọng tích cực với 2 đồng tiền xanh và 3 xanh dương (EV = 0.2)
Tôi nghĩ rằng chơi tối ưu có nghĩa là bạn chọn khi nào nên dừng chọn tiền xu. –
Các hướng dẫn nhất định chỉ cần nói để chọn một đồng xu ngẫu nhiên (số ít). Người chơi không có lựa chọn ở đây, do đó không có chiến lược. Bạn chọn một đồng xu, và kết quả mong đợi của bạn là (G-B)/(G + B). Rõ ràng, đây không phải là những gì bạn dự định, vì vậy hãy xây dựng. – Prune
Câu hỏi đặt ra là mong đợi lợi nhuận từ trò chơi như vậy, do đó chúng tôi không chỉ xem xét chọn một đồng xu đơn lẻ mà còn tất cả các khả năng, vì người chơi có thể thực hiện nhiều lựa chọn và dừng lại khi muốn. – user2980096