Giá trị kì vọng lớn nhất.

[magician_14312]

Khủng hoảng kinh tế làm cho các sòng bạc tại Las Vegas làm ăn thất thu, vì vậy họ đã có một chương trình khuyến mại đặc biệt như sau: nếu như bạn bị thua lỗ, sòng bạc sẽ hoàn trả lại cho bạn $x$ * số tiền bị thua đó. Không có giới hạn cho số lần đặt cược, nhưng bạn chỉ được hoàn lại số tiền (nếu thua) duy nhất một lần khi dừng lại trò chơi.

Biết rằng mỗi lần đặt cược mất $1$ đô la, và nếu chiến thắng thì bạn sẽ giành được $2$ đô la.
Gọi $p$ là xác suất thắng trong mỗi lần cá cược ($p \le 0.5, \,\ 0 \le x < 1$).

Với $x = 50\%$, $p = 49.85\%$, hãy tính kì vọng lợi nhuận lớn nhất có thể thu được từ trò chơi này.

Nguồn: ACM WF 2013.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[huynhcongbang]

Bài này mình có một số phân tích như sau:

Giả sử người đó đánh $n$ trận, ta sẽ tính kỳ vọng số tiền của người này có thể nhận được:
Giả sử người này thắng $i$ trận thì có 2 trường hợp xảy ra:

Nếu $i \le \frac{n}{2}$ thì người này thua, số tiền anh ta sẽ bị mất là $(1-\frac{x}{100})(n-2i)$.

Nếu $i > \frac{n}{2}$ thì người này thắng, số tiền anh ta nhận được sẽ là $2i-n$.

Kỳ vọng số tiền đạt được của người này là

$\frac{1}{n}((1-\frac{x}{100}) \sum_{i=0}^{[n/2]} (2i-n)C_n^i p^i (1-p)^{n-i} + \sum_{i=[n/2+1]}^{n} (2i-n)C_n^i p^i (1-p)^{n-i})$

Ta cần tìm $n$ sao cho đại lượng trên đạt giá trị cực đại (rõ ràng nó phụ thuộc vào cả $x$ lẫn $p$.

Do đó, mình dự đoán là cần phải cho $n$ chạy từ 0 đến khoảng $10^4, 10^5$ để tìm ra giá trị kỳ vọng lớn nhất.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[magician_14312]

Trong biểu thức tính kỳ vọng của anh có xuất hiện $\dfrac{1}{n}$, tức là tính kì vọng theo % số tiền ban đầu? Em thì nghĩ là số tiền kiếm được, tức không tính theo %.

Gọi $p_k$ là xác suất thắng $k$ lần trong $n$ lần chơi. Ta có $p_k = C^k_n p^k (1-p)^{(n-k)}$.
Nếu tính theo truy hồi sẽ là $p_k = \dfrac{(n-k+1)p}{k(1-p)}p_{k-1}$.
Trung bình số lần thắng sẽ là: $\displaystyle \sum_{k=0}^{n}kp_k = np.$

Kì vọng số tiền kiếm được với $n$ lần chơi:
$$\begin{align*}
EX(n) & = \sum_{k = 0}^{\left [ \frac{n}{2} \right ]}(1-x)(2k-n)p_k +\sum_{k = \left [ \frac{n}{2} \right ]+1}^{n} (2k-n)p_k \\
&= \sum_{k = 0}^{\left [ \frac{n}{2} \right ]}x(n-2k)p_k + \sum_{k = 0}^{n} (2k-n)p_k \\
&= x\sum_{k = 0}^{\left [ \frac{n}{2} \right ]}(n-2k)p_k + 2np-n \,\ (1)
\end{align*}$$
Với $\displaystyle \sum_{k = 0}^{\left [ \frac{n}{2} \right ]} p_k = F(\left [ \frac{n}{2} \right ],n,p)$ chính là hàm phân bố, ta có thể sử dụng phép chặn Chernoff: $F(k,n,p) \le exp\left ( -\dfrac{1}{2p}\dfrac{(np-k)^2}{n} \right )$, nhưng tính toán $\displaystyle \sum_{k = 0}^{\left [ \frac{n}{2} \right ]}kp_k $ vẫn còn khó khăn.

Công cụ dừng lại ở đây vẫn chưa đủ để tính toán, vì nếu tính $p_k$ theo công thức thông thường thì tổ hợp chập $k$ của $n$ sẽ lên quá lớn ($n<1000$ thì có thể tính được), nếu tính theo truy hồi thì $p_0$ quá nhỏ và dẫn đến sai số.
Không biết bao giờ họ công bố đáp án nhỉ?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]