Further Still On An Arithmetical Pursuit

| 0 Comments

Arithmetical Pursuit

We have spent some time now figuring the mathematical properties of the game of arithmetical pursuit[1][2] in which the goal is to arithmetically manipulate six randomly chosen integers to land as close as possible to a randomly chosen target, using only addition, subtraction, multiplication and division and admitting no fractions.
We use playing cards to determine those integers, with pip cards standing for their face values, Jacks for twenty five, Queens for fifty and Kings for one hundred, and three twenty sided dice marked twice each with the digits zero to nine to decide upon a target between one and one thousand, the latter being given on a roll of three zeros.
We have thus far shown that any target can be hit with the right deal of the cards and that there are something along the lines of \(210,000,000,000,000\) admissible formulae that might arise during the game.
The next question that my fellow students and I should like answered is just how frequently any given number might be the result of those formulae.

As before, given their tremendous number we have no hope of figuring them all so must satisfy ourselves with a subset of them.

A Reduced Arithmetical Pursuit

Rather than randomly sampling the formulae as before, we shall consider instead a reduced version of the game in which four cards are selected from a single suit of thirteen cards having, according to a suitably modified version of our formula for counting the number of formulae using \(n\) cards
\[ \frac{(2n-1)! \times 13! \times 4^{n-1}}{(2n-1) \times (n-1)! \times n! \times (13-n)!} \]
but \(5,546,749\) possible formulae, as demonstrated by deck 1. Note that the exclamation mark stands for the factorial, being the product of every number from one up to and including the value that precedes it.

Deck 1: The Reduced Number Of Formulae

Recall that, whilst deriving the above formula, we used reverse Polish notation, in which the arithmetical operators appear after the numbers upon which they act rather than between them, to divide formulae involving \(n\) numbers into subsets of differing general structure. These we named with \(x\) and \(o\) symbols where the former acted as a place-holder for the numbers and the latter for the arithmetical operators. Finally, we implemented a scheme for enumerating them with ak.rpnSubsets, as shown by deck 2.

Deck 2: The RPN Subsets

Enumerating The Subset Members

Formulae involving \(n\) numbers have \(n-1\) operators, each of which might be any of the four operators of addition, subtraction, multiplication and division. Consequently there are \(4^{n-1}\) possible arrangements which we can easily enumerate by noting that the remainder of dividing an integer by four will be zero, one, two or three, which we can use to indicate which shall be the first of the operators. If we subtract that remainder from the integer and divide by four, we can repeat the process to indicate which should be the second and so on and so forth, as illustrated by deck 3.

Deck 3: The Operator Arrangements

We can exploit a similar trick to enumerate the ways in which we might choose \(r\) from \(n\) objects, but rather than use the remainder of division by the same number at each step we reduce it by one to reflect the fact that there are one fewer objects to choose from. In doing so we map the integers from zero to one less than the number of permutations
\[ ^nP_r = n \times (n-1) \times \dots \times (n-r+1) = \frac{n!}{(n-r)!} \]
to particular permutations by utilising the scheme that we employed in student.shuffle6 in which we swap the card being shuffled with that indicated of those not already shuffled, as demonstrated by deck 4.

Deck 4: The Card Permutations

Note that, unlike the random shuffle, it is essential that the deck is returned to its original order after each step, which we do here by proceeding backwards though the deal array after writing out the cards.

Evaluating The Frequencies

With that, we are ready to put together an ECMA deck that constructs a graph illustrating the number of times each number from one to one thousand is the result of one of the arithmetical pursuit formulae. Deck 5 runs through the formulae subsets and for each arrangement of its operators updates the graph upon evaluating every formula admitted in arithmetical pursuit.

Deck 5: The Frequency Graph

Whilst there are many exceptions, there is a clear trend of smaller targets being more frequently hit than larger targets, a trend made clearer still by plotting a histogram of the frequencies of blocks of fifty numbers up to two thousand, as shown by deck 6.

Deck 6: The Histogram Of Fifties

These charts imply that it is much easier to hit small targets than large ones, which is certainly in accordance with my fellow students' and my intuition. However, the histogram also suggests that the frequency of large numbers flattens out somewhat and falls to zero rather slowly, behaviour that we should expect to be even more pronounced in the true game.

Power Law Distributions

Such behaviour is exhibited by random quantities governed by what is known as a power law distribution, being those having densities of the form
\[ p(x) = L(x) \times x^{-\alpha} \]
for \(\alpha\) greater than one and where \(L\) is a function that is almost constant in the sense that as \(x\) grows ever larger we have
\[ \lim_{x \to \infty} \frac{L(tx)}{L(x)} = 1 \]
for constant \(t\)[3], where \(\lim\) here indicates that we should take the limit of the expression following it as \(x\) grows towards infinity. With careful application of the rule of integration by parts we can find the probability that one of those quantities, \(X\), is greater than or equal to some given value, \(x\)
\[ \begin{align*} \Pr(X \geqslant x) &= \int_x^\infty L(x) \times x^{-\alpha} \mathrm{d}x\\ &= \left[L(x) \times \frac{x^{1-\alpha}}{1-\alpha}\right]_x^\infty - \int_x^\infty \frac{\mathrm{d} L(x)}{\mathrm{d}x} \times \frac{x^{1-\alpha}}{1-\alpha} \mathrm{d}x\\ &= -\frac{L(x)}{1-\alpha}x^{1-\alpha} - \int_x^\infty \frac{\mathrm{d} L(x)}{\mathrm{d}x} \times \frac{x^{1-\alpha}}{1-\alpha} \mathrm{d}x\\ &\underset{x \to \infty}{=} \frac{L(x)}{\alpha - 1}x^{1-\alpha} \end{align*} \]
where the final limit holds because, as \(L\) tends to a constant, so its derivative must tend to zero. Now if we take the logarithm we have
\[ \ln \Pr(X \geqslant x) \underset{x \to \infty}{=} \ln \frac{L(x)}{\alpha - 1} + (1-\alpha) \ln x \]
and so if we plot the logarithm of that probability against the logarithm of \(x\) it will tend to a straight line if \(X\) is governed by a power law distribution. Finally, we can approximate that probability with a random sample by simply counting the proportion of values that equal or exceed \(x\).

Given that the six number formulae comprise the very much greater part of those that are admissible in numerical pursuit and that we should expect them to yield the largest results, we can reasonably approximate this test by considering them alone, as is done by deck 7 for results up to fifty thousand.

Deck 7: The Logarithmic Probabilities

Well it certainly looks rather close to a straight line to my eye, but unfortunately this is not a terribly sensitive test and to conclude that the results of arithmetical pursuit formulae governed by a power law distribution we shall need some weightier evidence.

A Theoretical Justification

Now it is most certainly the case that the results cannot be exactly power law distributed since their greatest value is
\[ 100 \times 100 \times 100 \times 100 \times 50 \times 50 = 250,000,000,000 \]
beyond which the probabilities must trivially be zero. Nevertheless it may yet be the case that, beneath this value, they are approximately power law distributed.

To figure whether it is or not, I suggest that we analyse a much simpler game; starting from a value of one, toss a coin and if it comes up heads we double the value and play again starting from the doubled value and if it comes up tails we choose with equal probability an integer from a range of the current value up to but not including twice the current value and then cease the game.
Figure 1: The Probability Mass Function
The results of this game are much easier to deduce; one with a chance of one half, two or three with a chance of one eighth apiece, four, five, six or seven with a chance of one thirty second and so on and so forth. The probability that the result equals some whole value \(n\), say \(p(n)\), must consequently satisfy
\[ \frac{1}{2n^2} \leqslant p(n) \leqslant \frac{2}{n^2} \]
as illustrated by figure 1.

I propose that this game is analogous to arithmetical pursuit in the sense that the starting value represents the result of an initial sum, the successive doubling represents a sequence of multiplications and the final choice represents a final sum. Divisions may be interpreted as cancelling out multiplications but since, unlike the latter, they do not always produce integers we should not expect them to entirely do so.
I believe that it is consequently not unreasonable to conclude that the results of the arithmetical pursuit formulae are indeed approximately governed by a power law distribution, albeit one that is truncated at their maximal value.
\(\Box\)

References

[1] On An Arithmetical Pursuit, www.thusspakeak.com, 2015.

[2] Further On An Arithmetical Pursuit, www.thusspakeak.com, 2015.

[3] Clauset, A., Shalizi, C. and Newman, M., Power Law Distributions in Empirical Data, arXiv:0706.1062v2, www.arxiv.org, 2009.

Based upon an article I wrote for ACCU's Overload magazine.

Leave a comment

 
This site requires HTML5, CSS 2.1 and JavaScript 5 and has been tested with

Chrome Chrome 26+
Firefox Firefox 20+
Internet Explorer Internet Explorer 9+