时间戳

首页 > 解决方案 > 如何最大化总概率？

c++ - 如何最大化总概率？

问题描述

我想最大化在随机选择游戏中获胜的总概率，如下所示，

我有n张彩票，其中只有1张是幸运票，现在我有2个选择，要么抽一张彩票，要么要求主人从总彩票中删除一些X个不幸的彩票，X必须是k的倍数（可用) 并且 X 必须小于票的总数。

如果我抽到了一个倒霉的票，大师就会在这堆票中添加k张倒霉的票。

我们最多可以玩 m 个动作，每个动作都是以下之一

  1. 要么我们抽一张票
  2. 要么我们要求主人删除 X 票（X 是 k 的倍数）

我想最大化概率。

并将总概率 P/Q 输出为 P*Q^(-1)，其中 Q 是 Q 的模逆。

观察和玩游戏后，我认为只有当我们按照以下方式玩游戏时，总概率才会最大

  1. 第一步我们抽一张票，中奖的概率是 1/n。

  2. 如果我们在第一步中抽到一张不走运的票，则添加 k 票，我们可以要求大师在第二步中删除 k 票。

  3. 在第三步中，我们再次抽奖，现在获胜的概率是
    ((n-1)/n)*(1/n) 。

同样，如果有 m 个动作，我们可以得出结论，获胜的总概率为 (1-((n-1)/n)^r)，其中我们可以找到 r 的值

n

例如：n = 3 k = 20 m = 3

总概率为 1-(2/3)^2 = 5/9

n = 5 k = 7 m = 1

获胜的总概率为 = 1/5

最终输出：

5*(9)^(-1) % 1000000007 = 555555560

1*(5)^(-1) % 1000000007 = 400000003

如果这个游戏中有其他获胜策略，请提供证据，我也没有我的策略的证据，所以如果你能证明我的策略，我会很高兴拥有它以及伪代码将帮助我继续.

我们再次将我们选择的票再次放入堆中，所以在抽错之后我们有 n+k 而不是 n+k-1，并且还有 n < k（总是开始）

编辑：我的策略证明

我们采取的每一步都有两种可能性

我们要么获得 1/n*(n-1)/n 要么获得 (n-1)/n*(1/n+k) + (n-1/n) ((n+k-1)/n +k) (1/n+2*k)

现在解决两边后，我们得到方程 1/n 左侧和右侧是 (2*n+3*k-1)/((n+2*k)*(n+k) 我发现RHS 总是小于或等于 RHS

因此，在进一步求解后，我得到 LHS 为 2*(k^2) 和 RHS 作为 n^2-n 并且给定 n < k 所以 LHS 总是大于 RHs

因此证明。

请为证明提供反馈。

标签： c++mathrandomprobabilitymaximize

解决方案

你的策略不正确。抽到一张倒霉的票后，你会要求主人移除k张票，但如果你在完全相同的状态下开始玩，你就会选择一张票。这是没有意义的，因为游戏不记得你以前的动作，因此目前的情况应该总是决定最好的选择。

设P(n,m,k)是用n票、最多m个动作和k以及最优策略获胜的概率。

如果你选择一张票，那么概率是1/n + P(n+k-1, m-1, k)*(n-1)/n。

如果你不这样做，那么概率是P(nk, m-1, k)

最优选择是概率最大的选择，因此：

P(n,m,k) = max( 1/n + P(n+k-1, m-1, k)*(n-1)/n , P(nk, m-1, k) )

您可以使用记忆化递归地计算这个，因为可能存在重叠的子问题，即使用动态编程。

推荐阅读