2
$\begingroup$

I am currently working through W. Ross Ashby's An Introduction to Cybernetics, and I'm stuck on a problem of calculating variety for a vector. I know the answer (I caved and checked), but I can't figure out how to calculate it, and that's my real question. I'm not an advanced mathematics student, so it is possible--even likely--that I'm missing something obvious.

= = = = =
First, some definitions, since I'm not sure if vector, variety, etc. are used differently in cybernetics than in other areas of math:

vector: "a compound entity, having a definite number of components." Notated inside parentheses, separated by commas.

variety: "in relation to a set of distinguishable elements, will be used to mean. . . the number of distinct elements" (Also, depending on context, the log base 2 of the number of distinct elements, but this particular problem the first sense is used.)

independence: "The components are independent when the variety in the whole of some given set of vectors equals the sum of the (logarithmic) varieties in the individual components." The components "vary independently" within the defined set.

(All quotes from Ashby, 1956)
= = = = =

Now, the problem itself:

"A vector has ten components, each of which can take one of the values: 1, 2, 3, 4. How much variety has the set of vectors if (i) the components vary independently; (ii) under the rule that no two adjacent components may differ in value by more than one unit?"

The answer to (i) is simply 4^10, or 1,048,576 possible vectors. It's straightforward because the varieties of each of the independent components are the same.

Part (ii)... I don't even really know where to begin with part (ii). After wrestling with it for an hour or so, I checked the answer key to see if I was on the right track. I wasn't. The given answer is a variety of 21,892, and I have no idea where that number comes from.

As I read the problem, a value of 1 in a given component may be followed only by 1 or 2 in the next component, whereas a 2 may be followed by 1, 2, or 3--a different number of possibilities depending on the initial value (similarly, three possibilities follow a 3, and only two follow a 4). So, then, the first component will have the full variety of four, but each component that follows will have a different variety (either two or three) depending on the value of the previous component.

I've spent a couple more hours trying to come up with the 21,892, but I can't seem to set the problem up right. I could probably bang out a program in Python to brute-force the allowable combinations, but I assume that there is a (relatively) simple pencil-and-paper way to do this--Ashby was writing in 1956 (no pocket calculators) for non-mathematicians. So far the mathematics have been pretty elementary, except when marked as optional (which this problem isn't).

This is self-directed study, and no grade is riding on it, but I really want to understand before I move on. Can someone give me a push in the right direction? Thanks in advance.

1 Answers 1

2

The problem you pose could be a challenging one, if one tries to find a general result, but for vectors with entries chosen from $1, 2, 3, 4$ there is a not too difficult solution.

Suppose that there are $d$ possible types, namely $1, 2, 3, \dots, d$, and we want to find the "variety" when there are $n$ components, and adjacent components differ by at most $1$.

Call this variety $V(d, n)$. Your question was about $V(4,10)$. By the way, $V(4,10)$ is indeed equal to $21892$, which is twice the $21$-th Fibonacci number, we will get to that in a while.

It is trivial to find general formulas for $V(1,n)$ and $V(2,n)$, and not hard to find a general formula for $V(3,n)$.

Edit: I take that back, $V(3,n)$ is roughly as hard as $V(4,n)$.

I will get you to a general expression for $V(4,n)$, but have barely thought about $V(d,n)$ for $d>4$.

From now on, $d=4$, so we simplify notation slightly, but also at the same time complicate it. Also, from now on, by vector I mean vector with entries chosen from $1, 2, 3, 4$, where adjacent entries differ by at most $1$. (It is a nuisance to keep repeating that.)

For any $n$, let $G_1(n)$ be the number of vectors with $n$ components (with adjacent entries differing by at most $1$) that begin with $1$. Let $G_2(n)$ be the number of such vectors that begin with $2$, $G_3(n)$ be the number that begin with $3$, and $G_4(n)$ the number that begin with $4$.

I hope that it is obvious by symmetry that $G_3(n)=G_2(n)$ and $G_4(n)=G_1(n)$. So we focus attention on $G_1(n)$ and $G_2(n)$.

In order to get some insight, we compute. With care, one can easily calculate up to $n=3$, maybe even to $n=4$.

Here are the results that I get.

$G_1(1)=1, \qquad G_2(1)=1$

$G_1(2)=2, \qquad G_2(2)=3$

$G_1(3)=5, \qquad G_2(3)=8$

$G_1(4)=13 \qquad G_2(4)=21$

Does this experimentation scream out a message? Our numbers are $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$, looks an awful lot like the Fibonacci numbers. For details about these, look at the Wikipedia article.

Now let's think about the original problem. Let $H(n)$ be the number of vectors of length $n$, where as usual we only care about vectors in which successive elements differ by at most $1$. Then $H(n)=G_1(n)+G_2(n)+G_3(n)+G_4(n)=2(G_1(n)+G_2(n))$

If indeed $G_1(n)$ and $G_2(n)$ are always consecutive Fibonacci numbers, then $H(n)$ is twice a Fibonacci number. (It turns out, as you can see from the short computation above, that for $H(n)$ we end up using alternate Fibonacci numbers.)

A mathematician needs not only to compute, but to prove. Indeed, the computation was just to get a feeling about what is going on.

So let us prove the result. We do it by mathematical induction.

Suppose that we know that $G_1(n)$ and $G_2(n)$ are two consecutive Fibonacci numbers. We show that $G_1(n+1)$ and $G_2(n+1)$ are the next two consecutive Fibonacci numbers.

Look first at $G_1(n+1)$. We want to count the vectors of length $n+1$ that begin with $1$. The $1$ can be followed by any vector of length $n$ that begins with $1$ or $2$. There are $G_1(n)+G_2(n)$ of these. By induction hypothesis, $G_1(n)$ and $G_2(n)$ are consecutive Fibonacci numbers, and so, by the definition of Fibonacci number, $G_1(n+1)$, their sum, is the next Fibonacci number.

Now look at $G_2(n+1)$, the number of vectors of length $n$ that begin with $2$. After the $2$ must come $1$, $2$, or $3$. The number of possibilities that begin with $1$ is of course $G_1(n)$. The number of possibilities that begin with $2$ is $G_2(n)$. And the number of possibilities that begin with $3$ is $G_3(n)$, but recall by symmetry that this is $G_2(n)$.

We conclude that $G_2(n+1)=G_2(n) + (G_1(n)+G_2(n))$. Note that $G_2(n)$ is a Fibonacci number, and, by earlier work, $G_1(n)+G_2(n)$ is the next Fibonacci number, and therefore their sum $G_2(n+1)$ is the next one after that.

That's it, proof complete!

Comment: Maybe I should provide explicit formulas in terms of $F_k$, the $k$-th Fibonacci number. Define the Fibonacci numbers as usual by $F_0=0$, $F_1=1$, $F_{k+2}=F_{k+1}+F_k$. Then the reasoning above shows that the number of vectors of length $n$ with any two adjacent elements differing by at most $1$ is equal to $2F_{2n+1}.$

I wrote the post in a more or less stream of consciousness manner, roughly paralleling the way I found the solution. One could then polish things up, but I hope that what I wrote will be no less useful than a more concise presentation.

  • 0
    Thank you very much--I've only had a chance to skim your answer so far (I'm on my way out the door), but I'm pretty sure I follow you. Really appreciate it! @Asaf Karagila I tried to use "cybernetics" and "variety" tags, but I don't have the rep to add tags. I'll be more specific in future.2011-06-11