AICC II
113 flashcards · Mathematics · by Athena Papkouf
Probability distribution (probability mass function) p:
A function p:Ω→[0,1]p: \Omega \rightarrow[0,1]p:Ω→[0,1] such that ∑ω∈Ωp(ω)=1 \sum_{\omega \in \Omega} p(\omega)=1∑ω∈Ωp(ω)=1
If E1 and E2 are disjoint events then p(E1∪E2)p(E_1 \cup E_2)p(E1∪E2) ===
p(E1)+P(E2)p(E_1) + P(E_2)p(E1)+P(E2)
Law of Total Probability:
For any F ⊆ Ω and its complement Fc, p(E) = p(E|F )p(F ) + p(E|Fc )p(Fc ).
Bayes’ Rule
p(F∣E)=p(E∣F)p(F)p(E)p(F \mid E)=\frac{p(E \mid F) p(F)}{p(E)}p(F∣E)=p(E)p(E∣F)p(F)
Probability distribution pX
pX (y) is the probability that X = y, i.e. the probability of the event E=ω∈Ω:X(ω)=yE={ω∈Ω:X(ω)=y}E=ω∈Ω:X(ω)=y Hence, pX(y)=∑ω∈Ep(ω)p_{X}(y)=\sum_{\omega \in E} p(\omega)pX(y)=∑ω∈Ep(ω)
Expected Value E[X] of a random variable X : Ω → R:
E[X]=∑ωX(ω)p(ω) or, equivalently, E[X]=∑xxpX(x)\begin{aligned} &\mathbb{E}[X]=\sum_{\omega} X(\omega) p(\omega)\\ &\text { or, equivalently, }\\ &\mathbb{E}[X]=\sum_{x} x p_{X}(x) \end{aligned}E[X]=ω∑X(ω)p(ω) or, equivalently, E[X]=x∑xpX(x)
E and F are independent iff
p(E|F ) = p(E) or iff p(E ∩ F ) = p(E)p(F )
Two random variables X and Y are independent iff
p({X = x} ∩ {Y = y }) = p({X = x})p({Y = y }), or iff p X ,Y (x, y ) = p X (x)p Y (y ).
Entropy definition
0\right\} \end{array}"> Hb(S):=−∑s∈ supp (pS)pS(s)logbps(s) where supp(pS)={s:pS(s)>0}\begin{array}{r} H_{b}(S):=-\sum_{s \in \text { supp }\left(p_{S}\right)} p_{S}(s) \log _{b} p_{s}(s) \\ \text { where } \operatorname{supp}\left(p_{S}\right)=\left\{s: p_{S}(s)>0\right\} \end{array}Hb(S):=−∑s∈ supp (pS)pS(s)logbps(s) where supp(pS)={s:pS(s)>0} H(S)=E[−logpS(S)].H(S) = E[− log p_S (S)].H(S)=E[−logpS(S)].
binary entropy function.
h(p):=−plog2p−(1−p)log2(1−p)h(p) := −p log_2 p − (1 − p) log_2 (1 − p)h(p):=−plog2p−(1−p)log2(1−p)
IT inequality
For a positive real number rrr , logbr≤(r−1)logb(e)log_b r \leq (r − 1) log_b (e)logbr≤(r−1)logb(e) , with equality iff r=1r = 1r=1
Entropy bounds
The entropy of a discrete random variable S∈AS \in AS∈A satisfies 0≤Hb(S)≤logb∣A∣ 0 ≤ H_b (S) ≤ log_b |A|0≤Hb(S)≤logb∣A∣ , with equality on the left iff pS(s)=1p_S (s) = 1pS(s)=1 for some s, and with equality on the right iff pS(s)=1∣A∣∀sp_S(s) = \frac{1}{|A|} \forall spS(s)=∣A∣1∀s
Entropy bounds of discrete random variables
uniquely decodable code
The code is uniquely decodable if every concatenation of codewords has a unique parsing into a sequence of codewords.
prefix free codes
If no codeword is a prefix of another codeword, the code is said to be prefix-free.
if the reverse of a code is prefixfree
the code is uniquely decodable
instantaneous code
A prefix-free code is also called instantaneous code.
Kraft’s inequality
Kraft’s inequality and prefix free codes
consequences of Kraft-McMillan
Average codeword length
Relation between entropy and average codeword length
D-ary Shannon-Fano codes
average codeword-length of a D-ary Shannon-Fano code
The average codeword-length of a D-ary Shannon-Fano code for the random variable S fulfills
average path length of a tree with probabilities
sum of the probabilities of the intermediate nodes (root included)
length of Huffman's codes
conditional entropy
relation between conditioning and entropy
Chain rule for entropies
H(X , Y)
regular source
entropy of symbol and entropy rate
For a regular source S, H(S) is called the entropy of a symbol, and H∗ (S) the entropy rate.
stationary source
stationary source entropy rate and entropy of a symbol relation
Cesaro means theorem
theorem about stationary and regular sources
average codeword-length per symbol of a uniquely decodable code
perfect secrecy
A cryptosystem has perfect secrecy if the plaintext T and the cryptogram C are statistically independent.
perfect secrecy and entropy of plaintext and key
Division Algorithm
congruent modulo m integers
equivalence relation
rest after division of a decimal number by 9
To obtain the rest after division of a decimal number by 9, we can substitute the number with the sum of its digits.
prime factorisation theorem
Every integer greater than 1 has a unique prime factorization (except for order).
a divides b iff
Let a and b be positive integers. a divides b iff all prime factors of a are present in the prime factorization of b with an equal or greater exponent.
greatest common divisor and prime factorisation
coprimality
gcd(a, b) = 1
congruence class
multiplicative inverse
condition for existence of multiplicative inverse
multiplicative inverse of a congruence class with prime modulo
euclidean algorithm for greatest common divisor
Bezout's identity
commutative group must satisfy the following axioms
which group is commutative for every integer m > 1 ?
∀nϕ(n)\forall n \phi (n) ∀nϕ(n)
where p is a prime factor of n
isomorphism
order of element of commutative group
condition for isomorphism (order)
Two finite commutative groups are isomorphic iff they have the same set of orders.
when does an integer k satisfy a*a*...*a=e ?
Lagrange theorem
Let (G, *) be a finite commutative group of cardinality n. The order of each of its elements divides n.
Euler's theorem corollary
Fermat's theorem corollary
Chinese remainders theorem
([a]pq)lk+1([a]_{pq})^{lk+1}([a]pq)lk+1
RSA high level
integer m (modulus), integer e (encoding exponent), integer d (decoding exponent), such that, for all integers t ∈ Z/mZ (plaintext) the receiver generates m, e, d (m, e) is the public encoding key (m, d) is the private decoding key — d never leaves the receiver. the encoder forms the cryptogram c = te mod m The intended decoder performs cd mod m and obtains the plaintext t.
Hash function
a many-to-one function, used to map a sequence of arbitrary length to a fixed-length bit sequence of, say, 200 bits even the smallest change in the input produces a different output
cyclic group of order n generator
Any finite group of cardinality n, that consists of the cycle of a group element g
cyclic group
Given a finite commutative group (G, ?), we can take any of its elements, say g ∈ G, and compute g2 , g3 , . . . , until for some n (the order of g), gn = e, where e is the identity in G. The result is the group H = {e, g, g2 , . . . , gn−1 }.
erasure/error weight p
the total number of erasures (resp. errors).
information bits per codeword
entropy rate per symbol of an (n,k) block code
Hamming distance
The Hamming distance d(x, y ) between two n-tuples x and y is the number of positions in which they differ
minimum-distance decoder
minimum distance of a code C
error detection theorem
erasure correction theorem
A minimum-distance decoder for a code C corrects all channel errors of weight p iff
Singleton bound
cardinality of a finite field
The cardinality of a finite field is an integer power of its characteristic. (Hence all finite fields have cardinality p m for some prime p and some positive integer m.)
All finite fields of the same cardinality are
isomorphic.
For every prime number p and positive integer m, there is a finite field of cardinality
pmp^mpm
rank of the matrix
linear code
(Hamming) weight of ~x
The minimum distance of a linear code C
generator matrix
systematic form
parity-check matrix H for a linear (n, k ) code
an (n − k ) × n matrix that contains the coefficients of a system of homogeneous linear equations that defines the code.
If G = (I k , P), where P is a k × (n − k ) matrix, is a generator matrix (in systematic form) of a linear (n, k ) block code, then what is the parity check matrix of the same code?
syndrome
minimum distance of a linear code (parity check matrix)
Let H be any parity-check matrix of a linear code. The minimum distance of the code is the smallest positive integer d such that there are d columns of H that are linearly dependent.
Standard Array