# Rupees from Bushes in Majora's Mask, what distribution to use?

I have a probability table like so:

+---+-------+-------+-----+
| X |   P   | Mean  | X^2 |
+---+-------+-------+-----+
| 1 | 3/16  | .1875 |   1 |
| 3 | 1/16  | .1875 |   9 |
| 5 | 1/16  | .3125 |  25 |
| 0 | 11/16 | 0     |   0 |
+---+-------+-------+-----+


This represents the odds of getting Rupees from bushes in Zelda: Majora's Mask, with the chances of 1 rupee being 3/16, 3 being 1/16, and 5 being 1/16.

I've calculated the mean to be 0.6875 and variance 1.83984375, the standard deviation being 1.356408401.

However, this is only for destroying a single shrub, and I would like to calculate the odds of getting at least X rupees for cutting X number of shrubs, and ideally select the correct distribution to model the function. My initial thought was that this would more accurately be modeled as a Binomial Distribution, rather than using a Normal distribution as I was initially looking at doing, since I used one for modeling Bomb Drops in Ocarina of Time. However, as there are more than two possible outcomes, a binomial distribution doesn't seem to work here.

Using a normal distribution, I can simply multiply the mean and the standard deviation by the number of bushes to get the mean and standard deviation for the final rupee count, but since this is discrete data, with known probabilities and independent events, I'd prefer a discrete solution.

For example, when cutting 72 bushes (6 groups of 12), assuming normality gives me a mean of 49.5 and a standard deviation of 97.66, however, this gives a 31% chance of getting 0 rupees or less, which obviously makes no sense in this situation, and is completely incorrect in practice.

What's the correct way to model this behavior?

For those interested in the MM drop tables, I recently put together an infographic explaining them, with the data pulled from RAM.

• Using a normal distribution here will never make sense, because you will always have a positive probability of losing rupees by cutting bushes (no matter the mean or standard deviation), which to my knowledge is not possible. Do you know for a fact that the drops are independent between bushes? The distribution for the sum will follow from their joint distribution. May 25, 2018 at 12:23
• Yes, they are independent, assuming the Random Number Generator in the game works well enough. I'm not sure I quite understand "The distribution for the sum will follow from their joint distribution." can you clarify? I suppose I'm just not sure what kind of distribution this should be, clearly the average number of rupees gained will be .6875 per bush, but I'm not sure how it's distributed May 25, 2018 at 17:43
• I mean that there's nothing left to "model", the distribution of a single bush + independence between bushes completely determines the distribution of the sum (for fixed number of bushes); you just have to go through the cases and compute the result. Do you need an exact answer/formula for general number of bushes, or would an approximate Monte Carlo estimate suffice? Should the probability of zero rupees actually be 11/16 (so it adds up to 1)? May 26, 2018 at 0:11
• I suppose I was hoping there would be a cleaner formula to describe the distribution than simply running through the permutations, but I suppose this situation is unique enough that it wouldn't make sense for such a formula to exist. A Monte Carlo may be good enough for what I want, so that may be simpler in the end. May 26, 2018 at 3:52

So I contacted an old Statistics professor I had in college about this problem, and he pointed me to the Multinomial distribution, the exact solution to solving for the odds of getting any specific count of each drop type.

I used the Multinomial function in the form of

N! / (n1! * n2! * n3! *n4!) * (p1^n1 * p2^n2 * p3^n3 * p4^n4)


Where $$N$$ is the total number of shrubs being cut, with the $$n$$'s representing each possible drop outcome, and the $$p$$'s the probability of each outcome occurring.

With this, I could calculate the exact odds of getting 30 green rupees x1, 10 green rupees x3, 5 blue rupees, and nothing 27 times.

However, since the multinomial doesn't have a straightforward CDF, and I wanted a CDF of total rupees, not simply counts, I still needed to calculate all of the possible combinations of drops I could get, and not just the total number, but actually each individual combination.

This problem is called a multichoose, or stars and bars problem, and it's essentially a problem where, rather than selecting a smaller group from a larger group, as is typical in combination problems, you're basically figuring out every way you can place a large number of items into a smaller number of buckets. The total number of possibilities can be calculated by $$\left( \! \binom{k}{n} \! \right) = \binom{k + n - 1}{n}.$$

Where $$k$$ is the number of buckets, and $$n$$ is the number of items being placed into the buckets. (Or classically, number of bars to divide with and the number of stars). Now, this formula can get me the total number of possibilities, but not the possibilities themselves, for that I needed to brute-force the problem programmatically.

While I began by trying to write my own algorithm, I found a repository of multichoose generation functions in various languages by ekg. I used the Python version to output every possible multiset to a CSV file.

From there, in Excel I totaled up the Rupee value for each multiset, and ran the numbers through the multinomial function to get the probability of each multiset occuring. Then I used a Pivot Table to total up the probabilities for all multisets with the same Rupee totals, and then simply used that data to get a cumulative probability for the Rupee totals. I also did a Monte Carlo simulation of 10 million attempts in R to confirm that the numbers were correct, and they matched very neatly (closely enough in fact that I think I'd recommend a Monte Carlo solution to anyone dealing with a problem like this). Here's the Monte Carlo code:

combos <- matrix(0, nrow=10000000, ncol=4)
for(trial in 1:10000000) {
outcomes <- sample(c(1, 2, 3, 4), size = 72, replace = TRUE, prob = c(5/16, 1/16, 1/16, 9/16))
combos[trial,] <- tabulate(outcomes, nbins=4)
}

rupeeSimulations <- apply(combos, 1, function(row) row*1+row*3+row*5)
table(rupeeSimulations) I showed this to Majora's Mask speedrunners, and the numbers didn't seem to line up with their experience. This had me dig further into the Drop Table behavior, and I discovered that Majora's Mask has a drop type that I now call "Mask Drops," where the game actually changes the drop depending on what mask the player is currently using. Turns out, Deku Scrub mask would turn that drop into green rupees, and on my original table, I had tested everything as Link, with no mask, so I got Arrows rather than rupees for that type of drop.

So in the end, discovered something completely new about the game, had to update my Drop Table Infographic (new version here), and finally I was able to get an accurate chart of this original problem, enjoy: I learned a lot, I hadn't ever seen the multichoose and I didn't recall the multinomial function from my studies. Thank you for everyone who looked at this, big thanks to my college professor for pointing me in the right direction.

You can compute an exact distribution by using a repeated convolution.

Here is an example with r code:

n = 10
### a vector of probabilities for the number of rupees
p = rep(0,n*5+5+1)
p[1+c(0,1,3,5)] = c(11,3,1,1)/16

### loop some number of times for the number of shrubs
for (i in 2:n) {
p_new = p*0
### go through all values of the vector of probabilities and compute the new probabilities
for (j in 1:(n*5+1)) {
p_new[j+c(0,1,3,5)] = p_new[j+c(0,1,3,5)] + p[j]*c(11,3,1,1)/16
}
p = p_new
}

plot(0:(n*5), cumsum(p[1:(n*5+1)]), xlab = "number of rupees", ylab = "cumulative probability") • Yeah, my solution definitely overcomplicated by not consolidating the intermediary steps immediately, I appreciate you putting together the code for it. May 10 at 15:27