Thus a sequence can be regarded as a vector whose first com-
Ponent is the first value in the sequence, and so on to the n-th com-
Ponent, which is the n-th value. Thus if I spin a coin five times,
The result, taken as a whole, might be the vector with five compo-
Nents (H, T, T, H, T). Such vectors are common in the theory of
Probability, where they may be generated by repeated sampling.
If such a vector is formed by sampling with replacement, it has
Only the slight peculiarity that each value comes from the same
Component set, whereas a more general type, that of S.3/5 for
Instance, can have a different set for each component.
Constraint in a set of sequences. A set of such sequences can
Show constraint, just as a set of vectors can (S.7/11), by not having
The full range that the range of components, if they were independ-
172
Ent, would make possible. If the sequence is of finite length, e.g.
Five spins of a coin, as in the previous paragraph, the constraint
Can be identified and treated exactly as in S.7/11. When, however,
It is indefinitely long, as is often the case with sequences (whose
Termination is often arbitrary and irrelevant) we must use some
Other method, without, however, changing what is essential.
What the method is can be found by considering how an infi-
Nitely long vector can be specified. Clearly such a vector cannot
Be wholly arbitrary, in components and values, as was the vector
In S.3/5, for an infinity of time and paper would be necessary for
Its writing down. Usually such indefinitely long vectors are spec-
Ified by some process. First the value of the initial component is
Given and then a specified process (a transformation) is applied to
Generate the further components in succession (like the “integra-
Tion” of S.3/9).
We can now deduce what is necessary if a set of such vectors is
To show no constraint. Suppose we build up the set of “no con-
Straint”, and proceed component by component. By S.7/12, the first
Component must take its full range of values; then each of these val-
Ues must be combined with each of the second component’s possi-
Ble values; and each of these pairs must be combined with each of
|
|
|
The third component’s possible values; and so on. The rule is that as
Each new component is added, all its possible values must occur.
It will now be seen that the set of vectors with no constraint cor-
Responds to the Markov chain that, at each transition, has all the
Transitions equally probable. (When the probability becomes an
Actual frequency, lots of chains will occur, thus providing the set
Of sequences.) Thus, if there are three states possible to each com-
Ponent, the sequences of no constraint will be the set generated by
The matrix
↓ A B C
A 1/3 1/3 1/3
B 1/3 1/3 1/3
C 1/3 1/3 1/3
Ex. 1: The exponential series defines an infinitely long vector with components:
xx x 1, x, ---- , --------- , ----------------- , … ---2 2 ⋅ 3 2 ⋅ 3 ⋅ 4
What transformation generates the series by obtaining each component from
that on its left? (Hint: Call the components t1, t2, ..., etc.; ti' is the same as
t1+1.)
Ex. 2: Does the series produced by a true die show constraint ?
Ex. 3: (Continued.) Does the series of Ex. 9/4/3 ?
2
3
4
173
A N I N T R O D UC T I O N T O C Y B E R NE T I C S
I N CESSA N T TR AN SMI SSIO N
EN TRO PY
We have seen throughout S.7/5 and Chapter 8 how informa-
Tion cannot be transmitted in larger quantity than the quantity of
Variety allows. We have seen how constraint can lessen some
Potential quantity of variety. And we have just seen, in the previ-
Ous section, how a source of variety such as a Markov chain has
Zero constraint when all its transitions are equally probable. It fol-
Lows that this condition (of zero constraint) is the one that enables
|
|
|
The information source, if it behaves as a Markov chain, to trans-
Дата добавления: 2019-11-16; просмотров: 237; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!