7
$\begingroup$

This is a question that came up to me about the game Slay the Spire's 'potion chance' mechanic. It also applies to various other similar mechanics in other games (perhaps with different exact numbers).

It works as follows:

The potion chance $p_x$ at floor $x$ is defined based on whether you got a potion previously $r$ (which I take as $1$ if this happened, $0$ otherwise) as:

$$ \begin{equation} p_x = \begin{cases} 0.4 & \text{if } x = 1 \\ 0.1 & \text{if } r_{x-1} = 1 \\ 0.1 + p_{x-1} & \text {if } r_{x-1} = 0 \end{cases} \end{equation} $$

While setting up a spreadsheet to calculate all cases through brute force is possible for the actual game's mechanics (the number of floors where it's possible to get a potion in an act is realistically never above $10$), it's left me wondering if there's an actual closed solution or (failing that) 'close enough' approximation to the following:

Given an amount of combat floors $f$, what is:

  • The expected amount of potions you get $a_f = E(\Sigma_{x=1}^{f}(p_f))$?
  • What happens $\text{lim}_{f \rightarrow \infty}? $
  • The chance of getting $n$ potions $q_{n,f} = P( \Sigma_{x=1}^{f} r = n)$?

For example, $a_0 = 0$, $a_1 = q_{1,1} = 0.4$ trivially, and $a_8 \approx 2.36885918$ via suming 256 possible cases. This makes the brute force method $O(2^n)$.


Part solution:

Another example of someone using a code approach for a related (the inverse of this one) question is here: https://gaming.stackexchange.com/a/178681/148546. Adapting the forward code for this question, you get that $$n_{\text{max}} = 1 / 0.1 = 10 $$

$$\text{lim}_{f \rightarrow \infty} p_{\text{average}} = (\Sigma_{n=1}^{n_{\text{max}}} P(\text{potion nth floor}) \cdot P(\text{potion by nth floor}))^{-1} \approx 0.273207944 $$

The initial '0.4' chance can be entirely ignored as every potion past the first one works exactly the same as the formula there.

$\endgroup$

2 Answers 2

5
$\begingroup$

You have a sparse transition matrix which looks like

$$\begin{pmatrix} 0.1 & 0.9 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0.2 & 0 & 0.8 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0.3 & 0 & 0 & 0.7 & 0 & 0 & 0 & 0 & 0 & 0\\ 0.4 & 0 & 0 & 0 & 0.6 & 0 & 0 & 0 & 0 & 0\\ 0.5 & 0 & 0 & 0 & 0 & 0.5 & 0 & 0 & 0 & 0\\ 0.6 & 0 & 0 & 0 & 0 & 0 & 0.4 & 0 & 0 & 0\\ 0.7 & 0 & 0 & 0 & 0 & 0 & 0 & 0.3 & 0 & 0\\ 0.8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.2 & 0\\ 0.9 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.1\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{pmatrix}$$

You can find $\mathbb P(\text{potion on }n\text{th floor})$ by taking the $n$th power of this matrix combined with your starting position, an $O(n)$ exercise. So for example for the $1$st floor it is $0.4$, the second floor $0.34$, the third $0.286$, the fourth $0.2602$, the fifth $0.26038$ and the sixth $0.270154$.

Summing these gives the expected number of potions seen by floor $n$, so $0.4$, $0.74$, $1.026$, $1.2862$, $1.54658$, $1.816734$ etc.

The stationary distribution $\pi$ will have $\pi_{k}=\frac{11-k}{10} \pi_{k-1} =\frac{9!}{(10-k)!10^{k-1}}\pi_1$ and so the limiting proportion you want is $$\lim\limits_{n \to \infty}\mathbb P(\text{potion on }n\text{th floor}) =\pi_1 = \frac{1}{\sum\limits_{k=1}^{10} \frac{9!}{(10-k)!10^{k-1}}} =\frac{1562500}{5719087} \approx 0.273207943855$$ as you found. So the expected gap between finds of poison is the reciprocal of that, i.e. $\frac1{\pi_1}=\frac{5719087}{1562500}=3.66021568$ floors, with variance about $2.9426$ (standard deviation about $1.7154$).

Because you did not start at the stationary distribution, the expected number of poisons seen by the $n$th floor is not simply $\pi_1 n$ even for large $n$, but approaches $\pi_1 n +0.182546466$.

It is possible to find the distribution of the number of poisons $p$ found by floor $n$. Start with $M(n,0,k)=0$ except $M(0,0,4)=1$ then say that $M(n+1,p+1,1)=\sum\limits_{k=1}^{10} \frac{k}{10}M(n,p,k)$ and that $M(n+1,p,k+1)=\left(1-\frac{k}{10}\right) M(n,p,k)$. The probability of having found $p$ poisons by floor $n$ is $\sum\limits_{k=1}^{10} M(n,p,k).$

The columns of this table shows those probabilities for small $p$ and $n$ and can be used to confirm the expectations calculated earlier. Clearly by floor $n$ the number of poisons found can range between $\left\lfloor\frac{n+3}{10}\right\rfloor$ and $n$; the distribution is right-skewed within this range. The time-complexity of this calculation is $O(n^2)$.

 floor  0   1   2       3       4       5       6           7
poisons                             
0       1   0.6 0.30    0.120   0.0360  0.00720 0.000720    0
1       0   0.4 0.66    0.738   0.6636  0.50616 0.334800    0.1936080
2       0   0   0.04    0.138   0.2790  0.42240 0.523008    0.5527872
3       0   0   0       0.004   0.0210  0.06138 0.130332    0.2224656
4       0   0   0       0       0.0004  0.00282 0.010782    0.0294240
5       0   0   0       0       0       0.00004 0.000354    0.0016722
6       0   0   0       0       0       0       0.000004    0.0000426
7       0   0   0       0       0       0       0           0.0000004
$\endgroup$
2
$\begingroup$

Let $(X_n)$ be the binary random variable represents the chance of potions per floor. Then, $\mathbb{P}(X_1 = 1) = 1 - \mathbb{P}(X_1 = 0) = 0.4$, for $n \ge 2$, we have: $$ X_n \vert (X_{n - 1} = 1) = \begin{cases}1 \text{ with probability 0.1} \\ 0 \text{ with probability 0.9} \end{cases} $$ and $$ X_n \vert (X_{n - 1} = 0) = \begin{cases}1 \text{ with probability } 0.1 + \mathbb{P}(X_{n - 1} = 1)\\ 0 \text{ with probability } 0.9 - \mathbb{P}(X_{n - 1} = 1) \end{cases} $$

Let $p_n = \mathbb{P}(X_n = 1)$, then we have: $$ p_n = 0.1 \cdot p_{n - 1} + (0.1 + p_{n - 1}) \cdot (1 - p_{n - 1}) = 0.1 + p_{n - 1}\cdot(1 - p_{n - 1})\ \forall n \ge 2 $$ with $p_1 = 0.4$. This sequence quickly converges to $\sqrt{0.1} \approx 0.316$, which implies the expected amount of potions up to floor $n$ will converge to $\infty$ as $n \rightarrow \infty$: $$ a_n = \mathbb{E}\left(\sum_{k = 1}^n X_k\right) = \sum_{k = 1}^n p_k \rightarrow \infty $$

$\endgroup$
1
  • $\begingroup$ I suspect you may have misinterpreted the question: the probability of finding poison on a particular floor seems to increase with the number of recent floors you have not found poison, and the question gives $0.273207944$ as the limiting value of $p_n = \mathbb{P}(X_n = 1)$ $\endgroup$ Commented 13 hours ago

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.