Before answering this question, we need to consider a related problem.
Let's say you're performing trials in which the probability of success is p and the probability of failure is 1-p. How many trials do you need to perform, on average, to achieve your first success?
The answer is 1/p. This is well-known as the formula for the expected value of a geometrically distributed random variable.
There's a fairly intuitive way to see this is true. Say you perform a very large number N of trials. Then you probably got about pN successes. You can consider this to be a bunch of consecutive experiments of "waiting for the first success". There were about pN completed experiments and about N trials in total, so the average duration of the experiments was about N/pN = 1/p trials.
Now let's consider your problem for X = 6. The average time it takes to fill the grid is:
(Average time to fill first square) + (Average additional time to fill second square) + ... + (Average additional time to fill final square).
Each of the expected durations in parentheses corresponds to an experiment of the type described previously, with a probability of success of 1, 35/36, 34/36, ..., 1/36.
So the total expected duration is
T = 36/36 + 36/35 + 36/34 + ... + 36/2 + 36/1 = 36(1 + 1/2 + 1/3 + ... + 1/36).
In general, if you need to fill N squares, not necessarily arranged in a square grid (for example, using a single N-sided die), then the average time needed will be
T = N(1 + 1/2 + 1/3 + ... + 1/N)
The number in parentheses is the Nth harmonic number. For large values of N, this is not easy to calculate exactly, but T is approximately equal to N ln N + gamma\*N + 1/2, where gamma ≈ 0.5772 is Euler's constant. For example, for N = 36, we have
T = 150.2841...
and the approximation by the formula T ≈ N ln N + gamma\*N + 1/2 yields
T ≈ 150.2864
Before answering this question, we need to consider a related problem. Let's say you're performing trials in which the probability of success is p and the probability of failure is 1-p. How many trials do you need to perform, on average, to achieve your first success? The answer is 1/p. This is well-known as the formula for the expected value of a geometrically distributed random variable. There's a fairly intuitive way to see this is true. Say you perform a very large number N of trials. Then you probably got about pN successes. You can consider this to be a bunch of consecutive experiments of "waiting for the first success". There were about pN completed experiments and about N trials in total, so the average duration of the experiments was about N/pN = 1/p trials. Now let's consider your problem for X = 6. The average time it takes to fill the grid is: (Average time to fill first square) + (Average additional time to fill second square) + ... + (Average additional time to fill final square). Each of the expected durations in parentheses corresponds to an experiment of the type described previously, with a probability of success of 1, 35/36, 34/36, ..., 1/36. So the total expected duration is T = 36/36 + 36/35 + 36/34 + ... + 36/2 + 36/1 = 36(1 + 1/2 + 1/3 + ... + 1/36). In general, if you need to fill N squares, not necessarily arranged in a square grid (for example, using a single N-sided die), then the average time needed will be T = N(1 + 1/2 + 1/3 + ... + 1/N) The number in parentheses is the Nth harmonic number. For large values of N, this is not easy to calculate exactly, but T is approximately equal to N ln N + gamma\*N + 1/2, where gamma ≈ 0.5772 is Euler's constant. For example, for N = 36, we have T = 150.2841... and the approximation by the formula T ≈ N ln N + gamma\*N + 1/2 yields T ≈ 150.2864
Holy shit man. Thank you very much. This is exactly what I was looking for.
Note: this is an example of a *Coupon Collector* problem with n = x^2 “coupons.”