b******v
发帖数: 1493 | 1 题目如下：A gambler entered a game with initial money N. In the game, each
time the gambler flips a coin. If the coin is head, then he wins 2b,
otherwise he loses -b. He can flip the coin at most b times. The gambler is
allowed to choose the value b himself. How to choose b so that his expected
return is maximized?
多谢！ |
c***z
发帖数: 6348 | 2 EV = b, the larger b, the better |
k*****n
发帖数: 117 | 3 No E[V | no knock out] = b
Not that simple. Need to work out knock out / ruin probability at each state
. Then optimize on b. |
b******v
发帖数: 1493 | 4 有没有详细一点的解答？多谢！
state
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 k*****n 的大作中提到】
: No E[V | no knock out] = b
: Not that simple. Need to work out knock out / ruin probability at each state
: . Then optimize on b.
|
E*****T
发帖数: 1193 | 5 开始1块钱，赢一次赚两块，输一次赔一块，那么无限抛下去，不会输光的概率是大于1
/4的吧，随便估算了下比较明显。
然后证明，b=n时回报最大。
b>n/2时终止条件都一样，显然b=n最优。
b<=n/2时，赢钱数的期望<=n^2/8的。
b=n是，记g(n)为赢钱数的期望。那么g(n+1)>=(n+1)/n * g(n)+1/4 * (n+1)/2
(n+1)/n * g(n)是因为n+1时，无论赚赔都由n元变成了n+1元，1/4 (n+1)是1/4可能性
不归0可以多抛一次，这一次赚钱的期望为(n+1)/2。
然后由递归不等式易得：如果g(n)>n^2/8,则g(n+1)>(n+1)^2/8,然后再取n=3或者随便
一个数算算初值就行了。 |
