iTunes Randomness Part 6: Regressing the Tangled Equations

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

Regression

Thanks to the heuristic of the decomposition in integer powers from the previous section, we can guide our favorite statistical software R as to what linear regression to use.

Let's provide each of the sequences as our dependent variable, and all the integer powers as independent variables to determine, for each N, the alpha_j coefficients from the equation in the previous part:

For N=5, the regression would look something like:

Estimating the coefficients is then straightforward with most softwares, and even by hand considering the solution is most likely exact and thus only requires solving a system of 4 equations with 4 unknowns (any 4 rows of the equation above).

The underlying function generating the sequence for N=5 is:

And so, based on the equation derived in part 3 we obtain:

We now are capable of identifying the coefficients of s_1^k (N), but can we find a pattern in those in order to finally get a general formula for P(k|N), valid for all k and all N?

The next table summarizes the alpha_j coefficients of each of the powers in the equation mentioned at the top of this post:

Let us rewrite the values as fractions and momentarily drop the signs that seem to be in perfect alternance:

Let us take a closer look at this triangular matrix, diagonal by diagonal.

First diagonal: 1, 1, 3/2, 8/3, 125/24, 54/5

The 24 in the denominator hints at factorials yet again. With this in mind, the first terms of the sequence can be re-written as:

We can then view 16 as 4^2 and 125 as 5^3 hinting at k^(k-2). The first diagonal is then k^(k-2) / (k-1)!.

Second diagonal: 1, 2, 9/2, 32/3, 625/24

The 24 hints again at factorials. The sequence can be re-written as:

Encouraged by the formula for the first diagonal, the second diagonal can be written as k^(k-1) / (k-1)!.


Third diagonal: 1/2, 2, 27/4, 64/3

Based on the previous two formulas can we generalize? We would have hoped for k^k / (k-1)! for this new sequence but unfortunately the formula doesn't work. It is just off by a half: k^k / (2(k-1)!).

Third diagonal: 1/6, 4/3, 27/4

We have now become experts and the sequence is k^k / (6(k-1)!).


i-th row, j-th column:

Based on the previous findings, we can generalize the element on the i-th row and j-th column to be:

Adding the sign back in:

Is it me or does it feel like the end is right around the corner?