4

In a game called hearthstone you buy packs to collect cards. They have four types of cards. Each type of cards has assigned a probability. So you open a pack and a random number is generated. The most valuable cards (called legendary) as you may expect are the least frequent. The owners of the game didnt want people to quit the game because of bad luck so they added a pity timer. If you didnt open a legendary in the previous 39 packs, when you open the number 40 you will always get a legendary card and the timer is set to zero. If you opened a legendary before the 40 pack the timer is also set to zero.

The problem can be formulated as follows. If an event has probability p to happen and you ask for a condition that is if n-1 times in a row the event didnt happened, the event will always happen on the trial number n. What is the new probability of the event happening due to this condition?

Thanks for reading!

Qwerty
  • 6,165
beto
  • 41

2 Answers2

4

You have to think of it as the long term fraction of decks that give you a legendary card. Intuitively, if $p$ is fairly large, it won't matter at all because the chance of $n$ failures in a row is very small. If $p$ is very small, the probability goes from very small to $1/n$ because you will never find a legendary card until the pity timer kicks in.

If there is no pity timer, the waiting time to get a legendary card is $1/p$. The chance of failing the first $n$ times is $(1-p)^n$. The waiting time for a legendary card assuming you fail the first $n$ times is $n+1/p$, so the reduction in waiting time is (chance you fail $n$ in a row)(waiting time from then), which is $(1-p)^n(1/p)$ and the new waiting time is $\frac 1p-\frac 1p(1-p)^n$. The fraction of decks that give you a legendary card are then $\frac 1{\frac 1p-\frac 1p(1-p)^n}$

Ross Millikan
  • 374,822
  • I can not fully understand you. What do you mean by waiting time? How is it defined? – beto Jul 06 '16 at 19:21
  • 1
    Waiting time is the expected time until an event. For a discrete exponential distribution, it is the inverse of the probability, so on rolling a die the waiting time for a $4$ (or any other specific number) is $6$ throws. – Ross Millikan Jul 06 '16 at 20:05
3

Ross's formula is correct, here is another derivation/proof.

Let's call all packs with a legendary a legendary pack, and all packs without a legendary a bad pack.

Let's say you just opened a legendary pack. The probability that the immediate next pack will be legendary, with zero bad packs in between, is $p$.

The probability that you will open 1 bad pack before getting another legendary is $(1 - p) * p$, ie the probability of getting a bad pack on the first pack, times the probability of getting a legendary on the second pack.

The probability of opening 2 bad packs before getting a legendary is similarly $(1 - p) * (1 - p) * p = (1 - p)^2 * p$.

More generally, for $i < n - 1$, the probability of opening exactly $i$ bad packs before getting a legendary is $(1 - p)^{i} * p$.

Then, the probability of opening exactly $n - 1$ bad packs before getting a legendary is $1$ minus the probability of opening fewer than $n - 1$ bad packs in a row, which is simply the sum of all probabilities with $i < n - 1$. So the probability of having exactly $n - 1$ bad packs is $1 - \sum_{i=0}^{n - 2}p * (1 - p)^{i}$.

Then, we compute the average number of bad packs we need to open to get a legendary. This is simply the sum of all possible numbers of bad packs we may need to open, times the probability of needing to open that many bad packs. Using our formulas above, the average number of bad packs you will need to open for one legendary is:

$[\sum_{i=0}^{n - 2}i * Pr(opening\ exactly\ i\ bad\ packs)] + (n - 1) * Pr(opening\ exactly\ n-1\ bad\ packs)$

$ = [\sum_{i=0}^{n - 2}i * p * (1 - p)^{i}] + (n - 1) * (1 - [\sum_{i=0}^{n - 2}p * (1 - p)^{i}])$

You can look up those sums, and plugging in their closed form solutions and using some algebra, reduce this to:

Average number of bad packs needed for one legendary = $\frac {1 - p - (1 - p)^n}{p}$

If you need to open $k$ bad packs on average for every 1 legendary pack, then the fraction of legendary packs you will tend to have is $\frac {1} {k + 1}$. Plugging in our formula for k above, the average fraction of legendary packs you will have is:

$\frac 1 {\frac {1 - p - (1 - p)^n}{p} + 1}$

which simplifies to

$\frac p {1 - (1 - p)^n}$

the same as Ross's formula.

As Ross hinted above, we can double check our formula's behavior for limiting cases. Plugging in $n = 1$ returns an average fraction of $1$, as we expect, since a pity timer of 1 means we get legendaries every time. Taking $\lim_{n\to\infty}$ gives us $p$, the value we'd expect if we had no pity timer at all. Plugging in $p = 1$ also gives $1$, as we would expect to get legendaries every time. You can also confirm that $\lim_{p\to0}$ returns $\frac1n$.

sol_var
  • 163