Games vs. Simulations

This is not a full blog post. I just liked the differentiation between the terms "gaming" and "simulation" presented in "Applied Mathematical Programming" by Bradley, Hax, and Magnanti (Addison-Wesley, 1977).

[In] gaming [,...] a model is constructed that is an abstract and simplified representation of the real environment. This model provides a responsive mechanism to evaluate the effectiveness of proposed alternatives, which the decision-maker must supply in an organized and sequential fashion. The model is simply a device that allows the decision-maker to test the performance of the various alternatives that seem worthwhile to pursue.

v.s.

Simulation models are similar to gaming models except that all human decision-makers are removed from the modeling process. The model provides the means to evaluate the performance of a number of alternatives, supplied externally to the model by the decision-maker, without allowing for human interactions at intermediate stages of the model computation.

Multinomial Coefficients in Scala using Fold

Multinomial coefficients are often denoted as \( \left( n;~ k_1, \dots, k_m \right) \) where \( n = \sum_{i=1}^m k_i \). Another way to express a multinomial coefficient is using the \( {\rm choose} \) notation commonly employed in combinatorics for binomial coefficients. Given \( n \geq \sum_{i=1}^{m-1} k_i \), we say that the following are equivalent:

$$ \left( n;~ k_1, \dots, k_m \right) ~\mbox{where}~ k_m = n - \sum_{i=1}^{m-1} k_i \equiv {n \choose k_1, \dots, k_{m-1}}  $$

For convenience, I'm going to use the first notation.

Theorem

I'm not sure if this has ever been stated before, but here's an observation that I made a couple months ago:

$$ \left( n;~ k_1, \dots, k_m \right) = \left( n-k_m;~ k_1, \dots, k_{m-1} \right) \cdot \frac{1}{k_m !} \prod_{i=1}^{k_m} n-i+1 $$

That is, there exists a linear, tail recursive definition for calculating multinomial coefficients.

Proof of Theorem

Without loss of generality, assume that \( n = \sum_{i=1}^{m} k_i \). According to the equivalence noted above as well as the Multinomial Theorem, we have:

$$ \left( n;~ k_1, \dots, k_m \right) = {n \choose k_1, \dots, k_m} = \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_m ! } $$

(1) If we pull out the term \( k_m \), we get:

$$ \left( n;~ k_1, \dots, k_m \right) = \frac{1}{k_m !} \cdot \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } $$

(2) Now, let's find some \( \zeta \) such that:

$$ \frac{ (n-k_m)! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } \cdot \zeta = \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } $$

(3) If we isolate \( \zeta \) on the left-hand side, we observe the following:

$$ \zeta = \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } \cdot \frac{ k_1 ! \cdot \cdots \cdot k_{m-1} ! }{ (n-k_m)! } = \frac{ n! }{ (n-k_m)! }$$

(4) We know that certain terms cancel in this fraction. It is easy to see that

$$ \zeta = \frac{ n! }{ (n-k_m)! } = (n - k_m + 1) \cdot (n - k_m + 2) \cdot \cdots \cdot n = \prod_{i=1}^{k_m} n - k_m + i $$

(5) Since the product in \( \zeta \) is from \( 1 \) to \( k_m \), we can be further simplify the expression to

$$ \zeta = \prod_{i=1}^{k_m} n - k_m + i = \prod_{i=1}^{k_m} n-i+1 $$

(6) Replacing \( \zeta \) in (2) gives us the following:

$$ \frac{ (n-k_m)! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } \cdot \prod_{i=1}^{k_m} n-i+1 = \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } $$

(7) Now we use the result of (6) with (1) to get:

$$ \left( n;~ k_1, \dots, k_m \right) = \frac{1}{k_m !} \cdot \frac{ (n-k_m)! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } \cdot \prod_{i=1}^{k_m} n-i+1 $$

(8) Since the second fraction in (7) can be expressed as a multinomial, we have:

$$ \left( n;~ k_1, \dots, k_m \right) = \left( n-k_m;~ k_1, \dots, k_{m-1} \right) \cdot \frac{1}{k_m !} \prod_{i=1}^{k_m} n-i+1 $$

Therefore, the theorem is correct.

Some Notes

This result that we observed in (7) directly relates to the ratios between the coefficients on the face of a multidimensional Pascal triangle.

Corollary

It is easy to see that the following follows from the theorem:

$$ \left( n;~ k_1, \dots, k_m \right) = \left( n-k_m;~ k_1, \dots, k_{m-1} \right) \cdot \prod_{i=1}^{k_m} \frac{n-i+1}{i} $$

Folding with scala

In Scala, the expression in the corollary can be expressed concisely using the foldLeft operator.This operator applies a binary operator to a start value and all elements of a list, going left to right. If we let our list be the numbers \( 1, \dots, k_m \), then we can foldLeft with the following binary operator:

$$ \left(a,b\right) \Rightarrow \frac{a \left(k_m-b+1\right)}{b} $$

For more information on the general fold operator (with which you can pretty much do anything with), see "Introduction to Metamathematics" by Kleene (affiliate link).

The Code

Here is my recursive implementation of the recurrence relation mentioned in the corollary above:

 

I've omitted a an iterative implementation of the corollary that I've written for the sake of brevity. If anyone expresses some interest, I may include here or in a future blog post.

object Combinatorics {

/** Computes the multinomial coefficient (n; k_1, .., k_m)
* where n = the sum of k_1, .., k_m.
*
* This is a variadic convenience function that allows
* someone to invoke <code>multi</code> without using an
* array. Note, however, that the variadic parameter is
* transformed into an array when this version of
* <code>multi</code> is invoked.
*
* @author Michael E. Cotterell <mepcotterell@gmail.com>
* @param k items to choose
*/
def multi (k: Int*): Long = multi(k.toArray)

/** Computes the multinomial coefficient (n; k_1, .., k_m)
* where n = the sum of k_1, .., k_m.
*
* This implementation requires exactly n-many
* multiplications and m-many recursive calls.
*
* @see http://michaelcotterell.com/2013/03/multinomial-coefficients/
* @author Michael E. Cotterell <mepcotterell@gmail.com>
* @param k items to choose
*/
def multi (k: Array[Int]): Long =
{
if (k.length == 1) 1L
else {
(1 to k.last).foldLeft(multi(k.slice(0, k.length - 1))){
(prev, i) => prev * (k.sum - i + 1) / i
}
} // if
} // multi

/** Computes the multinomial coefficient (n; k_1, .., k_m)
* where n = the sum of k_1, .., k_m.
*
* This implementation requires exactly n-many
* multiplications and m-many recursive calls. Also, it is
* experimentally slower than the <code>foldLeft</code>
* implementation provided by the <code>multi</code>
* function.
*
* @see http://michaelcotterell.com/2013/03/multinomial-coefficients/
* @author Michael E. Cotterell <mepcotterell@gmail.com>
* @param k items to choose
*/
def _multi (k: Array[Int]): Long =
{
if (k.length == 1) 1L
else {
var product = _multi(k.slice(0, k.length-1))
for(i <- 1 to k.last) product = product * (k.sum-i+1) / i
product
} // if
} // _multi

} // Combinatorics

Stream-Based Linear Congruential Generator

I was playing around with the idea of a stream-based pseudo-random number generator in Scala using a linear congruential generator. The implementation obviously takes an LCG from the contant-time playing field to the linear-time field, however, I still think that it's cool that it can be expressed so concisely with a stream. Here is what I came up with. If you try to calculate the stats, then you force the stream to evaluate to 10,000. Besides that, all calls to gen are like a regular LCG except that the results are backed by some sort of sequence in Scala.

Armstrong Numbers

I gave the final for my CSCI 1302 class earlier today, and for one of the questions I asked them to write a program, in Java, that prints out all the Armstrong numbers without using any String methods. An Armstrong number is a 3 digit number for which the sum of the cubes of its digits is equal to the number. An example of an Armstrong number is 153 as 153 = 1 + 125 + 27 = 1^3 + 5^3 + 3^3. The final was supposed to be cumulative (and it was), and this just screamed 1301 material (Sorry for the UGA rhetoric. CSCI 1301 is the prerequisite for my class.). Here is the solution that I came up with when I encountered this question in an interview one time.

Since the definition of a 3 digit number seems to depend on who you're talking too, I always make sure to mention that the code can be easily modified to only work with true 3 digit numbers. Also, since Scala is my favorite language, here is the same code converted to Scala.

Another interesting approach is to enumerate all 3 digit numbers and use what I call the modulus technique to get the digits for each (mod 10 to get the last digit, divide by 10 to decrease the number by one digit, repeat). I suspected (correctly) that some of my students would think of this method because it's very similar to a lab in the prerequisite course.

If you know any other method to enumerate Armstrong numbers then please post it in the comments.