魔法羊的一条死路和两个猜想1
需积分: 0 86 浏览量
2022-08-03
19:18:36
上传
评论
收藏 60KB PDF 举报
魔法羊的一条死路和两个猜想
唐泽
February 19, 2020
定义 1：[i, j] 为 i 只黑羊，j 只白羊的状态
转移概率：[i, j]
[i + 1, j − 1] (P ossibility =
ip
i+j
)
[i, j] (P ossibility =
i(1−p)+j(1−q)
i+j
)
[i − 1, j + 1] (P ossibility =
jq
i+j
)
定义 2：f(i, j) 为 i 只黑羊，j 只白羊，剩下黑羊数量的最大期望
定义 3：F (i, j) 为 i 只黑羊，j 只白羊，本次不可移除白羊，剩下黑羊数量的最大期望
于是有：
f(i, j) = max
0≤k≤j
{F (i, k)}
F (i, j) =
ip
i + j
f(i + 1, j − 1) +
i(1 − p) + j(1 − q)
i + j
f(i, j) +
jq
i + j
f(i − 1, j + 1)
边界条件：
f(i, 0) = i
f(0, j) = 0
但这几个式子里有个 max，无法通过 Gauss 消元求解，所以这条路目前到此为止了。
于是我想尝试一些感性的想法。看到有变化的两个转移概率看上去像正反馈，变化对方的优
势会随着个数增多而变大。于是就有了下面两个猜想：
结论 1：∀i∃
1
k((∀j ≥ k, f(i, j) = f(i, k)) ∧ (∀j < k, f (i, j) < f (i, k)))
简 略 证 明： f (i, j) 在 j 变 化 时 最 大 值 存 在 是 因 为: 黑 羊 期 望 要 增 多，有 个 必 要 条 件 是
ip
i+j
>
jq
i+j
, 这个条件约束了白羊数量 j 有个上限，最大值必然在这个上限之前到来。j 足够大后
函数值不变是由于取 F 函数的前缀 max.
定义 4：将结论 1 中 i 所对应的唯一的 k 定义为 g(i)
猜想 1（白羊单调性）：∀i∀j
1
< j
2
≤ g(i), f(i, j
1
) ≤ f(i, j
2
)
猜想 2（决策单调性）：对于固定的 p,q，有 ∀i
1
< i
2
, g(i
1
) ≤ g(i
2
)
如果这两个单调性猜想正确的话就产生了一种策略：当前白羊数目超过决策点 g(i) 时，减少
白羊数量至决策点；当前白羊数目不到决策点 g(i) 时，继续魔法就行。
但是还有个问题是 g(i ) 的求解，拓展一点也可以说是 g(i, p, q) 的求解（可以用作 p,q 随着 i
变化的模型）。我没有求解出来的思路，但我觉得如果只是求解较优解的话可以假设决策点在黑羊
获取优势的边界处，即减少 j 至刚好
ip
i+j
>
jq
i+j
. 这本可以用 C++ 模拟的，但我和毛昕渝交流后
发现他已经对于这个模型模拟过了，我就不再做一遍了。
1
评论0