Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Problem description
- If, in Minecraft, you have a pool of n tiles filled with lava sources and an empty bucket in hand, and each time you right-click you target a random tile, how many clicks would it take on average before the pool is empty?
- Modelling the problem
- First of all, since the tile we click on is completely random, the lay-out of the pool doesn't matter. In fact, all that affects the current state is the total size of the pool (n), the amount of lava sources left in the pool (i) and whether or not the bucket in hand is currently filled. We will model the problem as the following Markov chain:
- States: F_i, E_i for i = 1, ..., n and E_n being the starting state. E_i represents the state with an empty bucket i lava sources left in the pool, F_i represents the state with a full bucket and i - 1 lava sources left in the pool.
- Transitions:
- For each i:
- E_i -> E_i: (n - i)/n (click on an empty tile)
- E_i -> F_i: i/n (click on a tile with a lava source)
- For i > 1:
- F_i -> E_i: (n - i + 1)/n (click on an empty tile)
- F_i -> E_i-1: (i - 1)/n (click on a tile with a lava source)
- For i = 1:
- F_1 -> E_1: 1 (click on an empty tile)
- We will define E_1 as the empty state and will try to calculate the average amount of steps from the starting state (E_n) to the first time we're in F_1 (after this we will cycle infinitely through E_1 and F_1).
- Infinite paths
- First, a note on infinite paths. Let's say we consider an infinite sequence of states (which I will call paths, although unlike in graph theory these paths can contain the same edge/transition multiple times) E_n, F_n, E_n, F_n, ... Technically speaking, this sequence can occur, but it does so with a probability of 0. After all, we would be multiplying infinitely many probabilities strictly smaller than 1 (assuming n > 1, in which case the problem is trivial).
- However, you might say, these outcomes still matter since, when calculating the mean of a discrete distribution, we multiply the probability of the outcome (in this case 0) with the value of the outcome, which would be infinite ... which in a sense is undefined (in a sense you can't even do arithmetic with infinity, but that aside). Even if you want to consider this, also consider that as we consider the subpath consisting of the first m states, as we increase m towards infinity, the probability of this path occurring goes to 0 exponentially while the length of the path only increases linearly. Therefore this term in the mean calculation would still converge to 0. As a result, it doesn't really make much sense to consider infinite paths so I won't discuss them anymore from here on out.
- Probabilities
- Because of the particular structure of the Markov chain, any path from E_n to F_1 will pass through the same steps: E_n to E_n-1, E_n-1 to E_n-2, ..., E_2 to E_1 and finally E_1 to F_1. We can consider the distributions X_n, ..., X_2, X_1 which represent the distribution of the path lengths going from each step to the next (so going from E_n to E_n-1 takes X_n steps and going from E_1 to F_1 takes X_1 steps). We know that the distribution of the total path length X is simply the sum of these distributions so we have:
- E[X] = E[X_n + ... + X_1] = E[X_n] + ... + E[X_1]
- i = 1 is the simplest case: when we are in E_1, we have a probability of (n - 1)/n to stay in the current state and 1/n to go to F_1. Therefore, E[X_1] = n.
- E[X_i] for i > 1
- Let's consider all paths going from E_i to E_i-1. These all fit into exactly one of the following three cases:
- - We go back to E_i, with a probability of (n - i)/n, increasing the path length by 1.
- - We first go to F_i and then back to E_i, with a probability of i*(n - i + 1)/n^2, increasing the path length by 2.
- - We first go to F_i and then to the target state E_i-1, with a probability of i*(i - 1)/n^2. The total path length is 2.
- Note that in the first two cases, the new state is again E_i, so the expected number of steps left is again E[X_i]. Therefore we can solve this problem recursively by writing out the mean in terms of these three cases:
- E[X_i] = (n - i)/n*(E[X_i] + 1) + i*(n - i + 1)/n^2*(E[X_i] + 2) + i*(i - 1)/n^2*2
- => (1 - (n - i)/n - i*(n - i + 1)/n^2)*E[X_i] = (n - i)/n + 2*i*(n - i + 1)/n^2 + 2*i*(i - 1)/n^2
- => (n^2 - n*(n - i) - i*(n - i + 1))*E[X_i] = n*(n - i) + 2*i*(n - i + 1) + 2*i*(i - 1)
- => (n^2 - n^2 + n*i - n*i + i^2 - i)*E[X_i] = n^2 - n*i + 2*n*i - 2*i^2 + 2*i + 2*i^2 - 2*i
- => (i^2 - i)*E[X_i] = n^2 + n*i
- => i*(i - 1)*E[X_i] = n*(n + i)
- i*(i - 1) is always strictly larger than 0, because i > 1, so:
- => E[X_i] = n*(n + i)/i*(i - 1)
- = n^2/(i*(i - 1)) + n/(i - 1)
- Putting everything together
- Combining the results for E[X_i] for i > 1 and i = 1, we get:
- E[X] = sum(i = 2, n, n^2/(i*(i - 1)) + n/(i - 1)) + n
- = n^2*sum(i = 1, n - 1, 1/(i*(i + 1))) + n*sum(i = 1, n - 1, 1/i) + n
- sum(i = 1, n - 1, 1/i) represents the (n - 1)-th Harmonic number H_n-1, for which no closed formula is known. However, it can be approximated as gamma + ln(n - 1), with gamma being the Euler-Mascheroni constant (https://en.wikipedia.org/wiki/Harmonic_number). Yet, since we multiply H_n-1 with n here, this approximation can be improved. To be precise, n*H_n-1 can be written as the following expansion (again, see Wikipedia):
- n*H_n-1 = n*ln(n - 1) + n*gamma + n/(2*(n - 1)) - n/(12*(n - 1)^2) + n/(120*(n - 1)^4)
- Although the standard approximation just keeps the two first terms, we can see that, because we multiply by n, the third term also doesn't converge to zero in our case, but rather towards 1/2. Therefore, for large n we can use the approximation:
- n*sum(i = 1, n - 1, 1/i)
- ~= n*ln(n - 1) + n*gamma + 1/2
- Meanwhile, the solution to sum(i = 1, n - 1, 1/(i*(i + 1))) is described on the mathematics Stack Exchange (https://math.stackexchange.com/questions/2422765/sum-of-reciprocals-of-product-of-consecutive-integers). I'll write down the essential part of the answer for our problem here:
- sum(i = 1, n - 1, 1/(i*(i + 1)))
- = sum(i = 1, n - 1, 1/i - 1/(i + 1))
- = 1/1 - 1/n
- = 1 - 1/n
- So, filling this in in our original formula, we get:
- E[X] = n^2 - n + n*H_n-1 + n
- = n*(n + H_n-1)
- which is approximated by n*(n + gamma + ln(n - 1)) + 1/2.
- Experimental verification
- I wrote the following Python code to experimentally verify the above mean calculations (and the approximation of the Harmonic numbers). The experiments seem to confirm the formula above.
- from random import randint
- from math import log
- import matplotlib.pyplot as plt
- gamma = 0.5772156649015328606065120900824024310421
- def get_sample_steps(n):
- # Perform an experiment and count the amount of steps it takes to get to an empty pool
- sources_left = n
- bucket_full = False
- steps = 0
- while sources_left > 0:
- tile = randint(0, n - 1)
- if tile < sources_left:
- # Clicked on lava source
- if bucket_full:
- bucket_full = False
- else:
- bucket_full = True
- sources_left -= 1
- else:
- # Click on empty tile
- if bucket_full:
- bucket_full = False
- sources_left += 1
- steps += 1
- return steps
- def H(n):
- # Calculates the n'th harmonic number
- return sum([1/i for i in range(1, n + 1)])
- for n in [2, 4, 8, 16, 32, 64, 128]:
- # Calculate experimental mean
- experiments_amount = 1000
- total_steps = 0
- average_steps = []
- for i in range(experiments_amount):
- total_steps += get_sample_steps(n)
- average_steps.append(total_steps/(i + 1))
- # Calculate theoretical mean
- theoretical_mean = n*(n + H(n - 1))
- # Calculate approximate theoretical mean
- approx_mean = n*(n + gamma + log(n - 1)) + 1/2
- print("n = %s: %s, %s, %s"%(n, average_steps[-1], theoretical_mean, approx_mean))
- print("Total steps:", total_steps)
- # Checked relative error, seems to converge with order O(n^-3)
- #print("Relative approximation error:", (theoretical_mean - approx_mean)/theoretical_mean)
- plt.plot(range(1, experiments_amount + 1), average_steps, "-", label="Sample mean (n = %s)"%n)
- plt.plot([1, experiments_amount], [theoretical_mean, theoretical_mean], "--", label="Theoretical mean (n = %s)"%n)
- # Verify convergence of sample means to theoreticalmeans visually
- plt.legend()
- ax = plt.gca()
- ax.set_xscale("log")
- ax.set_yscale("log")
- plt.xlabel("Samples")
- plt.ylabel("Mean")
- plt.show()
- plt.close()
Advertisement
Add Comment
Please, Sign In to add comment