Mathematical Recreations

General Solution to P(k) for arbitrary n and m

Here we consider the general case of m items, each of which can be any of n different colors. I'm going to go through the process of "discovering" the solution, then deriving it. This mirrors the way I actually solved the problem

First, let's consider the probability that all m items are all the same color. That is, the case where k = 1. There are n possible colors. The probability that any given item is a specific color is equal to 1/n, so we find:

where x₁ is the probability that all of the items are a specific color.

If we now consider the case where k = 2, we observe that there are n(n - 1)/2 different ways to choose two colors. The probability that any given item is one of two specific colors is 2/n, but we don't want to count the cases where all of the items are the same color. For each choice of two colors, there are two possible ways that the items could be one color. So we find:

Similarly, for k = 3, we note that, for each choice of three colors, there are three ways to choose two of those colors and three ways to choose one of those colors, so:

At this point, we can start to notice some patterns. The coefficient for the number of ways to choose k colors out of a possible n colors is, of course, the normal binomial coefficient n!/k!(n – k)!. Furthermore, the coefficients of x_j are also the binomial coefficients k!/j!(k – j)!. So we can write the general form:

Still, this is not in closed form. Let's do one more specific case for k = 4:

Now we can notice that the coefficients of (j/n)^m for each P(k) seem to be binomial coefficients as well, but with alternating sign. The coefficient of (j/n)^m seems to be (–)^(k – j)[k!/j!(k – j)!]. (Here I've used the notation (–)^(k – j) = 1 if k – j is even and = –1 if k – j is odd.) Let's see if we can derive the observed result. (I actually went up to k = 6 before I decided to tackle the derivation.) We've shown that

for j < 5, but we can also substitute Eq. 1.6 into Eq. 1.4 to get a result for k = 5. (We expect the result to be Eq. 1.6, in which case, it will hold for all k. In case it's new to anyone, this technique is called the principle of mathematical induction.) We find

We want to find the coefficient for each (i/n)^m, so we note that the order of the sum can be switched. For i = 1, there is a term for each j greater than or equal to one. Similarly, for arbitrary i, there is a term for each j greater than or equal to i. We rewrite the equation as

Looking at Eq. 1.6, we see that we want to pull out a factor of k!/i!(k – i)!, and we can also cancel out the like terms of j! to get

The sum from j = i to k – 1 isn't going to simplify, so let's substitute x = k – j to get a sum from one to k – i.

Now we can see the light of day. We can be pretty sure that the inner sum simplifies to a sign, and it simply remains to understand why. Now that we've switched the variables, we can notice that the inner sum is over the binomial coefficients of k – i with alternating sign. We know that the sum over all such coefficients must be equal to zero. (If you don't already know this, look at (y – 1)^(k–i) for y = 1.) The inner sum is over all of the binomial coefficients of k – i except for x = 0. The inner sum is therefore simply equal to –(–)^(k–i), and we get

which simplifies trivially to Eq. 1.6. We find, therefore, that

Method For Determining The Probability Of Finding At Least One Sequence Of n Different Colors In A Series Of m Locations.

The method used in AF5:BA21 of the spreadsheet for n = 6 and m = 15 can be applied to arbitrary n and m. (The computation in the spreadsheet tracks more information than is needed here, since it is keeping track of the number of colors which have ever occurred, in addition to the length of the current sequence.)

We can start by defining some notation. Let p_m be the probability that a sequence of n differently colored locations will be found within a series of m ordered locations. If we keep track of state as we step through the locations, then at any given time we will have a current sequence of i locations with another j locations remaining to be examined. We define p_i, j as the probability of finding a sequence of n differently colored locations out of a series of i + j ordered locations, given that the first i locations are known to be differently colored. We are looking for p_m = p_0, m. We can start by noting that

Let's start with the case where we have only one location left. We can see that

For all i < n and all j >0,

This can be used to calculate all p_{i, j} for successively larger values of j for any value of n. The computational complexity is linear in n and in j.

Method for Finding Analytical Solutions To The Probility Of Finding A Sequence Of n Different Colors In A Series Of m Locations For Specific n.

After examining j different locations, you have either found a sequence of n different locations, or you have a current state with a sequence of i different locations. Think of the state after examining j locations as a vector, where element i is the probability that you have a current sequence of i different locations.

The initial vector after examining one location is (1, 0, 0, ...). The sum of the elements is one minus the probability that a sequence of n consecutive differently colored locations has been found.

There is an operator which transforms the vector each time a new location is examined. For any specific value of n, we can find eigenvectors x such that x transforms into c x, where c is a constant (called the eigenvalue) which is characteristic of that eigenvector.

By finding the n – 1 different eigenvectors and decomposing (1, 0, 0, ...) into a linear combination of those eigenvectors, we can create a general solution for any specific n.

Let's look at the trivial case where n = 2. Each vector has one element. After examining one location, you will always have a current sequence of one differently colored location, corresponding to a vector of (1). After examining a second location, you will complete a sequence of two different colors half the time. The other half of the time, you choose the same color again, and you have a sequence of one differently colored location, corresponding to a vector of (1/2). After examining three locations, the vector is (1/4), and so on. The eigenvalue is 1/2, and the probability that you've found a sequence of n = 2 different locations after examining m locations is given by

For n = 3, the situation is no longer trivial. Let's write the vector as (x₁, x₂). When you look at another location, (x₁, x₂) transforms into

Our eigenvectors will, therefore satisfy

It will be convenient to define g = 3c – 1 (or more generally, g = nc – 1) while we solve the linear equations. We find

This can immediately be solved to find that g = ±√2. For the positive square root, we find an eigenvector proportional to (1, √2) with an eigenvalue of (1 + √2)/3. For the negative square root, we find an eigenvector proportional to (1, –√2) with an eigenvalue of (1 – √2)/3.

The vector x after examining one location can be written as

We know how each eigenvector evolves, so we can immediately write the state after examining j locations:

From here, we can easily find the probability that a sequence of n = 3 differently colored locations has been found after examining m locations:

At this point, you may want to skip to the next section. The basic techniques for doing n > 3 are pretty much the same, but the math gets more complex. That is, the eigenvectors and eigenvalues may be complex numbers. To demonstrate how the system evolves with complex solutions, I'm providing a solution for n = 4. Feel free to skip it unless you are truly intrigued.

Our simultaneous equations for n = 4 are

From these, we find

Solving the cubic equation is tedious, but not hard. Obviously, the real root can be found numerically, but the analytical formula also works:

This leaves the residual quadratic

This quadratic has complex roots

where this equation defines g_i = √(3g₀² – 20). Note that it is not necessary to have any powers of g₀ greater than g₀² or any powers of g_i at all, since these can be eliminated using the following identities:

We find the following three eigenvectors for n = 4

With a little bit of work, we can express (1, 0, 0) in terms of the three eigenvectors:

We know how each eigenvector evolves, so we can use this information to write the general form for the state after examining j locations

The elements of x are always real numbers. (Note that the last two terms are complex conjugates of each other; that is, the magnitude of the real and imaginary parts are the same, but with opposite sign for the imaginary part.) To get the answer to our question, we need to sum the elements of x to see how the sum evolves over time.

Multiplying out and using the identities to simplify, we get

Now, finally, we can eliminate the complex notation with the identity e^i t = cos t + i sin t. Noting that the answer we're looking for is 1 – (x₁ + x₂ + x₂), we can write the probability that a sequence of m ordered locations has at least one series of n = 4 differently colored locations:

General Solution For The Rate Of Occurrence of Sequences of n Different Colors In an Infinite Series

Here we consider an infinite series of locations, where each location can be one of n different colors. The question at hand is a variation on "How often do sequences of n different colors occur?" Taken at face value, the answer is simply the probability that n consecutive locations will be a different color. That is, n!/nⁿ. (There is only one set of n colors, but there are n! different ways to order that set. Each ordering has a 1/nⁿ chance of occurring.)

This answer counts overlapping strings twice, which is OK, if that's what you mean. For example, if there are six colors, the string ROYGVWOR would count twice—once for ROYGVW and once for YGVWOR. My intent is to count the number of nonoverlapping sequences of n different colors. (There is another variation of the question that I haven't solved: "What is the probability that a given location will be part of one or more sequences of n different colors?")

Let's look first at the simple case of 2 different colors. Let's assume that a sequence of two different locations has just occurred and we are looking for the next occurrence. When you examine the next location, you will have a sequence of one consecutive locations which are different colors. When you examine the second location, you will have a 50/50 chance of having a completed sequence of two different colors. If you don't complete the sequence, then you again have one consecutive location which is different.

Let's let x₁ be the expectation value of the number of additional locations that you will have to examine, if you currently have one consecutive location which is different. Then we can write

since you must examine one more location plus a 50/50 chance of examining zero additional locations or x₁ additional locations. In this case, we find x₁ = 2. We'll let i be the length of the current sequence, and x_i will be the expectation value of the number of additional locations which need to be examined before reaching a state of i = n. The answer we are looking for is x₀. (Actually, we are looking for 1/x₀, since the problem asked for the rate.) For any value of n, we can observe that

For the case of n = 2, we find x₀ = 3. Now let's start exploring the system for other values of n. For any specific value of n, we can create a set of linear equations:

We note that x_n is equal to zero. That is, when you get a sequence of n different locations, you terminate the search. I wrote out these equations manually (and solved them) up through n = 4. In doing that, I observed that there is a fairly small change from x_i – 1 to x_i. We can write

since all but one term of the summation is common to both equations. This recursion formula can be used to generate all of the x_i once we know two consecutive values. Since we know one value for i = n, we can also determine all of the x_i in terms of x_n – 1. Let's do the first few:

I actually had to do this many to notice that there was a pattern, because I wasn't expecting to see one. (I was hoping that n² + n + 2 would turn out to be something factorable.) We can now note that x_i and x_i + 1 bear some resemblance to each other. Let's assume that x_i –1 has the following form:

At this point, we can see that this form holds true for all i from n – 5 through n – 1. We can now rewrite the recursion formula above in terms of differences between neighboring x_i

This immediately simplifies to

Now (if you hadn't already noticed), we can see that the coefficients are factorials, and c_i = (n – i)!. Let's look specifically at x₀ – x₁:

Since we know that x₀ – x₁ is equal to one, and we know that c₁ is equal to (n – 1)!, so we find:

and we can write the general form for x_i

As a side note, x_n – 1 = nⁿ/n!, which is the rate at which (potentially overlapping) sequences of n different locations occur. (It is also one over the probability that n random locations will all be different colors.) Why?

Well, if you allow overlapping sequences, then you start looking for the next sequence when you already have n different in a row. So when you consider the next possible sequence, it's composed of the last n – 1 locations (which are all different), plus the next location. So the mean number of sequences that you have to examine to find the next one with all n locations colored differently will be x_n – 1. This is necessarily one over the probability that a random sequence of n locations will all be colored differently, since the rate is one over the mean interval.

I could have used this argument to simply state that x_n – 1 = nⁿ/n!, but I felt it was better to derive it and then explain it. After all, I didn't have that kind of clarity of thought until after I found the answer, so I felt it was fair to show how I actually got there.