Asymptotic Approach to 2D Arrays
How would one go about determining the value of the general term of
the array
1 1 1 1 1 1 1 1 ...
1 3 5 7 9 11 13 15 ...
1 5 13 25 41 61 85 113 ...
1 7 25 63 129 231 377 575 ...
etc.
where A(n,m) = A(n-1,m) + A(n-1,m-1) + A(n,m-1)? There is a nice
approach based on generating functions, but it's also interesting to
note that this array of numbers, like the binomial coefficients, has an
asymptotic relation to the normal distribution. In fact, the Central
Limit Theorem can be used to show that just about ANY symmetrical 2-D
recurrence formula with arbitrary boundary values gives a distribution
of numbers that asymptotically approaches normality.
In the example mentioned above, we can write the numbers sideways in a
manner similar to Pascal's triangle
1 1 1
2 1 1 2
3 1 3 1 5
4 1 5 5 1 12
5 1 7 13 7 1 29
6 1 9 25 25 9 1 70
7 1 11 41 63 41 11 1 169
The numbers in the right hand column are the sums of the individual rows,
and satisfy the linear recurrence s(n)=2s(n-1)+s(n-2). It follows that
s(n) = k(1+sqrt(2))^n - k(1-sqrt(2))^n
where k = 1/2sqrt(2).
Knowing the total sum of each row, it only remains to determine how the
values are distributed in a given row. If we are just interested in the
asymptotic behavior, the Central Limit Theorem can be used to estimate
the values of A(n,m), m=0 to n, because they approach a "histrogram" of
a normal distribution as n increases.
For example, take the 11th row of the preceding array:
1 19 145 575 1289 1683 1289 575 145 19 1
The sum of this row is s(11)=5741, so this is the overall scale factor
for the density. To find the scale factor for the "x axis", observe
that the integral over the central strip is 1683/5741 = 0.293154, so
we know the central strip extends from -0.3761 sigma to +0.3761 sigma,
and all the strips are 0.7522 sigma wide. On this basis we can use
the normal distribution to estimate the values in this row as follows
[rounded to integers]:
2 22 148 572 1285 1683 1285 572 148 22 2
This demontrates that even at n=11 the distribution is already quite
close to normal. The nice thing about this approach is that it works
on a very wide class of arrays - just about any array generated by a
symmetrical recurrence formula. It doesn't even have to be a linear
recurrence. For example, the Eulerian numbers are generated by a
recurrence of the form E(n,m)=nE(n-1,m)+mE(n,m-1), and they also
asymptotically approach a normal distribution.
Return to MathPages Main Menu
Сайт управляется системой
uCoz