iTunes Randomness Part 7: Putting it all together!!!

(This is the 7th (and final!!) part of a series of posts on iTunes randomness. The introduction and a link to all parts can be found here.)

The final formula

The long-awaited formula is finally within our reach as all pieces are put back together, taking i=N-1 in the last equation in part 6:

As a check, we can verify that the sum of the previous probabilities indeed adds up to one over all k.

Before proceeding, let us recall the main definition of the binomial coefficients.These appear in the expansion of (1+X)^N:

By differentiating the above expression d times (d ≤N) with respect to X, we obtain:

Setting X=-1 and multiplying both sides by (-1)^d yields, for all d ≤N:

As any polynom of degree N or less can be written as a linear combination of polynoms of the type X, X(X-1), ..., X(X-1)...(X-d), the following result holds for any polynom P of degree N or less:

We now return to our original equation where we will use the previous relationship, substituting P(k) with k^(N-1) which is of degree less than N.

This check having been performed, we now return to our primary calculation of interest consisting in the average number of plays required to hear each song at least once.

Unfortunately, we have been unable to further simplify the expression, and the last row is our best closed formula at this time.

The expected number of total plays is E(N + k)=N + E(k):

The next figure compares the theoretical expression with our earlier simulations from part 1.

The expectation we derived can also help compute the average number of times each song will have been played in a successful playlist, and results are shown in the next figure:

The open question that still needs to be tackled is whether this curve reaches an upper bound or continues to increase. With an infinite playlist, will we expect to listen to each song an infinite number of times?

Until then, time for celebration!