Determining the Average number of Attempts before a result occurs (using defined Probabilities)

Question

I'm trying to solve this problem but I'm completely unsure of what sort of concepts/formulas/proofs I need in order to tackle it. I'm just lost on where to start. Here's an example story problem as it relates to item drops off a boss in an MMORPG...

Loot Table:

• Pants - 30%
• Helm - 20%
• Shoulders - 15%
• Chest- 10%
• Arms - 25%

Given these values and that the boss always drops a single item and the probabilities of those drops are not influenced by previous drops, what the average number of boss kills one would need to get a Chest piece? What's the average number of attempts one would need to get 3 pants, 2 Shoulders and an 1 Arm piece?

Any help pointing me in the right direction for what I should be studying or reading up on to solve this would be most helpful.

Answer 1

Thanks to normalization the probability of looting a chest piece in N successful boss fights is: $$P_{N}(Chest)+P_{N}(No Chest)=1$$ The probability of getting no chest piece in N trials is much easier to write down: $$P(NoChest)= (0.9)^N$$ So, $$P(Chest)=1-P(NoChest)\rightarrow 1-(0.9)^N$$

The number of times you would expect an event is given by: $$<n_{Chest}>=\sum_{j=1}^N j*P_N=\sum_{j=1}^N j*(1-0.9^j)$$

Since you want at least one chest piece, then you want to know when for what value of capital N does the number of expected chest pieces raise above 1. Hope this helps.

Answer 2

As has been noted in comments, the expected number of attempts to get one item that has probability $p$ per attempt is $1/p$.

To find the expected number of attempts for a collection of items, we can use inclusion-exclusion. Let $A_n$ denote the event that the loot from $n$ kills doesn't contain $3$ pants, $B_n$ the event that it doesn't contain $2$ shoulders and $C_n$ the event that it doesn't contain $1$ arm piece. Then by inclusion-exclusion the probability that it doesn't contain the entire collection is

$$ P(A_n\cup B_n\cup C_n)=\\P(A_n)+P(B_n)+P(C_n)-P(A_n\cap B_n)-P(A_n\cap C_n)-P(B_n\cap C_n)+P(A_n\cap B_n\cap C_n). $$

The individual terms are

\begin{align} P(A_n)&=\sum_{k=0}^2\binom nk0.3^k0.7^{n-k}\;,\\ P(B_n)&=\sum_{k=0}^1\binom nk0.15^k0.85^{n-k}\;,\\ P(C_n)&=\sum_{k=0}^0\binom nk0.25^k0.75^{n-k}\;,\\ P(A_n\cap B_n)&=\sum_{k=0}^2\sum_{l=0}^1\binom n{k,l,n-k-l}0.3^k0.15^l0.55^{n-k-l}\;,\\ P(A_n\cap C_n)&=\sum_{k=0}^2\sum_{l=0}^0\binom n{k,l,n-k-l}0.3^k0.25^l0.45^{n-k-l}\;,\\ P(B_n\cap C_n)&=\sum_{k=0}^1\sum_{l=0}^0\binom n{k,l,n-k-l}0.15^k0.25^l0.6^{n-k-l}\;,\\ P(A_n\cap B_n\cap C_n)&=\sum_{k=0}^2\sum_{l=0}^1\sum_{m=0}^0\binom n{k,l,m,n-k-l-m}0.3^k0.15^l0.25^m0.3^{n-k-l-m}\;. \end{align}

The expected number of kills required to obtain the entire collection is the sum over $P(A_n\cup B_n\cup C_n)$ for all n, which we can get by summing the individual terms. For the first three terms, this just yields the known individual expectations:

\begin{align} \sum_{n=0}^\infty P(A_n)&=\frac3{0.3}=10\;,\\ \sum_{n=0}^\infty P(B_n)&=\frac2{0.15}=\frac{40}3\;,\\ \sum_{n=0}^\infty P(C_n)&=\frac1{0.25}=4\;. \end{align}

For $P(A_n\cap B_n)$, we get

\begin{align} &\sum_{n=0}^\infty\sum_{k=0}^2\sum_{l=0}^1\binom n{k,l,n-k-l}0.3^k0.15^l0.55^{n-k-l}\\ ={}&\sum_{k=0}^2\sum_{l=0}^1\binom{k+l}k0.3^k0.15^l\sum_{n=0}^\infty\binom n{k+l}0.55^{n-(k+l)}\\ ={}&\frac1{0.45}\sum_{k=0}^2\sum_{l=0}^1\binom{k+l}k\frac{0.3^k0.15^l}{0.45^{k+l}}\\ ={}&\frac{0.45^3+0.15\cdot0.45^2+0.3\cdot0.45^2+2\cdot0.3\cdot0.15\cdot0.45+0.3^2\cdot0.45+3\cdot0.3^2\cdot0.15}{0.45^4}\\ ={}&\frac{200}{27}\;, \end{align}

for $P(A_n\cap C_n)$

\begin{align} &\sum_{n=0}^\infty\sum_{k=0}^2\sum_{l=0}^0\binom n{k,l,n-k-l}0.3^k0.25^l0.45^{n-k-l}\\ ={}&\sum_{n=0}^\infty\sum_{k=0}^2\binom nk0.3^k0.45^{n-k}\\ ={}&\sum_{k=0}^20.3^k\sum_{n=0}^\infty\binom nk0.45^{n-k}\\ ={}&\frac1{0.55}\sum_{k=0}^2\left(\frac{0.3}{0.55}\right)^k\\ ={}&\frac{4460}{1331} \end{align}

and for $P(B_n\cap C_n)$

\begin{align} &\sum_{n=0}^\infty\sum_{k=0}^1\sum_{l=0}^0\binom n{k,l,n-k-l}0.15^k0.25^l0.6^{n-k-l}\\ ={}&\sum_{n=0}^\infty\sum_{k=0}^1\binom nk0.15^k0.6^{n-k}\\ ={}&\sum_{k=0}^10.15^k\sum_{n=0}^\infty\binom nk0.6^{n-k}\\ ={}&\frac1{0.4}\sum_{k=0}^1\left(\frac{0.15}{0.4}\right)^k\\ ={}&\frac{55}{16}\;. \end{align}

Finally, for $P(A_n\cap B_n\cap C_n)$,

\begin{align} &\sum_{n=0}^\infty\sum_{k=0}^2\sum_{l=0}^1\sum_{m=0}^0\binom n{k,l,m,n-k-l-m}0.3^k0.15^l0.25^m0.3^{n-k-l-m}\\ ={}&\sum_{n=0}^\infty\sum_{k=0}^2\sum_{l=0}^1\binom n{k,l,n-k-l}0.3^k0.15^l0.3^{n-k-l}\\ ={}&\sum_{k=0}^2\sum_{l=0}^1\binom{k+l}k0.3^k0.15^l\sum_{n=0}^\infty\binom n{k+l}0.3^{n-(k+l)}\\ ={}&\frac1{0.7}\sum_{k=0}^2\sum_{l=0}^1\binom{k+l}k\frac{0.3^k0.15^l}{0.7^{k+l}}\\ ={}&\frac{0.7^3+0.15\cdot0.7^2+0.3\cdot0.7^2+2\cdot0.3\cdot0.15\cdot0.7+0.3^2\cdot0.7+3\cdot0.3^2\cdot0.15}{0.7^4}\\ ={}&\frac{7300}{2401}\;. \end{align}

Putting it all together, we obtain the expected number of kills required:

$$ \sum_{n=0}^\infty P(A_n\cup B_n\cup C_n)=10+\frac{40}3+4-\frac{200}{27}-\frac{4460}{1331}-\frac{55}{16}+\frac{7300}{2401}=\frac{22334578793}{1380555792}\approx16.178\;. $$

Answer 3

Here's a different approach, more in Markov chain style. Let $t_{klm}$ be the expected time required to obtain at least $k$ pants, $l$ shoulders and $m$ arm pieces. Then

$$ t_{321}=\frac1{0.7}\left(1+0.3t_{221}+0.15t_{311}+0.25t_{320}\right)\;, $$

where the first term is the expected time required to make any form of progress and the remaining three terms are the probabilities of the three types of progress made times the expected times required for collecting the rest of the collection. Analogous equations hold for all $t_{klm}$ with all three indices non-zero. A zero index can no longer be reduced, so e.g.

\begin{align} t_{320}&=\frac1{0.45}(1+0.3t_{220}+0.15t_{310})\;,\\ t_{300}&=\frac1{0.3}(1+0.3t_{200}) \end{align}

and finally $t_{000}=0$. With these equations, we can determine all the expected times:

\begin{array}{c|cc} t_{kl0}&k=0&k=1&k=2&k=3\\\hline l=0&0&\frac{10}3&\frac{20}3&10\\ l=1&\frac{20}3&\frac{70}9&\frac{260}{27}&\frac{970}{81}\\ l=2&\frac{40}3&\frac{370}{27}&\frac{1180}{81}&\frac{430}{27}\\ \end{array}

\begin{array}{c|cc} t_{kl1}&k=0&k=1&k=2&k=3\\\hline l=0&4&\frac{182}{33}&\frac{2852}{363}&\frac{14174}{1331}\\ l=1&\frac{49}6&\frac{12319}{1386}&\frac{3317089}{320166}&\frac{919128559}{73958346}\\ l=2&\frac{667}{48}&\frac{3302417}{232848}&\frac{803043127}{53787888}&\frac{22334578793}{1380555792}\\ \end{array}

Here's the code that I used to calculate those numbers. The desired time $t_{321}$ is

$$ \frac{22334578793}{1380555792}\approx16.178\;. $$

Here's code to simulate the process, which confirms the result.