probability notes REVD

This is the Title PhL 3.26.05 I had some probability notes in Scrambler, but they ended up instead as an FT appendix. I did not want the same prob notes in two or three different places. FT already had to deal with statistical pulse trains. A few Basics of Probability and Statistics Applied to GF(2) tail of existing: The probability of events A and B both being true is denoted by P(AB), or P(A,B). This is known as the joint second-order probability density function (pdf). A related concept is P(A|B) meaning the conditional probability that A is true given that B is true. Here are the relations: P(A,B,C) = P(ABC) = P(A)P(B)P(C) . (2.5.7) Case 1: Sequence values are 0 or 1 The "event" of interest is that an = 1. The sequence {an} has some mean value which we denote by μ. The following shorthand notation is useful: p(an) ≡ P(an=1) = <an> = μ p(an, am) ≡ P(an= 1, am= 1) . (2.5.8) We can now express various mean values in terms of these pdf's: <an> = 1 • P(an=1) + 0 • P(an≠1) = P(an=1) = p(an) = μ (2.5.9a) <an2> = 12 • P(an=1) + 02 • P(an≠1) = P(an=1) = p(an) = μ (2.5.9b) <aman> = 12 • P(am=1,an=1) +3 zero terms = P(am=1,an =1) = p(am, an) . (2.5.9c) If m≠n, it is possible that am and an could be statistically independent. In this case, one would have: <aman> = p(am, an) = p(am) p(an) = <am><an> = μ2 // uncorrelated (2.5.10) For m=n, it is impossible that am and an be statistically independent, and one has: <anan> = p(an, an) = <an2> = p(an) = μ ≠ p(an) p(an) // correlated (2.5.11) In other words, the "diagonal" second-order statistical quantity p(an, an) is really the first-order quantity p(an). We can now write down a few related statistical quantities (we are doing GF(2) symbols here): The moments for N = 0,1,2,3...: m0 = <an0> = <1> = 1 N = 0 mN ≡ <anN> = 1N• P(an=1) + 0N• P(an=1) = p(an) = μ N = 1,2,3.. (2.5.12) The central moments for N = 1,2,3..: μN = < (an - <an>)N> = < (an - μ)N> = < Σj=0N (an)N-j [-μ]j > = Σj=0N (-1)j μj < (an)N-j > = Σj=0N-1 (-1)j μj+1 + (-1)N μN (2.5.13) The N=1,2 central moments μ1 = < (an - <an>)1> = <an> - <an> = μ - μ = 0 μ2 = < (an - <an>)2> = < (an - μ)2> = <an2> - 2μ <an> + μ2 = <an2> - μ2 = μ - μ2 = μ(1-μ) = σ2 = (standard deviation)2 = variance (2.5.14) Thus, in the special case of symbols in GF(2), all moment and central moments are determined by μ. For some different set of symbol values, this might not be the case. In general, a full characterization of a statistical sequence requires specification of the probability density functions of all orders. However, much useful information is contained in the first two orders, and this information is sufficient for many applications. Fact 1: The first and second order statistics are completely determined by the autocorrelation function. Proof: Assume that the autocorrelation sequence rk is known. Then, first order: p(an) = <an> = <an2> = r0 // (2.5.9a), (2.5.9b), (2.54) second order: p(an, an) = <an2> = p(an) = r0 // (2.5.9b), (2.54) p(am, an) = <aman> = rm-n m ≠ n // (2.5.4) Corollary 1: Third and higher order statistics are not determined by the autocorrelation sequence. One needs more information to get these higher statistics. Example: Consider the third-order density: p(an, an+k, an+k') = < anan+kan+k'> One could relate this to some kind of fancier 2-variable autocorrelation sequence defined this way, rk,k' ≡ (1/P) Fact 2: For a statistically independent sequence, all higher order statistics are determined by the first order statistics: (p(am) is independent of m ) <aman> = p(am, an) = p(am) p(an) = [p(am)]2 = μ2 m ≠ n <amanak> = p(am, an, ak) = p(am) p(an) p(ak) = [p(am)]3 = μ3 m ≠ n≠ k etc. Proof: This follows from the definition of "statistical independence" given above (= uncorrelated). ok to here Definition: A white sequence over GF(2) is one which is uncorrelated and has p(an) = μ = 1/2. For such a sequence, we have: <an> = p(an) = μ = 1/2 = r0 <aman> = p(am, an) = p(am) p(an) = μ2 = (1/2)2 = 1/4 = rm-n m ≠ n <amanak> = p(am, an, ak) = p(am) p(an) p(ak) = μ3 = (1/2)3 = 1/8 m ≠ n ≠ k etc. (2.5.15) From (2.5.15) here is a plot of the autocorrelation sequence for a white sequence an defined over GF(2): Figure 2.5.1: Autocorrelation function of a white sequence over GF(2) = {0,1}. This fits the general template shown in Fig *** above where α = μ2 = 1/4 and β = σ2+μ2 = μ = 1/2 Case 2: Sequence values are -1 or 1 It is sometimes convenient to think of the elements of the sequence an as belonging to the set {-1, +1} instead of to the official GF(2) set { 0,1 }. In this case, various statements made above must be modified. For example, P(an = 1) = p(an) ≡ p P(an ≠ 1) = P(an = -1) = 1 - p(an) = 1-p <an> = 1 • p(an) + (-1) • [ 1 - p(an)] = P(an=1) = [ 2 p(an)- 1] = (2p-1) = μ (2.5.9a)' <an2> = 12 • p(an) + (-1)2 • [ 1 - p(an)] = 1 (2.5.9b)' <aman> = 12 • P(am=1,an=1) + 1•(-1) P(am=1,an=-1) + (-1)•1 • P(am=-1,an=1) + (-1)2 P(am=1,an=-1) (2.5.9c)' If m≠n, it is possible that am and an could be statistically independent. In this case, one would have: <aman> = p(am, an) = p(am) p(an) = <am><an> = (2p-1)2 = μ2 // uncorrelated . (2.5.10)' For m=n, it is impossible that am and an be statistically independent, and one has: <anan> = p(an, an) = <an2> = 1 ≠ p(an) p(an) = p2 . (2.5.11)' The moments for N = 0,1,2,3...: m0 = <an0> = <1> = 1 N = 0 mN = <anN> = 1N p(an) + (-1)N [ 1 - p(an)] = p + (-1)N (1-p) N = 1,2,3.. (2.5.12)' = The central moments for N = 1,2,3..: μN = < (an - <an>)N> = < (an - p)N> = < Σj=0N (an)N-j [-p]j > = Σj=0N (-1)j pj < (an)N-j > = Σj=0N (-1)j pj mN-j (2.5.13)' The N=1,2 central moments: μ1 = < (an - <an>)1> = <an> - <an> = 0 μ2 = < (an - <an>)2> = <an2> - 2<an>2 + <an>2 = <an2>- <an>2 = 1 - (2p-1)2 = 4p(1-p) = 1-μ2 = σ2 = (standard deviation)2 = variance (2.5.14)' Fact 1': The first and second order statistics are completely determined by the autocorrelation function. Proof: Assume that the autocorrelation function rk is known. Then, first order: p(an) = <an> = <an2> = r0 // (2.5.9a), (2.5.9b), (2.54) second order: p(an, an) = <an2> = p(an) = r0 // (2.5.9b), (2.54) p(am, an) = <aman> = rm-n m ≠ n // (2.5.4) For a white sequence, we have p = 1/2 so <an> = (2p-1) = 0 = μ <an2> = 1 = r0 // (2.5.4) <aman> = p(am, an) = p(am) p(an) = <an><an> = 0 = rm-n m ≠ n // (2.5.4) <amanak> = p(am, an, ak) = p(am) p(an) p(ak) = 0 m ≠ n ≠ k etc. (2.5.15)' From (2.5.15)' here is a plot of the autocorrelation sequence for a white sequence an defined over {-1, +1} where we set p = 1/2 in the above equations: Figure 2.5.2: Autocorrelation function of a white sequence over {-1,+1}. This fits the general template shown in Fig *** above where now α = μ2 = 0 and β = σ2+μ2 = 1.