Reference / Paper · 1938
The SIS statistics textbook: defines the phi test (p. 38), cross-product sum/chi test (p. 52 ff.), kappa-r = 0.0385 and kappa-p = 0.066 (pp. 81-82); lists E(phi) for Japanese romaji 0.0819 N(N-1) (206-page scan incl. file cover; declassified 2013)
, CAUTIOR1 UOOllllll WILL • UISb PCS~...,.._ ORLY, DO NOT 10204 llCOBDS CH.OGE-OUT ·-·~:::s~TS FILE OR SERIAL NUMBER AND SUBJECT TO RETURN TO . INSTRUCTIONS _.,..-........ 10 Feb 61 25 Jan 61 Fram File ot l:?.'cial Consultant (Friedman) Statistical Methods in C~sis, Revised Edition. Register No. 193 · Serial No. 1008 NAME AND EXTENSION OF PERSON REQUESTING FILE ORGANIZATION, BUILDING, AND ROOJll NUJllBER Mr. William Frie 310 2nd. Str. Mrs Christian AG-2 LI 6-S520 SI Wash. D. c. DATE RET'ND. INITIAL HERB NBA Ft. Geo• G. Meade Mdo WREN"TRAMSFllRRING FILE TO AftOTHEll PZRSON, COMPLETE SELF·ADDRESSE]) TlUIJISFEB COUPON BELOW, DETACH, mTCH TO BLANlt LE'l"l'Ell·SIZB PAPER AND PLACE IN OUT-OOINO JllAIL SERVICE. 2ND TRANSFER COUPON lllll:::f" TO: 0 p N C)fmrRUiliiB~(iiimilciiiliiidiiii*iil° M Peclassified and approved for release by NSA on 12-26-2013 pursuant to E.O. 1352§ _ _ _ _ __ Register No. 19 3 WAR DEPARTMENT OFFICE OF THE CHIEF SIGNAL OFFICER WASHINGTON STATISTICAL METHODS IN CRYPTANALYSIS REVISED EDITION 30 April 1959 4 This document is declassified by authority of the Director, National. Security Agency. fd!if~-1 Colonel, AGC Adjutant General fi Statistical Methode in Crypt.analysis~ = Revised Edition da.ted 14 December 1948 9 signed Lt.,. Colo John A~ puty Chief, Army Security Agency, to Chief, Ind ors IL l :NO ACCOUNTl?IG J:ECESSAKr . rumsTRAT1Ct1 CANCELED by. Authority Hqs, ASA ltr dated Z'l Feb 46 2d Ind 11 Var 46, siened: HAROLD G. HAYES,. Cole, Sir,nal Corps Acting Chief, ArtJJ7 Security Agency I REF ID:A58459 CtniRtkn:Httl Register N'} WAR DEPARTMENT OFFICE OF THE CHIEF SIGNAL OFFICER WASIDNGTON STATISTICAL METHODS IN CRYPTANALYSIS REVISED EDITION TECHNICAL PAPER By SOLOMON KULLBACK, Ph. D. Aaaociate Crgptanalgat SIGNAL INTELLIGENCE SERVICE UNITED STATES GOVERNMENT PRINTING OFFICE 'WASBJNGTON11H8 193 REF ID:A58459 PREFACE It is here my pleasant task to acknowledge my indebtedness to Mr. William F. Friedman and to others of my associates in the OCSigO for their encouragement and assistance in the preparation of this book, and to the instructors and students of the Signal Intelligence School for their earnest efforts and cooperation. In particular I must acknowledge the aid of Mr. Frank B. Rowlett, Dr. A. Sinkov, Lt. L. T. Jones, U. S. C. G., and Capt. H. G. Miller, Signal Corps, in carrying out observational tests of the theories and the numerical computation involved in the preparation of the charts and tables included herein. S. K. I REF ID:A58459 CONTENTS Section I. Introductory remarks------------------------------------------------------------------------------------------------------ p.,_ 1 PART 1 II. Statistics General considerations of probabilitY-----------------------------------------------------------------------------·_ 2-3 III. ____________________________________________________________________________________________________________________ 4-6 IV. Frequency distributions.----------------------------------------------------------------------------------------------7-23 V. Applica.tions________________________________________________________________________________________________________________ 24-47 VI. Matching alphabets--------------·----------------------------------------------------------------------------------------- 48-80 VI I. Coincidences.------------------------------------------------------------------------------------·---------------------_ 81-92 PART2 VIII. Frequency dat&..----------------------------------------------------------------------------------------------------·---- 93-132 IX. Statistical tables--------------------------------------------------------------------------------------------------------- 133-144 X. Summary definitions.-----------------------------------------------------·----------------------- 148-157 145-147 XI. Appendixesof formulas and __________________________________________________________________________________________________________ XII. Charts_________________________________________________________________________________________________________________ 158-190 (V) REF ID:A58459 STATISTICAL METHODS IN CRYPTANALYSIS, REVISED EDITION SECTION I INTRODUCTORY REMARKS Paragr&ph Introduction__________________________________________________ Purpose _______________________________ ~----------------------- Paragraph 11 Arrangement of contents__________________________________ 2 · . 3 . 1. Introduction.-a. An examination of either plain-text or cryptographic text will convince the reader that the occurrences of the variou$ textual elements do not follow a definite.rigorous mathematical law. b. In the solution of a cryptogram the cryptanalyst deals alniost excl\!.Sively with un~er-, tainties as regards the relationships of its textual elements. Accordin~. he is cpncerned with the questioui Whftt.~..the.prob.ability of.a c:e:r:titm .e~eJ;t.t?. Of P.Q.U~!:l,. there are certB:i.n ~ausatj.ve or controlling factors which determine whether or not the event takes place .and with su:fficfo~t information the answer tc;> the ques.tion would be either: "It is certain. to occur,". or '~It" iS c,ertain not to occur." .. . . c. The )llatheinatical theory of prphability and statist~cs is accordingly of importa~ce tQ the cryptanalyst since it provides a means for the quant~tative analysis of the, uncertain.ti~~ with which he deals .. It also provides a means whereby he may study the behavior of groups of symbols and draw conclusions therefrom. . d. It. is not very often that statistical analysis alone will enable the cryptanalyst t~ arrive at the solution of a cryptogram. Statistical arwlysis wil,l, however, enable the cryptanalyst to evaluate the desirability of pursuing certain procedures and will indicate the most likely .order in which to try various possible steps in solution. . , · e. Of fundament~ Importance in the ~pplication of statistf.cal tecpmque .to cryptography are .the various freq1,1ency tables relating tO th~ characteristic frequene~ of textual elements of different langu~es. A numbeF, of such tables will be fou,nd in sect~op. VIII. ·.· . .. • .. .j. It must be emphasized here that .the methods and.proced;1µes tq be,clisc~$~ed:JJ.e~in i:µ:e a'means to' an e.rid, and not all end in themselves. . - . , . 2. Purpose.-This book has been prepared to prc;>vide cryptanalysts .with· &n introdu,ctio~. to certain concepts and methods of the mathematical theory of statistics whicli. are useful in cryptanalysis; and to provide the reader with certain formulas, charts; and tables .which have been found to he. of assistance. in the solution of a variety of cryptanalytic problem.S: 3. Ar.rangement of contents.-a. The book is. divided into two parts. In the first part, there are: (1) An exposition of the underlying theory; (2) .A presentation of many useful formulas; (3) Procedures for the use of these formulas in the solution of problems; (4) Illustrations. and examples. . . .. . b. In the second part are charts and tables which will assist in the application of the metho~ discussed in part 1, and a number of append:lxes presenting the mathematical development of formulas presented in the first part. There is also a summary of all the formulas and defuiitions found throughout the book. c. In keeping with the purpose as set forth 'in paragraph 2, no attempt has been made in the exposition of part 1 to present the mathematical analysis underlying the derivation of the formulas discussed. (1) PART 1 SECTION II GENERAL CONSIDERATIONS OF PROBABILITY I A priori probability_____________________________________~~P: Combinations of probabilities _______________________ ~~P~ Btatilltical probabilitY--------···----·---------------------5 I 4. A priori probability.-a. A complete discussion of the mathematical and philosophical implications involved in a logically rigorous approach to mathematical probability is beyond the purpose of this book. Herein it will suffice to use the following definition of a priori probability: The probabUi1y that an event will occur is the ratio of the number of favorable cases to the number of total possible cases, all cases being equally likely to occur.' By a favorable case, is meant one which 'UJi1l produce the etJent in question. ·" b. The probability for the occurrence of an event is always a positive fraction not exceeding 1. The numbers "1" and "O" are taken to represent certainty, since in those circumstances every ease is either favorable or not favorable and'will produce the event in question or will not· produce the event in question. If the probability that an event will occur is p and the probability that it will not occur is q, then p'+q= 1. (It is certain that the event either will or will not occur.) c. In cryptography the probability of occurrence of each of the letters of the alphabet in various languages is of interest. It is obviously impossible to apply the preceding definition of a priori probability, since that would involve a. study of every conceivable message that might be sent. In this case, which illustrates the situation most frequently encountered in practical statistical work, there must be introduced the concept of statistical probability. 5. Statistical pr()bability.-a. The fundamental .be.sis in .statistical probability is the fact that, for all. practical purposes, the difference between the unknown a priori probability and the ratio of observed favorable cases to the observed total number of cases, can be made as sm8ll as we please by indefinitely increasing the total number of observed cases. 1 The limit of the :ratio of the number of observed favorable cases to the total number of observed cases, as the latter number increases indefinitely', shall be called the probability that the event occurs.1 b. Thus, in order to find the probabilities of occurrence for each of the letters of the alphabet, it is necessary to examine a large amount of text. A study of 100,000 letters of English telegraphic text gave the result shown in figure 1. We thus find that the probability for the occurrenee of A is 0.07189; for Bit is 0.01146; for Cit is 0.03345, etc. c. It is usual to denote the numbers 7,189, 1,146, 3,345, etc. (i. e., the number of observed favorable cases) as the absolute frequencies, and the numbers 0.07189, 0.01146, 0.03345, etc . .(the ratio of the number of observed favorable cases to the tc)tal number of observed cases) as the relatWe frequencies. 1 See appendix A, p. 148. (2) REF ID:A58459 3 Letter A_ _____________ _ B ______________ _ c ______________ _ D-------------E ______________ _ F ______________ _ Q______________ _ g _____________ _ J _______________ _ J ________________ _ Number of occurrences 7, 189 1, 146 3,345 4,029 12,604 2,994 1,795 3,287 7,572 198 Letter Number of occurrences K_ ____________ _ 353 3,549 2,534 7,558 7,408 '2, 661 318 8,256 5,759 9, 042· L ______________ _ M-----------7-c N-------------~ . Q______________ _ p ______________ _ Q~---------~--R ______________ _ s_____________ c_ T-------·------FIGURE: I. Letter u ______________ _ y ______________ _ w _____________ _ x _____________ _ Y----.---------z_ _____________ _ Total___ Number of occurrences 2, 993 1,340 1, 401 469 2,099 101 100,000 ..... · 6. COml>in&tfoiis ·or-prooaoillties.-a. If an ev~mt· -und·er investigation is-- one of -several mutually exclusive events, then the probability that it occurs is the sum of the probabilities of occurrence of each of the mutually exclusive events. · · Ezampl,e 1.-What is the probability that any one ietter chosen at random from: English telegraphic text is a vowel? Since the event in question is one of the mutually exclusive events "finding A, E, I, 0, U, Y," the probability sought is P,=PA+PB+Pr+Po+Pu+PY where P,, PA, PB, Pr, P0 , Pu, Py, respectively, mean the probability for the occurrence of a vowel; the probability for the occurrence of A, etc. Adding the component probiibilities, as found ftom figure 1, there results P,=0.39865. It may be~een from this that approximately 40 percent of the letters of English telegraphic text are vowels. b. ·If the event under study is the simultaneous occurrence of several events, or the successive occurrence of several events, then the probability that it will occur is the prodmt of the "Probabilities of occw.Te~ce of the component event.s, provided the occurrenee of one does not effect the occurrence of the others-or, as we shall say, provided the events· are independent. Thus; the probability that two letters selected at random fr()tn English telegraphic tat ·are· vowels, is 0.4X0.4=0.16. SECTION III STATISTICS · Paragraph Definitions..----------------------------------------------------------------------------------------------------------------------------- 7 7. Definitions.-a. By statistical method we mean the mathematical treatment of observational data in accorda.nce with the fundamental laws of probability discussed in the preceding section. b. By a statistical variate we mean a variable which may assume a finite or infinite number of different values in accordance with a certain law of probability. The sum of the probabilities corresponding to each of the different values must be one. Example 2.-The variable fJ, where fJ is to represent any letter of the alphabet, is a statistical variate since fJ will assume the values A, B, 0, . . . , Z with probabilities corresponding to the values in figure 1. c. In order to be able to study efficiently a mass of data, it is desirable that we be able to oonwuft 11ewal numbers which will, to a certain extent, characterize the,data <L'IU1 dilrplay its important properties. · d. By a.statistic we mean any number computed from observed data in accordance with certain rules. The following are some of the more common statistics which are used to characterize a mass of data and which there will be occasion to use in the course of this work. e. (1) The arithmetic mean or average of a sequence of numbers is the sum of the numbers divided by the number of items. Example .3.-,.What ~the averag~ of 1, 2, 3, 4, 5? The average is (1+2+~+4+5)/5=3. (2) The weigkted mean or. average of a series of numbers is the smn of the product of each number and its weight, divided by the sum of the weights. In general, in the study .of obser:ved de.ta, the weigM corresponds to. the number of observed occurrences; in theoretli(al discus~ns, it corresponQ.s to the probability of occurrence. It is usual to omit the adjective "weighted11 since this definition reduces to the one first given. (3) Symbolically we may express the foregoing as follows: If the numbers xi, z2, ••• , x,. have, respectively, the weights Wi, w2, . . . , w,. (or occur respectively wi, w2, . . . , w,. times), then the e.vera.ge of xi, x2, • • . , x,. or symbolically x (read x bar) is given by x W1X1 +w2Z2+ . . . +w,.x,. w1+w2+ •.. +w,. Example 4.-A study of 100 sets of English text, each of 50 letters, yielded the following as the number of occurrences of the letter A per set. (4) REF ID:A58459 5 ~ '°' 1 2 3 4 5 6 7 8 3 26 21 19 15 8 7 1 100 (i. e., A occurred once in each of three sets; twice in each of 26 sets; three times in each of 2.J.. sets, etc:~:._!~~ 8.~~ra_g~ o~e,~~ o~n~~ ~f A:J:>er ~et.of 50 letters is ther~fore - (3Xl)+(26X2)+(21 X3)+(19X4)+(15X5)+ (8X6)+(7X7)+ (1X8) a+26+21+l9+l5+s+1+1 f=374/100=3.74 (4) If x is a statistical variate, i. e., if x takes on the values Xi, x2, . . . , x,. with the corresponding probabilities pi, P2, . . . , p,., respectively, then the average value of xis :t=p1x1 +P2Z2+ ... +p,.x,.. (In this case the total weightp1+P2+ . . . +p,.=1). j. The mean square of a series of numbers is the average of the squares of the numbers. , x,. is a sequence of numbers with corresponding weights Wi, w2, • • • , Symbolically, if Xi, x2, . w,., respectively, then w1x12 +wJX22+ . . . +w,.x,.2 mean square x W1 + W2 + • • • + W,. x f1X1 2 +fJX12 + • · · +f,.X,.2 wheref,=w,/(w1+w2+ . . . +w,.) (i=l, 2, . . . 1 n) I Intheforegoingwdi=l,2, . . . ,n)isanabsoluteweightandfdi=l,2, . ,n)isarelative weight. g. Let Xi, x2, . . . , x,. be a sequence of numbers whose mean value is f. The deviation of x, from the mean is x,-x. The deviation will be negative, zero, or positive according as x, is less than, equal to, or greater than i. h. The variance of a sequence of numbers is the mean square of the deviations from the mean, i.e., . w,(x1-f) +w2(~-x) 2 + . . . +w,.(x,.-f) 2 var1ance=v + + ... + W W1W2 f1(X1-x) 2 +f2(X2-f) 2 + . , . +f,.(x,.-i) 2 where the x's, w's, andj's are defined as above. The positive square root of the variance is called the standard deviation. It may be shown that v f1X1 2 +f2xi+ . . . +f,.x,.2 -(.f) 2=(Mean square of x)-(square of the mean of x). 2 11 2 The notation (i=l, 2, ••• , n) is a convenient way of indicating that i is to be replaced by all of the successive values 1, 2, 3, . • • , n, in turn. 6 i. In general, the average of a sequence of numbers is a central val,ue about which the numbers tend to cluster; the variance is a. measure of the variation about this central value.8 a The weighted sum of the deviations from the mean is not a suitable measure of the variation because it is in all cases equal to zero. The following simple algebra demonstrates this fact: w1(:e1-f)+w1(zt-f)+ •.• +w,.(:e,.-f) w1+w2+ ... +w. w1x1+w:ixt+ . +w..x.. f(w1+w2+ . . . +w,.) = w1+w2+ ... +w,. w1+w11+ ..• +w. : I , I =f-f=O The next simple possible measure of the variation about the mean is the weighted sum of the absolute values of the deviations (the weighted sum of the arithmetical values of the deviations neglecting the sign). Symbolically this would be written as wdx1-fl +toil:rs-fl + . . . +w,.!x..-fl w1+Wi+ ••. +w,. However, because ()f. the fa.ct that the variant!e is more amenable to mathematical treatment and because of its relationship with the theory of least squares and the normal probability distribution the variance rather than the weighted sum of the absolute values of the deviations is the more commonly used measure of variation. J REF ID:A58459 SECTION IV FREQUENCY DISTRIBUTIONS Para&rapb Generalitie&.--·----------·-----------------------------·----Binomial distribution.____________________________________ Normal distribution••••••••...----------------------------- 8 9 10 Paraatapb Poisson distribution ______________________________•••.•• Modified Poisson distribution.__________________ .••• Multinomial distribution •••----------------------------- 11 12 13 8. Generalities...--a. Some slight expecience in cryptanalysis will soon convince one that an outstanding characteristic of the data studied is its variation. The data which are the object of statistical study e.lways display variation in one or more respects. b. The notion of a collection of data arranged in a frequency distribution with respect to one or more characteristics is fundamental in statistical work. If n observations ociginating from the same set of circumstances are made with respect to a statistical variate, and if the individual observations are arranged with respect to their magnitude, the result is said to form a frequency distribution; to each value of the variate, there corresponds an absolute frequency. In example 4 there is a frequency distribution of 100 observations of the number of occurrences of the letter A per set of 50 letters of English telegraphic text. Subsequent discussion in this section will introd~ theoretical freq.nency distributiQilS. in Whi<,!h to each value of the variate will 8. probability instead of a definite number of occurrences. c. Frequency distributions may be discontinuous or continuous. In discontinuous distributions the statistical variate may assume a finite or infinite number of discontinuous values~ (Values which are separated one from the other by finite quantities.) The distribution of the number of occurrences of the letter A per set of 50 letters given in example 4 page 5 is an illustration of a discontinuous distribution in which the statistical variate (the number of occurrences of the letter A per set) takes on a. finite number of values. In continuous distributions the statistical variate may assume all possible values within its range of variation. In the latter case the frequency distribution may be expressed by stating the proportion of the data for which the variate is less than a given value or the proportion of the data for which the variate lies between given values. d. It is presumed that the reader is already acquainted with instances of frequency distributions, e. g., the frequency distribution of single letters, digraphs, etc., of cryptograms. e. The following is a. frequency distribution of the lengths of words in a. series of official telegra.ms; in a.ll 10,000 words were studied. correspond Number of letters per word Number of words Number of letters Number of letters per word Number of words Number of letters x, F, xo11, x, F, X,F, 1 2 3 4 390 1,028 1,369 1, 745 1, 457 1, 169 1,039 735 479 390 2,056 4, 107 6,980 7, 285 7, 014 7,273 5,880 4, 311 10 11 288 163 86 25 23 4 2,880 1,793 1, 032 325 322 60 10, 000 51,708 5 6 7 8 9 12 13 14 15 (7) 8 From this it is seen that the average number of letters per word of English telegraphic text is 5.17. For most purposes, assuming this value to be 5 will give a sufficiently accurate approximation. (This is one of the reasons why the arbitrary length of five characters per word has been adopted as standard for code or cipher text.) j. It is very desirable to be able to characterize by means of a mathematical formula the relationship between the various values that a statistical variate may take, and the corresponding probabilities (or frequencies). Such a formulation simplifies the study of frequency distributions and enables valid judgments about sample distributions to be formed. The study of the possible formulas for frequency distributions has yielded a number of important results. g. We shall here restrict ourselves to five types of frequency distributions which are of primary importance in cryptography, viz, the binomial distribulion, the normal distribution, the Poisson distribution, the modified Poisson distribution, and the multinomial distribution. 9. Binomial distribution.'-a. The binominal distribution is the first example of a theoretical distribution to be established, and was discovered by Jacob Bernoulli about the end 9f the seventeenth century. It can be shown that if the probability that an event occurs is p, and the probability that it does not occur is q, (q=l-p), then, if n independent observations are made, the probability that the event occurs exactly O, 1, 2, . , n times is given by the ~espective term of the expansion of the binomial '(9.1) · Thus, the probability that the event occurs 0 times in n trials is P 0 =qn; the probability that the event occurs exactly one time inn trials is P 1=nq•Hp; the probability that the event occurs exactly two times inn trials is P 2 nin.;;-21) r1- p 2 2 ; ••• ; the probability that the event occurs exactly x times (x an integer) inn trials (x~ n) is p " n(n-l)(n-2) . . . (n-x+l) n-z z nl n-z z 1X2X3 . . . Xx q P x!(n-z)!q P where x! (read x factorial) is equal to x(x-I)(x-2) . . . 1. Example 5.-Using 0.1 as the probability for the occurrence of T in English text, what is the probability that T occurs zero times, exactly one time, exactly two times, . . . , exactly eight times in a set of 100 letters of English text? In this <mse p=0.1, q=0.9, n=IOO, so that the desired probabilities are: that T occurs zero times (0.9) 100 =0.0000=Po that T occurs exactly one time 100(0.9)99 (0.1)=0.0003=P1 . that T occurs exactly two trmes . 100X99 lX (0.9) 98 (0.1) 2 =0.0016=P3 2 that T occurs exactly three trmes . that T occurs e~actly four trmes 100X99X98 lX 2 X (0.9) 97 (0.1) 3 =0.0059=Pa 3 100X99X98X97 , p lX 2 X X (0.9) 96 (0.1) =0.0159= , 3 4 100X99X98X97X96(0 9)95 (0 l) 5 O0339 p . . t h at T occurs exact1y five t rmes lX 2 X 3 X 4 X 5 . . = . = '· ' See appendix A, p. 148ff. REF ID:A58459 . . 100X99X98X97X96X95 e_ _ that T occurs exactly six ti.mes lX 2 X 3 X 4 X 5 X 6 (0.9) 94 (0.1) -0.0596-P, . 100X99X98X97X96X95X94 that T occurs exactly seven tunes . lX 2 X 3 X 4 X 5 X 6 X 7 (0.9) 113 (0.1) 7 =0.0889=P1 that T occurs exactly eight ti.mes 100X99X98X97X96X95X94X93(0 9 )02(o l\B=O 114s=P8 1X2X3X4X5X6X7X8 . . I • b. To find the probability that an event, whose possible occurrences are distributed in accordance with the foregoing distribution, occurs at least r ti.mes it is merely necessary to add the probabilities that the event occurs exactly r, r+l, r+2, . . . , n ti.mes. If then we use P(r) to represent the probability for at le8Bt r occurrences we have ... ti (The symbol E means the sum of the terms for all integral values of :drom r to n inclusive.) :r=r Example 6.-Using 0.1 as the probability for the occurrence of T in English text, what is the probahilitY that T occurs at least six times'in"'a set of 1001etters? In order to find the deSired probability it is necessary to subtract from 1 the sum of the probabilities that T occurs exactly 0, 1, .•. , 5 ti.mes. Using the values found in example 5, we have P(6) = 1- co.oooo+o.0003+0.0016+0.oos9+0.0159+0.oa39) = 1-0.0576=0.9424 c. For a statistical variate which takes on its possible vl;l+lues in accordance with the law of distribution given by the binomial distribution, it may be shown that. the mean value=µ=np, the mean square=µ 2 =n 2p 2 +npq, and the variance =u==np~. (See Appendix A, p. 148ff). . Example 7.-Let us take as the probability for the occurrence of .A in English text p=0.072. Then, the theoretical average value for the number of occurrences of A in a set of 50 lett~ of Eng~.t~t is~-:-np""'750(0.072}=3.6; the theoretical v&l.ue.of them~ square of the number of occurrences CJ'2) is ~=n2p2 +11pq= (50) 2(0.072) 2+50(0.072} (0.928) = 12.96+3.34= 16.30; the theoretical value of the variance (u2) is u2=npq~50(0.072)(0.928)=3.34. (In general, we shall use Greek letters for theoretical values and Roman letters for the corresponding observed vall.j.es.) Example 8.-It will be of interest to compare the theoretical values derived in example 7 with the observed values obtained from the observed occurrences of .A in 100 sets of English text of 50 letters each, already considered in example 4. In example 4 it was found that i=3. 74. Th~ mean square of the number of occurrences is given by (see p. 5). m2 3x1 2 +26x2 2 +21x3 2 +19x4 2 +15X52 +sx61 +1xt"+1xs2 3+26+21+19+15+8+7+1 rn10 100 16 70 • To find the variance we use the fact that variance= (mean square)- (square of mean), or ri'= µ.2 -µ.2 • Thus s2 =16.70-(3.74) 2 =16.70-13.99=2.71 . 1 Since p+q=l, (9.1) could be written as • EP.=1 :r ... o 10 A comparison of theoretical and observed values yields Theoretical Observed 3.60 16.30 3.34 1. 83 3.74 16. 70 Mean (µ) ____________________________ Mean square (µ2) __________________ Va.Fiance (u2) ________________________ Standard deviation (u ) ___________ 2.71 1. 65 d. It should be clear that the values of the observed means of a sequence of samples will also be distributed in accordance with a certain law of distribution not necessarily the same as the law of distribution of the original observations. The distribution of means of samples of N from a population 6 distributed according to the terms of (q+p )n is given by the corresponding terms of (q+p)nN plotted to l/N times the unit of the original binomial, i. e., the probability that the mean takes the value O, l/N, 2/N, 3/N, . . . , nN/N is given by the corresponding term of the expansion of (q+p)nN. e. The mean of the distribution of means is given by np and the variance of the distribution of ~eans is given by u~2 = ng. The Jatter equation shows us then, that if u be the variance of 2 a number of observations, the variance of the mean of N such observations is u,2= ~· This last result signifies that the sample means will show a smaller variation about the true (or population) mean than will the original observations. More exactly we may say that the mean of N observations is .JN times as reliable as any of the N original observations. j. In order to apply the binomial distribution to numerical cases, it would be desirable that there be available tables giving the values of the several terms of the expansion of (q+p)" for various values of p and n. Unfortunately, such tables do not exist. However, since there are tables for other distributions, which will provide sufficiently close approximations to the binomial distribution for all our purposes, the lack of tables for the binomial distribution will not greatly inconvenience us. · 10. Normal distribution.--a. In the case of the binomial distribution, we saw that the stati.Stical variate took on only integral values. However, for the distribution now to 9e oonsidered..l such is not the case. A statistical variate is said to be normally distributed when it takes all values between -oo (minus infinity) and +oo (plus infinity) with frequencies such that cthe logarithm of the frequency at any distance X from the mean of the distribution is less tha~'the frequency at the mean of the distribution by a quantity proportional to X 2• A more precise expression of the foregoing is the following: The statistical variate normally distributed takes on all values between -oo (minus infinity) and +oo (plus infinity) in accordance with on the following law of probability: The probability that the statistical variate lies between X-~ and X+~, where Eis a very small number is given by (10.1) p(X E) = ' E=e-(X-µ)'/2v' u ,J2r •By population we here mean the idealized aggregate of data from which the sample is supposed to have been drawn by chance. REF ID:A58459 11 In the preceding formula there are two parameters,7 µ and"· It may be shown thatµ and " 2 are the mean and variance respectively of a statistical variate with the normal law of distribution. (Hence the importance of the mean and variance or standard deviation, since aJmowledge of them is all that is necessary completely to determine the normal, /,aw of probability.) In (10.1) X-µ is the distance of the observation X from the meanµ and" measures in the same units the extent to which the individual observations are scattered. b. For purposes of tabulation, it is usual to treat ((X-µ)/")=x as the variate and to omit the factor E/u in (10.1); thus, in part 2 will be found tables giving the values of y for various values of x in accordance with the formula. (10.2) The curve corresponding to the formula (10.2) is the familiar normal probability curve, given in diagram 1 herewith. Geometrically," is the dist.a.nee on either side of the mean (or center) of the steepest points, or points of inflection of the curve. DIAGRAM 1. Normal Probability Curve: x=X-µ. " c. In practice it is more often n~a.ry to know the probability, that a statistical variate satisfying the normal law, lies between two values say X 0 and Xi, where X1>X0 • Tables have been calculated to enable this to be done readily. If we set X1= (Xi-µ)/u and Xo= (X0 -µ)/,,, the desired result is given by 1 (10.3) P(Xo, Xi)= ? rz· -y2rJz, d,u-:r'/2 The tables that have been calculated (shown in part 2) are for the value Xo= - cxi ; that is, the tables give the probability that xis less than or equal to X1. In order to obtain the result desired, use must then be made of the formula (10.4) P(Xo, Xi)=P(-cxi, X1)-P(-cxi, Xo) 7 A parameter is a "variable constant" which enters into a mathematical formula. Thus in (10.1) p. and tr are constant for a given population but take on different values for different populations. 8 The symbol ('zt (read the integral from :i:o to x1) may be traced back to the S of the word Sum. In eMenee J:r. the integral is the limit of the sum of the values of the integrand (the expression to be integrated) as x takes on values, between Xo and a:r, which differ by smaller and smaller amounts. Thus the discussion in paragraph lOc is conceptually similar to the discussion in paragraph 9c. 63301-38---2 12 A graphic description of the above will help clarify the matter. Assuming .the total area under the curve to be unity, then the shaded area in diagram 2 is that which is desired in accordance with (10.3). I I I j ; :ro Du.GRAM 2. The values that have been tabulated correspond to the shaded areas in diagrams 3a and 3b. ' -·f.4.-f-l--i-i-+++-H--J-J-.+.+++-+-+-+-H~-l--+++-+-+-1-1-4 :ro DIAGRAM 3b. I! By subtracting the area shown in diagram 3b from that shown in diagram 3a, we get the desired area of diagram 2. d. For the normal distribution 68 percent of the observations lie within a range of ±0' about the mean; 95 percent within a range of ±2u about the mean; 99.7 percent within a range of ± 311 about the mean. e. The means of sets of N observations distributed in accordance with the normal law of probability are also distributed normally; their mean is the same as that of the original observa• tions, but with variance 1/N as large; i.e., if the mean and variance of the original distribution areµ and u2 respectively, then the mean and variance of the distribution of means are p. and u2/N respectively. The remarks made in paragraph 9d apply here too. REF ID:A58459 13 j. If in the binomial distribution p and q do not differ greatly and if n is large, then that distribution is given with a sufficient degree of approximation by a normal distribution with mean equal to np and variance equal to npq; i. e., under the conditions set forth above n(n - 1) (n - 2) · · (n-x+ 1) q"-"p"=approx. 1 e_,,,_,,,,> •/2"Pf 1X2X3X · · · Xx ../2rnpq and r ~ n(n-1) · · · (n-x+ 1) 1 ~---'-----'----,-~q"-"p'"=approx.-= 1 X2 X • • • X;r. f-' • e-" 12dx ../2r - m :r-0 where t= (r-np)/npq_ g. To indicate the approximation of the binomial distribution by the normal distribution, there are listed on page 18 corresponding values as calculated from the binomial distribution, for n=64, p=~, and as given by the normal distribution.' (In the normal distribution we use p=np=32, and u2=npq · 16). . Example 9.-What is the probability that in a set of 100 letters of English text, tlle'number of voweTu· is between 3'5~5, incllisive? Taking as the probability for the occurrence of a ·vowel p=0.40, there is obtained from the binomial distribution, p=np=40 and u2 =npq=24. Xo= X - p 35-40 Xi-P 45-40 =-1.02, xi=-·-u-= . =1.02. From the table of the normal distribution, 4 899 it is found that P(-aJ, 1.02)=0.8461 and P(-aJ, -1.02)=0.1539 so that P(-1.02, 1.02)= 0.8461-0.1539=0.6922. In other words, about 70 percent of sets of 100 letters each of English text will have between 35 and 45 vowels, inclusive. h. Using the method employed in example 9, limits were calculated within which the 0 -u -= . 4 899 number of vowels (A, E, I, 0, U, Y), high-frequency consonants (D, N, R, S, T), medium.frequency consonants (B, C, F, G, H, L, M, P, V, W), and low-frequency consonants (J, K, Q, X, Z) would be expected to lie for messages up to 200 letters in length. The results have been graphed and may be found in charts 1, 2, 3, and 4. (See pp. 14, 15, 16, and 17.) In chart 1, curve V1 .marks the lower limit of the number of vowels to be expected in a message of given length; curve Vi marks the upper limit. Thus, for example, in a. message of 100 letters in plain English there should be between 33 and 47 vowels. In cha.rt 2, curves Hi and H2 mark the lower and upper limits as regards the high-frequency consonants. In a message of 100 letters there should be between 28 and 42 high-frequency consonants. In chart 3, curves M 1 and M 2 mark the lower and upper limits as regards the medium.frequency consonants. In a message of 100 letters there should be between 17 and 31 medium.frequency consonants. In chart 4, curves Li and ~ mark the lower and upper limits as regards the low-frequency consonants. In a. message of 100 .letters there should be between 0 and 3 low-frequency consonants. •These values are taken from Yule, G. U., An Introduction to the Theory of Statistics, 9th Ed. Rev. London, 1929, ch. XV. 14 No. 1 CHART -- - - e· e- ' -r- -- ' 7'" - 70 I 5: s-" ' ' 6' I - 4• '4~ ' I 3:. a:. 2:. J I - -- ~ I IS J --i-- ' l .1: --. 0 ti -- - - --- b - - 10 20 30 40 50 60 70 80 90 .... 1)0 110 I :to 130 140 l50 160 I 0 I IO NUMBER OF LETTERS PER MESSAGE uo 21() REF ID:A58459 15 CHART No. 2 9: a: e- I ~ .. - . " .,,6: e:: --) ·3~ 3: .- 2- ' ·~ . 1:. 1: -- -0 - II 10 2'0 30 40 50 60 70 80 90 ·~lo 10 I !O I IO I• IO 150 1110 I 'O I IO I IO l~ IO NUMBER OF LETTERS PER MESSAGE 16 CHA.RT No. 3 I ' -- - a.:; I - -·- aD E< z z0 aD z0 ·- ..rj 0 ~ 6~ -- :> -zril ll-f ~ u ~ ;:!1 ' 5.:; = .s;; ..:! iz.. ~ :ii 4~ b 0 ~ ~ ril ::;: 0 .. -- - 3:. I .._, 0 ~ p: ril. 3v ~p z I -- -· 1 i 11 ' - ' ... 2: I;; -. - to 20 30 I) 40 50 60 70 80 90 IOO 110 120 130 1"40 I iO 190 170 180 190 21 )() NUMBER o:r LETTERS PER MlllSsAGE r REF ID:A58459 17 No. 4 CHART -· 5 .' ~ - -- - ' I ... - I '' -- 0 10 20 30 40 50 60 70 80 90 100 I IO 1, !O .l: IO 1-40 150 160 PO 180 I IO 2~1() NUMBER OF LETTERS PER MESSAGE 18 Binomial distribution Normal distribution x 64X63X ... X(M-XH)cr-xcy IX2X ... XX 2 2 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ' 40 41 42 43 '44 • 45 46 47 0.0001 . 0002 . 0005 . 0011 . 0023 . 0044 . 0080 . 0136 . 0217 . 0326 . 0459 . 0606 . 0753 .0873 .0963 .0993 .0963 .'0878 . 0753 .0606 .0459 .0326 . 0217 . 0136 .0080 .0044 '.0023 . 0011 ·.0005 .0002 . 0001 .. X-32 X=-4- -3. 75 -3. 50 -3.25 -3.00 -2. 75 -2. 50 -2.25 -2.00 -1. 75 -1. 50 -1. 25 -1.00 -.75 -.50 -.25 0.00 .25 . 50 . 75 1. 00 1. 25 1. 50 1. 75 2.00 2.25 2.30 2.75 ... .. 3.00 3'. '25 3.50 3.75 ' _1_ -:r'/32 4~~ 0.0001 . 0002 . 0005 . 0011 . 0023 . 0044 . 0079 . 0135 . 0216 . 0324 . 0457 . 0605 . 0753 .0880 .0967 . 0997 . 0967 .0880 . 0753 .0605 .0457 .0324 .0216 • 0135 .0079 .06(4 . 0023 . 0011 .·0005 .0002 .0001 APPROXIMATION OF THE BINOMIAL DISTRIBUTION BY THE NORMAL DISTRIBUTION 11. Poisson distribution. 10-a. In both the binomial and normal distributions, it was seen that there are two para.meters that play important roles; n and p in the binomial distribution, and µ and u in the normal distribution. In the distribution now to be considered there enters but one parameter. b. The Poisson distribution, known also as the Law of Small Numbers, the Law of Small Probabilities, and Poisson's Exponential Law, relates to a statistical variate which takes on positive integral values only, (O, 1, 2, . . . ). According to this distribution, the probability that an event occurs zero, one, two, three, . . . x, . . . times is given by the corresponding term of the sequence 11 See appendix B, p. 149tf. '1··, Ii I; " '·'j REF ID:A58459 CHART No. 5.-PoissoN EXPONENTIAL - + -~ I t --- -T --W:- !-1 if#" t- r '- r: + -i ,-1 f-t:j~T11+t-1=!+t:J:tll:::J:+:tj::j::t+ttl+tt:tt::t+:11:t!:++l:t+:j_:;'-f:t:t't'J::t:t+t:-+-l-+-+-+4-t-+-H-~-+-l-++-l-++li--::O+:\_-+,+-H~H' -+-+-H~-+-1-H- 1-,j-H+i--+-l-++-t-t++-H+l-H+I 1 +-H-+-H++-H,1-t+H-t++-+++++--+-1-.+H-H-' -1-t-t-+-H-t-t--H-,r-;-;H,-++++·++++-++~+; ~1 50f:t:ti:t:t::t:t:t:t:t:t1ittt::t:ttt:t=H:::rn:+tttt:t1+tt+tl=f::l+++tt++H=t+++1++++1:ttt:t1+:+4:t!++:H=l+H.:t:tt+++:i+tt+l+H+!+tt+t:t::H+l+ttt+l=i+tt+l:tf+H+l=l=:i::i+lr+J:++l+H+!+l=l=+t+:H=H=H+H+!::++:t::t:ttH+l::+++ttt:~:ttt:H+!:tUttt:H+l:tttttl f+ ::L i+l=l+t:t::l+t::ltt:.t:t\tt+P:::t::l,::t::t.:1=1+ltt::t::t::!:::t:++i=J;::1+:tj::j:::t::t::ltt::t::t::!+t+P:::t::J,::tj::j::j::j::ltt::t::\=-~1=t+~:t::(1i 1+t1 t'~-!1i.T4+ti~±: