Jinx or Jackpot

The hidden jackpot chance is fixed. If the owner picked probability $q = p_i / 100$, then every round uses that same $q$. This means observations update Jack's belief. Treating each round as if the casino rerolls $p_i$ is the classic wrong turn here.

Belief states

Suppose Jack has seen $w$ jackpots and $l$ jinxes. For a candidate probability $q$, the likelihood of this observation history is:

$q^w(1-q)^l.$

The exact order of the outcomes does not matter, only the counts. Let cnt[p] be how many indices have value $p$. Define:

$S(w,l)=\sum_{p=0}^{100} cnt[p]\left(\frac{p}{100}\right)^w\left(1-\frac{p}{100}\right)^l.$

This is the total posterior weight of the state. Then the posterior probability that the next round is a jackpot is:

$P_W(w,l)=\frac{S(w+1,l)}{S(w,l)}.$

Similarly:

$P_L(w,l)=\frac{S(w,l+1)}{S(w,l)}.$

There are only states with $w+l \le k$, and $k \le 30$, so this part is tiny.

Why the balance disappears

Let $F_t(w,l)$ be the best expected final balance multiplier if Jack currently has 1 dollar, has seen $w$ wins and $l$ losses, and has $t$ rounds left.

Base case:

$F_0(w,l)=1.$

Now suppose Jack currently has balance $B$ and bets integer $x$. By induction, after a win his future expected balance is:

$(B+x)F_{t-1}(w+1,l),$

and after a loss it is:

$(B-x)F_{t-1}(w,l+1).$

So the expected final balance is:

$P_W(B+x)F_{t-1}(w+1,l)+P_L(B-x)F_{t-1}(w,l+1).$

Rearrange it:

$B\left(P_WF_{t-1}(w+1,l)+P_LF_{t-1}(w,l+1)\right)+x\left(P_WF_{t-1}(w+1,l)-P_LF_{t-1}(w,l+1)\right).$

For this state, everything except $x$ is fixed. So this is just a linear function of $x$.

Jack may choose any integer $x$ with $0 \le x \le B$. A linear function on that interval is maximized at an endpoint. No fancy fractional bet, no balance DP, no cursed 1000-dimensional nonsense. The optimal bet is always either:

• $x=0$, observe for free and keep the same money;
• $x=B$, go all-in.

Transition

If Jack bets $0$, his balance stays the same, and he learns the outcome:

$zero=P_WF_{t-1}(w+1,l)+P_LF_{t-1}(w,l+1).$

If Jack goes all-in, losing sends his balance to $0$, so only the win branch contributes:

$allin=2P_WF_{t-1}(w+1,l).$

Therefore:

$F_t(w,l)=\max(zero, allin).$

The answer is the expected final balance minus the initial 1000 dollars:

$1000(F_k(0,0)-1).$

Unreachable states

If $S(w,l)=0$, that observation state is impossible under all candidate probabilities. Its DP value never matters. In code, set it to something harmless like 1 and skip division by zero. This matters for cases with $p=0$ or $p=100$; otherwise NaNs sneak in and ruin the party.

Complexity

There are $O(k^2)$ states and only 101 possible probability values after compression. So the complexity is:

$O(101k^2),$

with tiny memory. For these limits, it basically runs before the slot machine finishes blinking.