Digging Probabilities

[flamebirde]

So the other day I was watching a speedrun of the Legend of Zelda: Ocarina of Time (a speedrun is a playthrough of a game with the intent of beating the game as fast as possible). In one particular part of the game, the player is forced to follow around a gravedigger as he digs up various holes. There is one particular outcome that is desired (the "jackpot" of the game, essentially): a permanent health upgrade. There are also three undesirable outcomes that only give out money: a green rupee (the least valuable prize, pretty much $1), a blue rupee (a fairly desirable prize, say about $5), and a red rupee (a very desirable prize, say $20).

Here are the rules:

The chances of digging up a green rupee is 40%, a blue rupee 30%, a red rupee 20%, and the health upgrade 10%.

If the gravedigger has dug up eight green rupees already, and he would dig up a ninth green rupee this time around, he will instead dig up the health upgrade.

If the gravedigger has dug up four blue rupees already and he would dig up a fifth this time around, he will instead dig up a green rupee.

If the gravedigger has dug up two red rupees already and he would dig up a third this time around, he will instead dig up a blue rupee.

As a result, the maximum number of attempts to dig up the health upgrade is fifteen.

Example: four blue rupees and two red rupees have been dug up. If the gravedigger hit the 20% chance to dig up a red rupee on his seventh total attempt, he would instead dig up a blue rupee. However, four blue rupees have already been dug up, so he would actually dig up a green rupee.

After digging up the health upgrade, the game is over.

 

Three questions:

One: what is the probability that it will take a player the maximum number of tries to dig up the most desirable outcome (the health upgrade)?

Two: What is the expected average number of tries for the health upgrade?

Three: There exists two methods to play this minigame. First is the method described above. Second is that after the first dig, the player exits and reenters the area. This resets the green/blue/red rupee counter, but also allows the player to try another dig far faster. This introduces the potential for an infinite number of tries (the world record currently sits at about 100, which is pretty unlucky to say the least). Say it takes a player ten seconds between digs using the first method, and five seconds between digs using the second method. On average, which one will get you the health upgrade the fastest?

 

Disclaimer: I've got an answer to the first question and maybe the second, but I've got no clue for the third.

Edited January 19, 2018 by flamebirde
Spelling.

[bonanova]

My understanding of the puzzle

Spoiler

In general:

• Each dig reveals a prize -- there are no empty holes.|
• Game ends when you get health.

In Method 1,

• Each dig takes 10 seconds.
• Gravedigger continues digging until health upgrade is found, then stops.
• You won't get more than (8, 4, 2) of the (green, blue, red) stones
• Best / Worst cases are 1 / 15 digs (10 / 150 seconds) to get health.

In Method 2,

• Each dig takes 5 seconds
• You reset and go to the next round after every dig
• You can end up with any number of (green, blue, red) stones
• Best case is 5 seconds. No worst case.

 

If that's all true, then

Q1:

Spoiler

Probability to take maximum digs (15) to get health.

After 14 digs we must have {X} = {BBBBBBBB GGGG RR} in some order.
No matter what, (with complete certainty) the next dig gives you H.

If we say we have to dig exactly 8 B's, 4 G's and 2 R's the probability would be

p = .4^8 x .3^4 x .2^2 = .00065536 x .0081 x .04 = 2.1233664 x10-7

But that's unnecessarily restrictive. We could also get {X} by digging 14 B's:

p = .4^14 = 2.68435456 x 10-6 (more than 10 x as likely)

But there are many more paths to get to {X}:

1. First, dig anything but H (p=.9) until you have dug or made two R's.
2. Then, dig anything but H or R (p=.7) until you have dug or made four G's.
3. Then, dig only B's (p=.4) until you have 14 rupies.

That admits a slew of cases, which we'd have to enumerate and compute a weighted average. Or, we might compute the expected number of steps (1) and (2). Too complex for my taste. Instead, here's a conservative estimate that involves doing (1) twice, (2) four times and (3) eight times. Now it's seen to be much more likely.

p = .9^2 x .7^4 x .4^8 = .0049787136  (about .5%)

Including the cases we omitted above for simplicity increases the result. If steps 1 and 2 are done only a few more times, it easily becomes a few percent.

Q2:

Spoiler

Average number of digs to get health upgrade.
What are the most likely ways to get H?

• H   p=.1  <digs> = 10  (100 sec)
• RRR   p = .008  <digs> = 125  (1250 sec)
• GGGG(G or R)RR   p = .0081 x .5 x .04 = .000163   <digs> = 6172.8  (61728 sec)

The likelihood of getting H (in the first 10 digs) without just digging it is very small.

Answer: 10 digs. (100 seconds)

Q3:

Spoiler

Compare Method 1 and Method 2 for speed of win.

In Method 2, there are no "upgrades."
You can't get H without actually digging it, with p = .1.
<Digs> is still 10, but now that's only 50 seconds.

Method 2 wins.

 

 

[flamebirde]

18 hours ago, bonanova said:

My understanding of the puzzle

  Hide contents

In general:

• Each dig reveals a prize -- there are no empty holes.|
• Game ends when you get health.

In Method 1,

• Each dig takes 10 seconds.
• Gravedigger continues digging until health upgrade is found, then stops.
• You won't get more than (8, 4, 2) of the (green, blue, red) stones
• Best / Worst cases are 1 / 15 digs (10 / 150 seconds) to get health.

In Method 2,

• Each dig takes 5 seconds
• You reset and go to the next round after every dig
• You can end up with any number of (green, blue, red) stones
• Best case is 5 seconds. No worst case.

 

If that's all true, then

Q1:

  Hide contents

Probability to take maximum digs (15) to get health.

After 14 digs we must have {X} = {BBBBBBBB GGGG RR} in some order.
No matter what, (with complete certainty) the next dig gives you H.

If we say we have to dig exactly 8 B's, 4 G's and 2 R's the probability would be

p = .4^8 x .3^4 x .2^2 = .00065536 x .0081 x .04 = 2.1233664 x10-7

But that's unnecessarily restrictive. We could also get {X} by digging 14 B's:

p = .4^14 = 2.68435456 x 10-6 (more than 10 x as likely)

But there are many more paths to get to {X}:

1. First, dig anything but H (p=.9) until you have dug or made two R's.
2. Then, dig anything but H or R (p=.7) until you have dug or made four G's.
3. Then, dig only B's (p=.4) until you have 14 rupies.

That admits a slew of cases, which we'd have to enumerate and compute a weighted average. Or, we might compute the expected number of steps (1) and (2). Too complex for my taste. Instead, here's a conservative estimate that involves doing (1) twice, (2) four times and (3) eight times. Now it's seen to be much more likely.

p = .9^2 x .7^4 x .4^8 = .0049787136  (about .5%)

Including the cases we omitted above for simplicity increases the result. If steps 1 and 2 are done only a few more times, it easily becomes a few percent.

Q2:

  Hide contents

Average number of digs to get health upgrade.
What are the most likely ways to get H?

• H   p=.1  <digs> = 10  (100 sec)
• RRR   p = .008  <digs> = 125  (1250 sec)
• GGGG(G or R)RR   p = .0081 x .5 x .04 = .000163   <digs> = 6172.8  (61728 sec)

The likelihood of getting H (in the first 10 digs) without just digging it is very small.

Answer: 10 digs. (100 seconds)

Q3:

  Hide contents

Compare Method 1 and Method 2 for speed of win.

In Method 2, there are no "upgrades."
You can't get H without actually digging it, with p = .1.
<Digs> is still 10, but now that's only 50 seconds.

Method 2 wins.

 

 

Question 1:

Spoiler

Everything you've said so far is true. Can you give me a better approximation than "a few percent"?

Questions 2 and 3 are correct! Followup question: What are the chances I get the health from the 14th dig versus the 15th dig? Do they differ significantly?

[bonanova]

20 hours ago, flamebirde said:

Followup question: What are the chances I get the health from the 14th dig versus the 15th dig? Do they differ significantly?

Assuming your interest is in Method 1:

Spoiler

Here are probability estimates (in percentage terms) of winning after all possible number of digs (1 2 3 4 ... 14 15) based on 2 million simulations of Method 1: (+/- ~0.1%)

10.0  9.0  8.9  8.9  8.7  8.2  7.8  7.5  7.1  6.2  5.1  4.0  2.9  2.0  3.6

So my estimate (Answer 1) of a "few percent" for 15 digs is confirmed at 3.6%.

To answer your subsequent question, the 14-digs and 15-digs cases are significantly different --  almost by a factor of two. It might be simple to analyze the possible 13-digs configurations to show exactly how the 14-digs and 15-digs likelihoods compare. I might look into that.

The simulations also give estimates for wait times for wins after 1 2 3 ... 14 15 digs:

10.0  11.1  11.3  11.2  11.5  12.2  12.8  13.3  14.1  16.1  19.5  25.1  34.4  49.4  28.0 

 

[flamebirde]

Very nice! Well done!

[bonanova]

No spoiler needed:

There are only three no-win-after-13-digs possibilities:

1. BBBB BBB GGGG RR  Win on dig 14 with G or R or H = 60%.  Win on dig 15 with B = 40%
2. BBBB BBBB GGG RR  Win on dig 14 with R or H = 30%.         Win on dig 15 with B or G = 70%
3. BBBB BBBB GGGG R  Win on dig 14 only with H = 10%.         Win on dig 15 with B or G or R = 90%.

Their relative occurrences were not saved in the simulations, so it's a bit uncertain how weight these cases when taking an average. But if they are equally likely, the relative dig-14 and dig-15 wins would be exactly 33.33...% and 66.66...% That is, Win 15 would be twice as likely as Win 14.

For the simulations, the last few probability estimates are the least precise, because they are averages of fewer cases. In particular, the probability of going beyond 13 digs is only 5.6%, so that out of 2 million total cases, only about 112,000 14-digs or 15-digs cases were averaged. Those relative win probabilities are 35.7% and 64.3% respectively.

I'll point out that the proportions of needed B G R and H (8 4 2 1) are similar to their occurring probabilities ( 40% 30% 20% 10% ). That partially justifies an equal-likelihood assumption. But the proportions do differ, somewhat. In particular, B is needed 8/15 of the time but occurs only 40/100 = 4/10 = 6/16 of the time. This fact might well make a missing-B-after-13-moves (Case 1) the most likely case of the three. That case has the highest win-14 probability. So we might expect an upward bias on the win-14 probability. The simulation suggests that is the case.