Skip to main content
added 1 character in body
Source Link
Henry
  • 174.2k
  • 10
  • 141
  • 314
Source Link
Henry
  • 174.2k
  • 10
  • 141
  • 314

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