Face Value II

cleaned up + generalized

This post is going to serve two purposes. 1) We will clean up our original formula and 2) this cleanup will lead to a more generalized formula for different variations.

Let’s start by restating the original question, although I would maybe recommend that you read the first version first to get a sense of maybe the “easier” way to approach the question (despite it actually being more work and far less clean). Well I guess “easier” is very subjective but I think that the use of indicator variables is just something that people are less likely to have seen before?

We’re going to roll a d3 (a fair, 3-sided die) 20 times, record the frequencies that each face value that shows up and take the product of said frequencies. What’s the expected value of such a game?

Just to make sure we’re on the same page here, an example simulation could end with six 1s, five 2s, and nine 3s giving this a value of 6 x 5 x 9 = 270.

At the end of the last post, I posed a bonus question asking why the approximation of ((20-1)/3)^3 was so close to the actual. We didn’t get any takers on that, but I’m here today to give the answer (which I honestly should have just put in the original post to make it complete because it is truly lacking, but whatever).

So just to recap, we had the formal solution for the product of 3 faces from n rolls of a d3 to be:

\(E[X_1X_2X_3] = \sum_{x_1=1}^{n-2}\frac{(n-x_1)(n-x_1-1)}{4}x_1{n \choose x_1}\frac{1}{3}^{x_1}\frac{2}{3}^{n-x_1}\)

and the approximate solution to be:

\(E[X_1 X_2 X_3] \approx \left( \frac{n - 1}{3} \right)^3\)

Cleaner Solution

I also want to give a simpler version to show this. Let’s say that instead we have a d2 and we roll this n times.

This ends up being E[X_A * X_B] where X_A is the number of times that side A shows up and X_B is the number of times that B shows up. Let’s denote p_A = Pr(a given roll is A) and likewise p_B = Pr(a given roll is B). We will use ~indicator variables~ to describe what each ‘trial’ is; I_{t,A} = 1{trial t is A} and I_{t,B} = 1{trial t is B}. Given this, we have:

\(X_A = \sum_{t=1}^n I_{t,A} \qquad X_B = \sum_{t=1}^n I_{t,B}\)

We want the product of these so:

\(\begin{array}{rcl} X_A X_B & = & \left(\sum_{i=1}^n I_{i,A}\right)\left(\sum_{j=1}^n I_{j,B}\right) \\[6pt] & = & \sum_{i=1}^n \sum_{j=1}^n I_{i,A}\,I_{j,B} \end{array}\)

Now clearly we can’t have trial t be both A and B right? This means that anytime i==j the probability of this is 0, hence we can remove all of those.

\(X_A X_B = \sum_{i \neq j} I_{i,A}\, I_{j,B}\)

For the product of two indicators, we simply have the product of the probability of occurrence:

\(\mathbb{E}[I_{i,A}I_{j,B}]=\Pr(i\text{ is }A)\Pr(j\text{ is }B)=p_A p_B\)

And since we do this for every indicator such that i!=j, we get the product of the number of ways to get two distinct i,j pairs from n trials (this is written as (n)_2) times the probability of occurring:

\(\mathbb{E}[X_A X_B]=(n)_2\,p_A p_B\)

Now, more generally speaking, we can say that the expectation of a multinomial distribution with categories c_1…c_m and probabilities of each being drawn from p_1…p_m is:

\(\mathbb{E}\!\Big[\prod_{\ell=1}^m X_{c_\ell}\Big]=(n)_m\prod_{\ell=1}^m p_{c_\ell}. \)

It can probably go without being said for the audience of this blog, but I think I should clearly define what (n)_m is mathematically. The number of ways to have distinct numbers drawn is:

\(\begin{array}{rcl} (n)_m &=& \prod_{\ell=1}^m (n - \ell + 1) \\[6pt] &=& n(n-1)(n-2)\cdots(n-m+1) \\[6pt] &=& \dfrac{n!}{(n-m)!} \end{array}\)

For the case of our original question where every outcome of a k-sided die happens with probability 1/k and we roll it n times, we get:

\(\mathbb{E}\!\left[ \prod_{i=1}^k X_i \;\middle|\; n \right] = \frac{n!}{(n-k)!} \cdot \left( \frac{1}{k}\right) ^k\)

And given the original question had a 20 rolls of a d3, this would become:

\(\mathbb{E}[X_1X_2X_3\mid20] = \frac{20\cdot19\cdot18}{27} = 253\tfrac{1}{3}\)

This is why our approximation was so close to the actual (notice that it’s barely off).

Anyway, I think that this version is much much cleaner and the fact that it generalizes out to more than just the product of 3 makes it actually usable for questions outside of the very specific one originally given.