APPLICATION OF DYNAMIC PROGRAMMING METHODS TO A PROBLEM OF IDENTIFICATION BY SEQUENTIAL EXPERIMENTATION Thesis for the Degree of Ph. D. MICHIGAN STATE UNIVERSITY ROBERT CARL JUOLA 1968 This is to certify that the thesis entitled APPLICATION OF DYNAMIC PROGRAMMING METHODS TO A PROBLEM OF IDENTIFICATION BY SEQUENTIAL EXPERIMENTATION presented by Robert Carl Juola has been accepted towards fulfillment of the requirements for Ph.D. Statistics degree in Maj'or pr‘ Date M 0-169 ABSTRACT APPLICATION OF DYNAMIC PROGRAMMING METHODS TO A PROBLEM OF IDENTIFICATION BY SEQUENTIAL EXPERIMENTATION by Robert Carl Juola Suppose we are given n + l urns each containing n balls of two types (to be specific we shall always refer to the two types as black balls and white balls), and further are given that the composition (the number of black balls and the number of white balls) of each of the urns is distinct from the composition of all of the other urns. That is, one of the urns contains n black balls and no white balls, a second contains n - 1 black balls and 1 white ball, a third contains n - 2 black balls and 2 white balls, and so on until the last contains n white balls and no black balls. However, we assume we are given no infor- mation about which urn contains any of the compositions. Consider now the problem of determining with certainty the composition of all of the urns by drawing the balls randomly, without replacement, one at a time from the col- lection of urns. The draws are to be made from an urn of the drawer's choice, but the choice of the urn from which to draw is allowed to depend only on the numbers of black balls Robert Carl Juola and white balls which have been previously drawn from each of the n + 1 urns. The goal of these draws is to determine the composition of all of the urns with the fewest possible expected number of draws. The method of solution of this problem is a dynamic program. A theorem giving upper and lower bounds for the smallest expected number of draws required to determine the composition of all of the urns is given for all n. An explicit solution is given for the smallest expected number of draws until the composition of all of the urns is determined for n = 2, n = 3, and n = 4. These Smallest expected numbers are: 3.5 for n = 2, 7.528 for n = 3, and 13.136 for n = 4. APPLICATION OF DYNAMIC PROGRAMMING METHODS TO A PROBLEM OF IDENTIFICATION BY SEQUENTIAL EXPERIMENTATION BY Robert Carl Juola A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Statistics and Probability 1968 ACKNOWLEDGEMENTS The author wishes to express his deep gratitude to Professor Leo Katz for suggesting the problem and for his supervision and guidance during the course of this inves- tigation. The work on this dissertation was carried out with the financial support of the National Science Foundation under contract no. GP 7362, and the author gratefully acknowledges this support. ii II III IV TABLE OF CONTENTS INTRODUCTION ................................. NOTATION ............... . ........... . . . . . ..... DYNAMIC PROGRAMMING ...................... . . . . THE URN PROBLEM OF ORDER n AS A DYNAMIC THE URN PROBLEM OF ORDER [1 AS AN INFORMATION THEORY PROBLEM ....................... . ....... BIBLIOGRAPHY ......................... . ....... 17 21 3'5 40 LIST OF TABLES Page TABLE 1 ............................................. 33 TABLE 2 ............................................. 34 TABLE 3 ............................................. 38 iv II APPENDICES Page FORTRAN IV PROGRAM FOR THE DYNAMIC PROGRAM TO SOLVE THE URN PROBLEM OF ORDER n .. ....... 41 THE DYNAMIC PROGRAM FOR THE URN PROBLEM OF ORDER 3 ...................................... 52 1'1" [I’ll Iitl I. INTRODUCTION Statistical problems are mainly of two types, estimation or hypothesis testing. Here we are concerned with a third type, identification. In an hypothesis testing problem, one formulates an hypothesis and an alternative; and compares the distribution of the observed data to the distribution which the data would have if the hypothesis were true and to the distribution it would have if the alternative were true. One then rejects the hypothesis if the distribution of the observed data is not sufficiently close to the distribution if the hypothesis were true compared to the distribution if the alternative were true. In an estimation problem, a class of probability dis- tributions which contains unknown parameters is postulated for the generation of the data, and those values of the para- tneters which best fit (in some pre-assigned sense) the observed (iata are found. In our identification problem the data are assumed to have been generated by one of a family of possible ggénnerating mechanisms and it is desired to know with certainty ‘vwflich of the mechanisms is the true generating mechanism for the observed data. As stated above the problem of identification is not PrObabilistic at all. However if we consider the problem of an“iiSSing the data necessary to make this certain identification sequentially, having to choose one of a number of possible experiments to obtain the next datum, the problem of finding an optimal decision strategy for obtaining the next datum is a dynamic programming problem. Further, if the experiments which are performed to obtain the next datum have random out- comes then this dynamic program has genuine stochastic elements. We here propose a formal problem with finitely many possible generating mechanisms and ask which of these is the true mechanism. (This can be considered a special case of the multiple decision problem, in which we require the probability of making an error to be zero.) Suppose that we are given n + l urns, each containing n balls of two types (to be specific we shall always refer to the two types as black balls and white balls), and further are given that the composition (the number of black balls and the number of white balls) of each of the urns is distinct from the composition of all of the other urns. That is, one of the urns contains n black balls and no white balls, a second contains n - 1 black balls and 1 white ball, a third contains n - 2 black balls and 2 white balls, and so on, to the last, containing n white balls and no black balls. Further, we assume we are given no information about which urn contains which composition. Consider now the problem of collecting information on the Cotnposition of all of the urns by drawing the balls raxuiomly, without replacement, one at a time from the col- lection of urns. Each draw is to be made from an urn of the drawer's choice, which is allowed to depend on his information concerning the numbers of black balls and white balls which have been already drawn from each of the n + l urns. The goal of these draws is to determine exactly the composition of all of the urns, with the smallest possible expected number of draws. The method of solution of this problem (which will be called an urn problem of order n) will be dynamic programming. This method is explained in chapter III and the solution of an urn problem of order n is presented as a dynamic program in chapter IV. A FORTRAN IV program is given in appendix 1 which utilizes the results of chapter IV in order to give an explicit solution for the urn problem of order n for small n (n S 4). II. NOTATION In order to approach a solution of the problem presented above (which will be called an urn problem of order n), it is necessary to develop a rather large set of notations which will allow us to make the problem specific. Since we will be recording the colors of the balls we have seen from each urn and must choose the urn from which to draw next, it is necessary to label the urns in some way. A convenient identification of the urns is arbitrarily to call one of them "0", one of them "1", another "2", and so on. Formally we have: Definition 11.1 The n + 1 urns in an urn problem of order n are indexed by 13 = {0,1,...,n}. The actual, but unknown, composition of the urn is claairacterized by the number bj of black balls (n - bj’ whi te balls) contained in it. The reason for the choice of irlcieaaring now becomes clear; because of the assumption that the composition of each urn is distinct from that of all of the other urns, the collection {bo,b1,...,bn} is a partic- ulsazr ealement of the permutation group of 13. The corre- spond ing composition of white balls is {n “ 13c), n - b1,..., n - bn}. Definition 11.2 The set of all possible "true" compositions of the urns is Sn+1’ the collection of all permutations of 13- As is uSual, we shall identify an element H E Sn+1 as n = (n0,n1,...,nn). At any time, to summarize the information which has been obtained on past draws, we shall use a 2 X (n+1) matrix M whose (1,j)th element is the total number of ,th . th black balls previously seen from the J urn and whose (2,3) element is the total number of white balls seen from the jth urn. Two extreme examples of M matrices are: 0,0,. .,0 . . . . l. M = 0 0 , representing the information obtained , :'°-2 prior to the first draw and 2. M = gym-1’7”?) , repre- , l,..., senting the information which could have resulted from draw- ing all n(n+1) balls available in the urn problem of order n, if the urns had been labelled so that their true composition was indexed by (n,n—1,n-2,...,O). In order to formalize the definition of information matrices and to focus our attention on the particular sub- set of the set of all the 2 X (n+1) matrices which we will call information matrices, we need the following definitions. Definition 11.3 Let b n n n n fig = {M = [WJIb 6 x 10, w E x 10, and i=0 i=0 6 se .n where e is b +tw n+1 I n the vector of n 1's. Definition 11.4 For each M = [b] E.%%, H(M) = w S S - = {n E Sn+l|b H n.en‘+1 w} where n (n0,n1,...,nn) is considered as an n+l-vector. H(M) will be called the M-admissible permutations. With these definitions, M E‘mb is a 2 X (n+1) matrix of non-negative integers whose columns total less than or equal to n and for every such M, the M-admissible permutations are the subset of Sn+ which corresponds to the true compo- l sitions from which it is possible to have observed M. We shall now prove a characteristic theorem for H(M), namely: b Theorem 11.1 If M - [w] 6%, and T] e 5M1, then n n n-n a n G H(M) ” H (bj)( w j) > 0 where (b) is the usual i=0 J J binomial coefficient. Proof: n E H(M) ” b S n S n.en+1 - w, where n = (n0,n1,fl2,...,n ) is considered an n+1 vector. ” . 2 b. 2 0 and n - . 2 w. 2 0 for all ' nJ J T1J J J TI. n-TI. ” (b3) >0 and (WJ) >o for all j J J' n Rj n-Rj e .H (1),“... > >0. J=0 J J Among the matrices in.‘Wk),‘We Shall restrict our attention to the subclass of all those M with the property that H(M) is non-empty. This is the set of matrices for which there exists at least one true composition for which it is possible to have observed, through draws from the urns, the b vector of black balls and the w vector of white balls. Definition 11.5 M is an information matrix if H(M) # ¢. The set of all information matrices will be denoted 7R. If M 6 7%, we may now say that there exists at least one actual, but possibly unknown, composition from which it is possible to have observed the information matrix M and then to identify H(M) as the set of permutations which index true compositions that have not been ruled impossible by observing MO The choice of a prior distribution whose support is the whole of Sn+1 will allow us to identify H(M) as the support of the posterior distribution on Sn+1 after observ- ing M. We will choose a uniform prior distribution to re- flect our initial assumption of complete uncertainty about the actual composition of any of the urns. a o o — ——1 Definition 11.6 P0(n) - (n+1)! for every H E Sn+1’ the uniform distribution on S . n+1 With this choice of a prior diStribution, it is now possible to give explicit formulae for the calculation of the posterior distributions. b Theorem 11.2 If M - [w] E 77:, and n e Sn+1, then PM(1T) = P(Tth) = TI _ 2 II (bk)( w TIEH (M) k=0 P(MlTr)P0(TT) Proof: P1401) ' z P(M 'II)P0(TI) TIES n+1 1'I'j tl-TTj n (bj)( wj ) H _________—. j=0 (b 1w.)(n+l)! _ 1 L TI n-TIk ( k)( w ) bk Wk 2 [-11 ——-fi———] TIES k=O ( )(n+l)! n+ bk-l-wk n-TT “ "j j n j=0(bj)( wj ) II II n-T] z [n (b:)(wkk)] TIESn+1 k=0 n 17:] n-Tl' H (b )( 3 Fe 3 “j n T] n-TI z [n (b:)( vb] TrEH(M) k=0 3') 9 n W. n-“. Since 11 e H(M) e 11 (b4)( w.J) = 0» J=0 J 3 It is not necessary to consider all of the matrices in ”L It often occurs that for a given matrix M E ”L it is possible to immediately conclude that more is known about the composition of the urns than is clearly shown by the matrix M. For example, consider M = (3 3 3 3); it is known that urn 3 contains all white balls since urns 0, l and 2 all con- . . . 1 l l 0 tain at least one black ball. Thus, the matrix M = (0 0 0 3) exhibits the same knowledge about the composition of all of the urns as does M, but M' exhibits this knowledge more clearly. If it were not for this possibility of immediately concluding that more is known about the composition of the urns than is clearly shown by the matrix M, there would be no problem in minimizing the number of draws until the compo- sition of all of the urns is known. We would be forced to draw all of the balls in the entire system. However, this is not the case; we know, in fact, that if the composition of n of the urns is known, then the composition of the re- maining urn is also known. This causes an immediate reduction in the total number of draws until the composition of all the urns is known from n(n+1) to at most n2. The fact that this ability on our part to be able to conclude more knowledge about the composition of the urns 1C) can and does occur at many other times in the process of drawing the balls provides us with the basic tool to find the minimum expected number of draws until the composition of all of the urns is known. 1 1 1 0 The matrix M = (o 0 0 3) exhibits the same knowledge about the composition of the urns as do the matrices 1 1 1 0 (O 0 0 0)’ 1 l l 0 1 l l 0 . . (0 0 0 1), and (o 0 0 2), but it shows this knowledge more . . . . . l 1 1 0 1 l 1 0 clearly. With this in mind we Will call (0 0 0 0), (0 O 0 1), l l 1 0 . . l l l 0 and (0 0 0 2) reduCible matrices and call (0 O 0 3) an irreducible matrix; and finally, we shall call (3 3 3 g) the reduction of (3 3 g g) and will denote this reduction by 1 l 1 0 l 1 l 0 . . 1 l l 0 _ 1 1 1 0 _ o o o 3) ‘ R(o o o o)’ Similarly (o o o 3) ‘ R(o o o 1) ‘ R(é g 3 g)' Formally, we have the following definition. Definition 11.7 An information matrix M = [2] is reducible if there exists j E 13 such that for every permutation n in H(M), “j is equal to some fixed integer k, but bj + wj < n. If M is not reducible, it will be called irreducible. The class of irreducible * matrices will be denoted WT. To illustrate this definition, let us consider the following two examples: 1 l l 0 May; M = (0 o 0 0); H(M) = {(3,2:1’0)9 (3:1)2:0)) (2,3,1,0), (2,1,3,0), (1,3,2,0), (1,2,3,0)}. Each of the permutations in H(M) has the last coordinate equal to zero. But b3 + w < n, and so M 3 is reducible. Similarly, 11. 1110 1110 . M‘ = H = redue b . J = 1 l l O (0001’M (0002)are lle B” M" (0003) is irreducible. b' 3010 b" 3000 '- .= '= = - Example 11. M —[W.] (03 10) and M' [w"] (0 300), H(M') = H(M") = [(3,o,2,1), (3,0,1,2)}. If T] e H(M'), then = = I n = I l ___ “0 3 and n1 0, and b0 + w0 b1 + w1 n, and b3 + wB = b; + w? = n, so that both M' and M" are irre— ducible, although they are different and induce the same posterior distribution on Sn+ , namely: 1 Pm.<(3.o,2,1)) = Pm..(<3.0.2.1>) = Pm.((3.o,1.2>) = Pm..<<3.o,1,2)) = 1/2. Every reducible matrix M, has corresponding to it an irreducible matrix, R(M), which exhibits all of the knowledge about the composition of the urns that M does. This re- duction of a reducible matrix to an irreducible matrix pre- serves the posterior distribution on Sn+l induced by M, and therefore, the conditional probability of drawing a black (or white) ball from any of the urns whose composition is not already known. This will be proven in the theorems following the formal definition of the reduction of an in- formation matrix. Definition 11.8 If M = [:1 6772, then R[M] = [2:], where: 1. If M is irreducible, b' = b, and w' = w. 2. If M is reducible, and for every n E H(M) 112 there exist non-negative integers 10,11, . . . ,i J ... S S and ko,k1, ,k.J for 0 J n such that Hi. = kj for J = 1,2,...,J, J ‘= d '= . . III I bL bL an WL WL for L # 11,12, ,iJ and bf = k, and w! = n-k, for j = 1,2,...,J. 1j J lj J The justification for considering only irreducible matrices is that if we have an information matrix M which has the property that every permutation in H(M) has the same jth coordinate (say nj) then no matter what the true composition of all of the urns is, the jth urn is known to have ”j black balls and n - “j white balls. Since we know the composition of the jth urn, there is nothing to be lost by letting the information matrix reflect this additional knowledge more completely. Theorem 11.3 M is an irreducible information matrix if and only if M = R(M). Egggf: Direct verification of definitions 11.7 and 11.8. The following two theorems will show that for any M E Wu the corresponding R(M) induces the same posterior distribution on Sn+1 as M does. Theorem 11.4 If M = [:1 6771 then H(R(M)) = H(M). Theorem 11.5 If M = 1:] E 771, then PMUT) = P (T1) for R(M) every R E Sn+l' 13 The proofs of these two theorems Will be indirect as there is a considerable overlapping if we prove both of them directly. The proof will consist of three steps: A. H(M) 2 H(R(M)), B. Theorem 11.5, and finally 0. H(M) C H(R(M))- Proof of A: 1. If M R(M) the theorem is true. 2. If M [2] ii REM] =13] then b' 2 b and w' 2 w and TI 6 H(R(M)) =’ '2 2 _I - b T] n.en+1 w where T] is considered as an n + 1 vector. =bSIISn.en+1-w where T] is considered as an n + 1 vector. = ”II 6 H(M) Proof of B: 1. If M = R(M) the theorem is true. 2. If M 1‘ R(M) and T] E H(M), then 11 E H(R(M)) and hence PM(TI) = PR (M) (TI) = 0 3. If M = [2] 75 R(M) and M EWZ, then there exists 1 E 13 and j E 13 such that Tli = j for every TI E H(M), then for every 11 E H(M) (I? (”9 “t 13.4.3.6? ("3‘31 PMUI) = “:3 “L n’IIL H b b1 {1‘1 L 2 n “1‘31 111 {EH M)k#i wk _£L#i:n We Min “k (.....2. w.“}© (33) The proof of B is now complete since we may repeat the above calculation for any other pair (L,p) such that “L = p for all n E H(M) and obtain the result PMm) = P1100 (11) Proof of c: If M e 772*, then 11 e H(M) == PM(TI) > o = PR(M) (TI) > 0 = TI 6 H(R(M))~ The proof of both theorems is now complete. Since we shall have a choice of the urn from which to draw next, after observing the results of previous draws, we shall denote by D(M,j) the act of drawing from the jth urn when the past information is M. We shall denote the random variable resulting from D(M,j) by DjEM]. D(M,j) must result in one of two results, namely, either a black ball is drawn or a white ball is drawn. For completeness of definitions, if D(M,j) is chosen and if n balls have 15 (:11 previously been drawn from the j Urn we will say D, (M) = M J . Definition 11.9 Let a =[6j,0’6j,l"°"6j,n] and J 0 ,0 ,...,0 O ,O ,...,0 B,=[ ],where 6,,=O if iafij J 6j,0’6j,l’9°"6j,n 1,] and 6. = 1 i * Definition 11.10 If M E 772 and 0 S bj + wj < n, then M"; = R[M + aj] and M3 = REM + 5],]. * Theorem 11.6 If M = [2] E 771 and bj + wj < n, let Pj(B|M) denote the conditional probability of drawing a black ball from the jth urn, after the M matrix of black balls and white balls have been previously drawn. Then n. - b. n Rk n-nk 2 H ( )( ) n-b,-w, b w J n "L n-n{. 2 n (b )< w ) nEH(M) L=0 of, L 3.1.3.3231: P (BlM) = 2 Ill—:1 P (TD j n-b -w M RESH+1 J J and apply theorem 11.2. Definition 11.11 A choice D(°,°) is a random mapping n * from WT X 10 a: into 771 given by: 16 b * 1. If M = [w] E W? and bj + wj < n, then + Mj with probability PjEBIM] Dj(M) = M]? with probability 1 - PjEBIM], b * or 2. If M = [w] E W? and bj + wj = n, then Dj(M) = M with probability one. This chapter has provided us with the tools and con- ventions which will now be used in order to present a tech- nique for solving an urn problem of order n. This proposed technique is dynamic programming and is discussed in chapter 111. Chapter IV then presents a specific dynamic program for the urn problem of order n, which is used to solve the several examples of an urn problem of order n, namely n = 2, n = 3, and n = 4. III. DYNAMIC PROGRAMMING Dynamic programming is a mathematical technique which is often useful for making a series of interrelated decisions. When it is applicable to a problem, it provides a systematic procedure for determining the combination of decisions which will maximize the overall effectiveness of those decisions in striving for some fixed goal. There are a number of problem types for which a dynamic programming formulation of the problem is useful. We will state for our problem a specific set of conditions under which a dynamic program is possible and at the same time introduce the standard terminology of dynamic pro- gramming. Following Bellman [1], these conditions may be stated for the urn problem as follows: 1. The decision problem may be divided into stages, (each of which can be characterized by a "small" set of para- rneters called state variables. In the urn problem we are cuoncerned with, the information matrices M are the state va riab 1es . 2. At each stage, the statistician has the choice (>15 a number of possible experiments. In our case, he has the choice of drawing from one of the n+1 urns; the act 17 menwi .m an”, r. W .- 18 0f drawing from urn j is denoted D(~,j) for j = O,l,...,n. 3. The effect of a chosen experiment is a transformation of the state variables. The act D(M,j) results in a trans- formation of the state variables to either M; or Mj' 4. The past history of the system has no importance in determining the future decisions, except through the present. 5. The purpose of the decision process is to minimize some fixed function of the state variables. In our case, the goal is to minimize the expected number of experiments made until a terminal state is reached. In finite decision problems, those with only finitely many possible decisions until termination, we have the addi- tional parameter of time. This parameter manifests itself in the form of the number of permissible decisions which re- tnain to be made in the problem. In our problem, time is the Trumber of decisions to be made until a terminal state is reached. It is usually helpful to separate the time para- nneeter from the state variables as time usually plays a role ziri the problem which is quite different from the state ‘Iéilriables. In our problem it is the parameter upon which the objective function depends. Standard terminology in dynamic programming is: a I>C>l¢icy is a rule for choosing, for each value of the state 19 variables and the time parameter, an experiment. An optimal policy is a policy which minimizes a pre- assigned function of the state variables. This pre-assigned function of the final state variables will be called the criterion function and will be denoted G. F‘- In the case that the decision results in a probability distribution on the transformations, it is not possible to ‘31 minimize with certainty the criterion function after N steps. Rather, the quantity which we will seek to minimize is the expected value of the criterion function. With the structure on the problem as above, the possibility of constructing an optimal policy rests on the following principle due to Bellman [l]. Bellman's Principle of Optimality: An optimal policy has the property that whatever the initial values of the state variables and the initial decision are, the remaining (decisions must constitute an optimal policy with regard to t:he state resulting from the first decision, treated as new illitial values of the state variables. Implementation of an optimal policy repeatedly utilizes tile principle of optimality to consider a series of decisions backwards, evaluating each decision on the basis of proceeding optimally from whatever state has resulted from previous decisions. This works as follows: for each possible state of 20 nature prior to the final decision, we answer the question "What is the best decision to make if we are forced to stop now or to stop at whatever state results from our decision?" This can be called the-final-step decision problem. Knowing the answer to the final-step decision problem for each state of nature, we now ask "What is the best decision to make at each stage from every state if we are permitted at most two more decisions?", and so on backward until we evaluate the best decision to make if we are permitted N decisions. In the urn problem of order n, with only n(n+1) balls available in the system, and with each decision to draw a ball removing one ball from the system, it is obvious that N = n(n+1) will be a sufficiently large number to solve the problem, since it exhausts the system. IV. THE URN PROBLEM AS A DYNAMIC PROGRAM The goal of determining the composition of all of the urns can be expressed as an hypothesis testing problem as follows: given the (n+1)! a priori equally likely hypothesis find a policy, i.e., a function from all information matrices M* into {0,1,...,n}, to test the (n+1)! hypotheses at size zero and power one. The goal of testing these hypotheses with minimum expected sample size is now: among all policies which test the hypotheses at size zero and power one find a policy whose expected sample size to termination is the minimum. In the following, all matrices M will be elements of 771* and if M is not an element of 771*, we shall identify M with R(M). This should cause no ambiguity or confusion since it will not affect the posterior distribution or the probabilities of drawing a black ball from any of the urns whose composition is not already known. Definition IV.1 M is a terminal information matrix if H(M) is a singleton. Definition IV.2 If P is any policy, let EP(vn) be the expected number of draws until a terminal information matrix is reached in an urn probleulof order n. 21 ." lI‘IblIr'll'lIII’ll |'{ L. .5 22 Definition IV.3 On - MIQQEP(VH) where 6’ 18 the class of all possible policies. We can find an upper and a lower bound on On’ both of the bounds being of the order of n2. n+1 2 Theorem IV.l ( 2 ) S On S n . 12323;: The upper bound is immediate since if we know the composition of n of the urns, we know the composition of the remaining urn. The composition of n of the urns can be found by simply drawing all of the balls in these urns. This policy requires drawing n2 balls. To establish the lower bound, we need a lemma. lLemma IV.2 If X,Y are n+1 vectors of integers between C) and n inclusive and is there exists one and only one [Dearmutation n satisfying the inequalities ‘63 . 0 S X S n S Y S e . n where n is considered as a 13r+1 n+1 ’ n-l-l vector, then n z .(Y.-X.)SM. i=0 1 1 2 P roof of Lemma: Without loss of generality, Trj = j since i f it is not, we can reorder the X's and Y's, and ftjl Z (Y. - X.) is independent of the order of the subscripts j_===q:) 1 1 on the X's and Y's. Now, if i < j, either Yi < j or Xj > i, for if n n hence 2(Y -X)SZ(Y ‘Y.+j)=2j=( j=0 j J 23 .t . “0t, it is possible to interchange the 1 h and 3th coordinates Of the permutation and preserve the inequalities of the Lemma. ' s Con31der Y 0 Y = X1, 2,...,)glo are all greater 0’ 0 than 0, which may be a vacuous relationship. ' S =° Now, conS1der Y1, 1 Y1 X2,X3, ,lLfl are all }{j_*_1,Xj_'_2,...,XYJ are all greater than j. Thus a block of Yj - j of the X's are greater than 1. Similarly, j S Yj =° greater than or equal to j+1 for j = 0,1,...,n-l. We then have n n g x. = z k[#x's = k] j: 1 k=0 n n-l = z k[#x's 2 k] - z k[#x's 2 k+l] k=0 k=0 n n-l = 2 k[#x's 2 kJ - 2 (k+1)[#x's 2 k+1] k=0 k=0 n-l + z [#x's 2 k+l] k=0 n-l = 2 [#x's 2 k+1] k=0 n-l n 2 2 [Y - j] = 2 [Y. - j], since Y = n, k=0 j k=0 3 n n n+1) j=0 j j j=0 2 Th is completes the proof of the Lemma. We shall be using the contrapositive of the Lemma in remainder of the proof. 24 gorollary IV.3 If X and Y are n+1 vectors of integers n 0 to n inclusive such that Z (Yi - Xi) > (n31) then the i=0 set of permutations 1T 6 Sn+l satisfying X S 11 S Y where 11 is considered as an n+1 vector is either empty or has at leas t two elements . n Suppose M = [:3 is a matrix such that )3 (bj + wj) < (“‘51) n j=0 then 2 (n - w. - bj) > (n31) which implies by the corollary i=0 that either H(M) = Q) or H(M) has at least two elements; in either case M is not terminal. The proof of the theorem is now complete since if fewer than (n31) balls have been observed, the resulting information 'matrix cannot be terminal. We can now express the solution of the urn porblem of (arder n as a dynamic program. For every information matrix 1!! € Wig define the function g(M) = 0 if M is a terminal IIJEItrlx; and g(M) = 1 if M is not a terminal matrix. * We would like to minimize for every M0 6 772 the N c riterion function GN(MO) = Z g(Mi), for N 2 n(n+1), where i=0 M1 is the state resulting from the ith act on the state Mi-l' Th is is impossible since the state resulting from the ith act 1 s a random variable whose value depends on the entire sequence . .t . . of decisions which have been made prior to the 1 h decision and a 18 0 on the randomness in the occurrence of a black ball or “711 i te ball in drawing from any urn. 25 We shall adopt the convention of using Mj to denote the random variable resulting from the jth decision on state Mj 1. With this notation we shall minimize the following criterion function N A meo) = g + Eel; g(Mi» (1) The principle of optimality requires that every optimal policy satisfy the following recursion relation: fN(M) = g(M) + min [fN_1(M:)Pq(B|M) + fN_1(MC'l)(l-Pq(BIM)] (2) where q ranges from 0 to n inclusive and Pq(B |M) is given by Theorem 11.6. lheorem IVA If P is an optimal policy which chooses the act Dj (M) for an M = [:7] such that bj + wj = n, then M is terminal. Proof: Consider fk(M) for k> n(n+1). The optimality of P requires that fk(M) = g(M) + fk_1(M) but k is suffi- c iently large so that fk(M) = fk-1(M) which implies g (N) = 0. But g(M) = 0 if and only if M is terminal. This theorem allows us to reduce the number of acts wh 1 ch have to be examined in order to find an optimal policy. We need not look at those acts which would have us draw from an LII-n whose contents are already known. lt'iifi' 26 In order to implement the dynamic program on a digital cxmnputer, it was found convenient to further restrict the class WF. of all irreducible information matrices and to 'hnpose an ordering on this restriction of ‘mr. This order- ing and restriction are of no value in deriving the dynamic program but they do serve to reduce the amount of calculation and the amount of core storage required to implement the dynamic program on a computer. . , b * Convention IV.l For every information matrix M = [w] 61% relabel the urns until the columns of M satisfy the follow- ing conditions: 2 '= ... - 1. bi + wi b1+1 +wi+1 for 1 0,1,2, ,n l and 2. if b. +'w. = b. i i 2 1+1 +-wi then bi bi+ for +1 1 i = O,1,2,...,n-l. LIIIi the remainder, all information matrices will be written in this way. Definition IVA Let >> be the ordering on 722* given by: * * M = [3*] >> M = [:7] if for some integer k S n either 1k 1: 1. b. + w = b +-w, for j S k-l and J j j J b+ 36 >576 >l4,400 >((k+l) !)2 Number of elements in 772* 12 122 1746 ? The dynamic program is now implemented by considering first, candidates for the last M. It is a terminal position so that f0(M) = 0. Now, consider the next to the last M. The only possible image under any optimal policy is the last M so that f1(M) = 1. Since the ordering was chosen in such a way that for any M€m* all of the M: and M3, for j = O,1,...,n, are higher in the ordering than was M, fk+1(M) is calculable as min [i +P (BIM) - f (MT) + (1 - P (BIM)) - f (M.)]. 3.613 1 R J j k J When we have calculated fL(g 8 g) , for some L 2 n2, we have calculated the minimum expected number of draws to reach the t erminal position. Appendix 1 contains a FORTRAN IV computer program to 1.1 1: ilize the above method to determine the minimum expected number of draws to the terminal information matrix for small n a (n = 2,3,4) . Table 1 at the end of this chapter (page 33) illustrates th is dynamic program for the case n = 2 and table 2 (page 34) Presents the case n = 2 as a tree diagram. 30 The dynamic program for n = 3 is presented as a table in Appendix 2. Since there are 122 information matrices for the case n = 3, no tree diagram is presented. It is a very difficult task to write down explicitly an optimal policy for solving an urn model of order n. However, it is possible to give a general rule for the first (n51) + 1 moves of an optimal strategy, for all n. If we use this strategy for the first (n21) + 1 moves it is possible for small n, to give a complete description of an optimal policy. The rule goes as follows: First, draw one ball from each of n urns. Suppose this results in k white balls and n — k black balls, then draw 1 more ball from each of k - l urns from which white balls have been seen and 1 more ball from each of n-k-l urns from which a black ball has been seen. The urns from which 2 balls have been drawn have 3 possible compositions: WW, WB, or BB. Now from each of the urns of equally seen Composition, break all ties by drawing one more ball from al 1 but one of tied urns, and continue this process of break- ing ties until the observed composition of all of the urns is distinct. The reason that this process is the start of an oPtitnal policy is two-fold: 1. no position is a terminal 908 1tion if the observations from 2 urns are the same, and i J 31 2- no draws from a 3rd urn will ever distinguish between two tied urns. Since the tie will eventually have to be broken to result in a terminal position, and since no draw except from one of the tied urns will ever distinguish them, the rule of the preceeding paragraph is simply to break all F‘ ties as soon as possible. a This rule gives at least the first 23%;12 + 1 moves since, for every j, if we have drawn j balls from an urn there are at most j + 1 possible distinct patterns of black and white balls that can be observed. Drawing 1 ball from each of n urns takes n draws, and at most two com- positions can result (black ball seen or white ball seen). ])rawing one more ball from all but one of the urns from which as black ball has been seen, and one more from all but one of c11e urns from which a white ball has been seen requires at Ileaast n - 2 draws (it is possible that all of the balls seen are the same color). Now there are at most 3 groups n-2-3 draws. (>1? ties, and breaking them takes at least CIc>r1tinuing, we see that the total number of draws until all ties are broken is at least n-l 1%E_(n_1) n + E (n-j-l) = n+ n(n-l) - i=1 — 4—1“ “'1 + 1. The rule given above cannot be a complete policy since o I .. .ll... . I Irr'rl. . I _ . ~ . .I'tlbrll‘Lelhf p . ..v r . 1"1 32 0fl 2 1%)- by theorem IV.1, and if n 2 2 n(3+l) > ngE-lz + 1. With this rule above one can easily verify that an optimal policy for n = 2 is to draw from urn O and urn 1. Then, draw from urn 0 and if the resulting M is not terminal, draw from 1 again. This strategy requires 3% draws on the average and is the smallest possible. For n = 3, this rule says to draw from urns 0, l, and 2, then break all ties, reduce all matrices to the corresponding irreducible matrix and then reorder in accordance with convention IV.l. This will yield the following irreducible information ‘nuatrices: _2100 _1100 =0100 M1‘[01oo]’Mz‘[1010]’Ma [2010] _0211 _3100 _3210 M4’[3010]’M5‘[0121]’and M6—[0123]' Referring to Appendix 2 the optimal policy for continuation frorn each of these can be found, and it will be seen that tikl<3 Ininimum expected number of draws to determine the composition Of all of the urns is 7 31%. For n = 4, the computer printout of the dynamic pro- gram is available, on loan, from the Statistical Laboratory, Mi ch igan State University, East Lansing, Michigan. There the ml-‘-13°Ltnumexpected number of draws to determine the composition of a~11 of the urns is found to be 13.136- Fan ‘ 1‘ x “1' .1“; " a .. 1 33 in H in H in H N: N N: N «\H m a 25 eases QN 2N 11m in «\H N: «\H m :5 Ne z: in H in H in H N: N N: N «\H m 25 Has: in in in N: «\H N: H m 25 one 2%. H :3. N: e. m3 m: in «\H «\H N: SN m: N\H a: 3 Na. N: N: 2N m: «\m N: e: 1{H “in m: a: 9.?va V V V V V V V in V V m: OH HO NO HH OVN NO ON NO ON NC m\~ I-IO V N: A O CO 00 OO CPI CO CO 00 OH HO OH HO Flu-l o av £50m umm .omuH HQ N H o Aim a a com cow oom OOH HHO OHO OOO OOO HO H Q OOH NHO HO OOH OHN rd OOO ‘ b on OOO ..‘VNQ so 34 o . HHO H OHO OOO J OOO H OON O OON OON N wanna V. THE URN PROBLEM AS AN INFORMATION THEORY PROBLEM A different approach to solving the problem in the first chapter is provided by treating it as a problem in information theory. The essence of this different approach was expressed by D.V. Lindley [4] as follows: "... although indisputably one purpose of experimentation is to reach decisions, another purpose is to gain knowledge about the state of nature (that is, about the parameter) without having specific actions in mind. This knowledge is measured by the amount of information ... The following decision procedure presents itself: choose at the first step to perform that experiment whose expected information gain is the greatest, and from the resulting state, perform next the experiment whose expected information gain is the greatest, continuing in this way until preassigned amount of information is achieved. This strategy will be called the "maximum information strategy". As our measure of information we shall use the Shannon informa t ion. * Definition V.l For M 6771 , let 1(M) = 2 p (H) log p (T!) nEH(M) M M .35 36 The reasons for using Shannon information as a measure of information are well known; see [3]; [4]. The following definition and the theorem are due to Lindley [4] and are stated here in the notation we have developed for the urn problem of order n Definition V,2 (Lindley [4], Defn 1) The expected information provided by an experiment D(M,j) with prior knowledge M is 1(D(M.j),M) = 1(M:)Pj(B|M) + 1(M;)(l-Pj(BlM)) - 1(M) Theorem v.1 (Lindley [4], Thm. 1) I(D(M,j),M) 2 0 for all n v'c jEIO and MEWZ. The following theorem is a characterization of a termi- nal set in terms of information. Theorem v.2 M is a terminal set if and only if [(M) = 0, Proof: If 1(M) = 0, then 2 PM(W) 10g PM(fi) = O TTES n+1 ‘Vhich implies PM(fi) = O or 1 for all n E Sn+1 or that t . here exists n0 6 Sn+1 such that PM(n0) = 1 and PM(n) = 0 if n i no 37 since 2 PM(TT) = 1. TTESn+1 H(M) is a singleton. If M is terminal then there exists no Such that H(M) = {no} and PM(fi0) = 1 and PM(n) = 0, for n # no therefore 2 PM(n) log PM(1'I') = PM(110) log PM(110) = 0 "ES n+1 Heuristically, information provides a criterionfunction which at the very least goes in the correct direction, in that, greater information is "closer" to a terminal position and further sampling will lead on the average to an increase in information. Thus, the procedure which at each stage chooses that experiment which has greatest expected information gain is not an obviously bad strategy. For n = 2, it is one of the optimal strategies. An example from the urn model of size 3 will show t:hat the maximum information strategy is not a good strategy. JIts expected number of draws until a terminal position is E3 trictly greater than an optimal procedure. The tree diagram 15<2r the first 3 draws of the maximum information strategy is sIlown in figure 3. The Succeeding draws for the maximum iInformation strategy coincide with an optimal strategy. 38 O O O m mamas Hmsowufiuwa qm\m m I o o o o o o o NV e\m O O O O m\N «\H \H O O N usage Heeosuaeee O\H e I O O O HV O O O H N\H O H mo O O H N\H eases Hneoauaeee O\H e I O O O N N e\ O\ O O O O Om Hm OO O O N . O O O O e\m Osage HeeoauHOOe em\m m I O O O m m manna --II N 00 CO CO SLSL 39 The first difference between the maximum information 2 O O O (O O O O)° th strategy and an optimal strategy occurs at M = The maximum information strategy is to draw from the 0 urn, while the optimal strategy is to draw from any other urn. The maximum information strategy has expected number of draws until the composition of all of the urns is de- termined equal to 7 11, whereas the smallest expected number 27 of draws until the composition of all of the urns is determined 19 as 7 36’ The question of the optimality of the maximum infor- mation strategy for an urn problem of order n for n > 3 is unanswered. Also unanswered are questions of optimality of the maximum information strategy for measures of infor- mation other than the Shannon information and for criterion functions other than the expected number of draws to deter- mine the composition of all of the urns. . . 1 . A llmlflf. . , v 1 ll I 4 ll 1 l 1. 9| {ill ll Jr 1 l . I! l l lrlalllt H. 11": l Illll-hlmnn “11.1”. ml 11.. .H‘ J. Y [1] [2] [3] [41 [5] BIBLIOGRAPHY Bellman, R. Dynamic Programming, Princeton University Press, Princeton, New Jersey. Blackwell, D. and M.A. Girshick Theory 2f Games and Statistical Decisions, Wiley, New York. Khinchin, A.I. Mathematical Foundations of Information Theory, Dover, New York. Lindley, D.V. "On a Measure of the Information Provided by an Experiment", Annals of Math. Statist., 27: 986-1005. Shen, Mak-Kong "Generation of Permutations in Lexico- graphical Order", Comm. ACM (1963), p. 517. 40 APPENDIX 1 FORTRAN IV program for the dynamic program to solve the urn problem of order n. 41 'Ila. - I 112“: - . . 1.4 .v [.1.:....u 1.1:. .I . . , in, y... .lJVVll’d/Llll I’P L11 73f ..n nlll'lr A s» NFACT 2(1) P(I,J) PROB(I,J) PP(I) C(I) DICTIONARY the number of urns in an urn problem of order n. N = n + 1 (n+1)! the information matrix MI in packed form the Jth coordinate of the 1th permutation on 13 in lexicographical order Pj(BIMI), the conditional probability of draw- ing a black ball from the jth urn given the past observations MI the posterior probability of the Ith permutation n of IO the smallest expected number of draws to termi- nation from information matrix MI 42 Al .Iq “‘39.? n '\ V0 v . Yr):- '\ ~ vn'Nc 10", .. .t—H'r':‘,M(L:,c~.‘ITQT.fC.\ I FV(L)’_: Jfizp 1.! \ 1:!¢(W).“.S(W~JJ) no T“ \ hunt-1 (En Tn lJ=Q(\n'» .— nur- :‘1 {30:11 3 :f‘l-rl— TO 1' “DB 1"" {leF'f‘f-f) H. 7.. 1,1].7. J 1,."11 .1! TD 9“: :N’-—‘,"+l T=3olNDVXI ,.1 ' 'N'TIM,_I‘— V K'T‘xc y; '\r\. .7 1 ‘. ,: T '~' I: ‘\(~._ (1 . (\'\1.7 T; ( \II+L) l! ‘,.l_ 3".,’) "'0 Ti" tr -F(L) A (N-‘.A'+‘ ‘,/?+fl.l n.1fi'flrx7’ \ 43 D( ‘ .30 ,G).D’—'V(‘.D{1),E3Q’l71(7r51'1'1'g,‘7(7pn(- (77?) .1'.( innn, 44 C C3NT 1 Nut? firw a K:1.N D(JJnV)= g(K) —1 JJ=JJ+ 1 so To a ?=: CONTINUF 9 TF(JJ.NF.(NFACT +1)) CO TO P?OO V(:! 7(VK) = 0 D6 no 1:1,M (”7 ”PFQ( 9(J+N) : IITTT(J) - 9(J) GO TO 170 $(J) = c1(.J---1) S(J+N) = 9(J+M—1) ]F(J.CQ.KKK) @fl TD 2100 coMTJMUC l:(lo=0.]) GO TO I?! fflMTIMUK mmmz m_1 no yes 1:1.Nwm YF( 1*OT(N+1—I) .CC. IT“T(M+1-I) = ITOT(V+1 —I) +1 11LL=M+?~! I”(LLL.CT.M) ”0 T5 ">”‘ 15:11 .JzLLJ-.~! TTOT(J) 20 73C) T0 In“ (StimTIMuF IF?( (N—1)) GO TO lTOT(!) .GC. I‘rnT(1)= ITOT(J) + 1 63“ 1:4 J=?9N I‘TOT(J) =0 ““9 1CA YZIQN C (1) = IT°T(Y) IT“T(N- Tl) re To is? 17((§(I)oNE'o(J*l))aCP. (S(I+N)-N7-_.(N—J))) CO T0 1?4! 3”: O 26;! PD(L)*Rl-"(D(Lol)9$(l))* QlC(l"‘1—D(Lol)0 9(TY)) QDOD(VK.I):O. U 9 m ?9] 'V \Q'r 1W6 90:; I..--__ 47 1F Q' 1+A-g’) A (l :<1).Nr. 311—1)).09. (sc our. C(I+N-1))) Co Tn 951 DDQD (was ,1) :: JQCD ("1K 0 1‘1.) lF((Q.(I) + S(I+M)).Fq. (N-‘l)) CC) 7". O0 Pee L: INDEX}. C” T“ ?F? DDOD(VV913 : DDOQ=(7(KK1»<7/11o>*rio>/(I10/1o> WDITpiéio°OJJJ KK.Z(KK)9(§(1191:1oIO)o(DQOD(KK~IJ.I=1.=) FODMAT(lmollqolnlfiqu10.1) am To 1?? 37(VV):0 “TM“ 791 1:1,m -;~ (KV)=7(KK) +(er1*10**l+(l*1)*30**(w+l) FZ(1):M_I S=<2+N>= I-J QDFIQ (l(.‘(qy) I O. A O 250 T0 ?000 ”.T) YMAM I .". Cir-305053 _w. I TGTAL l! KK ’5‘(VK) H (‘1.(fl :>ITC(A1.7}OO) KK9(§(l)0'219:)1fi(KK)9(Q(llol=fioln) ’(n(: WK—j l“(11 : 100. Dt". $90G J:] .m D” 1307 1:1,10 Ir?TIW ?Oha jDKnfifi 3] Kn r“ 9101 .9 2 9m? NO: 22 r: .2, '1“:1”4%(y+1) “(1):(7(KK)—(7‘le/‘ln)*T'O)/(110/10) 1: (9(4) +s ’(JJ)= 9(Y) “0 Pins !?(M(JI.JJJ .N’. 7(17} :11 K.» ." I TJ‘N'T \ .eer-T 1K1! ;r.° r, C n r: n r: t: '3," 'Dl'u'fj ‘f\ '3'".E l: 1 . I((<(JJ)+§(JJ+N)).KT, (C(y) +C(1+N))).OQ.(((C(JJ)+Q(JJ+N),.rq C (JOHN) “(Ii rl‘ f: vfhnrrlnfifl" T 17 :2 "‘3 (T+’\‘*) 2. Jqfil 9 "-' ‘(v'k’ll‘1 C" T“ 9 J»? : M«i~C£?7) 1H: ymrnnwnTrhN VATQIX JJ =!~ M 1:.JJ o N :Q(I+M) 7:IV+1(I)*1”**1 ("L") 1310‘: I '3 WK,” Y ‘HIIL' !F(?7.Nc.?([ ;. no To 2109 QD(:Nhex?) = all) +1 :F(:Nan1.FQ.1 3 ”D T“ 2304 an Tn 9’30}? I“f‘_1'\lTl'\" H: L-z’J)‘: ram T Viv! 3" rat-351:: { Kk’ . .)\ ‘35)77f ‘ l '0 TO 91”“ +(.-mnhn(VK,J})*DD(>W qurjffi 6:100 ”(797 .3004 1005 72 7a 7:. >4 h 50 C(KK) : AMIN1(H(1)¢ H(9)9 H(Q’O l”<fi(kk1.ce.ioo.o) Cd> c>c> O O O NO v-l r-i O HO c>c> c>c> c>c> c>c> c>c> c>C> c>c> vac: c>~4 c>rc sac: r4c> c>F4 CO 00 Q0 OH HO O O O o c o o o xwuumz coaumauowsH 54 ON\NH N\m om\m NH\O mH\m omxm ma\w o¢\mm o\H O\H me\mm mH\m N\O m N\m m n\< n mH\NH m N\H m mH\NH m «\m m mH\w.w: m<\mm e w\H e m\H s w¢xmm # MH\m q N‘s m ON\NH m ex» O -meNH m NxH m mH\NH m m? n N\H e wexmm-e. OOH e O‘H.q. O«\Om e N\H e sxm m “\m m oNaNH- m wam-e N\H m O~\m e OH\O.m fi' ON\mH OeeH.m w\H e OsH e OeXH m mm\mH # N\N OHxN Manes NxH NHxN Osxm; maxOH MN\MH mxm m\H mmxea. maxm N\m Nxa .maxm Oxa NH\O OH\N NH\OH ON\mH me m\H NN\OH Nme «N‘s WXM NH\O «\H maxn MN\QH mxm. axe mmxn MH\w. NXN “\m OH\m NH\O NxH OH\HH OH\N mes ON\m mew ass. mm\ma ma\¢ curl OO OH o1: c>c> c>c1 c>c> c>o 014 0.4 r10 r10 c>¢ c>¢> c>c c>¢ c>F1 CO at.» OH HO NO OH OH 00 HO Flt-l <30 HO HO v-lr-l HO OH HO OH Fir-1 ON ON ON ON NO. NO ON OIO odd 55 «\m N m\H m wxm m m\m n mxfi m m\N m N\H m m\e,N. m? N m\e.N NxH m N\H m M\N n e\m N mxe ~ mxH m OH\m m OH\m m m? N m\w N. N\H m eaXHH m OH\m.q. N\H m «\N m «\m m\e mxe Ome OO\N m\H «\H «\H waxm ¢H\HH «\H exH mxe nxq m\m mxm nxu mxa w\m, N\m mxa O\~ was. «\H m\<- m\e- N\H Nxa mxa wxm. N\m «\H N\H N\N OxN N\H ~\H OHeH OH\m OH\m N\H N\H N\H N\H N\H «\H N\m N\H «\H «\H NeH: OH\OH 0H\HH OH\¢: ~\H N\H N\H «fin N\w i OO r-IO ON OH OH I 043 c>d> c>c> c: c>c> c>c> czq c>c> c>c> c>c> c>c> c>c> c>—l C>Fl racy c>r4 r4c5 Flr4 c>na c>OJ c>oa c>ou NO NO r-lv-i NO NO NO HH Flt-l ON NO NO HH ON NO. NO NO HI-l NO 1 q . . . l 7.! I r l . l . . 3 0 III! \ '41.]. HA.!..1.!'I!|I . .- 1 .11. in: .....i....l_oaux.nb... z... n I . . .1 lwlllhaulru lie- Fritlfféknlf . . 56 em\m O\H O\H emxm mxu M\~ «\m «\m oa\m m m N em\m m O\H e O\H v emxm n N\H N qu N OH\O N em\m m ,.OxH e OxH q en\m O «NO N OH\N N N\H N «em N OH\N N N\N Oxm O\e O\H N\H m\N mxH «\m «\H is «\m m\~ «KN O\m O\e m\H N\H N\H m\H N\H w\H «\H e\m m\m m\N O\n m\<. mxfl N\H «\H «\H «\H «\H N\H Ome m\N «\H #\m wxn N\H oa\m OO 00 Pic: c>c> c>c> c>c> C>Fl FlC> c>oa c>c> c>c> pic: c>61 c161 c>o¢ c>c> c>c> c>oa c>c> our: OH OO ON ON ON HO c>¢ NO NO ON ON NO OO 00 NO HH NO NO ON on HN MO‘ NO NO N NO 57 N\H N\H NN\m O\N e\H O\m m\H m\H «\H mxh N NxN N\H HH\e e\H Oxs «\H O\m m\H m\H «\H mxn N m m N\H NxH HH\O ON\mH O\m «\H O\H n\N O\H m\H O\N mxH HH\O N\N O\N OH\HH e\n .... mxm e\H OH\N O\N O\H O\H NN\O eH\m Oxn OH\HH «\m me m\m «\H OH\N mxm Oxm O\m NN\O eH\m m\N m\N O\H m\e m\N O\m m\H m\H OO OH HO OO 00 CO OO 00 OO OO OO OH OO c>c> c>¢> c>c> c>c> OO q-s' t: c> c>c> HO NF'I OH 00 OH HO OH HO OH HO on NO NH OH HO OH no N NO ON 01:: .l . 1 ... 1c 111 l l. l11l V. I ’ ‘fl .- WY... 0»..- ... .......:.... ..lf...1.l,l. ..WH.L:.M1..m...HFnu|1 ..1?.lil.ll|.l“l4u.t. .... ... 111.1 ...... flulell1 - I .1 l .1 . . . .Yi 1.....54‘ It 91 11 . 1 l . . . . .ll. 1 1. .....1.. .1 Jul ..1 . .1. .l..1.l.. .wlu'hxvflwvfl.’ A 4“”th ...m . Emm- FFlim r1411" ...v. 'Illlnrrvllu .lllllluflllw. 1.!8.ll .. 1 . : . 1 ... . 11 H .l -..... .11.... .....1- . .. ...l..1lM..1..ll.1.1....l.l1ul... .m.11l.1"mln.1.r111lfll.fl.l1lllll.l1l.ll.1.1. _r , -11 . ..l... ..ll ...Wl; ! “of. .... fill- - 1 1l .1 . .11.1--.-lllll1ll- 1 -. . .111: lllll.-- 11d ‘58 NHxH .M\H NxH N\H m\H ~H\H m\H «\H oa\n “\m -\m NH\H «\H «\H N\H M\H ~H\H oaxn wxa N\H oaxn «H\m HH\¢ NH\H Ndxw N\H «\H NH\m NH\H oa\n «\H NxH m\H ¢H\H HH\¢ E ¢N\ma w\m mxm ¢~\HH «\H OH\0 ~\H ~\H 0H\m N\m HH\0 «\m ¢N\MH w\m w\m ¢N\HH «\H oa\n «\H «\H oa\m ¢H\m NN\mH N\H ¢\m «\m «\H «\H «\H oH\n NxH N\H m\N QH\HH NN\mH c>q> g>d> c>d> c1° c>C1 C10 01: c>c> c>c> c>c> c:o ON HP! c>a1 r4d> cr»1 CO OH OH OH 00 .410 140 cm 'HO c>¢> N OH OH HO HO cm «10 c>a1 Hl-l HO on HO mo p10 Och &1¢ o-a N clad no mo 59 «\H HHxOH mH\m OH\m nH\m HH\o ~\H «\H “\m «\H m\q HH\¢ mH\q m\< ma\q HH\¢ «\H «\H “\H «\H m\¢ HH\¢ MH\o m\q ma\m HH\¢ m\H 2N R\m m\H m\~ HH\~ ma\o m\m m\u mH\n HH\¢ n\H m\N M\H m\n HH\~ mH\o m\H mH\~ HH\¢ m\~ M\N m\H N\N m\N m\q Ha\m mH\m m\¢ m\H ma\¢ HH\~ Sm 0:: c>¢> C10 och c>o ova c>r1 0'4 Pic o-q 0.4 Fdo ~1H 00 OH QC) 0 ¢ Hé O‘V HO ND OH ON HO ON ¢v4 Bil-l HO QI-i HH MO NO NO ON on No ON ma mo m ('10 OM NI-I MO "30 i I I . 1. l ll 'll’l. fllL ll |1vl.l 60 N: QN Qu mxu uh. 2m in N: in N: QN mxu M: N: in in n: to NE” in in 53 N: N} CH 3m m\N N: N: m: o: N: N: n: in Cm Q.» 3m 2N N: N: m: 10.3 q: 3H 5}” :H 2N NE in in :m C.» m: in CO CO Heb CC: 00 OH Ho 00 oo oo 00 HO ON HH ocb co oo 00 Ho: on on QH co 00 N ON HI-l HN No 00') NO I-lv-I on no r-Iv-l ma ON no mo NH NI-l HN MO OCH QM 2 2/5 1 4/5 1/5 1/5 1 3/4 1/2 1/4 2 2/3 1 2/3 4/9 1/3 2 2/3 1 2/3 5/9 2/3 00 OH on ('10 1 3/4 1/4 3/4 DO HO om Nr-l 61 2 2/5 1 4/5 4/5 4/5 1 3/4 1 3/4 1/4 1/4 o.—1 01—1 61H «10 1/2 1/2 01-1 o.-1 .—1N mo 1 3/4 1 3/4 1/4 1/4 1 3/5 1 3/5 3/5 2/5 OH HO on NO 1 3/4 1 3/4 3/4 3/4 OH Or-‘l on (”'30 1/2 1/2 v-IO HO om NH 1 3/4 1 3/4 3/4 3/4 HO do on v-lN 1 3/4 1/4 1/4 00 ON NH MO 1 1/2 1/2 1/2 ¢¢> HF! on no 1 3/4 3/4 3/4 OD NO cam AN 1 2/3 1/3 1/3 OH ON NH mo 62 m \ N H 1/3 1/3 HQ Hr-I om mo 3010 0311 1 2/3 2/3 2/3 O 1 2/3 2/3 2/3 HO NO om HN 1/2 1/2 ON ON Nt-l m0 1/2 1/2 Hit-1 Flu-I on NC 1/2 1/2 NO NO on HN Cm HN Nr-l MO t a ......r w... u.’ui~..§ttvt - D k ‘ ”lllllllllllllflllllllllllllljlljlllls