A STOCHASTIC MODEL FOR TIME CHANGES

IN A. BINARY DYADIC RELATION, WITH
APPLICATION TO GROUP DYNAMICS

TstIs Ior “‘9 Degree oI DIN. D.
MICHIGAN STATE UNIVERSITY

T. N. Bhargava
1962

[HESIS

This is to certify that the

thesis entitled
A stochastic model for time changes in a
binary dyadic relation, with application

to group dynamics

presented by

T. N. Bhargava

has been accepted towards fulfillment
of the requirements for

Ph. D. degree inStatistics

 

 

Date June 11, 1962

 

0-169

 

 
  
     

  

LIBRARY

Michigan State
University

 

 

 

 

 

MSU

LIBRARIES
.—:I—.

 

 

RETURNING MATERIALS:
Place in book drop to
remove this checkout from
your record. FINES will
be charged if book is
returned after the date
stamped below.

 

 

 

 

 

 

ABSTRACT
A STOCHASTIC MODEL FOR TIME

CHANGES IN A BINARY DYAOIC RELATION,
WITH APPLICATION TO GROUP DYNAMICS

by T. N. Bhargava

This thesis is concerned with the development of a
stochastic model for analyzing time changes in a binary dyadic
relation over a finite set of points. For purposes of drawing
statistical inference in time the total relation IR.(A) on
the set A is looked upon as an aggregate of its subrelations
on subsets of the set A . The number of states in which a
subrelation may be found, at any time, is very large; conse-
quently three classification schemes are described to obtain a
small number of mutually exclusive and exhaustive classes.
Methods are presented to enumerate the number of subrelations
of TR, UI) in various states at any time, and to count the
number of transitions from one state to another in time. The
process of change in the total relation over time is described
as a time-dependent process, and some statistical tests to
determine the nature of the dependence are given. Certain as-
pects of the probability distributions of the random variables
Rn1 (number of n-point subrelations of IR.(A) in state 51 )

and R'n (number of n-point subrelations of ~(52(A) in state

1

5'1 ) are discussed in the second part of the thesis. It is

shown that the probability distributions of Rni may be approxi-

mated by Poisson distributions. Finally an application of the

of the model to group dynamics is described and empirical
examination of Markov properties is made for a particular set

of data.

A STOCHASTIC MODEL FOR TIME
CHANGES IN A BINARY DYADIC
RELATION, WITH APPLICATION TO

GROUP DYNAMICS'

by

.I
7“|- “:4 'R
Tl Nf'Bhargava

A THESIS

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY
Department of Statistics

1962

' PLEASE NOTE:
' Not original copy. Indistinct type
on several pages. Filmed as re-

ceived. . . .
Umvermty Microfilms, Inc.

ACKNOWLEDGEMENTS

Words can hardly suffice to thank this writer's major
professor, Dr. Leo Katz, for his time, able guidance, counsel
and encouragement all through the development of this thesis.
All the help given by him is deeply appreciated.

Thanks are due to Dr. J. F. Hannan for his constructive
criticisms and encouragement, and to Dr. K. J. Arnold for his
continued interest in the writer's work. Sincere appreciation
is expressed to Dr. P. H. Doyle for his help, in more than one
way, throughout the writer's stay at Michigan State University.

Thanks are expressed to the University for making available
the facilities of the MISTIC computer, and to the Department of
Statistics for all the help which made this work initially
possible. The writer is also very grateful to the National
Science Foundation and the Office of Naval Research for their

financial support during this work.

ii

TO MY PARENTS

iii

TABLE OF CONTENTS

INTRODUCTIONOOOOOOOOOO OOOOOOOOOOOOO 0.0 OOOOOOOOOOOOOOOO O 00000 0° 1

PART I. THEORYO. ........ O...OOOOOOOOOOOOOOOOOOOOOOO 0000000 000012

PART

PART

1.1
1.2

1.3
1.4

II.
2.1
2.2
2.3
2.4
2.5
2.6

2.7

III.

3.1
3.2

PreliminarieSCOOOO000......OOOOOOOOOOOOOOO 000000000 12

Classification of structures....................... 17

Enumeration of R . , R' . ,and transitions....... 26
n1 n1

Stochastic model ...... ...... ..... . ...... .... ...... . 40

DISTRIBUTION THEORY............. .......... .......... 47

Preliminaries.. ...... .............................. ”7
Dyadic case.. ....... ............................... 51
Triadic case....................................... 62
Quartic case....................................... 75
General case....................................... 83
An approximation for the probability distributions

of Rni .......................................... 84
An approximation for the expected values of R61 ,

R'ni , n‘g 4 .................................... 96

APPLICATIONS... ....... ........ ..... ...... ...... ....lOl

PreliminarieSOOO.OOOOOOOOOOOOOOOOOGOOOO0.00.00.00.0101

Empirical examination of Markov properties.........104

BIBLIOGRAPHYOO0.00.00.00.00.O.OOOOOO‘OOOOOOOOOOOOOOO.0000......111'.

iv

A.2

A.3
A.4

LIST OF APPENDICES

Page
N-point structures, N = 2, 3, A, connectivity,
accessibility, and weighted classifications .............. 118
Computer programs ................... . ..................... 136
Tables of E (Rni) , E(Rn1) n = 2, 3, A, ............... 148
Second-order transition tables for the accessibility
classification, N = 25, n = 3 ........................... 158

NOTATIONS

Pi holds relation 7$L to Pj
Total relation on the set A
Subrelation of 'TQ\(A), on subset a

Number of elements in the class

{'UZtIa): a‘:; A)
Directed graph corresponding to (’I

Incide?ce matrix corresponding
to °)

Structure of (')
P. is acessible from P
J i

i-th state in the connectivity
classification

i-th state in the accessibility
classification

i-th state in the weighted classificae
tion

11m E('I/ (:I
N—-> co

vi

13
13

13

14

18

19

I'I23

97

INTRODUCTION

Our object in this thesis is to present a probability
model for studying changes through time in a binary dyadic
relation on a finite set A consisting of N points° The
total relation RM) on the set “A .. takes the form of an
aggregate of directed binary dyadic relations between ordered
pairs of points belonging to A . Such a relation, changing
in its structure as time proceeds, is a reasonable mathema»
tical model for the evolution of interorelationships of the
members of a social or some other grnup. A group of this
kind is organized for a specific activity involving "communi—
cation" from one member to the other and may be observed at
successive discrete points in time,generating statistics
on the evolutionary process.

For the purpose of drawing statistical inference in
time we require:

(a) a reasonable number of "stated'in which

a relation may be found at a given time,
and

(b) enough data to characterize the process.

With regards to (a) we observe that, since at any time
t each point of the set A may or may not be in relation
with the remaining N~l points, there are (2N'l)N different
ways in which a relation ’SKIA) may be obtained on the set

A . Even for small values of N this number is much too

large; for example, for N = 5 the total number of relations

2
on set A is 220 which amountsto more than a million. How~.st
ever,once we have a relation 31 (A) on the set A we may
ignore its labels and obtain equivalence classes, under
permutations, on the set of total relations ZR.(A). The
number of equivalence classes is much smaller than the
total number of relations UR.IA) but is still very large;
for example, for N = 5 the number of equivalence classes
is 8,508. We also observe that all the relations belonging
to the same'equivalence class have same structure and many
of these structures are not very much modified by the addi-
tion or deletion of a few directed dyadic relations ‘R (Pf’Pj)
P1 and Pj belonging to the set A . Accordingly, we may
group some of the structures together to obtain a reasonable
number of mutually exclusive and totally exhaustive classes
such that, at time t , a relation 'Uzt(A) may belong to
one and only one of these classes. These classes are defined
as "states" in which a relation-UR (A) may be found at time
t . Clearly there are many ways of doing the above. In
this study we present three different classification schemes:
the first based on the combinatorial topological considerations
of connectedness; the second on the notion of accessibility
count, and the third on a refinement of the second to a
weighted classification obtained by assigning to an accessible
ordered pair (Pi, Pj) a weight of N-L if there is a
minimal directed path of length L from ,P1 to Pj , and
a weight of zero if the ordered pair (Pi’ Pj) is not

accessible.

3 .
With respect to requirement (b) , namely, obtaining

sufficiently large number of observations for the process,
we may either (i) make a series of observations on a single
set A for a sufficiently long time, or (11) make observa-
tions in parallel on a number of similar sets for a shorter
period of time.

In the particular example of a sociometric situation,
mentioned earlier, we are excluded from using either of
these procedures. The first procedure is excluded because,
firstly, a group of N individuals can function as an
intact group for a specific purpose, only for a relatively
short time, and secondly, for administrative and technical
reasons the observations cannot be made too closely to each
other, and we can get only a limited number of observations
in this short time. Thus practical reasons rule out the
study of the single relation 7$K(A) over many periods of
observations. As for the second procedure, namely, making
parallel observations over relatively shorter time, we are
excluded from using it because of the ground rules laid down
in applications. For example, the social scientists look
upon a group as a unique conglomeration of individuals
constituting the group and no two groups, as such, can be
considered .simila n. ~ .

We are thus left with the only possibility of studying
a single group over a short period of time which does not
generate enough statistics for a dynamic study. However,
if we consider the group relation in tenmSnOfuan:aggregate

of the relations on the subgroups (of the given group) of

4
size n then all the subgroups are at least embedded in the
identical milieu and participate in common group objectives

as seen by the parent group. In this way even a short record
provides us with many parallel records and we get a sufficiently
large number of observations. In the present paper our approach
consists of studying the relation TR (A) in terms of an aggre-i
gate of its subrelations TR.(a) where a, is a subset of A
and consists of n points. Thus at any point in time we
obtain (g) observations correspondingn to the number of

ways a subset of n points can be chosen from a set of size

N , but these observations, in general,are not independent.

It turns out, though, that this problem of non-independence

is not very acute for the case when N. is much larger com-
pared to n . We find,-;tth‘tt, irrespective of the values of

N and 'n , subrelations defined on disjoint sets of points

are totally independent, and the extent of dependence among sub-
relations defined on overlapping sets of points is directly
proportional to the number of common points in those sets.

If N >> n the number of Betuples of subrelations‘32(a1),

-5{ (a2), ...,‘12.(ak) with p points in common decreases

. as p increases and as such the extent of dependence among

the observations is also small. We indicate this by means of
the following table in which we enumerate the number of pairs

of subrelations with O, 1, 2, ... common points, for N - 25

and; n a 2, 3, A.

Table 0.] showing number of pairs of subrelations with 0, l, 2,

..., common points for N a 25,

I"! '2, 3’ he

 

 

 

 

 

 

 

 

 

Total Number Number of pairs of subrelations with
of pairs of -
n subrelations
points point points ints
N I N I N '
2 (2) - lI‘I,850 5W 2“; 3(3) 3! - _
2 . 37, 950 - 6,900
N I N 6! I N g! l N A!
3 3’ - 17(6) T3. E (5) 2. . '5 (A) '1'? '
2 . .
L 26,43,850 = I7,7I,000 -7,96,950 . 75,900
N lN8.’ IN 2: IN 6:1IN5:
II (A) " 'i' (8) 1'3! '2' (7) 3.3. '5 (6) 2.'2.' I725) 31'
I 8,00,ou,925 «3,78,55,125 a3,36,u9,000 -79,69,500 -5,3I,300

 

 

 

6
Summary. The main purpose of this thesis is to construct
methods to study changes in the relation '62:”) over a
period of time. To be able to generate enough statistics
for this process. we study the relation R t(A) in terms
of the aggregate of its subrelation nth). There are
two equivalent representations of Rt”): (i) in terms
of a directed graph Pt(A), and (ii) in terms of an in-
cidence matrix Ct(A) . In the present study we use both
of them interchangeably, and in section 1.1, we present some
definitions and results, both; from the theory of graphs
and the theory of matrices. In terms of the graph theory,
a relation 1R.(A) corresponds to a labelled digraph
(directed graph» and it is easy to see that there are
(2N'1) different labelled digraphs on set A . We say
that two relations have same structure if they belong to
same equivalence class under permutations, and we count the
number of different structures on set A by means of the
counting series

_ NIN'l) _ L
QNIY) ‘3 1:0 gNLY

where ENL is the number of structures with N points
and L directed lines.
We find that the number of states in which 12 t(A)
may be found at time t is much too large and consequently
we propose in section 1.2, three classification schemes
to group some of the states together to obtain a reasonable

number of new states. The first classification is based on

7
the strength of connectedness and is called the connectivity
classification. We define P(A) , the directed graph corres-
ponding to IR (A), to be strong if there is a directed path
from each point of A to every other point; to be unilateral
if for every pair of points belonging to A there is a
directed path from at least one of them to the other; to
be weak if there is a path, ignoring the direction, from
each point of A to every other point; to be disconnected
if P(A) is not even weak. These classes are not mutually
exclusive in themselves, but from these we obtain four
mutually exclusive and exhaustive classes and call them the
"states" of the connectivity classification. We say that

P(A) is in state 53 if it is strong, in state if it

52

is unilateral but not strong, in state 51 if it is weak

but not unilateral, and in state so if it is disconnected.
In the second classification we define a digraph P(A)

to be in state Si if the number of accessible ordered

pairs of points belonging to A is exactly 1 . This is

called the accessibility classification and the number of

states now depends on N , the order of P(A) . We denote

an accessible ordered pair by Cl (1, j) and the total number

of accessible ordered pairs in P(A) by p . In theorem

1.2.1 we show that p takes values of the form

m ( ) m -
p = 2 N N -1 + '2 e N N
k=1 k k k,L=1 k k

where Nk is the size of the equivalence class Ak.

(k l, 2, ..., m) defined by Q.(i, j)AQ.(j, i) on the

set A , and

1 if every point of A is accessible from every
ck = point of gAk '
0 otherwise

In the third classification we consider a refinement of
the accessibility classification: an accessible ordered pair
(P1, Pj) is assigned a weight N-L if the length of minimal
directed path from P1 to P. is L, , and a weight zero

J
if the ordered pair (P1, Pj) is not accessible. We say

that P(A) is in state s; if the aggregate weight of the
ordered pairs of points belonging to A is i . The
number of states in this classification also depends on

N , the order of the digraph P(A).

In section 1.3 we present formal procedures for enumer-

ating (l)Rni(t)-and R'ni(t), where Rni(t) (R'ni(t))

denotes the number of subrelations -Flt(g), of the relation
‘Gltm, in state s1 (51) at time t , and (2) the
number of transitions from state 51(51) at time t , to
state sj(sj) at time th . The main problem in enumerating
the above is that of identifying the state of a subrelation
'6K (a) at a fixed time t , and simultaneously at many
points t1, t2, ..., th (t1 < t2 < ... < th) in time. To
do this we find it more convenient to use the matrix representa-
tion C(A) of the relationR(A) .

V We define two numerical functions f :and f':
on the class {'1R t(a), aCA} such that f(th(a)) takes ‘
the value 51‘ if nth) is in the state 51 at time t, ,
and f'(ut(a)) takes the value 5i if Rt(a) is in the

9
state si at time t . The values of the function f('Rt(a))

are evaluated by means of the corollary 1.3.1 and that of
f'('at(a)) by means of the theorem 1.3.2. Then
Rni(t) =- n (filth). aCAIFIIQt(a)) 2- 51] , and

”mm = n {Nab aCA'f'IK‘a” = Si}

To count the number of transitions from state

(5'11) at time tl , to state 51 (5'1 ) at time

S
i h h

1

th , through the states 512(5'12) at time t2 , ...,

si (s'i ) at time th-l‘ , we define functions
hel hrl ,

f(h)(f'(h)) on the class {(RtIIa), Rt2(a), ...,

Ethan), aCAI such that

f(h) (Rtlb), Rt2(a), ...,Rth(a)> :3 ($11) .312) 00., 51h)

if f(&t1(a))= 511, mitten.» .. 512, fIRthIan - s1h ,

and f'(h)(‘&t1(a), Rt2(a), ...,ch(a)) =3 (5'11, 5'12,ioo.,

Stih) if f!(Rt1(a)) = 5:11;, fu(ut2(a)) = 5:12, ...,

f(&th(a)) = s'ih

10
As such the values of f(h) and f'(h) are evaluated by
repeated use of corollary 1.3.1 and theorem 1.3.2 respectively.
For n = 2 we also give global techniques to enumerate
Rni and to form the first order transition tables.‘

I In section 1.4 we describe the change in relations
'Ilt(A), over a period of time, as a stochastic process, and
consider in detailu a very simple case of change in relation
'32 t(A) , namely, when a relation depends only on what it
was at the immediately preceding time. This is a Markov type
model and there are standard methods for drawing statistical
inferences in Markov chains. We also describe tests for
(i) independence of the process, (11) stationarity of
transition probabilities in a Markov chain, and (iii) order
of the Markov chain.

Part II of the thesis is concerned with some aspects
of probability distributiomsof random variables Rnd. and
R'n1 . In section 2.1 we describe a method based on the
theory of compound probabilities, to compute exact moments

of Rn1 (R'ni) . We need to obtain probabilities of the

tYPe Pr [fl IR (a)) = SA , Pr [IH‘R (a1)) = 5113A.

1

(HRH?) = 512]] , ..., for which we use graphic rep-

resentation of IR (A) . In sections 2.2, 2.3, and 2.4
we obtain some results about the expectations and variances
of the random variables RnilR'ni) for special cases n a 2,

3, and 4 respectively.

 

 

 

 

. 11

A general method for obtaining probabilities of the kind
described above for any n 2_2 involves counting and removing
of redundant complex directed chains, which it seems can be
done only by direct enumeration. We discuss the attempts
made in finding a general solution and the difficulties
involved therein in the section 2.5. However we are able to
propose in section 2.6 an approximation for the probability
distributions of RniIn,2 2) for the case N >> d where
d stands for the number of points accessible from any point

P of the set A . In this case we find that each of

i

the variable Rni has an approximate Poisson distribution.
The expressions for expectations of random variables

R and R'n are rather involved and computationally

Hi i
difficult to obtain. Consequently a simple approximation
of these values is presented in section 2.7. We take d to
be a linear function of N and define e = d/(N-l) so that
O < 9.S 1, and find the limiting values of expectations as
N—-> oo . These approximate values are computationally
checked against the exact values for n - 2, 3, and 4 and
tables of their limiting values for 9 a .1, .2, ...,..Q
are given in the appendix (A.3.

Finally,in Part III of the thesis we give an application

of our results to the problem of group dynamics and present'

an empirical examination of Markov properties for an actual

example from group dynamics.

 

 

PART I
THEORY

1:1 Preliminaries

Let AN = I P1, P2,

of points and TR. be a binary relation between two ele-

..., PM I be a finite set

ments of AN . We denote by ‘62 t( i, j ) the fact

that Pi holds relatien R to Pj at time t . If
P1 does not hold relation R to Pj at time t we
denote it by 'di.t( i, j ) .

Throughout this paper we denote AN simply by A
and whenever there is only a single paint in time we
omit the subscript t from a“ i, j ).

At any point in time,for every ordered pair of

points (P1, Pj) either P holds relation IR. to

i
P. or F1 does not hold relation 'EK t0~ Pj’ that 15:

either' '52t( i, j ) or T§.t( i, j ). We define this
configuration of binary dyadic relation (51 between
ordered pairs of A as the total relation R t(A)

on the set A . As the time proceeds some of the
relations ‘32 t( i, j ) or 'Ui t( i, j ) may under-

go a change while the others may not. Thus the relation
'51 t(A) is a function of time and changes with time. We
propose to construct methods to study the change in rela-
tion '52 t(A) over a period of time. For this purpose we
consider the relation U{t(A) in terms of an aggregate of
the subrelationth(an), where an - I P1 , Pi , ...,

2

1
P1 I CA . We denote Rtfian) simply by hth) .
n

12

13
Clearly there are (fl) subrelations 'Ul(a), of the
relation 79.(A) , corresponding to the number of ways a
subset of n points can be chosen from a set of N points.
Let I R (a), acA} be the class of subrelations 752 (a)
of ‘52 (A) , and let M ‘62 (a) , acA} denote the number

of elements in the class I ER (a) , aczA} so that
Mm.) , acA] = (N)

n
There are two equivalent representations of ER.(A):
first, in terms of a directed graph P(A), and second; in
terms of an incidence matrix C(A)
We give below some definitions from graph theory.
A directed graph (or simply a digraph) P(A) consists
of vertices P1, P2, ..., PN corresponding to the points
of A and directed edges $IEE> shown by means of directed
lines from P1 to Pj , corresponding to relation TR 01, j)
on set A; F(A) is of order N if A consists of exactly
N points. P(A) is said to be a labelled digraph if each
vertex of P(A) is distinguishable from every other vertex.
Two labelled digraphs P(A) and P(A') are said to be
isomorphic to each other if there exists a one-to-one corres-
pondence between the labels P1 of P(A) and the labels
P'iy of P(A') which preserves each relation between points.
Two labelled digraphs which are isomorphic are said to have
the same structure )8 (A). Digraphs with same structure are
.said to belong to the same equivalence class under the permu-
t ations grouping .
We note that, by definition, presence of loops (directed

lLines joining a point with itself) is not allowed in a

14
digraph and that there cannot be more than one directed line
joining the same ordered pair of points.
A directed path from a point P1 to Pj is given by

a chain of directed lines of the form P P >, P F >, ...,
1 i1 i1 i2

5:;F]> where all Pi's are distinct; the number L of di-
rected lines in the directed path is called the length of the
directed path from P1 to Pj . A directed path of length
L from P1 to P1 is called a cycle of length L . A
digraph is said to be complete if all the possible directed
lines are present in it. A point Pi is said to be isolated
if we have ji(i, j)/\ fiifij, i) for every Pj- e A, ij

% Pi . A point Pj is said to be accessible from the point
P1 if there is a directed path from P1 to Pj and we denote
it by CI_(i, J); when this happens the ordered pair (Pi’ Pj)
is called an accessible pair.

Na), 36A is said to be a subdigraph of I‘(A) if it
consists of all the directed lines which connect points of sub-
set a .

Next we give some definitions from matrix theory. An
incidence matrix C(A), corresponding to‘Kl(A), is a matrix
of ones and zeros such that an element Cij of C(A) is one
if '5l(i, j), and zero if iifii, j), and C11 = O for all
' = l, 2, ..., N . Let C(a) be the incidence matrix corres-
ponding to ER (a) ; then C(a) is a principal diagonal sub-
matrix of C(A). A matrix X is said to be positive if all
its entries are positive and this is denoted by X > O

The elementwise product of two matrices C = (Cij) and D = (dij)

IE
is called as Hadamard product and is given by C * D

(cij . dij)

We now give a counting series for enumerating the num-
ber of distinct structures 38.(A) on the set A . Let
ENL be the number of structures with N points and exactly
L directed lines. The enumeration of the structures of
order N is equivalent to finding the expression for the

counting series.

... N(N'1) _ L
9N(v) = Z gNL Y

where the exponent of y denotes the number of directed
lines in a N-point structure. Up to N = 5, §N(y) are
explicitly given as:

31(Y) a 1

'§é(Y) = 1 + Y + Y2
'§3(y) = l + y + #y2 + 4y3 + Ayn + y5 + y6

+ y + By2 + 13y3 + 27yll + 38y5 + 48y6

27y8 + 13y9 + Sylo

§fi(Y) ‘ + 38)’7

+ yll + Y12

1

+

”55(Y) = 1 + y'+ 5y2 + 16y3 + 61y“ + 154v5 + 379V6
+
+

707y7 + 1155y8 + 1u90y9 + 1670y1° + 1490y11

u 16

O

1155y12 + 707y13 + 379v1 + isuyls + 61y

8

+ 16y17 + 5yl + y19 + y 2

For a derivation of these we refer the reader to Harary [12:]

16'
Table 1.1.1 Showing the total number of labelled digraphs

and structures on a set of size N , ng 5

 

N Number of labelled Number of structures
digraphs

2 4 3

3 6h 16

4 4096 218

5 1048576 8508

Even for small values of N the number of structures on
set A is very large. Therefore in the next section we
present classification schemes to group some of the struc-
tures together and to obtain a .smallehi. number of states

in which a relation YR.t(A) may be found at time t

17

1:2 Classifiggtion of structures

The number of structures on set A being very large,
one of the first problems encountered in attempting to
construct a formal theory for studying time-changes in
relation ‘62 t(A), is to devise suitable classes of
structures which are smaller in number, empirically
observable, mutually exclusive and totally exhaustive.
Obviously this could be achieved in many different ways.
In this section we present three different classifications
'of structures: the connectivity classification, the
accessibility classification, and the weighted classification.

For the purpose of classification we find it more
convenient to use the graphic representation, F(A), of
the relation TR\(A).
Connectivity classification. This classification is
based on considerations of the strength of connected-
ness in combinatorial topology. A digraph P(A) is said
to be (1) strongly connected (or strong) if for any
ordered pair of points (Pi’ Pj)’ Pi ‘and Pj be-
longing to A , the digraph contains a directed path
from P1 to Pj (ii) unilaterally connected (or
unilateral) if for any pair of points (Pi’ Pj) ,
.P1 =and Pj belonging to A , the digraph contains
a directed path either from P1 to Pj or from

Pj to P1 (111) weakly connected (or weak) if for any

18

partition of A into two non-empty subsets there
exists a path, not necessarily directed, between a point
of one subset and a point of the other, i.e. any two
points P1, Pj e A can be joined by means of a chain
of lines, ignoring their directions, from P1 to Pj
(iv) disconnected if the digraph is not even weak.

While this classification is exhaustive, it is not
mutually exclusive since a digraph which is strong is
also unilateral and a digraph which is unilateral is
also weak. To obtain mutually exclusive classification
we define a digraph to be (i) in state 53 if it is
strong (ii) in state 5 if it is unilateral but not

2

strong (iii) in state if it is weak but not uni-

s1

lateral (iv) in state if it is not even weak.

5
0
We say that a digraph is of type 51 if it is in state
51.

For N a 2, 3 and 4, all structures of type
51 CHEO, l, 2, 3) are shown in the appendix A.1 i
from which it follows that the counting series for the
structures of type 53 (for N 3,4) must take the
form:
- 2
—3 3 u 5
-3 ll 5 6. 7 8 9
g,‘s3 - y + 4y + 16y + 22y + 22y + lly + 5y

6
10

+ Yll + Y12
where 3‘5 represents the counting series for N-point
1

structures of type Si

III

(‘9-

III-'-

.,19

Similarly the counting series for structures of type

52 (for N‘s A) must take the form

— 2
9 = Y + 3Y + 2V
352

34.2 = Y3 + 9y" + 26,5 + 29y

u

6 + 16y7 + 5y8 + 2y9

And finally, counting series for structures of type
51 (for N's 4) must take the form

'5 o
251

- 1 3 4 5
9451 = 7V + 12y + 7y + 2v

2y2
6

Since the counting series for total number of N- point
structures is already known, the counting series for
structures of type 50 may also be obtained by differs ,
ence. Up to N a 4 it must take the form

3250 a 1

__ O

945 = 1 + y + 5y2 + 5y3 + By4 + y5 + y6
0

= 1 + y + Y2

A general method of enumerating the structures of various
types has not been found and is still an open problem.
Accessibility classification. This classificatiOn is
based on the accessibility count p of the digraph _P(A)
which is defined to be the total number of accessible
ordered pairs in .F(A) . We say that a digraph. P(A)

is in state s£ (of the accessibility classification)

if it consists of exactly 1 accessible ondered pairs.‘

ii20
By; definition the accessibility classes are mutually
exclusive and totally exhaustive, and the total number
of accessibility classes varies with N , the order
of the digraph P(A). To obtain the number of access-
ibility classes for a given N it is enough to find
all the possible values of l3 _for a digraph of order
N . In order to compute the accessibility count
p of P(A) we recall that an ordered pair (P1, Pj)
is said to be accessible if there is a directed path
from P1 to Pj , in which case Pi is said to hold
relation 0, to Pj and we denote it by Q.(i, j)
Some properties of such relations which are of interest
to us are given below.

The relation 0. is (i) reflexive if CL (1,1)
holds for all P1 in A (ii) symmetric if Q- (i,j)
!-9' Ch.(j, i) for all P1, Pj in A (iii) trans-
itive if G. (i,j)A C9. (j,k).-:.--_..:> O.(1,k) for all
P1, Pj’ Pk in A . A relation that is reflexive,
symmetric and transitive is an equivalence relation],
and.aw equivalence relation partitions the set A into
equivalence classes in such a manner that two elements
Pi and Pj are in the same class if Q. (i, j) holds.

It is easy to see that the relation (1. (of access-
ibility) is transitive but is neither symmetric nor
reflexive. But if we define a new relation Q,(i, j)

l\ CL-(j, i) then this relation is transitive and symme-

tric. It is also reflexiVe over the set of those points

 

 

21
P1 for which Cl,(i, J) holds for ebme other Paw-Thussthis new
relation is an equivalence relation and defines equivalence

classes on the set A . Let these equivalence classes be

A1, A2, ..., Am and the class Ak consists of Nk elements
(k- 1, 2’ 000, m) 50 that
m

These equivalence classes are such that two points P1 and
Pj belong to same equivalence class if both <2.(i, j) and
C1,(j, i) hold, that is,there is a directed path both from
to P

P and Pj to P1 . We define a relation Q* on

i

the set of equivalence classes by saying: that G_*(Ak, A1.)
holds if every element of Ak ubears the relation CI, to
every element of A*_ , that is every point in AL is
accessible from every point in Ak . Since two points

Pi , Pj belong to an equivalence class Ak if and only if,
both O.(i, j) and C9.(j, i) hold, it follows that«Q,*(Ak., AX.)
holds if any element of Ak bears the relation 0— to any
element of Afi_ . ‘This is a partial ordering of the equiv-
alence classes A1, A2, ..., Am and we call it the partial
ordering induced by CL . If Q,*(Ak, All.) holds then
C1}'(AL, Ak) cannot hold unless Ak a A,“ .

Theorem 1.2.1. For a digraph F(A)

. 22

1 if o..*(Ak, A‘L) holds

where 6k =
0 if &*(Ak, AL) does not hold.
Proof. For any k== 1, 2, ..., m
Pi’ Pj C Ak=> G—(ii J)“ Q- (J: i)

and the number of elements in Ak is Nk so that there
are Nk(Nk-l) accessible ordered pairs on the set Ak
For any k, = l, 2, ..., m

“*(Ak, AJL) holds => C§_(i, j) holds for every

P1 in Ak and Pj in ”L

___> there are Nk.NL ordered

accessible pairs

and Q.*(Ak, A ) does not hold => Q.(i, j) for every
‘ P1 in Ak and

===> the number of ordered
accessible pairs is
zero.

Hence
m ( ) m
p = Z N N '1 + E 6

as stated in the theorem.
Si in which a
relation Vt”) may be found, at time t , are 3, 6

We find that the number of states

and 11 for N a 2, 3, and 4 respectively. In the appendix

A.l we show structures of type sf for N's 4.

23
Weiqhted classification. Finally we describe a classé
ification which is a refinement of the accessibility
classification. While the accessibility classification
contains much information about the structure of the
relation R (A) , this information is aggregated,
and different structures, for example, lead to the
same accessibility count. We may partly remove this
difficulty by aseigning; to an accessible ordered pair
(Pi’ Pj) a weight NmL lif there is a minimal directed
path of length L from P1 to Pj , and a weight
zero to an ordered pair which is not accessible. If

the aggregate weight of the ordered pairs belonging to

i
We find that for N = 2 we get the same three states

A is i we say that the digraph is in state 5

as for the accessiblity classification,but for N a 3
we get 11 states which are exhibited in the form of a
lattice in the appendix A.l. Once again the number
of states become quite large even for small N (for

N a 4 the number of states is 31) and we do not discuss
the weighted classification in details in the present
study. That this classification is finer is seen from
the following examples: for N = 3, the structure

’fj?’ appears to be "stronger" than the structure ‘72> ,
in the sense that the latter is a substructure of the
former, but both have same accessibility count, namely,

4F4’
three; similarly the two structures EJ‘ and Rf

fuave same accessibility count, namely, five’but the first

243
'contains «the: second as a substructure and as such
appears to be stronger. In the weighted classification,
however, all of these structures have different aggregate
weights and are of different types,
We give now some properties of the connectivity
and accessibility classifications which are of interest

to US.
1222231.. For N22 : 53 E S'Nm-i).

By definition, P(A) is in state 53
if (l—(i, J) holds for every P1, Pj in A’ , that

if and only

is, the accessibility count of P(A) is N(N-l) and‘

F‘A) 15 in state S.N(N-l)

Property 2. For N = 2

$3 = 5'2 , 52 5 5'1 , 50

E s'

o --
53 5 5'2 from property 1 and a two-point digraph is
$2 if,and only if, either ‘52 (P1, P2) or
‘61 (92, P1) but not both (where A - {P1, 921), that

in state

is, exactly one of the ordered pairs is accessible and

hence 52 5 5'1 . Finally a two-point-digraph is in
state 50 if and only if neither R (P1, P2) nor
‘61.(P2, P1) , that is, none of the ordered pairs is
accessible and therefore 50 5 5'0 .

Property 3. For N - 2 the connectivity and accessi-
bility classifications are identically same. There are

two two-point structures which are weak but both are

as
also unilateral and as such a two-point structure cannot
be found in state 51 . Hencethis property is a direct
consequence of prOperty 2 . -
Property 4. A digraph P(A) is strongly connected
(or, is in state 53 or equivalently in state S'N(N-1))
ifi.and only if the correspoindhwymatrix C(A) is irreducible.
We note that a matrix C is said to be reducible if
there exists a permutation matrix P such that
p'lcp = (E 3)

Where 0 represents the zero matrix and B and D
are square matrices. Otherwise C is said to be I
irreducible.

This is proved in Dulmage and others E 8 3 .

Having described the states in which a relation may
be found at time t we wish to find formal procedures
for counting the number of subrelations Rthh ),
of fit”) in states ~51 (5'1) at time t and the
number of transitions from state 51 (5'1) at time
t1 to state s.( s'j) at time th (tl < th). These

J
are given in the next section.

26

1:3 Enumeration of, subrelations in states Si , 5'1 ,

 

and transitions.

In this section we propose to find formal procedures
for enumerating (i) the number of subrelations.62 t(a)
in states 51’ 5'1 at time t (11) the number of sub-

relations which are simultaneously in states 51 , si ,
1 2

..., s or states 5' , s' , ..., s' at times
1h 11 12 1h

t1, t2, ..., th respectively (tl < t2 < .... < th)

.lAt any time t, a subrelation 12.t(a) may be in any one
(and‘only one) of the states 51 of the connectivity
classification, and in any one (and only one) of the

states s'1 of the accessibility classification. ’The number
of points in the subset a is n and therefore there are
(E) subrelations ‘Q t(a) of the relation Rt”) . Let
at time t there be Rni(t) n-point subrelations El.t(e)

in state si , and R'ni(t) n-point subrelations 62t(a)
1h state s'i .

To find the values of Rn (t) and R'n (t) we define

1

the functions f and f' on the class (Q 1:(e), aCA]
with the set of states {51} as the range of f and the
set of states {5'1} as the range of f' . We say that
the function f('§2t(l)) takes the value si if‘62t(a)
is in state 51 at time t , and the functions f('62t(e))
takes the value s'i if 12~t(‘) is in the state s'i at

time t ; so that

27
Rm“) "‘ " [Qtub aCA I Hutu” = 51 1

and R'n,(t) =- n {‘61 t(a), aCA | f'(‘62t(a)) = 5'1}

-

Thereforethe main problem is that of being able to evaluate
the values of the functions f('5zt(a)) and f‘(‘51t(a))
at time t for every ‘62 t:(a) in the class {.62 t:(a), aCA ).
To do this we need to identify the state 51(5'1) to which
a given'Ul t(a) belongs at time t . While this can be
done at least in principle from the definitions of 51(5'1)
themselves, such procedures are neither practical nor desirable.
We present here technically equivalent methods which do not
require a point to point check, and which can be programmed on
computers for easy and time-saving computations. For this
purpose we find it more convenient to use the matrix repre-
sentation of Tit”)
Let Ct(a) be the (principal diagonal) submatrix of
Ct(A), corresponding tolfil t(a), and let C§(a) = Ct(a)
+ I where I is the nxn identity matrix.
Theorem<1.3.1
(1) f( ‘Q (a))
(11) f( R(a))

n-l
if, and only if, LENS] > O
or 52 if, and only if, [E*(a) "-1
+ C*’(a)] W} > 0

or 51 if, and only if,

53
S

2

(111) f( ~(52(50)

S3, S2

[C*(a) + C*'(a)] "'1 > 0

50 if, and only if, [5*(3) + c*'(afl "-1
j. 0

(iv) f( ~51(3))

28
MEL (1) Let C*(a) "'1 = (c* ij(n'1)). Then

Ci ("-1) - ”£1 CI . CI.1, 0197‘, C! j
j 11, 12, ..., 1n_2 t1 . 1 2 a n-2
311
Since the c*1j ane all non-negative, c*(? l) > 0 if at

least one of the terms in the summation is non-zero. For

i f; j each such non-zero term corresponds to a directed
path from P1 to Pj , and for i - j each such non-zero
term corresponds to c*jj > 0. By definition, c*jj > O

for all j =- 1, 2, ..., n . Therefore [2*(38 "-1 > 0.
if, and only if, for every ordered pair of points P1’ P1

(1 f j) belonging to the subset we there is a directed path
from P1 to Pj , that is,the subrelation RH!) is

"strond' (state 53).

(11) Let C*'(a) ”'1 a (c§3("'1)). Then

n-l
cf‘ml) - ,2: ca ci'i ..., c*'
11’ 1?: ..., in-2 1 l 21n-2j °
- 1
Since of} - cji it follows, as in (i) , that c§3(n'l) > 0
if there is a directed path from Pj to P1 (1 f j) .
111erefore c*§n 1) + cfj(n 1) > 0 if there is a directed

path either from P1 to Pj or from Pj to P1 . Hence
[0(a)] n 1 + [9*‘(a)_] "J1 0 if, and only if, for
every pair of points Pi’ Pj> (i f j) belonging to the sub-
set a , there is a directed path either from P1 to Pj

89
or from Pj to P1 , that is, the subrelationn (a) is

"unilateral" (state 53 or s 2).

(111) Since cgj + cij a c1] + cfii it follows
that cij + c§i > 0 if there is a directed line either

from P1 to Pj or from Pj to P1 , that is, there is

a line between P and P. (i #’j) . Define a matrix

1 J
D = 0*(3) + C*'(a) and let D a (d ij) so that dij
a of] + Gil . Let Dn"1= (d(n 1)) . Then
d(n- l) "'1
= 2' d d . o d
diJ 11, 12, ..., in~2 111 1112 9 inaeJ °
=1

‘ The dij are all non-negative, and diJ .> 0 if there is a
line between P1 and Pj (i #’j) . Therefore d(: 1) > 0
if there is.a chain of lines between Pi and Pj . Hence
0""1 > 0 if, and only if, there is a chain of lines between
every pair of points P1, Pj belonging to the subset a ,

that is, the subrelation }F{(a) is"weak" (state 5 , s or s )-
3 2 1

(iv) Finally, Dn-l =- [6*(a) + C*'(a)] n-l If 0:
if, and only if, the subrelation R (a) is not even"weak','
that is, (Q.(a) is'Uisconnected" (state so) . .

Corollar l. .1.
(1) HR (3)) == 53 if, and only if, ‘2*(a)]n-1 > 0
(ii) f( ‘Q (a)) = 52 if, and only if, LC*(afl "-1 I) O ,

M new

 

 

 

 

30
(iii) f(‘Q(a)) =- 51 if, and only if, [2*(aa "-1
‘ + LC... (a)]"'1 $0, Lou) + Wm] "'1 > 0
(iv) f( R(a)) =- 50 if, and only if, [9*(3)

+ 'C*'(ai] "'1 i 0 .

Theorem 1.322. f'( UR(a)) a 51 if, and only if, the number

of non-zero entries in the matrix (Eden "'1 is exactly

n + i .

figggf. As in theorem 1.3.1.,

for i‘% j, cfgn-1)> 0 if, and only it there is a directed path
from P1 to Pj , that is the ordered
pair (Pi’ Pj) is accessible,

(n-1)

and c3] > O as a consequence of the definition of

C*(a)’ j- l, 2, 0.0, n.

("-1) , i #’j of the

Therefore,the non-zero entries c*ij
matrix .[§*(a) "'1 count the number of accessible ordered
pairs of points P1, Pj belonging to subset a, . Let
this number be i so that the subrelation (R\(a) is in
state 5'1 and f' (&(a)) a; si . Since all the n
entries on the main diagonal of C*(a) "'1 are always
non-zero by definition;, the number of non-zero entries in
LC*(a))n-1is n+1 if, and only if, 1"(‘6Uan))-Js'1 .
The above results, namely, corollary 1.3.1 and theorem
1.3.2 can be programmed on an electronic computer in order
to obtain Rn1(t) and R'ni(t) . Later on in this section

we describe programs; for MISTIC computer which not only

enumerate Rn1(t) and R'n1(t) at different points in time,

31
but also obtain transition frequencies.
For n = 2 there is a global technique also, to obtain

R21 (1 = O, 2, 3) . Let 1 denote the column vector of ones

and 1' the row vector of ones.

Theorem 1.3.3

 

(1) R23, = 35- 1' Low 1
(11) R22 =- -,:$ 1' LC + 0] (mod 2) 1
(111) Red = (g) - (R23 + R22)

ELQQfo Let the matrix C(A) be simply denoted by C, and let
the subset a a (P1, Pj) .
(i) ‘ The subrelation ‘62 (a) is in state 53 if there

are directed lines both from P1 to Pj , and from Pj to

P1 3 that is. R (1. DA 752 (j, 1) holds. Let c * c'

= -! =.~
(cij °,c'1j)' Since c ij cji

1 if no. DA ”RU. i)

0 otherwise

cij - C'1j=

Therefore the i-j entry of. C*C' is one if, and only if,

i the subrelation 'E{(a) is in state 53 . Because of symmetry
the j-i entry of C*C' has same value as its i-j entry.
Hence onehhalf the content of the matrix C*C' counts the

number of two-point subrelations in state 53 , and we get

[(23.3% 1' LOWE) 1

(ii) The subrelation R (a) is in state 52 if there

is a directed line either from P1 to Pj or from Pj to

P1 but not both; that is, either ‘RU, j)/\ RU. 1) or

32
R(1,j)A RU, i) . The matrix C + C' = (c1j+¢"ij)
= (Gij + $31) , and

911+ 911 =- 2 if Ru, j),.«,/\ R (j, 1)»
1 if either Ru, j) ‘A & (j,i) or
gt” 1) A ‘RU. 1)
<)1J= '62(i, j) 7\ ‘Kl(j, 1)

(cij +Cji) mod 2 = 1 if either RU, j) /\ Yfi (j, i
or RU. 1) A RM. 1')
0 otherwise
Therefore the i-j entry of the matrix (C + C*) mod 2 is

one if, and only if, -E{(a) is in state 5 Because

2 .
of symmetry the j-i entry of (C + C*) mod 2 has same

value as its i-j entry, and hence,

R22. = g 1' UC+C') mod 2]

(iii) Finally, the total number of two-point subre-
lations is (g) and a two-point subrelation, by definition,

cannot be found in state 5 Therefore,

2 0

R20 ”‘2% * (~B23 T 822 )

which completes the proof of the theorem.
Nextys we' consider the enumeration of subrelations
'E{t(a) which are simultaneously in states 511, 512, ...,

s at times t , t , ..., t respectively. We define a
1h l 2 h

 

33
function f(h) on the class of all ordered h-tuples

(Rt 1M, t(a), ..., ~62 (a)) » wherem (a) repre—
t2 th tj .
sents lthe subrelation 62th) at time tj’ j = l, 2, ..., h.
The range of the function f(h) is the set of all ordered

h-tuples of states 51’ such that

1:“) (Rtlm), thb), ..., ~02th(a)) = (511, $12, .... sih)

if f( ‘Qto(a)) = 51. ,j= 1, 2, ..., h
J J
The value of the function f(h) for an ordered hotuple
( Ult (a), Uzt (a), ..., Bit (3)) represents a transition
1 2 h

of order h-l from state 51 at time t , to state

1
s at time t , through state 5 at time t ,
1h h i2 2
state 51 at time t3 , ..., state 51 at time thrl .

3

Therefore,the total number of transitions from state 51

at time t1 to state 51 at time th through states
h .

51. at time tj , j = 2, 3, ..., h-2 is given by
J

“{( mt 1(a):‘R 122(6), 0°02 Rth(a)) 2 am I f(h)( uti(a)9

Rt2(a)’ "'1 ath(a)) = (511’ $12) °°°! 51h)]

 

34
These numbers can be arranged in the form of a table, called
an (h-l)-order transition table.

Let Ct (3), Ct (a), ..., Ct (a) be the corresponding
1 h

2

matrix representations of subrelations Uztl(a),'3lt2(a), ...,
RE (a) respectively. To evaluate the value of the function
h
f for the ordered h-tuple (‘62 (a), ‘62 (a), ...,
(h) t1 t2

Rth(a)) we repeatedly apply the results of corollary
1.3.1 to matrices C*t. (a), j = 1, 2, ..., h whene.~

Cat (a) - C"-t (a) + I . In order to construct an empir-
ical transition table, we can write a computer program to
find the value of f(h) for every ordered h-tuple {
(Tittle), Rtem, ...,nthm), aCA, and to count the

number of (h-l)-order transitions from every state 51
to every state sj where sj may be same as 51 . For
the special caSe N - 25, and n a 3 we have MISTIC pro-
grams to obtain the first-order and second-order empirical
transition tables (for the connectivity classifieaeton);
these are given in appendix A.2.

In exactly the same way as above we can enumerate the
number of subrelations Ekt(a) which are simultaneously in
states 5'11, 5'12, ..., s'1h at times t1, t2, ..., th

respectively. We define a function f'(h) on the class

35
{ ('61 (a),'5{ (3), ...,.UI (a)) , aCA} which takes
- t1 t2 th
values on the set of all ordered h-tuples of the states
5'1 , and .
f'(h) (RtJ-(a), ~Rt2(a), oee,uth(a)) a (5'11, Sig, 000,

5'1 ) if f' (IQLt (a)) = 5'1. , j = l, 2, ..., h .
h J J

The value of the function f'(h) is evaluated by repeated
use of the results of theorem 1.3.2.
In order to construct an empirical transition table (for
the accessibility classification) we can once again write
a computer program; for the special case N = 25 and n = 3
we give a MISTIC program in the appendix A.2 to obtain
second-order empirical transition tables.

We note that a computer program which obtains (h-l)-
order transitions tables for a given data can also be
used» to obtain various transition tables of order less than

h-l , and the values of Rn (t) or R'n (t) by finding the
, 1

proper marginal totals. 1
For n = 2 we have global techniques to construct first

order transition table. There are only three possible

states, namely, 53 , $2 , 50 for two-point subrelations

so that the first order transition table T is of order

3 x 3. Let

 

 

 

 

t2 I
.fl 53 52 so Total
53 ‘33 t32. t3o T3
T a s2 t23 t22 t2o T2
59 t03 t02 too To
Total 1'3 1'2 T'o (3)

‘where tij - number of transitions from state 51 at

time ti to state sj at time t The row and column

2 .
totals Ti and T'i can be obtained from the theorem
.is enough to find any four independent tij's in order
to complete T

Let C1 and C2 be incidence matrices corres-
ponding to relations Rt (A) and at (A) respectively.

1 2‘

Define matrix D = (C1 + C'l) + (C2 + C'2), and let
an entry in D be denoted by dij so that dij takes
value 0, l, 2, 3, or 4 . We decompose matrix D
into matrices kD - (kdij) such that

4 _

. kD a 0.00 + 1. 10 + 2.20 + 3. D + ”'40

3

1 if d1. = k

where kdij a J
.0 otherwise

Theorem 1.3.4 For n - 2 , in the first order transi-

tion table T - (tij) , i, j = 3, 2, O

 

 

 

(1) too a '2
(11) t33 = -%
1
(iii) t30 8 'g
(iv) t33 == '2- [1'

37

[1' .o 13
Li" a“ 1]
[1' (61* c'1 * 2D)1 3
. 20;) 1 :1

(:C2* c'2

Proof. Let C = (Clij) , C2 = (c2ij)'

l

+ C . + C

dij = c11j lji
Let a = [P1, Pj] . The c

+c’5'

2ij 2J1

Then

lij’ C21j’ are all non-

negative. We note that because of symmetry the i-j

and j-i entries of kD takes same values (k =

2) 3) 4 ) ’

(i) 1 if d..
d . - lJ
o 1J

0 otherwise

Therefore d = 1 if there is no directed path

0 ij
between P1, Pj both at times
two-point subrelation R(a)

Q (a) and R (a) are in
t1 t2

one-half the number of ones in

of transitions from state s0

s0 at time t2 , and

too

= O, that is, 6

t1 and

this means that both

”state 50

00 count

at time t

= %-(the content of the matrix

t

f 1
)

l

O

0,

For

2

Hence

the number

to state

0)

liJ

(ii) 1 if dij = 4, that is, c . =

- a; e

0 otherwise

1,

38
Therefore, 4dij a 1 if there is a two-way directed
path between Pi and Pj both at times t1 and t2 ;
this means that both ~62 t1(a) \and .51 t2(a) are in

state 53 . Hence,one-half the number of ones in

#6 counts the number of transitions from state 53

at time t1 to state 53 at time t2 , and
.l
t33 - 2 (the content of the matrix MD)
(iii) 1 if dij = 2, that is exactly two
241] a of C11], clji’ dzij’ c2j1 are ones,
and the other two are zeros.
,OLotherwise
Therefore 2dij -‘1 if either there is a two-way

directed path between Pi and Pj at time t1(t2)
and no directed path between them at time t2(tl), or
there is a 'one-way directed path between Pi Hand

Pj both at times t1 and t2 . This means that

either at (a) is in state 53 (so) and Rt (a)
1 2
is in state 50(53), or both TSKt (a) and .Elt (a) are
l 2
in state 52
Since C1 * C'l a (Jiij . clji) , the i-j entry

(and because of symmetry the j- entry) of C1 * C'1

is 1 if both £11] and Izlji are one, that is,

there is a two-way directed path between P1 and Pj
This means that tht (a) is in state 53

1
Consider the matrix (Cl * C'l) * 20 . The i-j
entry of this matrix, namely, clij . Clji . 2dij is 1

 

 

39
if, and only if,Ԥ{ t (a) is in state

1
is in state 50
Hence, t3O = %' (content of the matrix

(iv) Consider the matrix (C2 * C'e)

s3 and‘Ult2(a)

I
c1*c1*20).

20, then

as in (iii), the i-j entry of this matrix, namely,

C21] ' °2ji ‘ 2 1J
is in state 53 and hence,

t =-l (content of the matrix C2

03 2
This completes the proof of the theorem.

d . is one if, and only if,~62t (a)

2

v
* C 2 * 20)

 

 

 

40

1:4. Change in relation 52t(a) as a stochastic process

 

In this section we present a simple probability model to
serve as a basis for analyzing time changes in the relation
'Eztfa). As time proceeds some of the dyadic relations
nth, j) or With, j) between ordered pair of points
(P1, Pj) may change while others may not. Consequently,
the total relat on 'Klt(A) is a function of time and
changes with time. To generate enough statistics on the
process we study the change in the total relation 1a.t(a)
in terms of the aggregate of changes in its subrelations
'El,t(a) . A shortcoming of this approach is the non-
independence of subrelations "Slt(a) . However, as
indicated in the introductory chapter this problem is not
very acute for N >> n (where N and n are the number of
points in set A and subset a respectively)#

At a specific point in time a subrelation TR‘t(a)
may belong to any of the states 51(5'1) ,w‘ahdr contin-
u‘e p to be in the same state for a certain length of time,
buzpossibly changing from one structure to another within
the Same state 51 (5'1) . At a subsequent time the
subrelation may change states abruptly and belong to some
other state until the next change, which may be a return to
the previous state or a passage to a new state. Such a
process is observed only at discrete points in time at
spaced intervals not necessarily equidistant; we recognize
only those changes which take place between two consecutive

observations. This is a limitation of our study, for these

a!

QC

r45

NV

A.

 

 

#1

changes can take place at any point in time, even though
they are discontinuous in themselves. The situation is
similar to what we find in many applications; for example,
in quantum theory while the emission and absorption of
radiant energy do not take place continuously, but dis-
continuously in small‘finite quanta, this phenomenon can
occur at any time.

We consider a very simple case of change in relation,
namely, that a relation depends only on the relations at
a fixed number of immediately preceding points. This is
a Markov chain model with unspecified Markovian pr0perty.
In many cases such a model may be too simple to explain the
process of change in relation but it leads to the formula-
tion of a more sopihisticated theory and to the consideration
of other kinds of models.

Let { x1, x2, ... I be a stochastic process or
sequence of random variables taking place in a finite
set of values {51, $2, ..., sm}. The process {xi} is
a Markov chain of order r if the cOnditional probability

P { xj = sj I x1 a s1 , i < j 1
is independent of the values of 51 for i < j - r.
The u-th order transition probabilities for a Markov
(u)

J

chain, denoted by p i' are

(u)
Pij a Pixk + u = Sj I xk z 51} '

42

A Markov chain is said to have stationary transition prob-

abi lities if
1

=Sl,xj'r+1=se, ”°, xj-l=';sr

P{ xj ' 5r + l I xj-r
rel these probabilities form

j.If

is independent of
known as the transition matrix of the

an m x m matrix,
For a detailed treatment of Markov chains we

process.
, Kemieny and Snell E9],

refer the reader to FellerE]

and Chung [5 J .
The simplest Markov chain is that in which there are a

Finite number of states and a finite number of equidistant
points at which observations are made; the chain is of first
order, and the transition probabilities are stationary.

In analyzing experimental data for Markov properties we use

Standard statistical tests for testing the following four

hypotheses:

(a) the observations at successive time
pOints are statistically independent against the alternate

hYpothesis that the observations are from a first-order

Ma rkov chain

(b)

<:P\aain are stationary
(c) the process is a (r-l)-th order Markov

Chain against the alternate hypothesis that it is a r-th

the transition probabilities of a Markov

(r-l)-th order chain
(d) in case the transition probabilities are

Constant, they are specified numbers.

but not a

43
‘Tl1ee derivation of these tests and an analysis of their statis-
ti cal prOperties are given in Anderson and Goodman[1 3;
also relevant are Bartlett L2] and Billingsley [’4]. We
present here a brief description of these tests for ready
reference, and for later use in section 3.2.
Let the states of the process be denoted by i = l, 2,

. .., m, and let the times of observation be t = O, 1, ...,
T . Let p1]...k (t) (1, j, ..., k,.(. = 1, 2, ..., m)
denote the transition probability of state X. at time t,
gyiven state k at time t~l, ..., state j at time
‘t-r+l, and state i at time t-r (t = r, r + 1, ..., TL
ILeet "ij...k1, (t) denote the observed frequencies of the
states i, j, ..., k,&, at respective times t-r, t-r +1,

- - ., t-l, t , and let nij...k(t'1)
m
= E nij...k (t) . We assume that nij...k(t-1)

are non-random.
(a) For testing the null hypothesis that the process
is independent against the alternate hypothesis that it is

a First-order Markov chain, we compute the statistic

2
2 n n. n n
x = Z [(n ° -______Li ) / —-j—'—J-}
1.1 1J N N
Where ”1]: {5 nu”), “i=2.”1j ’ nj=if niJ,

J'
and N=£' n1. . The statistic X2 has an asymptotic

2 1)j
X - distribution with (m-1)2 degrees of freedom.

 

 

 

44
(b) For testing the hypothesis of stationarity for a
first~order Markov chain, the null hypothesis is H: pij(t)
= Pij for all i = l, 2, ..., m z j = l, 2, ..., m; t a l,
2, ..., T. The x2 test of homogeneity in contingency

tables consists in calculating for each row i of the

transition matrix the sum

ni.(t) Z ni.(t)
tifJ {hi (t'l) [n1(t'l) - ————T§ Z 11‘ t)
1' t - 4

 

i nij(t)
Z Z ni.(t)
' J
J t
Under the null hypothesis H, x21 has an asymptotic
x%.distribution with (m-l) (Twl) degrees of freedom, and
the set of x21 for i = l, 2, ..., m are asymptotically

independent so that the sum

2 2
x =2x
1 1

also has an asymptotic x2— distribution with m(m-l)(T-l)
degrees of freedom.

To test the null hypothesis that the r-th order chain
has stationary transition probabilities we can use a straight-
forward generalization of the above test..

to) For testing the null hypothesis that the chain is
of order r-l (that is, Pij°°'k2_ a pj...k1_ for i a l,

2, ..., m, and all values from 1 to m of j, ..., k) a-
gainst the alternate hypothesis that it is not an r-l

but an reorder chainawe calculate the sum

(D

M

,X’

 

 

 

 

 

 

 

(m. (e. . -3. ,)2
j, ..., k 1" iJ...k iJ...KL J...kL

A ‘ .
/ pj k2, } which has an asymptotic xgxdistrieutien

with m“1 (m-l)2 degrees of freedom under the null hypothu

esis; T
=1
"*1j...k a tirol ”15...k (t)’
.«
Pi, k1 .. "ij...kL / ”*1, k ’
T \
”i, .k = tir “1, .kg, (ti’
" (T < 1 T'l ( 1
. = Z n. t Z . t
pJ kt t=r J...!<L ) / {tar-l nJ...k’ )

For r = 2 , the test is of the null hypothesis that the
chain is firstworder against the alternate hypothesis that

it is secondaorder, that is, H: pijk m p23k = ... a ijk

= pjk , say, for j, k = l, 2, ..., m . To test this

hypothesis we compute the sum

 

 

 

 

T T 2
{; t§2 nijk(t) t§2 “jk (t)

Z n* . — - r
. iJ T T-l

T (

Z n. t

t=2 Jk )

T-l

Z n.(t)

t=l J

 

 

46
which has an asymptotic x2 - distribution with m(m-l)2
degress of freedom, under the null hypothesis.

(d) For testing the hypothesis that transition
probabilities are specified numbers, the null hypothesis
is H: -pij = pgj , for all i, j = l, 2, ..., m_ where
pg] is a specified value for pij . Under the null

hypothesis

‘g ( o )2‘/ o T-1 ( )
n* p . - . p n* = Z n t

1, j=1 1 1, P 1, 1] ’ 1 t=0 1

has an asymptotic x2 - distribution with m(m-l) degrees

-of freedom.

 

 

 

 

PART II
DISTRIBUTION THEORY

ml Preliminaries
This part of the thesis is concerned with certain aspects
M the probability distributions of random variables Rnr' and

W The derivation of these distributions is based on the

ni
umory of compound probabilities, anu exposition of which may
be found, for instance, in Feller [9-] and Fre’chet Ell] ;
examples of the use of such methods may be found in Katzllh'] ,
and Katz and Wilson T38]. Here we briefly describe only those
fmmmlas which are used in this part of the thesis.

E

Let E .., EM be M events, not necessarily

l’ 2’
independent, with probabilities p1, p2, ..., RM respectively.
Let pi], pijk’ ..., p1]...M denote respectively probabilities
of, the simultaneous occurrence of events E1 and Ej’ the
simultaneous occurrence of events E1, Ej and Ek’ ..., the simul-
taneous occurrence of events E1, Ej’ ..., and EM . To compute
the probability P( m) of the simultaneous occurrence of exactly
m among M events E1, E

S

2, ., EM, we define sums f 51 - E Pi:

5-2: p -z p . We note that sums S
2 1.1 11’ ' ’ M ij...M ij...M m

are not probabilities but sums of mutually not independent-
PFObabilities. The principle of inclusion and exclusion (Feller
[9:], Chapter it) gives immediately

P I a m + 1 - + 2 ' M

(m) Sm ( m )Sm + 1 (E'm )sm + 2 .. i. (m) SM,(2.1.1)
Let PEN] be the probability of the occurrence of at least an among
,M events E1, E2, ..., EM . Then

Ptmj*- P(M) + P(m + 1) + ..., + P(M)

47

 

 

48

or in terms of the sums S S

1’ 2, ..., M
= m m+l _ M-l
PEm] (m-l) Sm + l + ( m-l ) 5m + 2 i (m-l) SM '

It turns out that the quantities Sk are of central importance

in finding the moments of the distribution. Fre’chet [11] has

shown that
.. T
Wk) " k'sk
where a(k) is the kgth factorial moment of the distribution,
‘ (k) (k)
given by a = 2 m P m = m(m-l) ...,
‘ (k) m=l (m) ’
(m-k+l). In particular,the mean and variance are given by
Mean = 51 (2.1.2)
2
Variance = 252 + S1 - S1 (2.1.3)

It is also of interest to note that the follow*ng inequalities
’P(m) g Sm and PEG 3 Sm
can be proved (Feller [9:] ) from the above formulas.
Throughout the rest of this thesis we suppose that dk
denotes the "valency" (or degree) of a point Pk in set A,
that is, dk is the number of points in set A 'with which Pk
is in relation "(R . In terms of graph theory dk is the number
of directed lines starting from Pk . We assume that for any Pk
the valency dk is fixed and the dI< directed lines starting
from the point Pk follow a hypergeometric law. Furthermore the
probability distributions of Rni and mm are derived for the
case of a completely random distribution of valencies. The general
case with varying number of valencies is known as the 'unrestricted
case', and the special case when all dk are same, equal to d

say, is known as the 'restricted case' . For the unrestricted

case the results are rather complicated, and although the

'restricted case' is a special case of the 'unrestricted case' we

present the two cases separately due to marked simplicity and

49

empirical importance of the former.

Let Pr Ln (1, 1)]

denote the probability that R (i, J)
holds, Pr ER”, 1) I ‘6). (i, k)] the conditional probability
I that Rh, 1) holds given RH, k), ..., Pr [22(1, J) I

'62 (1, 11)A‘62 (1, 12)/\ .../x ~61(1, 1m)

 

probability that RM, 1) holds given ~62(1, 11), TR (1, 12)
..., ‘&(1, 1m) . Then we note that
P v (1, 3 d1
r I: ”1 W17
... ‘ d
Pr DR”: 1)] - I-fi
P 1, R 1, k - d ’1
.- Em ‘J)| < )1 N1?
. .. . d
P 1, 1, k - 1
r Lu( J) I ’(PJ )3 W3
Pr [-5531, j) | ‘29. (1, 1.)] £13 di-l
Pr 1931; J) I min. k) :3. 1': di
Pr [mm 1) I R (1. 11M R11. 1,) /\ mA
m1. 1,,9]
- dbl - m , m < d1
- -m .
and so on.

this part of the thesis:

ye)

 

 

x(x-1)

We give below some conventional notations which are used in

(x-9+1)

the conditional

. e
. . a!
f .. -~

.5]!

{' iv

a." F

(2‘

(.-A.)

«h

um = ' 2 d1
il<1e<"'<1m l 2 m

The functions um are called elementary symmetric functions and
I may be expressed in terms of the power sums (for a proof see
Perron L213)

V = Z d
m .

m
1 i

For m = l, 2, 3, 4 the relations between um and vm are

given as
l .2 -
U2 3 21 ("1 V2)
_ l, 3 _
u3 - 3, (v1 3v2vl + 2V3)

 

 

 

51

2: o T d d1 ~ 3 I
The first results towards finding probability distributions

of Rn11 and R'ni are obtained for the simplest case, namely,

n-2 . lThe total relation R (A) is viewed upon as an aggregate
of'the two-point subrelations R (a), a - (P1 , Pj) where.

P1, PJ belong,to Set A . (Throughout this section 51 (a)
denotes a two-point subrelation.) We have seen in section 1.2
(Page 21) that for n - 2 the connectivity and accessibility
classifications are identical; there are only three different
states in which a two-point subrelation Rh) may be found,

and R a R' , R a R' , R

I 23 22 22 21
also indicated in section 1.3 (Page 21) that 52 (a) or equivalently

20 3 R'20 . We have

F(a) is in state s3 if there are directed lines both from
, if there is

 

. P, to PJ and PJ to P1 3 it is in state 52 .
l exactly one directed line between P1 and PJ 3 and it 13 in
I state so if there are no directed lines between P1 and .Pj .

I Theorem 2,2,; For the restricted case
(1) E (R23) ' (fi)
(11) E (R22) ..fldifihiidl
‘ 2,
(111) E (R20) "fllgTfiegI'

21221 from relation 2.1.2 we know that the mean (the expected
value) is equal to the quantity $1 . Let I ‘

51,1 - z Pr [_f( 19L(a)) - sijl
where the summation is carried over for all the two-point subsets
of the set A ." '
The Pr f( Rh) ) - s1 is same for all subsets a , and the

number of ways of choosing subsets of two points from a set of

 

N points is (g) . Therefore

52

E(R21) .. 51,1 .. (g) Pr LN ‘62(a)) - 51]

(1) Pr [H ‘Run =- 53] =- Pr Ilka, j)/\1R(j, 1)]

2
d
" (Wine
so that 2 2
N d Nd
E(R23) ' 51,3 ' (2) (N-1)2 ' (N_1

This is also obtained in Katz and Wilsontl8j , where Variable

R23 corresponds to the number of mutual choices in a social group

of size N
(11) ‘ Pr [H R (a)) = 52—) :- Fri {R(1,J)I\§U. 1))
' A 0T( ‘TRhl-s j)/\‘&(ja 1))J

1 d d
- 2111—7-1‘1‘fi71')

so that
N d « d 8
5(R22) '> S1 2 ‘ (2) 2' N-l (1 ' N-l ) N-l

’

(111) p.- [n Run) a 5;] - "But, ”A153,, 1):]
_ ( 1 - %_1)2

so that

N d 2 N(N-1-d)2
E (R20) = 51,0 " (2) ( 1 ‘ m ) ' _2(fl-1)'

Theorem 2.2.2 For the restricted case

(1) V(R23) - Nd2(N-1-d)2
2(N-1)3 '

(11) V(R22) - 2Nd2(N-l§d)2
(N-l)

(111) V(R20) - ~d2gu-1-d)2

2(N-1)3

53
Ifiiggf From the relation (2.1.3) we know that
Variance f 2S2 + Si - $12
The sums 51,1 ,_i a 3, 2, 0 have been already obtained in theorem
2.2.1 (page 51), and we only need to compute sums 52,1 , i a
3, 2, o f
52’, =- 2?er (‘61(a1)) :- 511A{f('61(a2))- 513]
where .1 = {P1, P1}, a2 = (Pk, Pl] are any two different subsets
of the set A .
If the subsets
points then the two eyents {f(‘R(a1))1# $1} , (Ha (a2))

a1 and a2 are composed of four different

= 51} are independent, and

Pr [m ‘R(a1)) - $1]A{f(u(le))= s11]

= Pr LH'RHIH = 51] . Pr [fl‘ahefl == 51:]
which is same for every pair of disjoint subsets of ‘A . If
the subsets a1 and a2 have one point in commoh then the two
events (f( R(a1)) - 51], {f(m(a2)) - 51} are notindepenhat
and we compute the compound probability

Pr [H462 (31)) - $13A(f(R(a2)) =- $111 .
which is same for every pair of subsets,of A , with one point
in common. .3 1
The number of ways of choosing four different points from N
points and forming two dyads from them is (3) 2.232. ; the
number of ways of choosing three different points from N
points and forming two dyads from them is (§)'§I . Therefore

52,1 511?) 57—527 {P' I.“ 11(5)) ' 51 (J) 2

'+ 313+ Pr [m ”6L(a1)) =- sir/mama» = s11]

because Pr Ef('R(a1)) = 51] == Pr lf(’62(a2)) - 51 for

disjoint subsets a1, a2 .

(A

aPI
II N

54
Since probabilities Pr [;f('52 (a)) = 51:] have been found in

theorem 2.2.1 (page 51), therefore to compute quantities

5
2,1
tYPe Pr [lf( (Q(i2)) = Si} /\ (F(ZQ,(al)) = 51):] where

have one point in common.

we only need to obtain the compound probabilities of the

subsets al and a

2
(i) This is obtained in Katz and Wilson [18:]
(n) Pr [(141292) = $2)}/\(f(7sQ(a1)) = 521:] ,
31 = {P1, Pj) ’ a2 = {Pi’ Pk}

= Pr R(1.j)/\ fin. HARM, k)/\ 2:10., 1), ”-I
mi, j)/\ fit]. ima’iu, kEvA wk. 1). or
{11, j)/\ no. mush. exam, 1), or
LfiLDAfiULMAflLUARWA)

d d del) d d-1 d
= (4-1 ‘1'W:I) [hr-72“,“ ‘1' m)+(l'm)‘m)

d d d
TNL2) (1 ' NTT) + (1‘fi72) (N-l)

 

After some calculations V(R22) can be written as
2Nd2(N.1ad)E
(N-1)3
(111) p.— [m ”&(a1))= so) /\IF(‘6{(a2)) = .01] .
.1 = [P1, Pj), 32 = [P1, Pk}
= p.- [1331, j) A an, 1) /\ fin. kM Wk. 1)]
= (1 - fié— ) 3 (1 - -Q— )

v(R22)

 

1 N-2
After some calculations V(R20) can be written as
_ 2 _ _ 2
V(R20) _ Nd (N 1 d)

2(N-1)3

55

i Theorem 2.2.3 For the unrestricted case

(1) vi - v2
E(R23) a 2(N-1)2

(ii) ' vi - v
E(R22) 3 v1 ' f§:;;22

 

(111) _ v2 - v
““20" ”‘79 ”fi—fif

Proof Let a = [P1, Pj)
(i) Pr Ef('61(a)) == 53 = Pr 1&(1.J)/\R(J. 1)]

d d.

 

N d d
ER =5'-z LJ.
I ( 23) 1’3 1<j=1 (N-l)2
= v1 ’ v2
‘ 2(N-l)2

as obtained in Katz and Wilson 118] ; the notations“ v1, v2

have been explained on page 50.
(11) Pr Latin» =_.- 52'] ...
Pr [1152(1. J)/\zi(j. 1)} or t sin. HARM. in]

d d d d
a Tn%—7' (1 "fiéi ) + 'Tfiéiy (1 - fléi')

. N d - d d d
' 1 1 ! i
[(R22) :- 51’2 :- iizj‘l ( I'm-.1 (1 "' ‘N'Z'i ) + _1 (1 ' -1 )1

which reduces to
2
v1 ' v2
(Iv-1)2

(111) Pr [f(‘®\(a)) =--- so] = Pr [641, J)/\ ‘63.”: 1)]
= (1 ";%1 ) ( 1 “;}i )

v1

 

 

56

which reduces to
2

N(g-1) - v1 + v1 - va
‘ 21 (1.152

It is easily verified that for the special case dl - d2
- .4. - d" - d the above results reduce to the results of the

theorem 2.2.1.

Theorem 2.2.1} For the gmnest‘ri-bbed-rcus'e:
(1) V(R23) = --lh-fi- (- v12 v2 + v22 + hvlv3 - 3v“) +

 

 

 

2(N-1)
1 3 2 2 _ 3
(N-1)3(N-2) ( v1 v2 * v2 * 2V1V3 + 2V4 V1
1 2
+ 3v v - 2v ) + ---- (v - v )
l 2 3 2(N_1)2 1 a
1 2 2
(11) V(R22) I 7;:13E' ('3Vu + uV1V3 + V2 ' 2V1 V2) +
a (2v - 2v v - v2 + v2 v ) +
(N-1)3(N-2) I 1,3 2 1 2
(v13 +429' - 3vwv )’
(N'l)3 i _ 3 lh3fi
..2EL_. - 3 -
+ (N-1)3 ( V1 2v3 +3V1V2
+1 4 (-v 3 - 2v + 3v1v )
(N-1)2(N-2)~ 1 3 2

2
(N-l)2

 

3 _ 2 -
+ (vl + 2v3 3v1v2 + v1 v2)

 

57

 

 

 

(111) V(R20) = This: ('3Vu + 4v1v3 + v22 - 2v12v2) +
?;::;%?;:2; (2V4 - 2v1v3 - v22 + v12v2 + 12v3 - 18vlv2

+6v13)
(N-l§g(N-2) (-2v3 + 3vlv2 - v13) + (N31)3 (6V3 - 9v1v2 + 3v13)
+ (Nfl)3 (-2v3 + 3v1v2 - v13) +
2?E%l;§’ (4V3 - 6v1v2 + 2vl3 - 3v2 + 3v12) +
322—??? (v2 - v12) + ail-€33 (-v2 + v12)+
'Tfigfy (v2 - v12 ) + (v2 - v12)

.figggf The derivation of variances in the general case follows

the same method as for the restricted case (page 53), except

that now

52,1? 2 p.- [f(7R(a1)) = 51‘} P, V‘Rhenc 51]"

+ z Pr [{nmaln - $11 A m mag» = 51)]
where the first summation is over all pairs of subsets ‘1
a [P1, Pj) and a2 a (Pk, PL]’ and the second summation is over
all pairs of subsets '1 = (P1, Pj) and a2 - {P1, Pk). AEach set
of four different points may form a pair of dyads in three ways,
and each set of three different points may have any of the three

points as the common points in the pair of dyads. Taking these

‘dl‘

Fig -

It 5

 

58

into account we may rewrite

N
52,1 = i<§§k<2 Pr [HR (a1)) = $1] Pr image» = 51]
=1
N N .
+ 121 {jgk Pr [IN null” I." 51} [f(R(a2)) = $19
=1

To compute $2 1 we need following relations (*) which are
’

easily seen to be true.

 

 

N LN-leN-gMN-fl v1

2 d = "

- i 4!
1<J<k<1,

=1

2

N .. .. . .

2 did. 3 LN?” 3) (v; ‘2).
i<j<k<£ J "

=1

d d.d = 15:31. (v13 - 3v2v1 + 2V3)

>3
1<j<k<,o_ 1 J' k a:

Z V
1 1 j<k=l 1 2 1
,4 1
N I N 1 15:31 ( 2 )
2 d d = v - v
i=1 j<k=l 1 J 2 . 1 2
#1
N N 1 3
didjdk } 5- (v1 - 3v2v1 + 2V3)

 

N N

2
2 I 2 d djdk )

ial j<k=1i

741

1
a 2 V2

2
(v1 -

v2) - v1v3 + V#

The quantities '51 i for the general case are given in theorem
’

IV)

”(R21) 3 S2,1 + S1,1

.2.3 (Page 55) and V(R21

)

- S

are calculated from the relation

2

1,1

(1) "Eh-e proof is given in Katz and Wilson [18].

_d_.L_ d. d1. "
1 ' N-l )1*(N+1) ( 1' fiflq:]'

(11) N d1
5 = 32
2’2 i<j<k IN'l

d

d
k x.
mm ”'11:”

N N di
.2 z Fm
i=1 j<k=l
x, #1

 

 

+

dk
+Trfifi) (1 ‘

d1:
N-l

<1- 1m

WNLIi—Ifir '1) <1- 5'1.)
N-l

1' .
Making use of the relations (*) , and substituting for S1 2
. ,

d
1 (1 -
IN~25
ar nd S in the relation for
2,2

ducticns,the expression

(11)

V(R2

2)

as given'

we .get, after some re-

in the theorem.

<11 - 1 )} dj ( d1
-————- + 1 - ,
N-2 Tfijiy “9}
d d
k k
N-l ) + (N-i) (1 ' N-2

i )3“

 

v—i

(111) 2 di d. dk
S2,0 - 3i<j<k<1 (1" N-i) (1 ' N-l ) (1' 'N'l'i)
=1 d
(1-‘ N71 )
N N < di) < 11> ( d") < d1
+ 2 >3 1 - — 1 - — 1 - —— 1 - —
i=1 j<k=1 N-1 N-1 -1 N-2
741

Making use of the relations (*) , and substituting for S2 0

.9
and S in the relation for V(R ) we get, after some

1,0 _ 2O
reductions, the expression (iii) as given in the theorem.
To obtain higher moments we need to compute the sums Sm ,

m 2.3 . The number of different types of terms in Sm rapidly
increases and the resulting expressions for Sm become rather
cxmnplicated algebraically but the principle of computations

remains same. We give here the derivation of S for the

3,3 ’
restricted case, to illustrate the method. The sum

53,3 = Z Pr [{f(‘62(al)) = 53} /\(f( ~(Q(32)) - 53}/\
(f('5L(a3)) = 53} :]

\uhere the summation extends over all the triples of two-point

subsets ‘1 a [P1, Pj) , a2 (Pk, P 3, a3 = (Pm, P"). For any

1.
[marticular triple of subsets a1, a2, and a3 the number of

(iistinct points in the three subsets may be six, five, four or
tfl1ree; there are two ways of forming a*triple of two-point

subsets on three points, namely, Pk = Pj’ Pm = P P = P , and

i’ n 1.
Pk = Pm'= P1 . Thus S33 consists of five different kinds of

I
terms, and there are (E) 375%? different ways of obtaining

. ' i
the first kind of term (six distinct points); (g) 5%37 ways of

61
obtaining the second kind of term (five distinct points);
(1?) g—z- ways of obtaining the third kind of term (four distinct
points); (2) %-;- ways of obtaining the fourth kind of term (three
distinct points); (g) ways of obtaining the fifth kind of term
(three distinct points). The probability element of each type.

is easily determined, and

. N __.6__ __d."’__ 3 5'
53,3 3 (6) 3:(2:)3[(N-1)2:) + (s)(2:)2[(—_N-1)2'2]

. 2 2 _ 2
+42) 32-? [“2] d12+<£>§§~
d2

 

zo.
II
[DI-i

d
("'1’ (N-l)

 

(d-l) (d- 2) + N d (d-l) d-i 2
X;(Nji) 2:12 (N-2) (N- 3) 3 (N- d1)2 (N-l)(N-2) (N-2)2

 

 

62

Q The triadic case: n =3

The complexity of problems concerned with the probability
cflstributions of the random variables Rn1 and R'n1 .increases
many times for n greater than two. In section 1.3 (page 24)
we have seen that while there are three distinct two-point struc-
tures (one.each of types s3(or 5'2), 52(or 5'1) and 50(or}9¢0))
the number of distinct three-point structures is sixteen,and in
general there are several structures of each type in both the
connectivity and accessibility classifications. From appendix
A.1 (page125)we find that, in the connectivity classification
there are five structures of type 53, six structures of type 52 ,
two structures of type 51 , and three structures of type (so ";
in the accessibility classification there are five structures of
type 5'6 , four structures of type S'h , two structures of
type 5'3, three structures of type 5'2, and one structure each
of types 5'1 and s'O . Thus in general a subrelation on three
points may belong to a given state through more than one structure.
Consequently the computations of various probabilities of the type
Pr [;f('5l(a)) ”5121 and hence that of sums S‘m become much
nmre involved, even for the restricted case. In the unrestricted
case the formulas for sums 52} even for n = 2 are quite com-
plicated (section 2.2, page 57), and it hardly seems possible to
compute probability distributions of random variables Rn1 and
R'n1 for the general case.

In this section we obtain, for the restricted case, the
expected values of the variables R31 and R'3i , and the
variances of two of the empirically important variables R33 and

R30; the calculations of variances for other variables involve

63
no difficulties in principle. Throqghout this section we denote
by a, the subset. {P1, Pj’
set A ,.and by 79t(a) the threewpoint subrelation on the

Pk}:pcint5 Pi, Pj) Pk belonging to

subset aCA

Theorem 2.3.1 For the restricted case

Nd3(2N + 3d=111 _ N d3 (d2=d~l)

(1 5(2 = .
) 33) 6(N~2)2 (N-1)(N-2)2

 

N(Nalcgi .2 _ N(Nul-d) .
1 Tholjlmuié 2d 2
(N-1)(N-2)

 

.3 d2 (d-l)
2

' - 22 r» '2 i 4- \ - -
_ N(N 1 1) a (d 21 11 + N(N 1 d) .

(Nal)2 (N~2) 2 (N-1)2(N-2)2

 

d3(2d2-d-l

N(Nul-d)2(Nm2~d) g3 + N(N-l-d)?(N-2-d) .

 

 

(111) E(R33)

(N-1)(N-=2)2 2 (N-l)2 (N-2)
dfld-l)
2
N(N-l-d)2(Na2=dl . d212d-1)

 

 

(N-1)2(N°2)2 * 2

62
(iv) my) ... N(NgiifgéN-ja-di 1 N(%1?%:§N2)_L_ld 2 d
N(N-l-d)3(N-2-d) g3
(N41)2(N-2)2 ‘ 3

Proof. The probabilities Pr Y_H "R(a)) =- 511 are evidently the
same for every three-point subrelation 7Q (a), ICA, and the
number of ways of choosing three different points fnom a set of

N points is (g)’ Therefore
E(R ) = (N) P.- [Hwan = s 1
31 3 1

In the appendix A.l (pagelzs) we have shown all the three-
point structures in the different classes of the connectivity
classification. It is easily observed that a subrelation 'fikfia),
or equivalently the subdigraph P(a), is in state 53 if P(a)
consists of either at least a three-cycle, or a pair of two-
cycles with one point in common and exactly four directed lines;

it is in state s if P(a) consists of exactly two directed

1
lines both of which either start or terminate from a single
point; it is in state 50 if P(1) consists of at least one
isolated point; finally, it is in state 50 if it is in neither

of the states s3, 51’ or 50 . It follows that

(i) E(R33) is equal to the expected number of subrelations whose
corresponding digraphs have either, at least a three-cycle or a
pair of two-cycles with one point in common and exactly four
directed lines. However the expected number of three-point
digraphs consisting of least a three-cycle is equal to the ex-

pected number of threeacycles on a set of N points minus the

65

expected number of symmetric than-cycles on the same set (a
symmetric cycle on three points P1, Pj’ Pk is such that in

addition to the directed path P1 P:. P. JP:kPkP : it also has the

>'—P->-—P> )

directed path PiPkPkPj since a symmetric three-cycle

counts as two three- -cycles1 on the same set of points. Therefore

E(R33) = (Expected number of three-cycles on A -
Expected number of symmetric three-cycles on A)
+ (g) 3 Pr Dim, DARQ, k) Ann, 1M
wk, 1)/\ 192’”, k)/\“o1’(k, D]

fem i any of the three points may be the common point in the
second kind of term. The first term in the parenthesis can be
calculated from results on the expected number of cycles obtained
by Katz and Olkin [15]. They have shown that E(k-cycles)=[N(k)/k}°
{d/(Né1)}k and E(symmetric k-cycles) = [N(kl/ek} [d(2)/(N-l)(2)}k
Making use of these for k=3 and writing for the probability

in the second term we get,

E(R33) 3 NSN- '1} (_ __-__Nl )2 .,. N(N-12 { nggilg -2 12

2
d
+ (3) 3 (N-i) N-2 (N-l)2 (I'd— N-2 )

which reduces to result (1) of the theorem.

(111) 6(R31) = (g) Pr [H‘Rhm = 51]

= ('3‘) Fr rNa) consists of exactly two directed lines

either both starting from the same point or

 

both terminating at the same point

66

- (g) 3 ”Evan, mun, km sin, 1)A 15in, km
wk, 1M "63(de
+ Pr [‘63. (j, 1M '32(k,1)/\ fi(j,k)/\ fiw, J'M fiUJM

mm]

 

I N
(3) 3 M

vflxich reduces to result (iii) of the theorem.

(1v) 5(R3o) = (g) Pr E('R(a))= 50:!
= (N) Pr {T(a) consists of at least one isolated point.}

= (g) Pr {P(a) consists of one, two or three isolated
points.}
where an isolated point of F(a) by definition, is such that there
are no "lines" connecting it to any of the points of the subset

a . Therefore

N 2 d-l 2 d d
5(R30) g (3) jgi__7§ (l - -:§ ) (l-'fi:i~) ( l- “:5')
(N-l)
6 d d-l d 2 d 2

67

\uhich reduces to result (iv) of the theorem.

(11) Finally E(R32) is obtained by the difference E(R32) =

N
(3) - {E(R33) + E(R3l) + E(R3O)) .

Theorem 2.3.2 For the restricted case,

 

(1) E(R'36)

(N) d? ) 3 2(N-1)3 + 3 (N-l)2 (do3)
\ 2
3 [:N”l} :] -6(N-l)(d2-dr1) +(2d3'3d‘1)

(§> 3d2(NZlidl3 2<~«1>‘2>(d=1> + 2(N-2)2 d
[}N°1) ‘ :1 =3(N~l}d(2) - (N-2)(3d2-2d-i)
+d(2d2 =- d - 1)

(11) E(R'34)

= (N

3) 6d2(N«l-d)1 jN»2-d)(N-_1

(111) HR; BN_1)(2TJ 3

3)

 

t (2)
(iv) E(R 2) (N) 3fi(N“1“d% (Nal-dl 2(N-1)d + (N-e).
'3 3 [(N‘l) 2)J3 (d-l)-d(3d+l)

) 6d(N-l-d) [(N-l-d)(2):l 2

UN-l) (2)] 3

3
' g N N-l-d)(2X]
(v1) E(R30) (3) El

DN_1)(2)J 3

Proof From section 1.2.1 (page 2#) we know that a three-point

(N

(v) E(R' 3

31)

subrelation which is in state 53(5'6) must also be in state
' . E ' = E 1 '1 d
s 6 (53) Therefore (R 36) (R33) wh ch has been obta ne

in the previous theorem.

68

In the appendix A.l (page130)we have drawn three-point
structures in the different accessibility classes. Comparing
these with the three-point structures in connectivity classes we
find that a subrelation which is in state 52 is also in state
S'h or 5'3 ; a subrelation which is in state 51 or 50 is
also in state 5'2 or s'1 or s'O . Consequently

E(R'3u) + E(R'33) a E(R32)
and

E(R'32) + E(R'31) + E(R' 2(R31) + E<R3o)

30) a

Furthermore IR.(a) is in state 5'3 if r(a) consists of
either exactly one directed path of length two, or two directed
paths one of length one and the other of length two between the
same ordered pair of points.

Therefore

E(R'33) =- (g‘) "6Pr Dan, jmmj, k) /\ “fin, kMfiU. km

"fisk, 1)/\ 131k. 1).:]
+ 6Pr [11”,1M‘Wj. k)/\ 23;“, i)/\ '15;(k,j)/\'R(1. k)/\

fin. 1)] }

Writing down for various probabilities and simplifying we get
N 6 d2 N-l-d 2 N-2-d N-2
I a
E(R 3 (3).

BM) 2:13

Since E(R32) is already known (theorem 2.3.1, page 53) we obtain

3)

E(R'3n) by the difference
E(R32) - E(R'33)

69
Next, we find that 7Q.(a) is in state s'1 if F(a) consists of

exactly one directed line, and in state s'O if P(a) consists

of all the isolated points. Thus
E(R'31) = (g) 6 Pr [ML JM fin. k) A flu, 1) A

ix}. km wk, 1)/\ fitk, 1)]

and

E(R'3o) = (g) Pi 292(1, 1M an. m an, km
151k. 1M 1510, k)/\ Wk, 1)]

which reduce to results (v) and (vi) of the theorem. Finally
E(R31) and E(R3O) are known (theorem 2.3.1, page63) and therefore
E(R'32) is obtained by the difference
.- '. I

E(R31) + E(R3O) E(R'31) E(R 30)
This completes the proof of the theorem.

The derivation of the variances V(R3i) or V(R'31) is much
more involved. From the relation 2.1.3 we have

' 2

V(R3i) y 2521 + 511 - 511
Since 511 - E(R31) have already been calculated earlier in this
section, we only need to compute the sums

521 = z: Pr [{f(‘6l(a1))=- 51] /\{f(‘R(a2))' = 51)]
where the summation runs over all the distinct pairs of subsets
al, 82 contained in the set A . A subrelation 7R“) may be
found in state 51 through many different structures of type
51 . Let there be I structures 511, $12, ..., siI of type
51 so that Rh) belongs to state 51 through one (and only

one) of the substates sip, p = l, 2, ..., I . Then

7o
Pr [mmaln .. $11 A mung) ... 51]]

- P f = p} f a
pal rL{(‘Q(a1)) s m (R(a2)) siq

I
- p51 pr [m Ruin =51p14tf(n(a2)) a siplj

N
+92; ”Bunny ) = s pm mam,» = sip]

Let $21 denote the sum

2 Pr [m may) --- sipmm ma,» =. siqij

ara2
It is easily seen that the Expression for S21 reduces to

+ 2 E (R
1
{Fl 2 :9 p<q=1

To calculate S21p and E(R31p R31q)

S = Z S

R )
21 31p 31q

we notice that there are

(2)13T3géT different pairs of triads a1 a (P1, Pj’ Pk},

' {P ‘3) 5%?"

.k’ P

P") having no points in common;

32 m:

different pairs of triads , P P }

.31 ={Pi ’Pj’ Pk}: .3 = [P1 g: m
with one point in common; (3 %—-1 different pairs of triads

)
= (P1, Pj’ P k]’ an - (P1, P l with two points in common.

a1
Therefore

s21p " (2) 31%;? P" E“ R‘fi” " siplAtflm‘ew " 51:]

T
J");

71

(g) 5%,- Fr [m 152(5)) = sipm m map) = 51:3]

Pr DHR‘MH .. sipmm Rh,» =’ 51;]

+

+(2) 32-:-

and
E(RsipR31q) = (2) 37%;,- Pr Dflmaln = sip}/\ In 120.2»
= 51 I j
q

Mg) 51.2457 prEf(R(1]-)) - 51PMWW‘3) =- 5%)]

+ (E) 55-:- Pr[[f(R(al)) I! sip1/\(f( 71(3)”) 3 51:]

We also note that since the triads a1 and 32 are disjoint

p.- [m may) - sip}/\[f('fl(12)) =- siplj

3%r [H Rh” = Sigge

and
Pr {f('@~( ))=s )Atf-(Rh ))=s }
C 3‘1 1p f _ 2 .1q]

... Fri“ 72th = 51;) Pr[f(p‘(‘2)) = 51;]

Thus 2
N 6!
521') '3 (6) 3:332! (Pr E( &(a)) 3 Sip-J }

+ (g) 5%;— Pr Dunn,» = sipmm ma,»

=51}:]
p

 

 

 

72

I]

+ (1')) g—. Pr [mmuln = sip} Amnuw = 51’)

‘md

E(R31PR3iq) = (g) 37%;,- PrLH‘GUaH == 51;) Pr Dram)

=51]

q

+ (g) g—g—Q— Pr [m 12(al))= sip1/\{f(ZR(i3)) = sin]

4! a
+ (5) 5,- Fr [m R(a1)) = sipmmma,» = siqf]
We give here explicitly the variances of the random variables,
R33 and R30 .

Theorem 2.3.3 For the restricted case

"(6) d6 “(N-l-d)6 + 45(N-1-d)4(d-1)2 +-~-—1

‘1) v(R33) ’ 36((N-l)(2)}6 2(N-1-d)3 (d-1)3

+ 90(N-1-d)2 (d-1)” + h8(N-1-d)-
(d-l)5 + (d-l)6 )

v

+ N(5)d5_d-1 F’4(N-l-d)5(N-2-d) + 2(N-1-dyi
4((N-1)(2§}5 (N-3)(2)

 

{N(69d2 - 193d + 138) +

2(17d3 - uad2 - 3d + 18))

+ 6(N-1-d)2(N-2-d)(d-l)2
+(N-l-d) (d-1)2 (N(45d2 - 169d

+ (d-1)“ (d-2) (d-3)

‘—

 

\.

{3N(3d-4) - (9d2-d-4)) + (N-1-d)§

+162) - (37d3 - Bod2 - 79d + 198))

.1

 

a

+ N(4)du(d£;)
{(N-l)(2)} (14.3)2

 

36((N-1)Té7)“

73

[—(N-lad)4(No2ad) + 2(N-1-d)§ -]
{3N(4d~5)-(13d2+2d~23)}
+4(N=1-d)3(d=1){N(16d-25)~—
(8d2 - 3d - 15)} + 2(N-l-d)
(d-1)(2) [3N(3d=4) - (5d2 +
L.2d ; 12)}4- (d-l)3 (d-2)2 _J

 

 

Tfl6(N«-—»1)1‘(N---2)2(2))+3d«--11)-- ‘—7
36(N-l)3(N-2)2(d2~d-1) +5{(N-1)(2)}2,
(2d3u3dml)-N(N=l)u(2N + 3d -1)2 d3
+12N(N=1)3 (2N + 3d - 11) d3.

(d2 - d - 1) ‘
-2N(N-1)2 {2N(2d3 - 3d - 1) + )
18d“ - 3Od3 - u9d2 + 66d + 291d3

 

1

 

 

(11) V(R3O) = —§g—

(5) 5 4 -—1
+ ,(N-l-d) f (N-e-d) (N-2-d) (N~3-d)(N-u-d)
' {xN-l) 2)} (N-3) 2) )— A

N(6) (N-1-d)(2)36 (N-e-d)4 + 6(N-2-d)3d _)
(N-l)(2)

 

+12N(N-1) d3 (2d3-3d-1)(d2-d-l)
)_:Nd3(2d3-3d-1) -—J

+ 39(N-2-d)2 d2 + (N-2-d).
d3 + 9dLl

 

.1

+2(N-2-d)3(N-3-d)(3N-3d-1o)d

+(N-2-d)2{§2(39d-4)_
-2n(22d2 + 49d-8)
+(39d3 + 225d2
+324d-4) } d )

 

 

+ N(“) N-l-d 3 N-2-d )
”‘ "TED‘%'1"“51
{(N-l) ) (N-3)

¥ N(N-l-d)3(N-2-d
I
36(5N-1)(2)}

74

+2(N-2-d) §_N2(9d-2)-N(18d2
+43d - 8) + (9d3 .
+ 45d2.+ sud-8)} d2

 

 

 

L_-4N(N-l-d)3 (N-2-d) d4

+ {N3(9d-4)-N(18d2 + 35d-l6)
+(9d3 + 39d2 + 36d
-16)} d3

(N-l-d) (N-2-d)3 (N-3-d)2 _—)
+(N-2-d)2 {9N2 - N (18d + 43)
-(d2+5d-22)}dg
+2(N-l-d)(N-2-d)2(N-3-d)d2
+2(N-1-d)(N-2-d) {N(ud-l)-
(4d2 + 10d - 3))d2 ‘ '

+ (N-l-d) {N(2d-1) —- (2d2 + 11d

 

-3)) d3 ...

r“ 6(N-1)2(N-2)“ + 24(N-1)2(N-2)3 -)

d-{l2(N-l)(2)]2 d2

-N(N-2)4 (N-l-d)3(N-2-d)
-8N(N-2)3(N-1-d)3(N-2-d)d
-12N(N-2)2(N-l-d)3(N-2-d) d2
+16N(N-2)(N-1-d)3(N-2-d) d3

 

 

..J

 

Id.-

 

 

 

 

75

an The guartic case: n = 4

In this section we briefly describe the case n = 4 and
mesent the expected values of the random variables R41 and
”hi for the restricted case. The derivations of variances
flfllow the same principle as described in the previous section
hm the computations getcuéte involved and the expressions be-
ame algebraically complicated. We have seen in section 1.2
Uhge115) that there are 218 different four-point structures;
flmse are shown in the appendix A.1 (Pagelzd) from which we
dnain the following table.

Tflfle 2.4.1 Showing the number of four-point structures of types

!
s1 and s 1

 

 

 

TYPe of structure Number of Type of structure 'Number of
h1connectivity structures in accessibility structures
.Efiéélflggtion classification 8

$3 83 5'12 83

52 88 5'9 49

s1 28 5'8 9

s0 19 5'7 21

5'6 22

5'5 11

5'4 11

5'3 6

5'2 h

S'l l

__7 5'0 1

Total 218 Total 218

 

 

 

76

Direct computations on the same lines as in the previous

section, give the following res‘ults.

. Theorem 2.4.1 PEN the restricted case

 

 

 

 

u
' 3 N d
u) E(Ru3) - (4) [(N-l) 3 )

__
(_8(N-3)n[2(N-2)4-(d-1)n} +

Md-l)(N-1-d)3(N-2-d)2(6N2 + 2N(lld-31)
+(5d2 - 81d +1)2))

+ 12(d-1)2 (N-l-d)2(N-2-d) [9N2(d-1) I
+2N (15d2 - 39d + 5) + (d3 + 33d2 - 7d
-45)}

__+ 18(N-1-d)”(d-1)4 )

 

 

 

 

 

 

(2) 2 a
1 2d{(N-1-d) ~,)
“1) E(Rul) ' (2) {(N-l)(3)) i ‘ i ’

r—u(N-1-d)(3) (2N2(13d2 - 9d + 1) - 2N(26d3
~30d2 + 37d + 6) + 2(13dlIL + 39d3 4 d2
-30d + 9) 1
+6d(N-1-d)(N-3-d) {N2 (33d2 - 50d + 19)
-2N(31d3 + an2 - 81d
+ 23) +(31d4 + 68d3
- 68d2 - lhOd + 129))
+211d3 {(N-l-d)(2)]2
+l2d(2)(N-l-d) {3N2(3d2 - 5d+2) - 2N(7d3
+ 6d2 - 21d + 6) +3(3d”
+9d3 - 9d2 - 25d + 18)}
+ 6d(d-1)2 {2N2(d2 - 2d + 2) - 4N<d3 - 4d + 6)
' +2(d" + 2d3 - 5d2 - 6d + 18)

 

 

L__

 

 

 

 

 

77

. N 1 (N-1-d)” (N-2-d)
(111) E(R4O) =- (4) [W
F~2(N-2)(N-2-d)3(N-3-d)u
+2(N-3)2(N-3-d) {2N3d‘w 9N2d(2d + 9)
+3Nd(19d2 + 12d +60)
-3d(d3 + 9d2 + 26d 244)}
+3d2(N-2-d)3 {4N2 - 4N(d+6) + (d2 + 12d + 36))
L_ ‘ _.
(The expected value of R42 is obtained by the difference
(2) - {E(Ru3) + E(R“) + E(R40))

 

 

Theorem 2.4.2 For. the restricted case,

E(R'4,12) :2 E(Ru3) (theorem 2.4.1, (1))

3
E(R' a (N 4 d fl'l'd)
”9) u) {(N-1)137)”

F'6(N-l-d)3 (N-2-d)3{N(2d-1) - (d2 + 6d + 3))
+3(d-1)(N-1-d)2(N-2-d)2 (4N2(5d?3) -2N(2Od2'
+24d - 27)+ 2(10d3
+ 30d2 + 5d - 18))
+(d-l)(N-l-d)2(N-2-d) [N2(9,d2 - 173d + 77)
-2N(51d3 - 15d2
-224d + 184)
4494.)"l + l43d3 - 456d2
- 302d + 411)}

 

 

 

 

 

 

 

E(R'

N

78

+3(d-1)2 (N-l-d) (N-2-d) {N2(20d2 - 57d + no)
-2N(23d3 - 20d2 - 89d
+ 92) + (17d; + 17d3
-119d2 - 35d + 192))

+3(d-1)3 (N-l-d) { N2 (4d2 - 13d + 12)
-N(8d3 - 11d2 - 36d + 60)
+(4d” + 4d3 ~ 31d2 - 13d
+ 72) 1

+(d-1)3(d-2) { N2(2d2 - 3d + 4) - "(4d3

+ d2 - 4d + 20 + (2d‘l

+2d3 - 11d2 - 5d + 24) )

 

. ...———

a) 6d3(d- 1).1N- 1- 3-d): (N-2- -d)2

{(N- 1)3

2(N-1-d)2 {N(Sd - 3) - (d2 - 14d + 3))
+ d(d-2) (N-l-d) (N+3d - 6) + d(d-1)(d-2)2

12d3 N-l-d 2 N-2-d)

((N-l) 3 )

(22(N-1-d)2 (N-2-d)2 { N(3d-2) - 3(d2 +2d-2)) ~]
+(d-1) (N-1-d) (N-2-d) {N2(17d - 15)

-2N(17d2 + 18d - 32) + (17d3 + 51d2 - 7d

-45))

+ (d-1)2 (N-l-d) {N2(9d-l4) - N(18d2 + 13d

-68) + 3(3d3 + 9d2 - 4d - in» )

+(d-1)2 {3N2(d2 - 3d + 2) - N(6d3 + 5d2

-12d + 2) + (d-2)(d+1) (3d2 + 5d -‘9) 1

L— , .1

 

 

 

 

 

79

 

, N 2d2 n.1-d)2 (N-2-d
“R446) ' (4) '—-?%;:;3737} 4 1

F-2d(N-l-d)(N-2-d)(N-3-d) (8n3 +«3N2 (2d2 + 15d -1)
-N(12d3 - 31d2 - 55d -

94) + (6d2 + 32d3
-137d2 + 50d - 95))

—

 

+l2d (N-l-d)2 (N-2-d)3
+2(d-l) (N-l-d) (N-3-d) [5N2(6d2 - 7d + 2)
=6N(22d3 - 7d2 -
35d - 1o) +2(17d”
+87d3 - 126d2 - 54d
+ 36)]
+(d-1)2(N-3-d) {N2(17d2 - 32d +12)
-N(67d3 + 72d2 + 16d)
+2d(19d3 - 11d2 - 25d - 25))

L_46d4(d-1)2(N-1-d)2(N-2-d) ___)

E)“, ) a (N) l2d2(N-l-d23§N-2-d)2 (N-3-d)
“5 u {(N-l) 3 ) -
N3(2d-1) - 2N2(3d2 + 4d - 3) +N(11d3 + 6d2
+ 11d - 11) -(6dh + 5d3 - d2 + 13d - 6)

2 3 2
E(R' ) .. (N W122) (N-3-d)
44 ' 4) {(N-l) 3,)

l6N3(2d—l) - N2(6ld2 + 192d - 126)_W
42M (21d3 - 213d2 - 130d + 156)
+(l9du + 43d3 ~ 597d2 + 36d + 234)

 

 

 

 

 

 

 

.1

 

 

 

8O

nd(N-1-d13 (N-2-d)3 (N-3tgl

HN-Dm) fl
F6N3d - N2 (d2 + 51d - 2) - 2N(8d3 + 18d2
+ 65d - 6)

L: (11d4 + 15d3 - 41d2 - 105d + 18)

HR'n3) = (E)

 

 

—

 

, N 6d2 N-l-d 4 N-2-d 3 (N-3-d)2 _ 2
“242) = (4) ( ((1)-(#2012 ) [SNd (5d + 8d + 28

Euv ) = (N) 11221!;1;21;_1N&2;g)u ("-3-213
41 _4 ‘ ((N-l) 3 )

((N-l-d)(3))”
[(N_1)(3)]u

 

mum) = (If) '

81

2:5 The general case: n 3_2

 

So far we have obtained the probabilities Pr I:f(‘52(l))

= $1] , Pr [H Rh” a 5'1] , and sums Sm , for ngll by
the direct method. This method consists of enumerating all the
n-point structures, classifying them into various connectivity
and accessibility classes, and then directly evaluating the prob-
abilities Pr [HEARD == 51:] , Pr EH “Run ... 5'1] and
the sums Sm . For values of n greater than 4 the number of
different n-point structures is very large; for example for n a 5,
there are 8508 different fiveapoint structures. Consequently
use of the direct method does not seem to be practical for n > h .
We need a general method which, firstly does not involve direct
enumeration and classification of structures, and secondly de-
pends possibly only on the definitions of states 51 and s'i .
An attempt in this direction has not been successful and it hardly
seems possible to find such a general method.

The main difficulty in findingageneral method seems to
be caused by the redundant complex directed chains in the sub-
digraphs P(a) . Consider, for example, the probability that a

Subrelation Ffikla) is in state 5 ; by definition ‘VQ.(a)

3

will be in state 5 if there is a directed path between each

3
ordered pair (P1, Pj) of points P1, Pj belonging to subset

a . Each of these directed paths may be of any length L ,
1 5_L.5 n - 1 , and a directed path of length L from Pi. to

P. may pass through any of the Lol points Pi , P1 , ...,
J 1 -2

P1 belonging to subset a . Such a directed path also
L-1 ‘
contains many other directed paths of lengths l, 2, ...,

Lél from point P1k to point ka, k #,L_= 1, 2, ..., L - l .

82

Furthermore point Pj may be accessible from point P1 in many
different ways, that is there may be more than one directed path
from P1 to Pj . Thus to find the probability that every
ordered pair (P1, Pj) contains a directed path in P(a) we need
to enumerate all the possible cases, remove redundancies and
calculate the probability for each of the case. This results in
enumerating all the n-point structures of type s3 ,which amounts
to using the direct method.

Another way of obtaining the probability Pr [H "Rh”
== s3:] would be to derive a recurrent relation for these

probabilities. Let denote the probability Pr EH 19(3))

P3,"
= 53:] where a = { P1, P2, ..., Pn} consists of n distinct
points, and let s3q , q = l, 2, ..., Q denote all the n-point
structures of type 53 . The relation R (a) may be found in
state 53 through only one of the structures S3q ; the rest
of the n-point structures are not of type 53 , and 1R.(a), if

not in state 53, must have one of these structures. We may

write the probability p3 as
~ 9

n + l

p3m+1= Pr E(Rhwnfln ... s3 1 f mm) = 53]
+ Pr B may?" + 1)) m3 | f(lR(a_)) + 53 1

To find the first term on the right hand side we need to find
all those cases in which addition of point Pn +1 to one of

the structures $3q produces a (n + l)-point structure of

type 53 3 to find the second term we need to find all those
cases in which addition of point Pn+1 to a n-point structure,
which is not of type 53 , produces a (n + l)-point structure of
type 53 , Evidently this requires the knowledge of the compo-

sition of various n-point structures.

83
Similar difficulties are encountered in trying to evaluate
other probabilities Pr EFVRHH a 51] and Pr EHRHH =
5'1] by a general method.
In the next section however we propose an approximation for
the probabilities Pr , LN R(a)) = $1] for the restricted
case, and obtain the approximate probability distributions of

random variables Rn1 , n‘Z 2.

84
2:6 Approximate prohibility distributions of random variables

Rni

In this section we propose a method for obtaining probability

distributions of the random variables Rn1 for the restricted

case, under the assumption that N (the number of points in the

set A ) is large compared to d(the valency of points belonging
to the set A) . The probability that a point P1 holds rela-
tion .52 toa point Pj (both Pi and Pj belonging to the
set A ) is d/(N-l) , and the probability that P1 does not
hold relation ‘61 to Pj is l- d/(N-l); for N > > d the first
probability, namely, Pr-[fil(i, ji] is quite small compared to
the second probability, namely, Pr‘lfii(i, ji]. In terms of graphic
representation this means that the probability of having a

directed line from P to Pj is much smaller than the probability

1
of not having a directed line from P1 to Pj . Therefore the
probability that a subrelation ~51h.) has a certain structure will
be small if the number of directed lines in the corresponding
subdigraph E(a) is large, and it will be large if the number of
directed lines in P(a) is small.

Throughout this section the number of points in the subset

a is taken to be n , that is, a = {P11, P1 , ..., P1 1 ,
2 n

and n-point structures are simply referred to as structures.

In general, Pr {HR (l)) = 51 is the probability
that UR.(a) is in state 51 through any of the severaldiffer-
ent structures of type 51 (section 2.3, page 69). Hewever
if N > > d, we may approximate Pr [HR (a)) a- Si] by the
probability that N(a) is in state 51 through only

those structures of type 51 which contain minimum

85

number of directed lines. It follows from the definitions of
states 51 (section 1.2, page 18) that(i) a structure of type
53 must have a minimum of n directed lines, and the only
structure of type 53 of this kind is a n-cycle (ii) a structure
of type 52 must have a minimum of n-l directed lines, and the
only structure of type 52 of this kind is a (n-l)-step chain of
directed lines (111) a structure of type 50 may not have any
directed lines, or may have only one directed line (except for
n a 2 when such a structure is of type 52) .

The probabilities Pr Lf(‘R(a)) = 511 may, therefore,
be. approximated by Fr [f(R(a)) =31] where

(1) '75,. E(‘RHH - 53 = Pr Na) consists of n directed
3
lines arranged as necyele
.2]

5%] = Pr

Pr

Pr T(a0 consists of n-l directed

(n) "r.- E(RHH

lines arranged as (n-l)-step

[—a

chain

P(a) does not consist of any

(mm [H a (a))
.iifl=2
directed lines -

P(a) consists of O or 1
b‘N>2
directed lines

(iv) swam): .3:- 1-2 in Luann) = s1]-

i=0,2,3

r‘—’Tr—"‘1

Both for the restricted and the unrestricted case, these
approximate probabilities can be easily calculated. In what follows,

(9) (Section 2.1, pageifi9) is used.

the factorial notation x,
(i) A n-cycle may follow any of the n! different paths among the

n points of the subset arand the same cycle may start from any of

86

i
the n points. Therefore there are 34

n different ways of

obtaining a n-cycle on n points, and we have

[H12(a))=s3] — w: «a» of ,.

directed lines arranged as

n-cycle starting from point

 

 

P1 . l
1 n ‘_H
= (N-l)! Pr‘i mull) 12)/}Eifi(il,j)}l\
1
7‘12’13
1
| n
{79412, i3)/\jl__]ifi(12.j)l /\
t 1
7112,13
in-l
{'R(i.1)H ”(i,j)l
n l ._ n
1 ( J—i2 ...—L
n
where 'Hi ‘6'):(1, j) denotes the event 881, il)/\ 153(1, 12)/\
J— 1 i
n
/\7R(i, in) . The events uuk, 1"“)AJ‘E1 fink, j) ,
l
fik’ 1k+1

, are independent of each other, so

k=1’ 2’ 0.0, n; 1n+l=1l n
= (n-l)? I] Pr[32&ik, ik+l)/\

that 'Fr E(Rbn = 53:]

 

k=1
n
H “’ (1 . j)
j=11 k
%ik’ iI<+1
" d d -1 d -1 d -1
= (N-l)! 1k (l - 1k )(1- it )... ('1- 1k )
kI-Jl 7—in-1 “""N-e N-3 N-n+l
n d (N-l-d ) (N-‘rT-‘2 - d )
= (n-l)‘ H 1k 1k 1k

 

 

' k=l T‘TN-i 01-2) (N_ “—5)

87

or, for the unrestricted case

— R (n'l) : ‘ n (n-2) .
and, for the restricted case d11 = dizxa ... = din a d
-' (n-l)! (n-2)n
P f =3 - {d N’l'd 000 .6.
r [(man 53 'W"'1) ( > J (2 2)

(ii) A (n-l)-step chain of directed lines may start from any of
the n points of the subset a_ , and may follow any of the (n-l)!
different paths among the remaining n-l points. Therefore there
are n(n-l)! i- 334 different ways of obtaining a (n-1)-step chain
on n points, and we have

Fr L“ R (a) = $2] = n! Pr _I‘(a) consists of (n-l) - step ' 1

chain of n directed lines from'

 

point P1 to point P1 through
1 n

 

points P1 , P1 , ..., P1

 

 

in 2 3 i n-l _.t
=- n! Prfi‘RMl, 12)/\H “£111, D} /\ (RU-2:13) H" fi(12.1)1;l
j=13 jflil
"12'13
in-2
Anna“, in) /\ fl Uiu‘n-l’ j) 1

jail ...-a

"'1 d d 1 d1 - 1 d1 -1

=2 1k (1- 1- (1- ..
"-4.111 fi-‘i 1%) T73— m

 

 

 

 

88

p i
As before, the events Rflk, 1H1) /\ Tr flik: J) :
a, 1

ka 1, 2, ..., n-l are independent of each other. Therefore, for

k+l

the unrestricted case,

 

n! "'1
'9} mm )) a =- _ ( -1) d (N-l-d )‘n'2)
L “ 52:) (N 1) " 31 1k 1k (2.5.3)

and, for the restricted case d =- d = s d ... d
11 12 in

 

_ 2 -l
P.- [H mm) ... 52] .. (N_:)(n-l) {d(N-1-d)("'2)} n ..., (2.6.4)

(iii) For n - 2,

Fr anan=soj = Pr Lama» =50]

which we have already obtained in section 2.2 (page 52).

For n > 2,

Pr [H Rh” rat-50:] a Pr {All the points in I‘(a) are isolated]
+ Pr [Haj consists of only one dinected

line from any point PL to any

other point P1 3
k

n

=- Pr H flu], ik)
57“;

n , n
P (R(i., i i , i l
+ J§k=1 r[ J k) A4111 fi‘ 1 ) A

n {k

(3 fin . 1 )1]
i=1-p

p70

 

 

n
The events kg fiuj, ik) , j =- 1, 2, n , ahd the events
K71
. n ‘
. i "’ . "’ i a
R (1J1 k>AfiE1R(j—J’ 1L) : L131 1 n‘ip) L) 9 P 1:
.Lrlk .# p

2, ..., n are independent of each other, so that for the unrestric-

ted case,
FERRH) fi< d1 )( d1 ) (1 d1 )
= = l - l - " ... - I
r a 5%] j:1 N71 NT? Ntfigl
d d d
i. -i. - 1 i. - 1
(1 - (1-
+ g (N71) -N{§-__ ) N-n+1
1”“1 d d d
fit (1 -._i& ) (1 - ht ) ( 1-‘ it. )
i=1 -1 N-2 Wu

 

 

 

£=
Jlfh
and for the restricted case d = d1 = = d1 = d
1 2 n
- = - {(N-l-dl(2:1)}" n(n-1) .
prfiymm 5;] .. ("mm-1V + “MM-1))"

-1
d(N-1-d)("'2) {(N-i-d)("'1)}n
. (2.6.6)

 

 

90
(iv) Both, in the unrestricted and the restricted cases, the

probability T5.- LH 61m) = 51:] is obtained by the difference

t.- [HRQH =2 s1] "’ 1 ‘ ’3 P" E“ “‘3” "’ 5'1]

1 :3 0,2,3

-Using the above approximate probabilities .f-r [H R (a)) = $1]
and assuming that N is very large and n is small, we obtain
approximations for the probability distributions of Rni ,

n‘z 2; i = 3, 2, l, O, for the restricted case. This is done
by investigating the forms of the approximate values of the
probabilities P(m), 1 == Pr [Rni = m] which can be expressed
in terms of the sums Sk,i by means of the relation 2.1.1
(page #7).

Theorem g:§.1. For large N, and d << N, we have

1 m
(i) Pr [Rn3= 1 ~ E! 93 exp (~93) ,

 

_ dn dal n(n=2)
where 93 — -fi (1 - N'flil
2
(ii) P.- [Rn2 = m] ~ $3 eg exp (-92) ,
(n-l)(n-2)
n-l d-l
where 92 = d (N-l-d) (l --fi:-E;T ) .
2
d n’2
( 1 ' N- n+1 )
2

l m -
(iii) Pr [Rno = m] m m! 90 exp ( GO) ,

91 .
n-l

 

 

- d n(n-l) n n-l d-l
where 90=(1-'fi:-fl-) + N-l d(1-TN_!L+A ).
2 2
. d (n-1)2
(1 ' N-

2.
.2

9? exp (-90)

(iv) Pr [RmIj = m] ~ :13!

N
where 91 a (n) - (93 + 92 + 90)

ELQQE (m) tThetfirst termhinwthe sum .5k 3 can be approxi-
. ,

mately written as,

k!
(:k) (“:31 k! {Fr ‘3“ Rh” 3 53.] )k

S a)! _ k
N: (n!)Ek! {(N-l‘) "1 Elm-I'd)” 2)] n} .

N-nk 3

 

using expression (2.6.2) for the probability fr [1% ~@\(a,)) =- 53] .

This may be rewritten as

 

dn "-1 n k
N! 2" {T__-——_fi II (1 - .ézl ) :}
‘(_"7"N-nk : k! n(N-1) N-p
p=2
N 1 L d-l n(n-2)} k
N (N-nk)! 'k! §n(N-1)" (l - N'.flil ) , replacing p
2 .

by the arithmetic mean of its extreme values.

 

N(nk)- l [ dn (1 - d-l n(n-2) } k
k!) '_fi .N- n+1
2

=m <

92

For large N we may approximate this by

n(n-2) k
1 d" d-l
'k! {;'_F ( 1 ' N- at; ) .}
. 2

The other terms in Sk 3 are, at most, of order 0 (%) , and
, _ .

the number of these terms depends only on It , not on N .

Thus for fixed k. and d , sum of these terms tends to zero

for increasing N , and we may approximate Sk 3 by its first
, .

term:
1 d'l "(n‘2) k
Sk,3 ~ Ti: [(12) (1 " “N__ 3.3—1) j

With this approximate value for 5k 3 we obtain
3

(:1)
i i 1
P(m),3 a Pr fin3 a m] N .130 ('1) (m3) ("H-1)! '
( -2 + i
”—n)‘1'N-—difi'i)nn) m
‘5'

 

 

2
dn d'l "(n-2)
Let 93 = -—; (1 - N-.n:l ) . Then
2
N
(n) i

, 9m exp (-9 ,for large N

3)

‘Ere

 

93

which is the general term of a Poisson distribution with parameter
93 . ‘ 2

We note that for n = 2 , the parameter 93 = -g§ , and our
result agrees with that of Katz [18] who proposed a PoiSson
distribution with parameter .23 as an approximation for the
distribution of the number of iutuals (which is the random
variable R23 in our notations) . I
(ii), (iii) The next two results for Rn2 and Rno are
obtained in a similar manner. We easily find that the first

term of the sum 51' can be approximated by

,2

n-2' k
%! [dn'l (N-l-d) (1 ' filiz'rlfi‘i )(n-l)(n-2) (1 ' N-dmtl.) J ’
2

2
and the sum of the other terms of Sk 2 tends to zero for in-
)

creasing N . Therefore we approximate the probability

Pm), 2:. Pr [Rn2 = mbe

i
i m+l 1 "H
130 "1>-(m)Tm—+1')fr 92
__ n-l d-l (n-l)(n-2) __g_ "'2
where 92 - d (N-l-d) (l - N- n+1) . (l - N, n+1 )

2 ' ' 2
For large N , therefore

1 m
Pr [Rn2 =m:]~ m! 92 exp (-92) ,

which is the general term of a Poisson distribution with para-

meter 92 .

9#

Similarly after some reductions we find

 

 

- Nnk 1 k
Sk,o ” Tn:)k ‘ET 90
d n(n-l) n(n-l d-l "-1
Where 90 =3 (1 " N“ 2) + N-l d( 1 ”N- n+1 ) .
2 2
2
d (n’l)
( 1- N= n)
'2
and for large N the probability P(m) O = Pr {:RnO := In:]
, .
is approximated by
1 m

-&3 90 exp (Dee)

which is the general term of a Poisson distribution with parameter

90 .

(1v) Finally, the sum of the random variables Rn3’ Rn2’ Rn1
and Rno is a constant (2) , and the approximate probability.

n3’ Rn2 and Rn0

93, 92 and 90 respectively. Therefore it follows that the

distributions of R are Poisson with parameters
probability distribution of Rn1 is also approximately Poisson

with parameter (2) - (93 + e + 90) a 9 . We find that

 

 

2 1
- N dn°1 d‘l (n‘1)(n-2)
91- W"? ‘1' m) ‘
2
dnl n-2 d n-2
Efl " N' m) + 0(N°l'd) (1 "—"——N_ 14;]; ) J
2 2
2
n (n=l) n-l
d d n n-l d
a. E. ( 1‘ N“ D.) [31 ' N-.fl) +IT%:T71
° 2 2 1
"-
(1--%:l—- )

n+1
—§—.

95

Below we make some computational checks of the exact values

of E(Rni) against the values obtained from the Poisson approx-

mations, for N = 25, d = 3, and N = 2, 3 .

 

A—l_:#—

Table 2.6.1 Comparing the exact values of E(Rni) with the

Poisson approximations.

 

E(Rn3) E(Rn2) E(Rnl) E(Rno)

 

n
2
3

Exact Poisson Exact Poisson Exact Poisson Exact Poisson
5 5 65 63 - 4 230 232
10 8 186 14h 112 306 1992 A 1843

 

96

2.7: A simple approximation for expected values of the random

 

T
variables Rn1 and R n1

 

In this section we present an approximation for E(Rni)
and E(R'ni) , which is mainly of interest in applications.
The exact values of E(Rni) and E(R'ni) given in sections
2.2, 2.3 and 2.4 (for n 5 2, 3, and 4 respectively) have '
rather involved expressions, and are competationally difficult
to obtain. Consequently simple approximations for E(Rni) .
and E(R'n 1) would be convenient.' The'naturai-Way seemsrto be
to investigate the limiting values of E(Rn i.) and E(R' ni) as
N5 tends to infinity.

By letting N -—> oo in the expressions for E(Rei)’

E(R31) and E(R' given in the theorems 2.2.1, 2.3.1 and 2.3.2,

31))
we f1 nd that

E(R ) __>‘§3 E(R )-—> dO(N) E(R 0(N2)
23 2 ’ 22 ’ ’

__..l
20) >2

’ 2 2 1
, E(R32)—> d 0(N). E(R31) -- d - -2-d MN).

3
_ .9.
E(R33) > 3

E(RBO) —> @0013) ; and
3 .
a __ 51. s 2
E(R 36) > 3 , E(R 32+) == 2d3, E(R 33) = d 0(N),
E(R'32) —> g 62 0(N), E(R'31) —> ‘d 0(N2), E(R'Bo) ——>% 0013) .

Therefore all the ratios E(Rn1)/(n N), i f’o , and
E(R'n1)/(N) ), i {'0 tend to zero as N -—> oo . Such an

approximation is, therefore, of no practical use. However, we

observe that if d be a linear function of N then all the

97

expected values are of order of magnitude 0(Nn) . Hence the
ratios. E(Rni)/(:) and E(R'ni)/(:) tend to non-zero constants
as N ——> oo . We take d to be a simple linear function of

N , that is, d = 9(N-1) , O < 9‘s 1 . The number 9 = d/(N-l)
is the ratio of the number of outgoing directed‘lines from a point
of set A to the total number of points on which these directed
lines may terminate. Thus d is meaningful and may be called

as the *rate of valency' in set A .

The exact values of E(Rni) and E(R' for the re-

m.)
stricted case are given in theorem 2.2.1 for n = 2 (Page
51 ), in theorems 2.3.1 and 2.3.2 for n= 3 (Page63 and'
67 ) , and in theorems 24.1 and 2.4.2 for n= 4 (Page 76
.and'TY). Let the limiting values of the ratios* E(Rhi)/(fl) y
2nd E(R'ni)/(fl) as N-—+> a) be denoted by E (Rnii and
E(R'n ) respeCtively;Writing d = 9(N-l) and taking the limits
as N -> oo , we obtain:
for n == 2,
E (R23) = 92 , E (R22) = 29(1-9) , E (R20) = 1 - 29 + 92
for n= 3,
E (R33)=- e3 (2 + 39 - 3 92 + 293), E (R32) = 692(1-e)-
(1-292 + 93)
E (R31) = 692 (1 - e)4 , E (R30) = (1 - 9)4 (1 + #9 - 292) 3

E(R'36) = E (R33), E (R'34) = 692 (1 - e)(2e - 392 + 93).

E(

' 2_3. 1:2-“
R 33) 6e (1 9) , E (R 32) 99 (1 e) .

. - 5 ' . a - 6
E(R 31) 6e (1 e) , E(R 3O) (1 e)

A1;

i
b

98

fOr n = 4 ,
E(R43) = 94 (6 + 369 - 10492 + 21193 + 1779il - 25295 + 15696
-4897 + 698 ),
E(Ru2) = 293 (12-141192 + 29693 - 11494 - 30395 + 116896 - 291197
+ 9098 - 1199 ),
E(Rui) = 93 (104 - 7269 + 217292 - 369093 + 351094 - 200495
+51696 + 11897 - 6098 + 1099),

E(Rho) = 1 - 12893 + 72094 - 192095 + 311296 - 333697 + 213398
11 + 6912-

6

~120099 + 384910 - 729

= 9n (6 + 369 - 10492 + 2493 + 17794 - 25295 + 1569

-4897 + 698 ),

E(R'4,12)
E(R'ug) = 894 (1 - 9)3 (6 - 1392 + 993 - 95) .
E(R'AB) = 695 (1 - 9)ll (10 ~209 + 11192 - 393) ,
E(R'47) 1294 (1 - 9)5 (6 - 9 - 592 + 393),
E(R'hs)
E (R'ns) = 1293 (1 - 9)7 (2 + 39) ,
E(R'nu) = 393 (1 - e)8 (32 + 39) .
E(R'u3) 492 (1 - 9)9 (6 + 119) ,
4292 (1 - 9)10 ,

E(R'hl) = 129 (1 - 9)11 ,

E(R'uo) = (1 - (9)12

#93 (1 - 9)6 (8 + 219 - 3092 + 1193 ),

4:-
N
V
II

We give below some computational checks of the approximate
values of. E(Rni) with their exact values, for the particular

cases N = 25, d = 3, and n = 2, 3 ; the rate of valency 9 is

3 =
24 0.125

99

Tab1e 2.1.1 Showing the approximate and exact values of E(Rni)
for n = 2, 3, and N = 25, d = 3

 

 

 

 

n = 2 n = 3

Exact Approximate Exact Approximate

value value value ‘ Value
E(Rn3) 5 ‘ 5 10 10
E(an) 68 66 186 183
E(Rni) - 112 126
E(Rno) 227 229 1992 1981
Total 300 300 2300 2300

 

Table 2.7.21 Showing the approximate* and exaCt values °f E(R'ni)
for n = 3; and N g 25’ d a 3

 

 

Exact value ' Approximate
7 value .
E(R'36) 10 ' 10
E(R'34) 171 144
E(R'33) 25 39
E(R'32) 169 190
E(R'31) .912 885
E(R'BO) J1013 1032

 

Total‘ '2300 2300

100

For 9 = .1, .2, ..., .9, the values of the ratios E(Rni)
and E(R'ni) have been computed for n - 2, 3, and 4 ; these
values arranged in form of tables are shown in the appendix A.3 .
In applications these tables showing ratios E(Rni) and E(R'ni) ,
and their corresponding graphs with 9 as the independent var-
iable may be used ‘
(i) ' to estimate the ratios E(Rni) or E(R'ni) for
predetermined values of 9 and n , 6
(ii) to find that value of 9 (and hence d ) which for a
predetermined n , will give a certain preassigned ratio
E(Rni) or E(Rni) ,

(iii) to find that value of n which for a fixed 9 , will

give a certain preaSsinged ratio E(an) or E(R'ni) .

.L

PART III
APPLICATIONS

jig: Prelimiggries In the first part of this thesis we have
developed a stochastic model for analyzing time changes in a
binary dyadic relation '12 on a finite set of N points. As
indicated in the introductory chapter, a motivation for the de-
velopment of this model is its possible application to group
dynamics. Let us consider a group consisting of N individuals
and let each member designate a certain number of individuals,
from the N-l possible associates, with whom he would like to
be associated with regards to some specified activity.in the
group. Such a group organization, in the sociometric sense,

is composed of directed relations between the pairs of its members,
and is representable in terms of the aggregate of the interper-
sonal relations among subgroups of n persons (T12 2) belonging
to the given group. This aggregate of interpersonal relations is
called the configuration for the group.

As time proceeds some of the members of the group may
change then-choice of associates. Consequently, some of the
interpersonal relations among n-person subgroups change from
one type of relationship to the other, while others remain
unchanged. Therefore, the configuration for the group is a
function of time and changes with time. In general a study of
the changes in the group organization over a period of time can
be made only by viewing the group organization in terms of the
interpersonal relations of ncperson subgroups (see Introduction,

pages 1-5 ).

101

102

In terms of our probability model, each point of the set A
represents a specific member of the group, and the fundamental
relation 62 corresponds to the specified activity in the group. The
fact that the point P1 holds relation 0{ to point- Pj (that is
TR.(1, j) holds) signifies that the individual i chooses to
associate with individual j with respect to the specified activity.
The total relation TQ.(A) stands for the group organization and
the subrelations F5K(a) represent the interpersonal relations among
n-oerson subgroups of the given group.

At any point in time, a particular relation among a subgroup
of n members may be in any of the several different kinds of
relationship. The number of different kinds of relationship is
very large, but the classification systems described in section
1.2 give us a smaller number of states in which a relation may
be found at any given time. The connectivity classification is
based on the criterion of the compactness of the group, and con-
sists of four different states si ; the accessibility classificaé'
tion is based on a notion of density of connections in the group,
and the number of states 5'1. depends on n . The type of
classification to be used in a given situation depends upon the
nature of the example under consideration.

Statistical methods for testing the hypothesis of indepene
dence in time, and for determining the nature of the dependence on
the past have been given in section 1.h. An illustration of use,
of these methods is given in the next section. We also refer
the reader to a study by Katz and Proctor (L163 . In this
paper they describe the configuration of interpersonal rela-

tions between pairs of individuals in a group as a time=

103

dependent stochastic process, and examine a particular collection
of data [24:] to determine the dependence of the process on the

past, in terms of pair wise relations.

104

,3:2 Empirical Examination of the Markov properties

We have available to us a particular set of data reported
by Taba as part of a project in inter-group education ILQKJ .

A group of 25 eighth-grade students, 16 boys and 9 girls, were
interviewed in one school year in September, November, January,
and May. Each student was asked "with whom would you like to
sit?". Each of the students made three choices, except in
November when two gave only two choices each. A complete de-
scription of the static group structure is given in [243 , and
a dynamic study in terms of pairwise relations is given in Katz
and Proctor [163 .

In this section, we investigate the change in the choice
behavior of this particular group, in terms of the interper-
sonal relations among three person subgroups. Since the data
consists of choices made on the basis of a seating criterion
it seems more appropriate to use the connectivity classifica-
tion for relations rather than the accessibility classification.
However we give in appendix A.4 the second-order transition
tables for the accessibility classification (These are easily
obtdned by using the computer program given in appendix A.2)
which may be used to carry out an empirical examination of the
process for the accessibility classification.

In the connectivity classification a relation may be in
one of the four states s3, s2, s1 and s0 . To test the hypoth-
esis that the process is independent in time, we calculate
chi-square statistic (given in section 1.4, pagelua) for each of
the following 4 x 4 transition tables. These tables are

easily obtained by using the computer programm given in appendix

105

A.2. Since the observations are made at four points in time,
there are (2) = 6 such tables to be examined.

We note here that for a contingency table with small ex-
pected frequencies the chi-square statistic may be calculated '
‘without any correction for continuity if some expected frequency
is greater than 5 and the degrees of freedom are greater than

1 (see Cochran, L6] )
Tables 3.2.1 showing first-order transition frequencies

State of Relation State in November

 

 

 

 

in September s3 s2 s1 s0 Sums
s3, 4 8 2 2 16
52 4 47 12 77 140
sl 1 7 11 44 63
s0 2 71 41 1967 2081

Sums 11 133 66 2090 2300

State of Relation State in January

in November 53 52 s1 s0 Sums
s3 ‘2 6 l 2 ll
52 9 39 4 81 133
51 2 15 5 44 66
5O 2 85 66 1937 2090

Sums 15 145 76 ‘2064 2300

State of Relation

106

State in January

 

 

 

 

 

 

in September s3 s2 51 so Sums
$3 6 1 .6 16
s2 38 8 86 140
S1 1 8 5 49 63
so 3 93 62 1923 2081

Sums 15 145 76 2064 2300

State of Relation State in May

in January 53 52 51 so Sums
s3 3 9 0 3 15
52 10 39 9 87 145
s1 4 9 3 10 76
sO 1 73 39 1951 2064

Sums 20 ' 130 51 2099 2300

State of Realtion State in May

in November s3 s2 51 so Sums
s3 4 6 O l 11
52 3 36 10 84 133
S1 2 15 11 38 66
so 11 73 30 1976 2090

Sums 20 130 51 2099 2300

State of Relation

State in May

107

 

 

in September s3 s2 51 so Sums
s3 2 3 10 16
52 4 26 6 4 140
S1 2 4 5 52 63
SO 12 97“ 39 1933 20817
Sums 20 130 51 2099 2300

The chi-squares values are shown in the table below:

Table 3.2.2

esis of independence

Showing chi-square values for testing the hypoth-

 

Time changes - Time gap x2 Degrees of Decision
freedom at 5% level
September - November 2 months 613.30 9 Reject I
November - January 2 months 317.48 9 Reject
September - January 4 months 236.57 9 Reject
January - May 4 months 288.85 9 Reject
November - May 6 months 244.65 9 Reject
September - May 8 months 201.91 9 Reject

The hypothesis of independence is threfore rejected, and we

ask whether the dependence is Markovian.

First we test the hypothesis that the transition probabilities

are stationary by computing the chi-square criterion as given in

section 1.4 (page 44). To make the time gap of the transitions

 

 

108
equal, we compare the transitions from September to November
with that from November to January, and the transitions from
September to January with that from January to May. We examine

the following two tables for this purpose.

Tables 3.2.3 Showing different kinds of transitions for testing

the hypothesis of stationarity

 

Starting Ending Transition Transition
from at September November September January
to to to to
November Jgnuary January May
53 4 2 3 3
s2 8 6 6 9
s
3
51 2 1 1 0
so 2 2 6 3
s3 4 9 8 10
s2 47 39 38 39
S2 51 12 4 8 9
so 77 81 86 87
53 1 2 1 4
s2 7 15 8 9
s1 s1 11 5 5
so 44 44 49 60
53 2 2 3 1
s2 71 85 93 73
S0 S1 41 66 62 39
sO 1967 1937 1923 1951

 

The two chiasquare values are:

109

 

Comparison of Chi=square Degrees of Decision
value freedom at 5%
September to November 19.84 24 Accept
and
November to January
September to January 14.79 24 Accept

and
January to May

 

Having decided that the transition probabilities for the

process may be taken to be stationary, we test for the order

of the Markov chain. The chi-square statistic for testing the

null hypothesis that the Markov chain is of order one against

the alternate hypothesis that it is of order two is given in

section 1.4 (page 44) . We can calculate the values of chi-

square both for the chain of 2~month gaps, and the chain of

74-month gaps, from the following tables.

Tables 3.2.4

 

Structure in

showing second order transition frequencies

110

Structure in January

 

 

 

 

September November 53 $2 sl so
53 1 3 0 0
s2 53 l 2 0 l
51 0 0 0 1
so 0 l 1 0
s3 2 3 0 3
s2 so 5 16 0 26
s1 “ 0 1 1 5
so 2 19 3 47
$3 0 0 1 1
s2 51 1 6 l 4
$1 1 2 1 7
so 0 7 2 32
s3 0 0 0 2
52 s 1 14 7 55
51 O 0 5 3 36
so 1 66 56 1844

 

111

Structure in May

Structure in

51

S2

January

 

 

September

32.1.0

 

22

12

3210

56

24

S S

 

49

32.1.0

 

40

1828

31

63

 

112

The chi-square values (with correction for continuity) are:

 

Transition Chi-square Degrees of Decision
values freedom

September - November 143.66 36 Reject

to January

November - January 44.98 36 Accept

to May

 

While the chain of 2=month gaps shows a second or higher
order dependence, the chain of 4-month gaps does not. Thus we
may decide to treat the chain of 4-month gaps as a Markov chain
of first order w th constant transition probabilities. To estimate
these transition probabilities we make use of the first-order
transition tables, for 4-month gaps, showing transitions from
September to January and January to May, and obtain the average
transition probabilities.
Table 3.2.5 showing the estimated transition probabilities for

first order Markov chain with 4-month gaps

 

From To V3 V2 V1 V0

v3 .194 .484 .032 .290
v2 .063 .270 .060 .607
v1 .036 .122 .058 .784
v0 .001 .048 .024 .928

113
All states can be reached from each other so that the Markov chain

is irreducible and possesses a unique stable distribution with

limiting probabilities for states s 51 and s The

3, $2, 0 .
estimate of these limiting probabilities is the characteristic

vector of our matrix estimate. It is

 

This .ives us exnected stable values of the number of three=
r:
person relations in states 31 . These are: 16 in state 53 ,

156 in state 2 in state 51 , and 2066 in state s

52 , 0 .
Thus, we find that the interpersonal choice behavior of the
eight-grade students on a seating criterion may be viewed as a
Markov process with stationary transition probabilities. While
the chain of two-month gaps shows a possible secord or higher-
prder dependence, the chain of four-month gaps does not depart
significantly from a firstuorder dependence. The Markov chain
of fouremonth gaps is irreducible, and future predictions may

be made using the stable transition probabilities '3 .

Va

1 ,

a- n‘ .41 1. 4,1
and I 1 AH: . o

I
I
12
~
1'
-l
o.
0
I
I4
.-
h—
I
I
n
F‘,
‘—
I
A
I
a
\r
A
5
~

A e .s a u A4 Irb

I
b
a
v

FL ...!
IN. uh :

 

10.

11.

BIBLIOQRAPHY

Anderson, T. W. and Goodman, L. A: "Statistical Inference
about Markov Chains," The Annals of Mathematical Statistics,
V01. 28, Number 1, March 1957, pp. 89-110 . f '
Bartlette, M. S.: An Introduction to Stochastic Processes,
Cambridge University Press, 1956.

Berge, C.: Theorie de Graphs et Ses Applications, Paris,
1958.

Billingsley, P.: Statistical Inference For Markov Chains,
University of Chicago Press, 1961.

Chung, K. L.: Markov Chairs With Stationary Transition Proba-
bilities, Springer-Verlag, Germany, 1960.

I“

Cochran, W. 6.: "The x6 Test of Goodness of Fit," The

 

Annals of Mathematical Statistics, Vol. 23, 1952, pp 315-345.
Cramer, H.: ‘Mchematical Methods of Statistics, Princeton
University Press, Princettn 1946, Chapter 30.

Dulmage, A.L.; Johnson, D. M.; and Mendelsohn, N. 5.:
"Connectivity and Reducability of Graphs," Canadian Journg;
of Mathematics, (To Appear).

Feller, W.: An Introduction to ProbgbilityTheory and Its
Agglications, John Wiley and Sons, 1950.

Festinger, L.: "The Analysis of Sociograms, Using Matrix
Algebra," Human Relations, Vol. 2, 1949, 153-158.

Frechet, M.: Le Probabilites Associees a Un Systeme d'Evene-
ments Compatibles, Et Dependents Actualites Scientifiques

Et Industrielles, Nos., 859 at 942, Hermann Et Cie, Paris,
1940, 1943.

114

 

 

 

13c

14.

15.

16. '

17.

18.

19.

20.

Harary, F,: "The Number of Linear, Directed, Rooted, and
Connected Graphs", Transactions of fheAmericgn Mgthemgtical
Societ , 78, 1955, pp. 445-463.

Harary, F.: "Unsolved Problems in the Enumeration of Graphs",

Publications of The Acgdemy of Sciences, Vol. V, Series A,

FASC, 1-2, Budapest, 1960.

Katz, L.: "The Distribution of the Number of Isolates in a
Social Group", The Annals of Mathemgtical Statistics, Vol.
23, No. 2, June 1952.

Katz, L.; and Olkin, 1.: "Expectations of Certain Configura-
tion in Net WorksV, Research Monograph (mimeographed),
Department of Statistics, Michigan State University, 1952.
Katz, L.; and Proctor, C. H.: "The Concept of Configuration
of Interpersonal Relations in a Group as a Time-Dependent
Stochastic Process", Egychometrigg, Vol. 24, No. 4, December
1959. _ .

Katz, L.; Tagiuri, R.; and Wilson, T. R.: "A Note on

Estimating The Statistical Significance of Mutuality",

The Journal of General Ps cholo , 1958, 97-103.

Katz, L., and Wilson, T. R. : "The Variance of the Number
of Mutual Choices in Sociometry," Ps chometrika, Vol. 21,
No. 3, September 1956.

Kemeny, J. 6.; and Snell, J. L. : Finitegflggkov Chgigg,

D. Van Nostrand Co., Inc., Princeton, 1960.

Konig, D. : Theorie Der Endlichen_ggg3Unendlichen Grgphen,
Leipzig, 1935.

115

 

 

21.

22.

23.

24.

Perron, D.: "Zen Theorie Der Matrizen", Mg;hema;igal_Annils,
64, 1907, pp. 248-263.

Polya, G.:"Kombinatorische Anzahlbestimmungen Fur Gruppen,
Graphen, and Cheunsche Verbindungen", Acta Mathematica, 68,
1937. pp. 145-255.

Riordan, J.: An Introdggtion to Combingtorig;_Ana1 sis,

New York, 1958.

Taba, H.: With Perspective on Human Relations: A Study of

Peer Group Dyngmics in an Eighth GradeI Washiggton, D. C11
Ameriggn Cogncil of Education, 195 .

116

 

APPENDICES

117

 

 

No directed lines

One directed line

———>

Two directed lines

6—9

118

A:1 N-point structures: N = 2, 3,4

 

Two- point Structure 5

 

 

119

Three Point Structure 5

No directed lines

One directed line

—9

Two directed lines

Three directed lines

 

Four directed lines
H <——9 <—-> _
S? v v v
Five directed lines
R7

Six directed line 8

i7

 

120

7i :1
l7l

' I

Z 71
71 71

 

 

BEN HMH EHMQHMHHHW H
E. Z HN HNH HRH HM HNH HHNHHM r H
E HN HNH HMH HRH H/L HNH HN‘ Hm HMH
HM HwH HN NH NH HHH 7H 7H 7H Z Z
KHVHVHHNMH HUSHHZHVHW
H\ HVHH/HHNHNH VHLHIHHNHHNR T
HHLHHHHHM NH HH$ WHHHHEHNHHH
HHHH H H. H WALH H H/HM H7 HM Hm,

 

 

:3

 

 

 

 

 

 

 

 

 

 

lII

Seven directed 1 iiii

 

 

 

 

 

 

 

 

 

 

 

BEENMWQQ
EEEEEEEE
MMEEMHEE
EEBSEEEH
E®®®®®
BEQEESEE
EEEEEEEQ
EHHHEEEH
@EE

up.

124

Connectivity Classification: N=2

Type 83

Type 82

Type 50

125

Connectivity Clas sification: N: 3

Type 83

Type s;

”l
4
”1
5.
<1

Type 61

TYPe So

,I‘
1‘.
I.

‘ I It"

"O
(D
T U)
u

:

3%
EB

H1

17

 

 

 

1

1X1 1X1 131

1

12
1211211241 1191131121

1

$2

1

1

1X

1

1:

1

/
——>

1

Connectivity Clas sification: N=4

 

 

 

 

 

 

 

 

 

ESSERBV
EEEBEEQ
@QEENQE
®®%8ME®
HHHHHQS
EEEEEEE
®E®®®@®
BQEEEQg
EHEHHEE

e

HWMZNBREEEE

ES,

WZNQREEHW
NENEEEMEL
NBE®EH®E:U
QESBEEHSHK
ERUEUEHQEH
CREWEZHWSE

fiEEVEERWEfi
flKUKEDEEME

H

 

M
V

 

1

 

‘21
(all

 

 

Hay-1

. 1

UV

129

A s ses sibility Clas sification: N: 2

Type 50'

Type 31'

Type 53'

Type 50'

Type 51'

Type 52'

Type 53'

Type 54"

Type 56'

Acce s sibility

V

T

\V

W

6—99

V

130

Classification:

ea

V

N33

131

bility Clas sification: N14

Accessi

Type 50'

A1

Q HM/H
E 3

11

H H HMH

132

W

¢

v4;

4315

 

Type 87'

n ..Nlallad

«inc.

 

TYPe 56

 

m E;

< 77
/
_..>

T

[Em->-
V<——>

<~ ~>
I.
V<-——>

._.— --,,

II
t.

¢ \

<___

T6

133

Type 89'

>

Z S E M E 3 Ne
RE:

, fin! .V e 9W4
V Ra Vb Wm, V
N W. S e. z w. R WM.

‘1“.

EWEEZZE

4w (Alllv

E ”N E ”M“ Wm mm Q

NEERmflfi

Type 812'

NEE

E E m

 

@ng

E U a a

E E E
BEE

EEEVZEVEVEV

<—-><—><—9<—><__><_>

EVEVSV EVEVVYVE’V
ram; VZV/ VZVV EVE

 

E EVE: EVEVEVZV
EVEVZVEVE VEVV’ZV
EEVEVE VEV EVEV
EVEEVEVEV EVEV
EVEVEVEVEE

A. 2: COMPUTER (MISTIC) PROGRAMS FOR
N = 25, n = 3

136

137

Program for obtaining fir st-order transitions for the connectivity
classification.

8002840001 0010K

8002840002

2600000000 81 7F 40 243L
8002840000 10 2F L4 243L
F500142001 40 243L 81 4F
80028403F6 L4 243L 40 243L
$5000263L6 L4 260L 40 244L
81004263FJ F4 243L 40 245L
4000122000 L5 263L L0 243L
7J3LFL4001 L4 261L 40 254L
40001263L8 49 259L 41 247L
L4002263FS 41 246L 81 4F
423FFL5001 L4 246L 80 1F
L4000L4000 40 246L F5 247L
263FSL03LL 40 247L L0 243L
703LLSS3F7 36 14L 22 9L
4000081004 41 256L L5 246L
50000L43LL 10 1F 40 366L
'323FLL43L0 F5 15L 42 15L
423L5L5001 42 8F L1 245L
L400026000 L4 8F 32 19 L
40002L03L4 22 BL L5 260L
423L8233L9 40 255L L5 255L
5000140000 L4 251L 42 35L
L13F9L43L4 42 39L 42 43L
423F9L43L8 L5 255L L4 252L
423L800027 42 47L 42 51L
800080000N 42 55L L5 255L
40001273L1 L4 253L 42 59L
465F660458 42 63L 42 67L
7LLLLLLLL6 L5 254L L4 251L
223L500001 00 8K 42 36L 42 48L
00F 00F3L 42 60L L5 254L
00F 00F L4 252L 42 40L

42 52L 42 64L
L5 254L L4 253L
42 44L 42 56L
42 68L 50 ( ) L

N0
S3
F5
09
32
S3
F5
09
32
53
F5
09
32
S3
F5
09
32

F J0 ( )L

F 32 38L
258L 40 319L
1F 50 ( )L
40L J0 ( )L
F 32 42L
258L 40 320L
1F 50 ( )L
44L J0 ( )L
F 32 46L
258L 40 321L
1F 50 ( )L
48L J0 ( )L
F 32 50L
258L 40 322L
1F 50 ( )L
52L J0 ( )L

S3L 32 54L

F5
09
32
S3
F5
09
32
S3
F5

09
32
53
F5
09
32
S3
F5
N0

258L 4o 323L
1F 50 ( )L
56L J0 ( )L
L 32 58L
258L 4o 324L
1F 50 ( )L
60L J0 ,( )L_
L 32 62L
258L 4o 325L

1F 50 ( )L
64L J0 ( )L
L 32 66L
258L 40 326L
1F 50 ( )L
68L J0 ( )L
L 32 70L
258L 40 327L
256L 41 257L

138

50
SS
74
50
S3
SS
50
SS
74
50
S3
SS
50
SS
74
50
S3
55
50
SS
74
50
S3
SS
50
SS
74
50
S3
55
50
SS
74
50
S3
55

31 9L 75 319L

F 50
320L
325L
F' 32
F 40
320L
F 50
320L
326L
F 32
F 40
321L
F 50
320L
327L
F 32
F 40
319L
F 50
323L
325L
F 32
F 40
320L
F 50
323L
326L
F 32
F 40
321L
F 50
323L
327L
F 32
F 40

322L
SS F
74 321L
192L
328L
75 319L
323L
55 F
74 321L
193L
329L
7S 319L
324L
SS F
74 321L
194L
330L
75 322L
322L
55 F
74 324L
19SL
331L
7S 322L
323L
SS F
74 324L
196L
332L
75 322L
324L
SS F
74 324L
197L
333L

50 319L
SS F 50
74 326L
50 325L
S3 F 32
SS F 40
50 320L
SS F 50
74 326L
50 326L
S3 F 32
SS F 40
50 321L
SS F 50
74 326L
50 327L
S3 F 32
55 F 40
L3 257L
F5 256L
L3 328L
L3 332L
L3 336L
L3 329L
36 1361;
L2 334L
L3 333L
36 1361;
F5 256L
L5 319L
40 328L
L4 322L
L5 321L
40 330L
L4 326L
50 323L

7S 325L
322L

SS F

74 327L
198L
334L

7S 325L
323L

SS F

74 327L
199L
335L

7S 325L
324L

SS F

74 327L
200L
336L

32 168L
40 256 L
36 136L
36 1361,
36 136L
L2 331L
L3 330L
36 136L
L2 335L
22 168L
40 256L
80 1F
L5 320L
40 329L
L4 325L
L5 324L
40 333L
L5 327L

139

80
SS
L3
L2
L3
L3
36
L3
L3
L3
L3
36
L3
L3
L3
L2
L3
L3
36
L3
L3
L3
L2
22
40
36
L5
40
40
L5
42
41
N0
F5
F5
F5

1F 40 336L

F 40
328L
330L
329L
328L
151L
333L
330L
330L

' 328L

156L
329L
333L
329L
333L
333L
332L
163L
329L
330L
330L
336L
168L
256L
364L
256L
256L
ZSSL
256L
175L
256L
F 40
251L
252L
253L

332L

L2 329L
32 167L
36 151L
L2 332L
26 153L
32 167L
32 167L
36 156L
L2 336L
26 158L
32 167L
32 167L
L2 332L
32 167L
36 163L
L2 336L
26 165L
32 167L
32 167L
L2 333L
32 167L
F5 256L
L3 259L
41 259L
80 2F
L5 244L
22 20L
L4 365L
42 176L
F5 ( )L
( )L

40 251L
40 252L
40 253L

F0
22
40
36
40
40
40
F5
40
40
F0
L5
22
26
26
26
26
26
26
26
26
26
92
92
92
J0
26
92
92
92
L5
J0
26
92
92
92

243L 32 181L
19L F5 250L

250L F0 243L
187L L5 250L
253L LS 249L
252L L5 248L
251L 22 19L

249L 40 249L
252L F5 249L
250L 40 253L
243L 32 201L
248L 40 251L
19L 49 257L

77L 49 257L

83L 49 257L

89L 49 257L

95L 49 257L

101L 49 257L
107L 49 257L
113L 49 257L
119L 49 257L
125L 93 133F
259F 92 710F
707F 92 579F
967F L5 264L
11F 50 205L

337L 92 131F
259F 92 706F
450F 92 707F
5791? 92 967F
26SL 22 leL
11F 50 211L

337L 92 131F
259F 92 706F
130F 92 707F
S79F 92 967F

140

L5
J0
26
92
92
92
L5
JO
26
92
92
92
92
92
92
92
92
92.
92
N0
JO
26
42
L1
32
22
40
00F
00F
00F
00F
00F
00F
00F
00F
00F

266L 22 217L
11F 50 217L
337L 92 131F
259F 92 706F
67F 92 707F
579F 92 967F
267L 22 223L
11F 50 223L
337L 92 133F
195F 92 259F
450F 92 707F
387F 92 963F
259F 92 706F
963F 92 450F
963F 93 130F
963F 92 67F
971F 92 194F
322F 92 83SF
707F 92 131F
F L5 268L
11F 50 236L
337L F5 235L
235L 42 9F
262L L4 9F
241L 92 131F
23SL F1 1F
1F 22 241L

00( )F

00( )F

00( )F

00F

00F

001F

002F

003F

001F

00F
00F
00F
00F
00F
00F
00F
00F
00F
00F
00F
00F

OOZF
003F
00()F‘
00()F
00()F‘
00F
00F
00F
00365L
00279L
002801;
0039F

00 290K

00F
00F
00F
00F
00F
00F
00F
00F

00274877906944F
00137438953472F
0068719476736F
0034359738368F
0017179869184F‘
008589934592F
004294967296F
002147483648F

00F
00F
00F
00F
00F
00F
00F
00F
00F
00F
00F
00F
COF
00F
00F
COF
00F
00F
00F
00F
00F
00F
00F
00F
00F
00F
00F
00F
00F
00F
00F

141

001073741824F
00536870912F
00268435456F
00134217728F
0067108864F
0033554432F
0016777216F
008388608F
004194304F‘
002097152F
001048576F‘
00524288F
00262144F
00131072F
0065536F
0032768F
0016384F
008192F
004096F
002048F
001024F
OOSIZF
00256F
00128F
0064F

0032F

0016F

008F

004F

002F

001F

00 374K
49 269F‘ 26 1835‘

00F

00 274F‘

00 347K

40F412F
SSF46ZF
L419L4216L
366LL5F
325L92706F
266L92642F
5019L7517L
LSZFLfllSL
402F326L
SSF401F
L7F50L
661F7517L
0036F824F
1040FL52F
L419L422F
3211L92961F
36F22F
00F0010F
001F001F
80F001F

24 10N

142

Program for obtaining second-order transitions for the accessibility

classification.
8002840001 00 10K
8002840002 1. 81 F5 40 3001"
2600000000 2. 80 2F L4 300F
8002840000 3. 40 300F 81 4F
F500142001 4.. L4 300F 4O 300F
80028 403F6 5. L4 301F 40 302F
55001 6. L4 300F 40 303F
263L2 7. L4 300F 40 304F
L03Ll 10003 8.. LS 306F L4 305F
L4000 00002 9.. L0 300]? 40 307F
L4000 00001 10. 41 347F 41 349F
40000 81004 11. 41 348F 41 350F
L43L1 363F8 12. 81 4F L4 350F
L43F7 423FF 13. 80 1F 40 350F
L5000 26000 14. F5 348F 40 348F
0000000002 15. L0 300F 32 15L
465F6 60458 1.6. 26 11L L5 350F
7LLLL LLLL6 17. 10 1F 40 (500)F
403FL 223LN 18. F5 16L 42 16L
81004 223L? 19. 42 349F L5 349F
42001 22001 20. L0 304F 32 20L
503L0 7.1000 21. 26 10L LS 301F
263L9 223LN 22. 40 351F L5 351F
FS3FJ 423L8 23. L4 352F 42 36L
LSOOO L4000 24. 42 40L 42 44L
L4001 40002 25. L5 351F L4 353F
40001 L13L4 26. 42 48L 42 52L
L43FK 423L4 27. 42 56L L5 ‘ 351F
L43L9 423L9 28. L4 354F 42 60L
503FL L5001 29. 42 64L 42 68L
80008 OOOON 30. L5 - 307F L4 3521?
40001 273FS 31. 42 37L 42 ' 49L
263F7 00000 32. 42 61L L5 307F

33. L4 353F 42 41L
34.,42 53L 42 6511.2"?
35. L5 307F 'L4‘ 354F
36. 42 45L 42 57L
37. 42 69L 50( )F
38. 41 364F JO()F
39. 83F 32 39L

40- L5 346F 40 3551'?
41.09 1F 50()F

42.
43
44.
45.
46.
47.
48.
49.
'50.
51.
52..
S3.
S4.
55.
S6.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78..
79.
80.
81.
82
83.

84..

85..
86.

36

.. S3
. L5

09
36

.58
.L5

09
36
S3
L5
09
36
53
L5
09
36
S3
L5
09
36
S3
L5
09
36
S3

.L5

09
09
53

.L5

50

.55

J0
50

.54

L3
F5

.50

SS

.. J0

50
S4
L3
F5

F J0( )F

F 32
346F

43L
40 3S6F

1F 50( )F
F J0( )F

F 32
346F

47L
40 357F

1F 50( )F
F J0( )F

F 32
346F

51L
40 358F

1F 50( )F
F J0( )F

F 32
346F

55L
40 359F

1F 50()F
F J0()F

F 32
346F

59L
40 360F

1F 50( )F
F J0( )F

F 32
346F

63L
40 361F

1F 50) )F
F J0( )F

F 32
346F

67L
40 362F

1F 50( )F
15F JO( )1?

F 32
346F
355F

- F 50
358F‘

357F
F 40
348F
364F
355F
F 50
359F
357F
F 40
348F
364F

.71L

40 363F
J0 355F
35 6F

S4 F

J0 361F
348F

36 79L
40 364F
J0 3S6F
3S6F

S4 F

J0 362F
348F

36 86L
40 364F

143

87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102-
103.
104.
105.
106-
107.
108.
109.
110.
111.
112.
113.
114.
115.
116..
117-
118.
119..
120-
121.
122-
123“
124.
125.
126.
127.
128-
129.
130.
131-

50

,55

J0
50
S4
L3

.F5

50
SS
J0
50
S4

.L3

F5
50
SS
J0
50
S4
L3
F5
50
SS
J0
50
S4
L3
F5
50
SS
J0
50
S4
L3
F5
50
SS
J0
50
S4
L3
F5
50
SS
J0

355F
F 50
360F
357F
F 40
348F
364F
358F
F 50
358F
360F
F 40
348F
364F

J0 357F
3S6F

S4 F

J0 363F
348F '

36 93L
40 364F
J0 3SSF
359F

54 F

J0 361F
348F

36 100L
40 364F

358 F J0 3S6F

F 50
359F
360F
F 40
348F
364F
358F
F 50
360F
360F
F 40
348F
364F
361F
F 50

359F
54 F
J0 362F
348F
36 1'07L
40 364F
J0 357F
359F
S4 F
J0 363F
348F
36 114L
40 364F
J0 355F
362F

35 8F S4F

363F
F 40
348F
364F
361F
F 50
359F
363F
F 40
348F
364F
361F
F 50
360F

J0 361F

348F

36 121L
40 364F
J0 3S6F
362F

S4 F

J0 362F
348F

36 128L
40 364F
J0 357F
362F

S4 F

132.
133-
134.
135.
136.
137.
138.
139.
140.
141.
142-
143.
144.
145-
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175-
176.
177.

50
S4
L3
F5
L5
42
36
32
L5
F5
F5
32
40
L0
F5
L5
36
50
J0

363F
F 40
348F
364F
364F
153L
163L
165L
301F
354F
374F

J0 363F
348F

36 135L
40 364F
L4 368F
22 153L
L7 347F
22 155L
40 351F
40 354F
L0 354F

21L F5 353F

353F LS 374F
353F 36 152L
352F 40 352F
376F L0 352F

151 L 36 148L

700F 50 215F
30F 50 149L

26 250F 0F
F5 352F 40
F5 353F 40
22 21L LS(

F
353F
354F
)F

40
26
40
L5
L5
22
42
N0
41
L5
49
26
40
40
26
S4
36

364F L3 347F
137L L5 364F
3673 50 365F
366]? 74 377F
367F 74 377E
168L 42 160L
161L F5( )1?
F 40( )F
347F 26 139L
364F 4o 365F
347F L5 302F
21L L5 364F
366F 89 1F
347F L5 303F
21L L5 378F
F 22 159L

L 41 (700)F

F5 1701. 40 170L
L0 379F 26 170L

00250K

K5 F 42 32L
L0 40L 42 3L
46 L 40 2F

144

178.
179.
180.
181.

182..

183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.

42
42
L5
32
32
26
50
46

.L5

36
40
00
32
L0
50
L7
23
L7
40

39L LS F
20L 46 SL
F 40 F

8L F1 2F
8L 92 706F
9L 92 963F
37L 26 11L
L 75 37L

L L0 24L
10L SS F
1F F1 2F
6F 50 21L
19L L7 F
1F 36 41L
21L 26 18L
F 66 1F
20L 67 1F
F S4 F

F 50 F

75 37L 00 36F
82 4F 10 40F
KS 10F 40 F
L5 L L0 44L

46
36
L5
46
32

.L8

36

.L5

40
40
92
00
L7
00
00
L5
46

L 00 9F
28L 92 961F
2F L0 24L
2F 00 10F
21L LS 20L
38L 42 20L
33L 22 F

5L L4 44L
5L L5 39L
2F 46 L
131F 26 SL
F 00 10F

F ' S4 ' IF

F 00 F

11F 00 2F
2F L4 24L
2F 50 1F

75 37L 22 12L
00 1F 00 F
00300K

00F 00()F
00F 00500F
00F 00()F

224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
266.
267.
268.
269.

00F
00F
00F
00F
00F
40
20
10
08
04
02
01
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00 '
00
00
00
00
00
00
00
00
00
00
00

145

00( )F
00()F
0039F

00 308F
00( )F

00 F

00 F

00 F

00 F
00F

00F

00F
2048F 00 F
1024F 00 F
512F 00 F
256F 00F
128F 00 F
64F 00 F
32F 00 F
16F 00 F
8F 00F

4F 00 F

2F 00 F

1F 00 F
80
40
20
10
08
04
02
01
00 2048F
00 1024F
00 512F
00 256F
00 128F
00 64F
00 32F
00 16F
00 8F
00 4F
00 2F
00 1F
00 F

00 F

6656666

66666666

mmmmwmmmmmmmmmmmmmmmmm

270.
271.

272.
273.
274.
275.
276.
277.
278.
279.
280.
281.
282.
283.
284.
285.
286.
287.
288.
289.
290.
291.
292.
293.
294.
295.
296.
297.
298.
299.
300.
301.

00
00

00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
36
20

00F
00F

00( )F
00 (0)F
00 (1)F
00 (2)F
00 F
00F

00 F
00F

00F

00F

00 F
00 F
00 F
00 F
00 F
00F

mmmmwwwmwmmmwmmmmmm

65666656
0
O
N
U0
v-q

00 700F
10F 41 920F
180N

Program for obtaining second-order transitions for the connectivity
classification is the same as that of assessibility classification given

inAppendix A. 2 (pages 142-145) except for the changes indicated below:

Order No.

42.
46.
50.
58.
62.
66.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.

146

Changed to

 

36 llSL
36 122L

J0( )F
J0( )F

36 121L J0( )F

36 113L
36 179L
36 177L
L5 49L

J0( )F
J0( )F
J0( )F

46 llSL

L5 45L 46 113L
L5 411. 46 MIL

50 355F
SS F 50
J0 359F
50 357F
S4 F 40
L3 780F
SO 355F
SS F 50
J0 360F
.50 357F
S4 F 40
L3 781F
50 358F
SS F 50
J0 358F
50 360F
S4 F 40
L3 782F
50 358F
55 F 50
J0 360F
50 360F
S4 F 40
L3 783F
50 361F
SS F 50
J0 358F
50 363F
S4 F 40
L3 784F
50 361F

JO 356F
3S6F
S4 F
J0 362F
780E
32 MIL
JO 357F
3S6F
54 F
J0 363F
781F ‘
32 113L
JO 355F
359F
S4 F
J0 361F
7RZF'
32 115L
J0 357F
359F
54 F
JO 363F
783F
36 117L
JO 3551?
362F
84 F
JO 361F
784F
32 1181..
J0 3S6F

Order No.

107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
149.
J’fi'

9::

51:"

3}:

>1:

5::

*
298

147

Changed to

 

 

55 F 50 362F

J0 359F S4 F

50 363F JO 362F
54 F 40 785Fi
L3 785F 36 120L
26 L5 57L . .;
46 111L 26 81L
26 L5 57L ‘ '
46 111L 26 87L
22 1:5 57L ,
46 111L 26 93L
L5 57L 46 111L
26 99L L5 57L
46 111L 26 105L
L5 57L 46 111L
26 111L 27 154L
L1 780F L0 782F
32 127L L1 781F
L0 784F 32 127L
L1 783F .LO 785F
32 127L L5 i 346F
26 154L L5 61L
46 113L L5 65L
46 115L L1 356F
Lo 358F 32 132L
L5 346F 4o 356F
40 358F L1 357F
Lo 361F 36 174L

.LS 346F 26 173L

50 700F‘ 50 63F‘
40 357F 40 361F
L1 360F L0 362F
36 177L LS 346F
40 360F 40 362F
26 74L L5 345F
26 154L 00 F

F5 345F 26 154L
00 F 00 4F

5::
These orders are placed between order number 173 and order number

174.

* >3
A. 3: TABLES AND GRAPHS OF E (Rm) AND E (R'ni),
n=2, 3AND4, FOR6= .1, .2, .3, .4, .5, .6, .7,
.8AND.9

148

149

3'
Table A. 3. 1. Limiting Values F: (R21)

 

 

w

9: 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

 

* >1: .
E(Rz3)=E(R'231 0.01 0.04 0.09 0.16 0.25 0.36 0.49 0.64 0.81

:9:
(RZZ)=E(R'21) 0.18 0.32 0.42 0.48 0.50 0.48 0.42 0.32 0.18

Ill-x-

>V< >V<
E(R“): E(R'zo) 0.81 0.64 0.49 0.36 0.25 0.16 0.09 0.04 0.01

 

150

 

 

 

 

 

55555 5555 8555 $555 5355 355 2:5 335 235 Lonmvw
5555 2555 555 $85 $555 6625 £555 @555 335 35a
0.
3555 N585 $.85 $555 6535 825 325 2.25 3655 163m
5555 385 “535 $25 325 $5.45 $25 $.25 52.55 163m
555 $35 5535 8555 235 .285 $25 $555 .5555 28.45%
35.55 5255 N265 62.5.5 235 325 $655 5555 £555 3.....me
55 55 65 65 m5 «.5 m5 N5 25
3.5 w 334$ 9.38.3 , .... .m .... 636.5
8555 2.555 355 65555 $25 33.5 $2.5 32.5 $555 2.5%
3555 $555 5255 $55 $555 2.25 65.25 3555 2.35 Liam
5355 5:5 585 652.5 $3.5 32.5 5.35 325 5555 3me
$55 5:55 N365 6:45 5:35 225 $655 5555 N555 195m
55 55 2.5 65 m5 5.5 m5 N5 25

195 m 6636.4, 9.583 .N 5 .4 636.5
no.

151

 

 

 

 

 

 

885 885 885 885 885 885 5255 885 £85 23.5mm
885 885 885 885 885 4:55 .285 885 885 3.5%
885 885 885 £85 885 885 825 825 $35 3.5%
885 885 885 885 885 :85 $25 3:5 8:5 Asavm
885 885 8.85 3.85 585 :25 5825 225 :85 3.5m
885 885 885 $85 285 885 $.85 885 n:85 2.....me
885 285 5:55 2855 $85 835 :25 5855 885 35mm
885 885 885 2.85 825 8:5 2.85 885 885 .2.me
885 885 855 885 885 885 855 $85 885 23.5%
885 885 £25 885 8.35 885 825 885 “$85 28.5“
885 5855 $85 885 5855 825 885 $85 885 «2.4-Em
55 55 65 55 m5 45 ...5 N5 25
:3: m 6632/ 80283 .... 5 .4 633.
885 885 5855 2.85 885 825 5855 $85 $85 Loy-em
885 885 885 885 825 825 885 8:5 885 35%
2.85 885 835 885 885 3.85 885 825 :85 LNJLW
5855 5855 $85 885 5855 835 885 $85 885 Lnfivm
55 55 L5 65 m5 ..5 m5 N5 25
i

A}: m $32, 8585. .45 .4 636.2.

152

>1:
Graph A.3. l. E (Rn3), n = 2, 3,4

 

 

 

J
I

   

\l__

:1:
Graph A. 3.2. E (an), n = 2, 3,4

fi ulna»

l—u-

. 7-5—

 

153

 

 

n=4 _
nziZ
1 l l \ \
T l T 1' /
.5 .6 .7 .9 1

* .-
Graph A. 3.3. E (Rm), n - 3.4

E (Rm)
fl\
. 9"

 

154

 

 

 

\V

 

.1....

 

 

d-I—

3'1"

:1:
Graph A.3.4. E (Rm). n = 2.3.4

1.1-

5"-

155

 

\V

 

 

 

 

 

 

 

156
*
Graph A.3.5, E (R'3i), 1: 0,1, 2, 3,4,6

*
E (R'si)
1 $
.9_§\ . x
17"
13.0
.8+
.7“
\
E
\

 

 

 

(I,
\
\
\\
\\
\ i-
\ —- p
\\
% l
. 5 . 6

1557

0.1,Z.3,4,5,6.7,8.9.12

'1:

4i)z,

E (R'

Graph.A.3.6.

 

 

 

 

A. 4: SECOND-ORDER TRANSITION TABLES
FOR ACCESSIBILITY CLASSIFICATION

158

159

 

Sum s

t
82

State in Jan.
sf».

Nov.

State in
Sept.

 

27

15
18

16
28

10

5

1 _______-___-___________-

20
11
110

34
13

43

17

51

47

10
12

105

24

55

9

2 -____-___________________-_

10
25

11
18
139

105

32
93
127

47

313
224

64
10

6 81

0

O

5'6
I
34
S
s

12
10
267
874

I
3

2

5'0

117
660

20 115
197

14

12

5'1

8‘0

 

85 60 289 693 1158 2300

15

Sums

 

160

 

State in May

State in

Sept.

I
sz 51 so Sums _

53

I
54

Jam

 

'-

7
19

4

2

S6

54.-

20

10

17'

7

o _

11

14
19
15

O

10

I
56
I
54

53

27
11

83

13

11
27

16
35
28

44

52

52

85

20‘

51

92

55

5

2 2

0

So

19
20

.
355.
.122.
.

_

.

_

.

.
904.
27.
11.
_

.

_
228"
7015.
.

.

.

.
763.
322"
_

.

.

.
850.
.

.

.

.

.

_

_
4.83.
.

.

_

.

.

.

.
1.00.
_

_

.

.

.
all-IO—
SSS.
.

.

_

.

_

.

_

.

.

40694
2318
37
01/081
38
.15
3.1835
1115
.11
0450/2
44
111121

1
02365
01310

43210
ISISISaSIS
0
.S

 

2300

310 673 1117

76 54

20

Sum s

 

161

 

I
5'; 3'1 so Sums

a
.3

State in May
Nova 6 5'4 5

State in
Sept

 

M-—--l-----------—---------—--—--------—fl

18

10

.-------—-m---------—---—-----—‘m-—-‘-—..--wm-——-—“---------—-----

16
28

17

11
110

18
31

26
49

51

11

105

22

55

44

____________ ___ __ _ _ 7

10
25

15
49
140

105
313

19
119

26
32
30

8'1

10

224

163

12
10
267
874

137
586

95

196

25
70

13

20’

 

2300

310 673 1117

54

76

Sum s

 

162

 

State in May

State in
Nov.

5'1 8’0 Sum s

“I

5'6 5'4 5’3 D 2

Jan.,

 

22

12

12

——-—----—-----------—------—-Co---u-l--uaum----n--—-------------u-—--

13
14
22

12
5

26

11

105

l
28
18
35

61

46

14
f 29

75

29
121

21

13
75

£1

_

.

-

11.

23.

32.

.

.

.

—

_

_

SID.

33.

ll.

.

.

.

.

20.

47.
1

_

.

_

_

3.1.

32"

_

.

_

_

80.

.

.

.

.

_

.

_

34..

_

_

.

.

_

.

—

00.

_

_

.

.

_

10.

cS.S.

.

_

.

_

_

_

_

.

_

g6

12
25
291
837

3'3

32

143
652

79

139

53

10

40

go

 

2 300

310 673 1117

76 54

20

Sums