ㅇㅇ

Integral transform의 일반적 얘기 정리

Laplace Transform정리

Fourier Transform정리

1. 용어

f_n:seq from {0,1,2,...}->F

f(t):fps from {f_n}, :=G[f_n]

f(t,w):fps from {f_(n,k)}, bivariate formal power series from {f_(n,k)}

[t^n]f(t)

ord(f(t))

bar(f(t))

F[[t]], F_k[[t]]

L, laurent power series, 원소는 l(t)

(x)_k, falling factorial

[x]_k, rising factorial

(d(t),h(t))가 pRa

M(d(t),h(t)), riordan array

renewal array

R, riordan group

A, Appell subgroup

Lag, Lagrange subgroup

derivative subgroup, {M(h'(t),h(t)) s.t. h(t) in F_1[[t]]}

2. 정리

About F[[t]]

ord(f(t)+g(t)) >= min{ord(f(t)), ord(g(t)))

ord(f(t)g(t)) = ord(f(t)) + ord(g(t))

(F[[t]],+,*):ID, quotient field는 L

About F_0[[t]]

(F_0[[t]], *):abelian group((F_0[[t]], +, *)에서는 +에 대해 닫혀있지 않음)

About F_1[[t]]

(F_1[[t]], o):group

About L

[t^n]의 성질 중 f(t)g(t)와 f(g(t))와 bar(f(t))에 관해서 복습, 특히 마지막을 Lagrange Inversion formula([t^n]bar(f(t)), [t^n]{bar(f(t))}^k)

About riordan array, riordan group

R:group

M(d(t),h(t))*M(a(t),b(t))=M(d(t)a(h(t)),b(h(t))), riordan arrays are closed under the matrix product

multiplicative identity는 M(1,t)

M(d(t),h(t))의 multiplicative inverse는 M(1/d(bar(h(t)), bar(h(t)))

Every pRa can be seen as the product of an Appell by a Lagrange matrix

{f_(n,k)}:pRa iff te d(t) in F_0[[t]] and h(t) in F_1[[t]] s.t. f(t,w) = d(t)/{1-wh(t)}

pRa is characterized by d_(0,0), Z-seq, and A-seq

About functional equation w(t)=tΦ(w(t))

Φ in F_0[[t]] and F in F_0[[t]]일 때

[t^n]w(t) = 1/n * [t^(n-1)](Φ(t))^n, n>0

[t^n](w(t))^k = k/n * [t^(n-k)](Φ(t))^n, n>0

[t^n]F(w(t)) = 1/n * [t^(n-1)]F'(t)(Φ(t))^n = [t^n](F(t) * (Φ(t))^(n-1) * (Φ(t)-tΦ'(t)))

f(t), g(t) in L

[t^(-1)]f(t)g'(t) = - [t^(-1)]f'(t)g(t)

Φ in F_0[[t]] and F in F[[t]]일 때

(Diagonalization rule) {c_n}={[t^n]F(t)(Φ(t)^n)}의 generating function은 F(w)/(1-tΦ'(w)), w=tΦ(w)

F and Φ and φ in F_0[[t]]일 때

[t^(n-k)]F(t)(φ(t))^n(Φ(t))^k M(d(t),h(t)), where d(t) = F(w)φ(w)/(φ(w)-wφ'(w)), h(t)=wΦ(w), w=tφ(w)

About A-seq and B-seq and Z-seq of pRa, given pRa(=M(d(t),h(t))

About A-seq

An infinite lower triangular array D is pRa iff te A-seq of D(a_0 != 0)

(->방향은 M(d(t),h(t))에서 M(d(t),h(t))*M(A(t),M(t)) = M(d(t)h(t)/t, h(t))이용해서 M(t)=t보이고 좌우변 generic element비교)

(<-방향은 h(t)=tA(t) 이용해서 h(t) 구하고 d(t)는 D의 0-column읽어서 구함)

Given pRa, A-seq의 generating function바로 구하는 법, A(t)=t/bar(h(t)), A(y)=h(t)/t, y=h(t)

About B-seq

Given pRa, te B-seq(M(d(t),h(t))=M(d(t)h(t)/t, h(t))*M(A(t),t)^(-1)을 이용해서 구함, B(t)=(A(t))^(-1)임)

About Z-seq

Given pRa, te Z-seq

(z_0 = d_(1,0)/d_(0,0), d_(2,0)=z_0 * d_(1,0) + z_1 * d_(1,1)해서 z_1구하고 이런 방식으로 쭉 구함)

Given pRa, Z-seq의 generating function(implicit), d(t)=d_(0,0)/(1-tZ(h(t))), 따라서 Z(y)=(d(t)-d_(0,0))/(td(t)), y=h(t)

About renewal array

a pRa M(d(t),h(t)) is renewal array

iff d(t)=h(t)/t

iff A(y)=d_(0,0) + yZ(y) and d(0)=h(0) != 0

A:Appell subgroup

A:normal in R

Lag:Lagrange subgroup

L:subgroup in R

L giso (F_1[[t]], o)

3. 요약

P=M(1/(1-t), t/(1-t))의 경우 generic element가 계산 쉬움, binomial formula쓰면 됨

C=M(1/sqrt(1-4t), (1-sqrt(1-4t))/2)의 경우 generic element를 guess한 다음, [t^n]~~꼴로 써넣고 보니 n이 포함된 형태, 따라서 diagonalization rule사용하여 증명

4. 문제들

1. 용어

K_n, K_(n,n), K_n^o,

K_n^*

SS

incidence matrix for the configuration {X1,X2,...,Xm} of n-set X(mxn (0,1)-matrix), a seq of m distinct elements of X is a SDR

partly decomposable, fully indecomposable

reducible matrix, irreducible matrix, nearly reducible

totally unimodular matrix

nnn irreducible matrix중

primitive matrix

exponent

imprimitive matrix

index of imprimitivity

Adjacency(multigraph에서 생각, multiple edge개수가 entry로 들어감)

(0,1)-incidence

(0,1,-1)-incidence(orient는 내맘대로)

Adjacency(digraph에서 생각, multiple arc개수가 entry로 들어감, from row to column)

minimally strong digraph

index of imprimitivity of a strongly connected digraph

tourment

permanent(rectangular에서는?)

σ_k(A)

affine set, dimension of nonempty affine set, hyperplane, affine hull

convex hull, convex polytope, dimension of convex set

DQSMT

DSMT, elementary DSMT

SSMT

OSMT

Ω_n, Ω_n(D) where D:fully indecomposable (0,1)-matrix

DSSMT

DSPSMT

RSMT

CSMT

α=an, β=bn

α < β,majorization

α <_w β, weakly submajorized

α <^w β, weakly supermajorized

Ω_n(α<β)

preordering and partial ordering

A is a subset of R^n, f:A->R일 때

A:symmetric이란?

f가

Schur-convex on A

strictly Schur-convex on A

Schur-concave on A

strictly Schur-concave on A

kth-symmetric function, S_k

S=[n], Latin rectangle of S, Latin square of S, reduced Latin square of S

L_n:the number of Latin square of [n]

quasigroup, loop

partial transversal of size t of a Latin square A on [n], transversal of A

2. 정리

About affine, convex

affine set <-> Linear system's solution Ax=b

About Nearly reducible matrix

A:nearly reducible (1,0)-MT일 때

te P and 1<=m<=n-1 s.t. PAP^t = ...

P-chain of [n]으로 permutation구하기

about PAP^T

불변량:n-digraph에 labeling만 영향(adjacency matrix A), egv

about PAQ

(n,n)-bipartite에 labeling만 영향, rank

A:invertible 이고 PAQ:LMT iff te! 1-factor of nonzero weight in the weighted bipartite graph associated with A

About det

det(MT(nxn))를 weighted bipartite graph로 표현하기

det(MT(nxn))를 weighted digraph로 표현하기(loop도 포함, 조심)

det(MT(nxn))를 n개의 rectangular MT의 곱으로 표현하기

If MT:PSD, then det(MT) <= prod over all diagonals of MT

About per

per(MT(nxn))를 n개의 rectangular MT의 곱으로 표현하기

per(PAQ)=per(A)

per((A)^t)=per(A)

Laplace Expansion Theorem for permanent(for mxn matrix, choose r, α)

per(A+B)=...

(Frobenius-Konig Theorem), A:nnn nxn MT일 때 per(A)=0 iff te P,Q s.t. PAQ=... sxt, s+t=n+1

(Alexandrov-Egorycev Inequality)If A:nnn, then (per(A))^2 >= ... (if t column빼고 다 positive columns, then = holds iff t는 q column의 multiple)

If per(A(i|s))=per(A(i|t)) for any 1<=i<=n and some s,t, then per(B)=per(A), where B=A except for s,t column은 A의 s,t column의 평균

If A:CSMT s.t. 0<per(A)<=per(A(i|j)) for any i,j, then per(A(i|j))=per(A) for any i,j

About subpermanents, some conjectures

If A:nnn, all row sum<=1, then σ_k(A) <= nCk

(Tverberg)If A:DSMT, then σ_k(A) >= σ_k(J_n) for k=1,2,...,n, with = iff A=J_n

(Dokovic)A:DSMT일 때 σ_k decreases at A on the segment joining A to J_n.(거짓, 1999, Ian)

(Dittert)A:nnn, all entries sum=n, f(A):=prod rowsum + prod colsum - per(A)일 때 f(A) <= 2 - n!/n^n with = iff A=J_n

(Cheon and Hwang)A:nnn, all entries sum=n, f_k(A):=...

About egv

Gershigorin theorem

About Irreducible MT

irreducible 판정:n-digraph가 strongly connected

Frobenius normal form of any matrix A, PAP^t

Frobenius form of irreducible A with index of imprimitivity k, then PAP^t ...

invariant operation of irr:

-transpose

-product? NO

-addition? NO

Perron-Frobenius Thm의 내용(positive일때랑 nnn irreducible일때의 차이는 spectral circle상 egv개수뿐)

About imprimitivity

M:nnn irreducible일 때

M:primitive iff M^m:positive(M:irreducible없어도 됨)

M:primitive iff lim m->inf (M/r)^m exists, limit값은?

imprimitive of M = gcd of the lengths of directed cycles in n-digraph.(index of M = index of D(M))

index of M=k일 때

k개의 egv는 x^k=r^k인 복소수 근들이다.

k_i = k, where k_i:the gcd of lengths of all cycles of D(M) through vertex i

About exponents of primitive MT((0,1)-MT만 다뤄도 됨, 이하 모두 (0,1)-MT)

If M:primitive with p개 nonzero diagonals, then exp(M) <= 2n - p -1

If M:primitive with n개 nonzero diagonals, then exp(M) <= n - 1

If M:primitive and symmetric, then exp(M) <= 2n - 2 with = iff te P s.t. PMP^t = ...

If M:primitive, then exp(M) <= (n-1)^2 + 1 with = iff te P s.t. PMP^t = ...

About Incidence, Adjancecy

About graph, A:(0,1)-incidence, B:Adjacency, C:(0,-1,1)-incidence

(A)^t * A = B + D

(C)^t * C = B - D

If G:connected, then rank(C)=n-1

About DSMT and Majorization

About DQSMT

A:DQSMT iff 1:egv for A with (1,1,1...,1) eigenvector

About DSMT

A:each row sum = each column sum = 1이면 A:square

A:DSMT iff AJ=JA=J, J=[1/n] iff for any x in R^n, Ax < x (majorization)

DSMT1*DSMT2 is also DSMT

per(DSMT) > 0

(Schur)H:hermitian, then te SSMT s.t. h=SSMTλ, h:diagonal entries로 구성된 vector, λ는 egv로 구성된 vector(증명도)

if A:DSMT and reducible, then te P s.t. PAP^t=the direct sum of DSMTs

if A:DSMT and irreducible with index k, then k|n and te P s.t. PAP^t = ... all blocks are (n/k)-square and DSMT

(Birkhoff)Ω_n={all DSMT}=closed bounded convex polytope, dim=(n-1)^2, whose vertices n! permutation MT of order n

D:nxn fully indecomposable (0,1)-MT일 때

Ω_n(D):={all DSMT s.t. DSMT<=D}, called the face of Ω_n, which is a subpolytope of Ω_n

dim(Ω_n(D))=the number of 1 in D - 2n + 1

the number of vertices = per(D)

the barycenter of Ω_n(D) is 1/per(D) sum over P<=D P(P:permutation MT)

About Minimizing

A:minimizing이면

fully indecomposable

if a_(h,k)>0, then per(A(h|k)) = per(A)

(London-Minc)for any i,j, per(A(i|j)) >= per(A)

if 1st row of A and 2nd row of A have the same zero pattern, then per(A)=per(A'), A'의 1,2row는 A의 1,2row의 average로 replaced

if A:positive, then per(A)=per(J_n)=n!/n^n

if A != J_n, then all its zeros cannot occur in a single row(column)

(Egorycev)per(A(i|j))=per(A)

(Alexandrov-Egorycev Inequality)에서 = 성립 for any q,t(q != t)

per(A)=per(A'), A'의 i,j row는 A의 i,jrow의 average로 replaced

(van der Waerden)If A:DSMT, != J_n, then per(A) > per(J_n)

if A:positive DSMT sufficiently close to J_n and A != J_n, then per(A) > per(J_n)

About DSSMT

A:DSSMT

iff te DSMT s.t. A<=DSMT

iff A:nnn and Ae <= e and eA <= e

iff A:nnn and αA <_w α for all nnn α.

{all DSSMT}=convex hull of {M s.t. M has at most one 1 in each row and each column}

About DSPSMT

A:DSPSMT 이면 all row sums and column sums are at least 1(역은 성립 안함)

{all DSPSMT}=convex, not convex hull of its extreme points(extreme points가 permutation matrices뿐)

About Majorization

α < β with nnn

iff (Muirhead) using c and per

iff (HLP) using DSMT

α <_w β with nnn

iff te DSSMT s.t. α = DSSMTβ

α <^w β with nnn

iff te DSPSMT s.t. α = DSPSMTβ

About Schur-convex function on A, A:symmectric and convex subset of R^n, f:A->R, g:R->R

직접 Schur-convex보이기, 단, n=2일때만 보여도 충분

f:C1 on int(A) 일 때 f:Schur-convex on A iff f:symmetric and Schur-condition

f:symmetric and convex이면 f:Schur-convex

f:inc and Schur-convex and g:convex이면 f(g)는 Schur-convex

f:dec and Schur-convex and g:concave이면 f(g) 는 Schur-convex

f:Schur-convex이고 g:inc이면 g(f)는 Schur-convex,

f:Schur-convex이고 g:dec이면 g(f)는 Schur-concave.

대표적인 Schur-convex

sum 1/x_i

sum x_i

sum (-log(x_i))

대표적인 Schur-concave

S_k(k=1,2,...,n)

symmetric, inc, Schur-concave

(S_k)^(1/k):symmetric, inc, concave, Schur-concave

(S_k)/(S_(k-1)):symmetric, concave, Schur-concave

Note)

<_w인 경우 order-preserving의 경우는

f:order-preserving

iff 0>=f_x1>=f_x2>=...>=f_xn for all z in A(f가 C1일 때)

iff f:inc and Schur-convex

<^w인 경우 order-preserving의 경우는

f:order-preserving

iff f:dec and Schur-convex

About Latin squares

L_n = n!(n-1)!R_n, where R_n:the number of reduced Latin squares of [n]

quasigroup on [n] <-> Latin square, bijection

K_(n,n)의 edge coloring(adjacent edges는 다른 coloring, color set=[n]) <-> Latin square, bijection

M_i:=same color perfect matching

transversal of Latin square <-> differenct color perfect matching

|G|=odd이면 {(g)^2|g in G} = G(i.e. all element of G has a unique square root)

따라서 cayley table for a group with odd order의 diagonal은 transversal가 된다.

3. 다시봐야할 것들

αP <^w α for all nnn α이면 P는 DSPSMT인가?

Chapter 1 What is CMT?

*Def

walk

path(walk와의 차이는 distinct vertices)

connected graph

matching, k-matching, matching number

vertex-cover, cover number

K_n, complete graph

K_no, complete graph with all loops

K_n*, complete digraph with all loops

G(MT), called the Konig digraph

IcMT(configuration of X)

MT(nxn):reducible or irreducible

nnn irreducible중에서

primitive MT

the exponent of primitive MT?

imprimitive MT, 이경우 index of imprimitivity 정의
G1,G2:cospectral if spec(A(G))=spec(A(G'))

IcMT(G), (1,0) matrix

*Thm

Principal tools of Combinatorics

-Mathematical Induction

-Pigeonhole Principle

-Inclusion-Exclusion Principle

-The methods of recurrence relations and generating functions

-Graph Theory

-Burnside's Theorem

-Polya Enumeration Theorem

각각 내용 알기, 특히 Exponential Generating Functions관련해서 내용정리 추가 필요

Tree의 equivalent def

-connected acyclic

-for distinct u,v in V(G), te! path from u to v

-connected with n-1 edges

-connected and removing any edge makes G disconnected

G:bipartite이면 cover number = matching number

From Matrix to graph

no need square(invariant for PAQ, like rank)

MT(mxn) -> K_(m,n)의 subgraph, ker(MT), bar(ker(MT)), bar(ker(MT))의 경우 weigted로도 볼 수 있는데 그 경우 bar(ker(MT))에서 0는 no edge로 보면 됨

MT(mxn) -> G(MT), K_(m,n)의 digraph 형태, weight있는 경우

MT(nxn)의 경우 그냥 G(MT)보고 det(MT)를 wt(all 1-factors)로 묘사가능

square(invariant for PArt(P), like egv)

SMT(nxn) -> K_no의 subgraph, ket(MT), bar(ker(MT)), weighted로도 볼 수 있음, bar(ker(MT))에서 0는 no edge로 보면 됨

MT(nxn) -> K_n*의 subgraph, ker(MT), bar(ker(MT)), weighted로도 볼 수 있음, bar(ker(MT))에서 0는 no edge로 보면 됨

From (di)graph to matrix

(1,0)-A(G)

arc가 있냐 없냐로 1,0

det(A(G))=(-1)^n * wt(D_n),

where D_n:={all 1-factor of σ, σ in S_n},

wt(D_n)=sum over all σ wt(F_σ),

wt(F_σ)=sign(σ) * prod over all i=1 to i=n a_(i,σ(i))

따라서 (di)graph의 형태를 보고 det구할 수 있다. cycles

A(G)^k의 (i,j)원소의 의미는 the number of walks of length k from i to j

IcMT(G)

rt(IcMT(G))*IcMT(G) = sLap(G)

det, perm using IcMT

det(MT(nxn))=W^1 W^2 ... W^n, W^i:(n choose i-1)x(n choose i) using (i+1)th row element in MT

perm(MT(nxn))=W^1 W^2 ... W^n, W^i:(n choose i-1)x(n choose i) using (i+1)th row element in MT

Perron Theorem for positive MT

About irreducible

MT:irreducible

iff G(MT):strongly connected, (G(MT):K_n*의 subgraph, unweighted directed)

About primitive MT

the index of imprimitive = gcd(the lengths of all directed cycles in G(MT))

MT:primitive

iff lim m->inf (MT/specR(MT))^m exists, the limit = (p*rt(q))/(rt(q)*p) > 0, where p:perron for MT, q:perron for rt(MT)

iff the index of imprimitive = 1

iff gcd(the lengths of all directed cycles in G(MT)) = 1, (G(MT):K_n*의 subgraph, unweighted directed)

iff MT^m > 0 for some m, called the exponent

Perron-Frobenius Theorem for irreducible NNN MT

계산복잡도 수업 내용 정리

*Def

-FA(finite automata): FA are finite collections of states(Q) with transition rules that take you from one state to another.

-apb(alphabet):apb is any finite set of symbols

-str over apb:apb에 속한 원소들의 lists(juxtapositions)

-apb^*, the set of all strs over apb with empty string eps

-eps:empty string

-L(over apb)(language):a subset of apb^*

-DFA(deterministic finite automata): FA(5, Q,Σ,δ,q0,F)

with input apb(Σ), start states(q0), final states(F⊆Q), 이때 transition function δ은 domain이 (state, symbol), extend하면 (state, string)까지도 됨

-L(A):the set of all strs s.t. δ(q0,str) is in final states for some DFA A

-L is regular if L=L(A) for some DFA A.

-NFA(Nondeterministic finite automata):FA(5, Q,Σ,δ,q0,F) with δ(q,a) is a set of states

특히 NFA에서는 a string w is accepted if δ(q0,w) contains at least one final state.

-TM(Turing machine):(7, Q,Σ,Γ,δ,q0,Β,F), Γ:tape apb set(읽고 쓰기가 가능, 쓸대는 Σ에 없는 것도 사용 가능, Σ<Γ)

(input의 양옆에는 blank로 채워서 들어가는 infinite tape)

(δ(state,tape symbol)=(변경 후 state, 변경 후 tape symbol, head이동방향))

(algorithm이 없는 language를 보이기 위해서 TM다룸, C program보다 simple하면서도 powerful함)

-ㅏ:TM에 input 한개 계산

-ㅏ*:TM에 input 모두 계산

-L(TM):the set of all strs w s.t. q0wㅏ* in final

-L=L(TM)이면 L을 recursively enumerable languages라 한다.

-Algorithm:=TM s.t. 어느 input이어도 halt할지 안할지 guaranteed된 TM을 가리킨다.

-L=L(TM) with algorithm TM이면 L을 recursive language라 한다.

-CFG(Context-free grammar): CFG(4, V,Σ,R,S)

with V:variables, Σ:terminals, R:rules(variable넣으면 variable과 terminal의 조합으로 이루어진 string이 output인 rule), S(in V):start variable

-L(CFG):the set of all strs w s.t. Sㅏ*w(즉 start variable S로부터 시작해서 나올 수 잇는 모든 strings with only terminals)

*Thm

the reverse of a regular language is also regular

Equivalence of DFA and NFA using subset construction

(NFA, DFA모두 the same language를 갖게 만들 수 있고, NFA가 state개수가 exponentially 적게 가능하지만, 구현가능 한 것은 DFA뿐)

가능한 L over {0,1}의 개수는 uncountable(임의의 language는 infinitely binary seq로 만들 수 있고, infinitely binary seq의 개수는 uncountable이므로)

Language가 program보다 많다는 것을 가리킴, 즉 There are languages with no membership algorithm(w in L인지 아닌지 판단하는 것을 membership algorithm), 이러한 류의 증명 방식을 Hungarian Arguments라 한다. 가능한 총 개수가 더 많음을 보여서 무언가 존재하는지 안존재하는 지 보이는 방식을(존재성은 알지만 particular language를 제시하는 데에 어려움(with no membership algorithm인 language를 건설하기 어렵다)

DFA->TM(DFA꺼 그대로 하고 방향도 R만 쓰고 tape write안하면 됨)

모든 Data type은 integer로 변환 가능

Binary strings to Integer는 Binary sting마다 앞에 1 붙여서 순서매기면 된다. 101->1101 =  13번쨰 integer, 0101->10101 = 21번째 integer

GIF는 ASCII string으로 구성, ASCII string을 binary string으로 바꾸고 integer로 바꾸면 됨, 따라서 i번째 image라는 걸 생각 가능

*Example

(Non-regular language)

L={0^n1^n|n>=1}, a^i means a가 i개 병렬나열

L={0^n1^n|n>=1}={01,0011,000111,...}, finite state을 가지는 DFA로는 얻을 수 없다. 따라서 non-regular

TM으로는 가능

L={01*0}={00,010,0110,...}을 TM으로 묘사하기

(Mortality of matrices)S:given finitely generated submonoid of nxn matrices from MT(nxn)(Z)

Determine whether there exists a seq of matrices M1,M2,...,Mk in S s.t. M1M2...Mk = 0(link1)(link2)(link3)(link4)

===========================================================

CFG이후의 내용 쭉 읽어서 PDA까지도 이해하기

수업내용 이해하기

undeciable관련해서 이해하기

Discriminative Model

-P[input, C_i], P[C_i]는 관심없고 P[C_i|input]만 modeling, learning하여서 P[C_i|input]을 구하여서 Classification

-특징

-SVM, Logstic regression 등 

Generative Model

-P[C_i], P[input, C_i] 혹은 P[C_i], P[input|C_i]을 modeling, learning하여서 P[C_i|input]을 구하여서 Classification

-특징

-HMM, GMM 등

1. Prior만 있을 때(P[Ci])

주어진 것:개와 고양이의 비율(0.6과 0.4)

문제:수영이네 애완동물이 개냐 고양이냐?

->개로 선택하는 것이 가장 best, error는 항상 0.4

2. P[Ci]와 P[Observation|Ci]가 주어졌을 때

주어진 것:개와 고양이의 비율, 어떤 개가 가지는 키의 분포, 어떤 고양이가 가지는 키의 분포

문제:수영이네 애완동물의 키가 k일때, 그 동물이 개냐 고양이냐?

->P[개|k]와 P[고양이|k]중 큰 것을 고르는 게 best

3. Loss Function(=cost function) 설정

L(true parameter, estimated parameter from input)을 최소화하고 싶지만

input으로만으로 true parameter을 모르므로, expectation of L을 최소화하자. 

근데 그것 또한 expectation of L given input을 최소화 하는 것과 동치이므로 expectation of L given input을 최소화 하자.

이렇게  expectation of L given input을 최소화시키는 estimator for parameter from input을 bayes estimator라 한다.

Loss function을 어떻게 설정하냐에 따라 Bayes Estimator의 형태가 달라진다.

Chapter 1 Hilbert Space

*용어정의

1. vector space의 semi-inner product란? inner product란?

2. Hilbert space의 정의

3. Absolutely continuous for f:[a,b]->F의 정의와 동치 2가지

4. G:open in C일 때 the bergman space for G란?

5. perp(E)의 정의, projection of a closed linear subspace(P_K)의 정의

6. S:subset of HS, VS란?

6. bdd linear functional f:HS->F의 정의

7. basis for HS의 정의

8. infinite subset S of HS가 linearly independent란, any finite subset of S가 linearly independent

9. dimension of HS란?

10. HS1,HS2:isomorphic이란 linear, surjective, preserve ip map이 존재

11. f:MetricS1->MetricS2가 isometry란?

12. f:HS->HS가 unitary operator란?(isomorphism인데 정의역=공역)

13. direct sum of HS1,HS2란?direct sum of countable HS_i란? direct sum of HS_i란?(net)

*Thm

1. CBS inequality and equality iff there are scalar a,b(not both 0)...

2. Absolutely continuous for f:[a,b]->F의 성질

-+,-,*,/에 닫혀있다.

-Lipschitz Continous이면 Absolutely Continuous이다.

-Absolutely Continuous이면 Uniformly Continuous이다.

3. Completion of IPS(extention of <,>, norm, and metric)

4. Polar Identity란

5. if K:closed convex, then dist(h_o,K)=d(h_0,k_0)인 k_0 in K존재 and unique

6. if K:closed linear subspace, then dist(h_0,K)=d(h_0,k_0)인 k_0 in K존재 and unique and h_0 - k_0:orthogonal to K

7. if K:closed linear subspace and h_0 - k_0:orthogonal to K인 k_0 in K 존재, then dist(h_0,k_0)=d(h_0,k_0)

8. perp(E):closed linear subspace of HS

9. projection of a closed linear subspace(P_K)의 성질

-linear

-norm<=1

-idempotent

-ran(P_K)=K, ker(P_K)=perp(K)

10. K:closed linear subspace of HS이면 perp(perp(K))=K

11. perp(perp(E))=closed linear span of E

12. S:linear subspace of HS일 때 S:dense in HS iff perp(S)={0}

13. f:HS->F, linear, TFAE

-conti, uniformly conti, conti at 0, conti at any pt, bdd

14. (Riesz for HS)f:HS->F, linear, bdd일 떄 f(h)=<h,h_0>인 h_0가 유일하게 존재 with ||f||=||h_0||

15. (Gram-schmidt) S:linearly ind이면 S':orthonormal s.t. ....

16. S:finite orthonormal일때 projection of VS의 representation

17. (Bessel)S:countable orthonormal일때 sum of (coefficients)^2 <= ||h|| 

18. S:orthonormal일때 sum of (coefficients)^2 <= ||h||(net)

19. net으로 cv이면 걍 cv

20. S:orthonormal일때 sum of <h,s>s는 always cv(net)

21. S:orthonormal일때 TFAE

-S:basis

-hㅗS이면 h=0

-VS=HS

-h=sum of <h,s>s(net)

-<h1,h2>=sum of <h1,s><s,h2>(net)

-(Parseval's Identity)||h||=sum of ||<h,s>||^2(net)

22. S1,S2:basis then, |S1|=|S2|

23. HS:separable iff dim(HS):at most countable

24. f:HS1->HS2가 linear일때 f:isometry iff f:preserve ip

25. f:HS1->HS2가 linear, isometry일 때

-ran(f):closed

26. HS1,HS2:isomorphic iff dim(HS1)=dim(HS2)

-HS with basis S, HS와 l^2(S)는 isomorphic

(Fourier는 따로 보고, 보고나서는 Chapter2, Example 4.12보기)

Chapter 2 Operators on Hilbert Space

*용어정의

1. B(HS1,HS2)란?

2. M_Φ란?

3. k:MSxMS->F, measurable, K:integral operator란?

4. u:HS1xHS2->F, sesquilinear란? sesquilinear가 bdd란? 대표적인 bdd sesquilinear는?

5. f in B(HS1,HS2)일 때, adj(f)란?

6. f in B(HS1,HS2)가 invertible이란?

7. f in B(HS)가 hermitian이란?, normal이란?

8. f in B(HS)가 idempotent란?, projection이란?(of a closed linear space란 거 없이)

9. K_i:closed linear subspace of HS일 때 the direct sum of K_i란?

10. f in B(HS)에 대해 invariant subspace for f란?(closed필요), reducing subspace for f 란?(closed필요)

11. f in B(HS)에 대해 f:compact란?

12. B_0(HS1,HS2)란?

13. f:HS->HS가 finite rank를 가진다란?

14. B_00(HS1,HS2)란?

*Thm

1. f:HS1->HS2, linear, TFAE

-conti, uniformly conti, conti at 0, conti at any pt, bdd

2. B(HS1,HS2):NVS

3. f in B(HS1,HS2), g in B(HS2,HS3), then g o f in B(HS1,HS3)

4. u:sesquilinear, bdd이면 u(h1,h2)=<Ah1,h2>=<h1,Bh2>인 A:HS1->HS2, B:HS2->HS1, linear, bdd가 유일하게 존재

5. f in B(HS1,HS2)일때 f:surjective isometry iff adj(f)=inv(f)

6. about adjoint, f,g in B(HS), a:scalar

-adj(af+g)=conj(a)adj(f)+adj(g)

-adj(gf)=adj(f)adj(g)

-adj(adj(f))=f

-if f:invertible, then adj(f):invertible and adj(inv(f))=inv(adj(f))

-||f||=||adj(f)||=(||adj(f) o f||)^1/2

7. (Consequence of Open Mapping Theorem) f in B(HS1,HS2), bijective이면 invertible이다.

8. f:HS->HS, linear, bdd일때 f:hermitian iff <f(h),h>:real for all h in HS(Base field가 C일 때만 성립)

9. f:HS->HS, hermitian일때

-||f||:=sup over ||h||=1 {|<f(h),h>|}

-<f(h),h>=0 for all h in HS이면 f=0(HS over C이면 f:hermitian조건 없어도 됨)

10. f:HS->HS, linear, bdd일때 TFAE

-f:normal

-||f(h)||=||adj(f)(h)|| for all h

-the real and imaginary parts of f commute(HS over C일 때만)

(real part of f := (f+adj(f))/2, imaginary part of f := (f-adj(f))/2

11. f:HS->HS, linear, bdd일때 TFAE

-f:isometry

-f:preserve ip

-adj(f)f=identity

12. f:HS->HS, linear bdd일 때 TFAE

-adj(f)f=fadj(f)=identity

-f:unitary

-f:normal isometry

13. f:HS->HS, linear bdd일 때

ker(f)=perp(ran(adj(f)))

ker(adj(f))=perp(ran(f))

perp(ker(f))=closure of ran(adj(f))

perp(ker(adj(f))= closure of ran(f)

(perp(ker(f))=ran(adj(f))는 아닐 수 있음, 조심)

14. f:idempotent iff I-f:idempotent

15. if f:idempotent, then ran(I-f)=ker(f), ker(I-f)=ran(f), and HS=the direct sum of ker(f) and ran(f) (여기서 direct sum은 그냥 Vector Space에서의 direct sum)

16. HS=the direct sum of S1 and S2이면 te! f in B(HS) s.t. ran(f)=S1 and ker(f)=S2

17. f:nonzero idempotent이면 TFAE

-f:projection

-f:orthogonal projection onto ran(f)

-||f||=1

-f:hermitian

-f:normal

-<f(h),h)> >= 0 for all h

18. K1,K2:closed linear subspace of HS일때 the direct sum of K1 and K2는 K1+K2와 같다.(finite는 다 됨, infinite는 안됨)

19. K:closed linear subspace of HS일 때 HS=the direct sum of K and perp(K)

20. f in B(HS), K:closed linear subspace of HS, P:projection onto K, TFAE

-K:invariant subspace for f

-PfP=fP

-f:K->perp(K)는 0가 된다.

21. f in B(HS), K:closed linear subspace of HS, P:projection onto K, TFAE

-K:reducing subspace for f

-Pf=fP

-f:K->perp(K)는 0, f:perp(K)->K도 0

-K:reducing subsapce for f and adj(f)

22. f in B(HS), K:invariant closed linear subspace of HS일 때 ||the restriction of f onto K||<=||f||

23. B_0(HS1,HS2):closed in B(HS1,HS2)

24. f in B(HS1), g in B(HS2), T in B_0(HS1,HS2)일 때 Tf in B_0(HS1,HS2)이고 gT in B_0(HS1,HS2)이다.(two-sided ideal)

25. f in B(HS1,HS2)일때 TFAE

-f:compact

-adj(f):compact

-te seq {f_n} s.t. f_n:finite rank and ||f_n - f||->0

26. f in B_0(HS1,HS2)일 때

-cl(ran(f)):separable

-if {e_n}:basis for cl(ran(f)) and P_n:projection onto V{e_j | 1<= j <=n}, then ||P_n o f - f||->0

27. HS:separable with basis {e_n} and {α_n} s.t. sup|α_n|=M<inf일때

-if f e_n=α_n e_n for all n, then f can be extended by linearity to a bdd f with ||f||=M. 그리고 그 f:compact iff α_n -> 0

28. f in B_0(HS), λ:nonzero egv for f일때, eigenspace는 finite dimension

29. f in B_0(HS), λ:nonzero s.t. inf{||(f-λ)h|| over ||h||=1}=0이면 λ:egv for f

30. f in B_0(HS), λ:nonzero, nonegv for f, conj(λ):nonegv for adj(f)이면 ran(f-λ)=HS and inv(f-λ):bdd

Chapter 3 Banach Spaces

*용어정의

1. seminorm on VS란?

2. two norms가 equivalent란?

3. C_b(X)란?C_0(X)란?C^(n)[0,1]이란?

4. NVS1,NVS2가 isometrically isomorphic이란?(linear, surjective, isometry)(그냥 isomorphic하면, linear, bijective, homeo를 가리킴, 즉 topologically iso)

5. direct sum of NVS using finite p, using inf, using cv to

6. hyplerplane of VS란?

7. NVS가 reflexive란?

*Thm

1. two norms가 equivalent iff C1||x||<=|||x|||<=C2||x||

2. B(NVS1,NVS2):BS iff NVS2:BS

3. dim(NVS):finite이면 any two norms on NVS are equivalent

4. any finite dimensional linear manifold is closed in larger one.

5. f:NVS1->NVS2, linear, dim(NVS1):finite이면 f:continuous

6. K:closed linear subspace of NVS이면

-NVS/K:normed vector space

-natural map Q:NVS->NVS/K, linear, conti, open

-if NVS:BS, then NVS/K도 BS

-U:open in NVS iff Q(U):open in NVS/K

7. X:NVS, M:closed linear subspace of X, N:finite dim of X이면 M+N은 closed linear subspace of X

8. direct sum of NVS using cv to 0 is linear subspace of direct sum of NVS using inf

9. X:direct sum of NVS using finite p

-X:NVS and projection onto NVS_i is linear, conti, bdd with 1 norm, open map, surjective

-X:BS iff NVS_i:BS

10. S:hyperplane of NVS이면 S는 dense in NVS or closed in NVS

11. f:NVS->F, linear functional일때 f:conti iff ker(f):closed

12. (NVS)^*:BS(if NVS is nonzero)

13. (Hahn-Banach Theorem)X:VS over R and g:sunlinear functional, S:linear subspace of X, f:linear functional on S s.t. f<=g

then te F:X->R s.t. F=f on S and F<=g

(이 Theorem의 의미는 g에 dominate가 계속 유지되면서 extension을 찾는 것임)

(Lemma6.3부터 Cor6.8까지 읽기)

(Thm 6.13부터 Cor6.14까지 읽기)

14. (Open Mapping Theorem)f in B(BS1,BS2)가 surjective이면 open map

15. (Inverse Mapping Theorem)f in B(BS1,BS2)가 bijective이면 f^(-1)도 conti(bdd)

16. (Closed Graph Theorem)f:BS1->BS2, linear가 closed graph를 가지면 f는 conti

17. (Uniform Boundedness Principle)F:a collection of f:BS->NVS s.t. for any x in BS, sup over f {|f(x)|}<inf이면 sup over f ||f||<inf

*example

1. semi-inner product인데 not inner product인 예?

2. {f:[0,1]->F, f:AC, f(0)=0, f' in L^2[0,1]} with int from x=0 to x=1 f'coj(g')=<f,g>, HS임을 보여라.

3. 걍 cv인데 not net cv인 예?(net cv를 abs cv로 생각하면 예 찾기 쉬움)

4. idempotent인데 not projection인 예 (1 0 1 0) matrix

5. NVS/S가 seminorm은 되는데 norm안되는 예 X=C_0, M=C_00

6. natural map Q:NVS->NVS/K가 not closed map인걸 보이는 예, X=L^2(-pi,pi), M=V{e_n}, F=V{f_n} where f_n(t) = e_(-n)(t) + n*e_n(t), e_n(t)=exp(int)

7. ker(linear functional):not closed in NVS, dense in NVS인 예 X=C_0(N), {e_n(i)=1 for only i=n}, x_0(i)=1/i, then Hamel basis containing {e_1,...,x_0}, make f

*특정 concepts

-L^p with MS, 1<=p<=inf

-BS

-(L^p)^* = L^q

-p=1일땐 sf-M여야 가능

-reflexive for 1<p<inf

-about K with k

-K:L^p(MS)->L^p(MS), linear, bdd, ||K|| <= (c_1)^1/p * (c_2)^1/q

-l^2(I)

-{simple functions}:dense in l^2(I)

-HS

-basis = {e_i s.t. i in I}

-HS with basis S일때 HS와 l^2(S)는 isormophic as HS

-I=N일 때

-unilateral shift

-isometry

-not surjective

-not normal

-backward shift

-adj(unilateral shift)

-l^inf(I)

-I=N일때

-all bdd seq of scalars

-the bergman space for G

-HS(Cauchy, Riesz, Morera Theorems 필요)

-L^2[0,2pi] with C

-HS

-basis = {1/sqrt(2pi) * exp(int) s.t. n in Z}

-L^2(-pi,pi) with C

-L^2 with MS

-about K with k

-K:L^2(MS)->L^2(MS), linear, bdd, ||K||<=(c1*c2)^(1/2), compact operator, ||K|| <= ||k||_2 (L^2 norm)

-adj(K)는 with kernel conj(k(y,x))

-about Volterra, k:[0,1]x[0,1] ->R, char function of {(x,y) s.t. y<x}

-no eigenvalues

-k:L^2(-pi,pi)xL^2(-pi,pi) -> C,

-L^2 with sf-M

-M_Φ in BS(L^2) and ||M_Φ||=||Φ||

-adj(M_Φ)=M_(conj(Φ))

-M_Φ:normal

-M_Φ:hermitian iff Φ:real

-M_Φ:unitary iff |Φ|=1 a.e.

-L^p with sf-M, 1 <= p <= inf

-M_Φ in BS(L^p) with ||M_Φ||=||Φ||

-C_b(X)

-BS

-C_0(X)

-closed in C_b(X)

-X=N일때

-all seq cv to 0

-C^(n)[0,1]

-BS
 

로지스틱 회귀

-종속 변수가 범주형인 데이터를 대상으로 한다.

-독립 변수를 통해 종속 변수값을 얻고 그것을 통해 classification하는데 사용한다.

-즉, (종속, 독립)=(범주,기타)로 regression돌리고, 실제로 사용은 (얻은값, 입력값)을 통해서 classification

-범주의 종류가 2개보다 많으면 multinomial logistic regression이라 한다.

-범주의 종류가 2개보다 많고 순서가 존재하면 ordinal logistic regression이라 한다.

-얻은값의 범위가 [0,1]이기 위해 logsistic function(1/(1+exp(-x))), gumbell function(exp(-exp(x)))등을 합성해서 사용한다.

-계산 편의상 전자를 많이 쓴다.

-1/(1+exp(-~~~~))는 p(y=1|x)를 가리킨다. 즉 독립변수 x가 주어졌을 때, 그것이 y=1(카테고리)일 확률을 가리킨다.

-추정계수를 구하는 건 Maximum likelihood method쓰거나 gradient descent사용

*정의 

1. X:J->R, rdv, f:pdf of X, 이때 Information entropy(or Shannon entropy) of X is defined as H(X):=(-1)*E[ln(f(X))]

(이때 밑이 2인 log를 사용할 경우 단위는 비트이고 자연로그를 사용할 경우 단위는 nat이다.)

(혹은 H(f)라고도 쓴다.)

2. X,Y:J->R, rdv, f,g:pdf of X,Y, 이때 두 분포의 Kullback-Leibler divergence, KLD is defined as 

D_(KL)(f||g) = int from x=-inf to x=inf f(x)*log(f(x)/g(x))dx (Radon-Nikodym derivative를 사용한 것도 있다.위키참조)

3. H(f,g), the cross entropy between f,g, := E[-log(g)] using pdf f

*의의

1.

-H(X) using parameter p1 > H(X) using parameter p2라면, parameter 값이 p1일 때 불확실성이 더 높다는 의미를 가진다. 예를 들면 동전던지기의 경우, 동전의 앞면이 나올 확률이 1/2일 때가 entropy값이 가장 높게 나오고 그때가 불확실성이 가장 높다는 것. 즉 entropy란 불확실성을 정량화한 지표이다.

-H(f)란 f를 묘사하기위해 필요한 불확실성(정보량)을 가리킨다. 

2. 

-D_(KL)(f||g)는 f가 있는데 샘플링 과정에서 그 f를 근사적으로 표현하는 확률분포 g를 f대신에 사용할 경우 엔트로피 변화를 의미한다. 

-따라서 D_(KL)(f||g) = H(f,g) - H(f)

3. 

-H(f,g)란 f를 묘사하기위해  g를 쓸 경우 필요한 정보량(불확실성)을 가리킨다.

-machine learning and optimization에서 사용되기도 하는데, error function(=cost, loss function)으로서 사용한다. 

-예를 들면 logistic regression의 경우, 분류의 실제 분포가 베르누이를 따른다고 하고 (p=P(y=1)), 실제로 우리가 regression을 통해 얻은 분포(g=P(y=1|x), 

이때 H(p,g)=(-p)*log(g) - (1-p)*(log(1-g)), 이값이 작아지도록 regression 계수 추정 가능(대게는 Maximum likelihood method사용하기도 하지만)

-혹은 samples모두 의 H(p,g)의 평균을 줄이는 방향으로 regression 계수 추정하기도 함

*Class of Graphs and their a(G) in terms of graph invariants

K_n

-a(G) = n

K_(a,b)

-a(G) = min(a,b)

P_n

-a(G) = 2 - 2cos(pi/n)

C_n

-a(G) = 2 - 2cos(2pi/n)

W_n

-a(G) = 3 - 2cos(2pi/n)

S_n

-a(G) = 1

S_n^*(K_(1,n-2)의 pendant vertex와 P_2의 한 점을 identifying)

-a(G) < 0.5(직접 characteristic polynomial 구해서)

Q_n

-a(G) = 2

X(Z_n,C)

-C={1,n-1}

-a(G) = 2 - 2cos(2pi/n)

-C={1,2}

...

J(v,k,i)

-v>=2k, i=(k-1), johnson,

-v>=2k, i=0, kneser

-J(5,2,0), petersen, a(G) = 2

CS(n,w)

-a(G) = n - w

PA(n,w)

-a(G) = 1

Ki(n,w)

ST(a,b)

T(n,a,b)

multipartite

split graph

difference graph

cograph

threshold graph(=maximal graph)

r-regular

(r,s)-semiregular

caterpillar, CTPL

binary tree

------------------------------------------------------------------------------------------------------------------------

*Graph Invariants

V와 V의 subset의 개수

n

τ(G)

γ(G)

α(G)

p(G)

q(G)

E와 E의 subset의 개수

m

Τ(G)

ν(G)

degree관련

δ(G)

d(G)

Δ(G)

1-Zagreb(G)

2-Zagreb(G)

decdseq(G)

tr(G)

path, length관련

r(G)

D(G)

md_G

d(G,k)

W(G)

H(G)

TW(G)

HW(G)

RCW(G)

MTI(G)

DD(G)

topological관련

genus(G)

subgraph관련

sd(G)

g(G)

G(G)

ω(G)

t(G)

Tree관련

Type 1 or Type 2

Connectivity관련

connectivity

# of components

cutvertex

bridge

κ(G)

λ(G)

Color관련

χ(G)

Homomorphism관련

Aut(G)

------------------------------------------------------------------------------------------------------------------------

*Related bounds for a(G), G:connected

a(P_n) <= a(G) <= n (Fiedler 1973)

a(G)<=κ(G)<=λ(G)<=δ(G), (Fiedler 1973)(G:K_n일땐 성립안할 수 있음, 조심)

처음 <은 path생각, 두번째 <은 triangle 2개를 1개꼭지점을 common, 세번째 <은 T1(a,b)에다가 양 끝에 path을 attach한 것

처음 = iff G=G1VG2, where G1:disconnected of order n - κ(G), G2:of order κ(G) with a(G2) >= 2 * κ(G) - n (Kirkland, Molitierno, Neumann and Shader 2002)

if G:not K_n, then a(G) <= [[-1 + 2 * sqrt(1 + 2 * m)]] (Belhaiza, Abreu, Hansen and Oliverita 2005)

a(G) >= 4/(n * D(G)) (Mohar 1992)

a(T) <= 2 * (1 - cos(pi/(D(T)+1))) (Grone, Merris and Sunder 1990)

if T:planar, then a(G) <= 4, with = iff G=K_4 or K_(2,2,2)

if n >= 6 and G:non-isomorphic to K_n, then a(G) < 0.49

a(G) <= a(P_(D(G)+1))

2*cos(pi/n - cos(2pi/n))*κ(G) - 2*cos(pi/n * (1-cos(pi/n)))*Δ <= a(G)

------------------------------------------------------------------------------------------------------------------------

*Main Theory of matrix, or Fiedler vector, etc

y_i = 0 and i~j and y_j > 0이면 te k s.t. i~k and y_k < 0

y_i > 0이면 te j s.t. i~j and y_j < y_i

v:cut vertex, G - k = G_0+G_1+...+G_r일 때

y_k > 0이면 te! G_j s.t. contains a vertex(vertices) with negative valuation이고 나머지 components의 y값은 y_k보다 큼

y_k = 0이고 te G_j s.t. containing both positive and negative이면 te! G_j이고 나머지 components는 다 0

y_k = 0이고 te no G_j s.t. containing aboth positve and negative이면 각 G_k들은 모두 only positive or only negative or only zero

(y_k < 0인 경우도 결국 설명됨, eigenvector니까)(Fiedler 1975)

G:connected with at least one cut vertex일 때 다음 2가지 중 1가지는 반드시 성립(Fiedler 1975)

(a)

te! B0 in which contains both positively and negatively.

Each other block has either vertices with positive only, negative only, or zero only

Every pure path P starting at B0 and containing just one vertex k in B0 has the property that the valuations at the cut vertices contained in P form either an increasing, decreasing, or zero sequence along this path.(pure path란 각 block의 articulation을 0,1번만 지나는 path)

a(G) is simple

(b)

No block of G contains both positive and negative.

te! j which has zero and is adjacent to a nonzero and j is a cut vertex.

Each block contains either positive only, negative only, or zero only.(zero랑 positive가 같이 있는 경우도 없는!)

Every pure path P starting at j has the property that the valuations at the cut vertices contained in P form either an increasing, decreasing, or zero sequence along this path.

the induced subgraph from zero is connected

위의 내용을 Tree에 적용하면(Fiedler 1975)

(a)

all valuations are nonzero

te! ij s.t. yi >0 and yj < 0

any path from i not containing j 는 increasing concave down(위로 볼록)

any path from j not containing i 는 decreasing concave up(아래로 볼록)

a(G):simple

(b)

te! i s.t. yi = 0 and i is adjacent to nonzero

any path from i 는 increasing concave down(위로볼록), decreasing concave up(아래로 볼록), or identically zero.

T:tree일 때

L_k:invertible,

inv(L_k)_(i,j) = sum over all edge in P_(i,j) 1/w(edge)

, where P_(i,j):the set of edges of T which are simultaneously on the path from i to k and on the path from j to k, w:weight

inv(L_k) permutationally similar to a block diagonal matrix in which each block is positive and correponds to a branch at k.(즉 Lap(T)에서 branch에 해당하는 submatrix의 inverse가 됨)(Kirkland, Neumann, Shader, 1996)

T:tree일 때

T:type I with characteristic vertex k iff te two or more Perron branch of T at k.

Moreover, a(T) = 1/specR(inv(L_k)), where L_k:Lap(G)에서 kth row와 kth column제거한 것. (Kirkland, Neumann and Shader 1996)

T:tree, i~j일 때

T:type II with characteristic vertices i,j iff te 0 < eps < 1 s.t. specR(M1 - eps * J) = specR(M2 - (1 - eps) * J)

Moreover, a(T) = 1/specR(M1 - eps * J) = 1/specR(M2 - (1 - eps) * J) and the branch at i containing j is the unique Perron branch at i and the branch at j containing i is the unique Perron branch at j

where M1:bottleneck matrix for the branch at j containing i, M2:bottleneck matrix for the branch at i containing j. (Kirkland and Neumann 1997)

T:tree일 때

T:type I iff te! i s.t. te two or more Perron branches at i

T:type II iff for any i, te! Perron branch at i(Kirkland, Neumann and Shader 1996)

T:tree type I with characteristic vertex i이고 am(a)=k이면 i has exactly k+1 Perron branches(Grone and Merris 1987)

T:tree, i:non-characteristic vertex이면 te! Perron branch at i and the branch contains all of the characteristic vertices of T(Kirkland, Neumann and Shader 1996)

For positive integers k1,k2,...,km, form an tree T by taking a vertex x and making it adjacent to the root vertices of both T(k1,k2,...,km) and T(km,...,k1). Then T is a type I tree with characteristic vertex x.

where T(k1,k2,...,km):한 vertex x에서 k1개 pendant붙이고 각 pendant에 k2개 pendant붙이고...km까지(Kirkland 1999)

T:tree, B:branch at i which does not contain all of the characteristic vertex(vertices) of T. Form T' from T by replacing the B by some other branch B' at i.

M:the bottleneck matrix of B, M':the bottleneck matrix of B'

if M << M', then

a(T') <= a(T)

the characteristic vertices of T' are either on the path joining the characteristic vertices of T to i, or they are located on B'(Kirkland, Neumann 1997)

(A << B means te P,Q s.t. P:Permutation MT, Q:permutation MT, if the order of A < the order of B, PArt(P) is entrywise dominated(<=) by a psubMT of QBrt(Q), if the order of A = the order of B, PArt(P) is entrywise dominated by QBrt(Q) with at least one strictly inequality)

the corollaries

위의 내용을 adding a pendant vertex로 보면

a(T') <= a(T)

the characteristic vertices of T' lie on the path between the characteristic vertices of T and the new pendant vertex.(Kirkland, Neumann 1997)

위의 내용을 change B to path로 보면

Form T' from T by replacing B(the order of B is k) by P_k with i adjacent to the end of P_k, then

a(T') <= a(T)

위의 내용을 change B to star로 보면

Form T' from T by replacing B(the order of B is k) by K_(1,k-1) with i adjacent to the center of the star, then

a(T) <= a(T')

위의 내용을 subtree인 경우를 보면

Any subtree T' of T, a(T') <= a(T)

T:type I with characteristic vertex i, d(i)=d, B1,B2:Perron branches, B3,B4,...,Bd:other branches, |B3UB4U...Bd|=k

Let H:any graph on k vertices

Form G from T by discarding B3,B4,...,Bd and adjoining i to some or all vertices of H.

Then a(G) <= a(T) (Grone and Merris 1990)

------------------------------------------------------------------------------------------------------------------------

*Graph Perbutation and related theorems

G -> G'=L(G)

G -> G'=bar(G)

a(G') = n - μ_G(1)

G -> G'=T(G)

(G,v) -> G'=G-v

a(G') >= a(G) - 1

(G,v) -> G'= (G-v and then +e), smoothing of v

(G,v,k,l), k >= l >= 1, -> G' = v에서 길이가 k, l인 path를 attaching, G'' = v에서 길이가 k+1, l-1인 path를 attaching

a(G') >= a(G'') (Guo 2010)

(G,v) -> G' = adding some edges among pendent vertices at v

if a(G) != 1, then a(G) = a(G') (Shao, Guo and Shan 2008)

(G,U,V) -> VD(G) = (G[U], G[V])

a(VD(G)) <= min(a(G[U]) + |V|, G[V] + |U|)

(G,v,u1,u2,...,uk), each ui not adjacent to v -> G' = G+H, where V(H)=(v,u1,...,vk), v~ui for any i

if G' not K_n, then a(G') - a(G) <= k - eps where eps is the smallest positive root of

"d(v) * eps * (k - eps) - (1 - eps)^2 * (k - 1 - eps)^2" (Kirkland, Oliveira and Justel 2011)

(G,e) -> G'=subdivision of e

a(G') <= a(G)

(G,e) -> G'=contraction of e

(G,e) -> G'=G-e

a(G') <= a(G)

(G,e) -> G'=G+e,

a(G') >= a(G)

(G,v,e) -> G'=G+pe

if G, G':both trees, then a(G') <= a(G)

G1, G2 -> G1+G2

a(G1+G2) = 0

G1, G2 -> G1VG2

a(G1vG2) = min(a(G1)+n2, a(G2)+n1)

G1, G2 -> G1xG2

a(G1xG2) = min(a(G1), a(G2))

G1, G2 -> EDP(G1,G2)

G1, G2 -> DS(G1,G2)

a(DG(G1,G2)) >= a(G1) + a(G2)

(G1,u), (G2,v) -> G = identifying u and v

a(G) <= min(a(G1),a(G2))

(G1,u), (G2,v) -> G' = (G1+G2) + (uv), G'' = G' and then identifying u and v(say u) and then +(uw),

a(G') <= a(G'') (Guo 2010)

(G,u,v) with some nbds of v(Specifically, {v1,v2,...,vs}:subset of N(v) - N(u) and any vi is different from u), G' = G - vv1-vv2-...-vvs + uv1 + uv2 + ... + uvs

if y(u)=y(v), then a(G') <= a(G)(Lama 2016)

-----------------------------------------------------------------------------------------------------------------------

*Extremal Problems

(Among tree, n, D(G))a(T(a,b,c)) is the minimum where a = ]](n-c)/2[[, b = [[(n-c)/2]], c = D(G) - 1(Fallat and kirkland 1998)

------------------------------------------------------------------------------------------------------------------------

*Problems

(Among Tree)one edge subdivision always make a(G) decreasing.

------------------------------------------------------------------------------------------------------------------------

읽었는 논문

읽을 논문

*Special Functions

1. Gamma function(T(z)라 적자.)

-History:Euler가 Factorial function n!의 domain 확장할 때 알아냄

-정의:factorial의 일반화(link1)(link2)

-성질:

-T(z):meromorphic with poles 0, (-1), (-2), ... 

-(1/T(z)):entire with zero at 0, (-1), (-2), ... 

-T(z+1)=z*T(z), T(1)=1(link)

-T(1/2)=sqrt(pi), T(3/2)=sqrt(pi)/2 (더 감소한다, 증가할 것 같았는데)(link)

-Re(z)>0인 z에 대해 T(z)는 적분으로 표현가능(link1)(link2)

2. Beta function(Β(z1,z2)라 적자.)

-정의:for Re(z1)>0, Re(z2)>0, Β(z1,z2):=int over [0,1] t^(z1 - 1) * (1-t)^(z2 - 1) dt.

-성질:

-Β(z1,z2)는 z1,z2에 대해 symmetry

-Β(z1,z2)={T(z1)*T(z2)}/(T(z1+z2))(link1)(link2)

Probability, Statistics, and Process

-About Random Variable(rdv:(J1,C4(J1))->(R(std),C4(TS)), Z라 표현, ((ETR,C4(TS))에서도 다룰 때가 있음))

-Z는 MF이다. MF성질 다 만족

-rdv충분조건

-monotone이면 rdv이다.

-(R(std),C4(TS))에서 C4(TS)의 generating set에 대해서만 판단해도 됨

-정의역이 metric space인 경우, rdv가 conti이면 MF됨

-conti(rdv):rdv됨, 특히 rdv_1+rdv_2 같은 것도 rdv(각 rdv의 C4들이 같을 때 이야기)

-{rdv_n}에서 각 rdv_n의 C4들이 다 같을 때

-sup rdv_n, inf rdv_n, limsup(rdv_n), liminf(rdv_n) 모두 MF가 된다.(ETR,C4(TS))

-{x in J1 s.t. lim rdv_n(x) exists}는 C4(J1)의 원소이다.

-Event 분석

-E1=liminf {rdv_n = a}, E2=limsup {rdv_n = a}

-E3={liminf rdv_n = a}, E4={limsup rdv_n = a} 

-E5={lim rdv_n = a}

이면 

-E1:rdv_n(x)가 어느 순간부터 쭉 a인 x들

-E2:rdv_n(x)가 무한번 a인 x들

-E3:rdv_n(x)의 subsequence의 수렴값 중 가장 작은게 a인 x들

-E4:rdv_n(x)의 subsequence의 수렴값 중 가장 큰게 a인 x들

-E1<E2

-E1<E3

-E1<E4

-E1<E5

-E3교E4=E5

-E3=c-intersection over k, liminf {1-c_k<= rdv_n} 교 limsup{rdv_n<=1+c_k} for dec seq c_k cv to 0

-E4=c-intersection over k, liminf {rdv_n<=1+c_k} 교 limsup {1-c_k<=rdv_n} for dec seq c_k cv to 0

(따라서 E1혹은 E1의 여집합의 정보를 아는 것이 가장 강력하다.)

(Borel-Cantelli, Fatou, Borel Zero-one Law 등 rdv의 liminf, limsup이 아니라, Event의 liminf, limsup에 관한 것)

(따라서 E3, E4등이 나오면 Event의 liminf, limsup으로 바꾸고 다뤄라.)

-C4(f), (f:(J1,C4(1))->(R,C4(TS), f가 rdv란 가정은 없음)

-정의:f가 rdv되게끔 하는 smallest C4 of subsets of J1

(rdv_1, rdv_2가 있을 때 C4(rdv_1 + rdv_2) or C4(sup rdv_1, rdv_2)등은 rdv_1, rdv_2의 형태에 따라 다르다, 단지 알 수 있는 것은 C4(rdv_1 + rdv_2)<C4(rdv_1, rdv_2)와 C4(sup rdv_1, rdv_2)<C4(rdv_1, rdv_2)라는 것만 알 뿐)

-C4(rdv_i)

-정의:rdv_i들 모두가 rdv가 되게끔 하는 smallest C4 of subsets of J1(rdv_i들의 정의역은 모두 같을 때 논의)

-C4(rdv_n>k)

-정의:rdv_(k+1), rdv_(k+2)...모두가 rdv가 되게끔 하는 smallest C4 of subsets of J1

-C4(rdv_n<=k)

-정의:rdv_1, rdv_2, ..., rdv_k 모두가 rdv가 되게끔 하는 smallest C4 of subsets of J1

-C4(rdv)<C4(1)

-for C:collection of subsets of R s.t. C4(C)=C4(TS) of R, C4(rdv^(-1)(C))=C4(rdv) 

-C4(lim rdv_n)의 대표적인 예

-C4(limsup rdv_n)의 원소들

-C4(liminf rdv_n)의 원소들

-{x in J1 s.t. lim rdv_n(x) exists}

-{x in J1 s.t. c-sum rdv_n(x) cv}

-{x in J1 s.t. lim n->inf [rdv_1+rdv_2+...+rdv_n]/n = a}

-ProbM(|rdv1|<inf)=1이면 for any eps>0, te bdd rdv2 s.t. ProbM(rdv1 ≠ rdv2)<e

-Two seq of {rdv1_n}, {rdv2_n}이 tail-equivalent

-정의:c-sum ProbM({rdv1_n ≠ rdv2_n})<inf

-성질

-{rdv1_n}과 {rdv2_n}이 tail-equivalent이면 

-c-sum (rdv1_n - rdv2_n)<inf a.e.

-c-sum (rdv1_n):pt cv a.e. iff c-sum (rdv2_n):pt cv a.e.

-te {a_n} in R^N and te rdv s.t. (sum from k=1 to k=n rdv1_k)/a_n:pt cv a.e. to X이면

(sum from k=1 to k=n rdv2_k)/a_n:pt cv a.e. to X이다.

-About Random Vector((J1,C4(J1))->(R^n,C4(TS)), RDV라 표현, coordinate function은 rdv1,rdv2,...로 표현)

-RDV가 MF이다. 따라서 MF의 성질을 따름

(예를 들면 RDV가 Random Vector iff rdv1, rdv2, ..., rdvn이 rdv)

(또는 MF를 composite해도 MF유지)

-C4(RDV)=C4(rdv1, rdv2, ..., rdvn)

-rdv와 마찬가지로

-RDV가 있으면 (R^n,C4(TS))에 Distribution을 정의할 수 있고, DF(x):=Distribution((-inf,x])로 정의함

((-inf, x]따위를 논하기 위해 R^n에 ordering을 줌)

-DF(x)가 다음을 만족하면, (R^n,C4(TS))에 Distribution(Probability Measure)을 정의할 수 있다.

-lim x->inf(각각의 coordinate모두가) DF(x)=1

-for some x_i, lim x_i ->inf DF(x)=0

-DF is conti from above

-R^n 에서 inc

-DF(x)로도 rdv1,...,rdvn의 ind판정가능

-rdv1,rdv2...등 여러개 있고, 그것의 함수의 distribution 구하기(즉 f(RDV) 형태의 distribution)

-Method1, Use Transformation theorem

-Method2, Use chf

-Method3, Use Transformation and Jacobian(RDV의 joint density을 알고 있을 때)(link)

-About Probability Mass Function for RDV

-정의:discrete RDV가 있을 때 (R^n,C4(TS))에 정의된 Measure을 Probability Mass Function이라 하고 pmf라 적자.

-About Marginal Distribution 

-정의:RDV에서 rdv1을 제외하곤 나머진 inf을 둠으로써 marginal DF을 얻을 수 있다.

(RDV의 Density를 통해 Marginal의 Density도 구할 수 있다.)

-성질

-Marginal Distribution이 같다고해서 Joint Density가 같다곤 보장 안해줌

-RDV가 density를 가지면 marginal density도 항상 존재한다.

-

-About Probability Measure(ProbM이라 하자.)

-f-M이다.

-f:C4->[0,1], f(J)=1이고 f가 finite-additive이면 다음 4개가 모두 동치이다.

-f가 ProbM이다.

-f가 conti from below

-f가 conti from above

-for {E_n} in (J,C4,M) s.t. ProbM(E_n)=1, ProbM(c-intersection E_n)=1

-for {E_n} in (J,C4,M) s.t. ProbM(E_n)=0, ProbM(c-union E_n)=0

(따라서 liminf, limsup 형태의 set을 ProbM을 구할 때 도움 됨)

-almost trivial C4란, 모든 원소의 ProbM이 0이거나 1일 때, C4를 almost trivial C4라 하자.

-ProbM(f-intersection k=1 to k=n E_k)=ProbM(E_1)*(f-product k=2 to k=n ProbM(E_k|f-intersection j=1 to j=k-1 (E_j))(link)

-(The Inclusion-Exclusion Formula)(link)

{E_n}:finite seq, 

M(f-union E_n}=f-sum(M(E_n)) 

- sum 1<=i<j<=n M(E_i 교 E_j) 

+ sum 1<=i<j<k<=n M(E_i 교 E_j 교 E_k)

...+(-1)^(n+1) * M(E_1교E_2교...교E_n)

-Transformation Theorem에 의해, E[X]를 abstract space인 X의 정의역상의 적분으로 구하지 말고, ProbM을 이용하여 Distribution F을 구한다음에 R에서 적분하면 된다.

-(J1,C4(J1))=(R(std),C4(TS))인 경우

-Probability Measure induced by DF라면 {all atoms}={{x} in R s.t. DF(x)-DF(x-)>0}

-About Independence(1개의 ProbM에 대한 Concept)

-{finite개의 events}, {finite개의 classes of events C_n}, {arbitrary개의 classes of events C_t}, {arbitrary개의 rdv_t}

(각각 정의 조심)

-{arbitrarily index개의 classes of events C_t}가 ind이고 각 C_t가 PC이면 {C4(C_t)}도 ind이다.(link)

(이걸로써 two events E_1과 E_2가 ind이면 (E_1)^C와 E_2가 ind인 것도 앎)

(이걸로써 rdv_1, rdv_2가 ind인지는 ProbM(rdv_1<=x, rdv_2<=y)=ProbM(rdv_1<=x)*ProbM(rdv_2<=y)만 따지면 됨)

-rdv_1, rdv_2가 ind, f:MF, g:MF이면 f(rdv_1), g(rdv_2)도 ind이다.

(절댓값을 씌우든 제곱을 하든, exp()을 하든... ind가 유지됨)

-{rdv1_n}, {rdv2_n}, for each n rdv1_n과 rdv2_n이 ind이고 {rdv1_n}:pt cv a.e. to rdv1, {rdv2_n}:pt cv a.e. to rdv2라면 rdv1과 rdv2는 ind이다.(link1)(link2)

-(Grouping Lemma)(link)

:T:index set, {arbitrary개의 C4_t}가 ind, S:another index set, {T_s} is a partition of T일 때 {C4_(T_s)}는 ind이다.

(C4_(T_s)란 T_s의 원소 t_0의 C4인 C4_(t_0)들을 포함하는 (over t_0 in T_s) 가장 작은 C4를 가리킴)

({arbitrary개의 rdv_t}가 ind일 때 주로 사용함)

-f-dim DF를 이용하여 {arbitrary개의 rdv_t}의 ind판정 가능(iff로)

-(Reyni's Theorem)(ind가 아닐 것 같은데 ind인 경우)

:{X_n}:iid with common conti DF, {R_n}:relative rank of {X_n}, E_n=[X_n is a record]일 때

(R_n은 X_1,...,X_n 중 X_n의 순위, 따라서 1,2,3,...,n이란 값을 가질 수 있다.)

(E_n은 X_n이 X_1,...,X_(n-1) 모두 보다 큰 event)

-ProbM[a tie occurs]=0

-{R_n}:ind이고 ProbM[R_n=k]=1/n for k=1,2,3,...,n

-{E_n}:ind이고 ProbM[E_n]=1/n(사실 ProbM[R_n=1]과 같음)

-(Kolmogorov's Convergence Criterion+Kronecker's Lemma을 이용하면)

lim n->inf (n까지 record일어난 횟수/ ln(n)) =1 a.e.인 것도 알 수 있다.(link1)(link2)

-(Borel Zero-One Law, BZO){E_n}:ind events일 때

-c-sum ProbM(E_n)<inf이면 ProbM(limsup(E_n))=0

-c-sum ProbM(E_n)=inf이면 ProbM(limsup(E_n))=1

(ProbM(liimsup(E_n))은 0아니면 1이다. 따라서 ProbM(limsup(E_n))형태로 만들고 주어진 것과 ProbM비교하라.)

note)ProbM(limsup(E_n))=1이 되는 다른 충분조건

-c-sum n=k to n=inf ProbM(E_n|f-intersection i=k to k=n-1 (E_i)^C)=inf for all k({E_n}이 ind일 조건이 없어도)

(Kolmogorov Zero-One Law)(link)

:{X_n}:ind일 때, for any E in C4(lim X_n) ProbM(E)=0 or 1(즉 C4(lim X_n) is almost trivial)

-따라서 [c-sum X_n:cv] 등 대표적인 C4(lim rdv_n)의 원소들은 {rdv_n}이 ind이면 ProbM이 1이거나 0이다.

-{X_n}:ind일 때, tail rdv Z에 대해 P[Z=c]=1인 c가 유일하게 존재

-{X_n}:ind일 때, 대표적인 tail rdv는 

-limsup X_n

-liminf X_n

-{X_n}:ind일 때, 대표적인 tail event

-lim X_n(it exist하는 event)

-c-series X_n(it cv하는 event에서)

-{E_n}:iid, seq of events 이면 ProbM(c-intersection E_n)=c-product ProbM(E_n)

-(J1,C4(1),ProbM1), (J2,C4(2),ProbM2)의 Product Measure on PrC1에서

-C4(1)*와 C4(2)*는 independent

-X1:(J1,C4(1))->(ETR,C4(TS)), X2:(J1,C4(2))->(ETR,C4(TS))

X1*와 X2*는 independent

-rdv1, rdv2:ind이면 E[rdv1*rdv2]=E[rdv1]*E[rdv2](link)

-rdv1 with DF1, rdv2 with DF2, rdv1, rdv2:ind이면 rdv1+rdv2의 DF는 DF1 conv DF2(link) 

-rdv1 with density1, rdv2 with density2, rdv1,rdv2:ind이면 rdv1+rdv2의 density는 density1 conv density2

-RDV=(rdv1,rdv2)의 density = rdv1의 density * rdv2의 density iff rdv1과 rdv2는 ind

-{rdv_n}:ind이고 S_n = sum from i=1 to i=n rdv_i의 성질(iid인 경우는 random walk와 Sample Distribution 참조)

-(Skorohod's Inequality)(link)

:a>0, c=sup over 1<=i<=n ProbM(|S_n - S_i|>a)<1이면

ProbM(sup over 1<=i<=n |S_i|>2a)<={ProbM(|S_n|>a)}/1-c

(즉 stochastic process의 sum의 sup의 확률이 final term의 확률로 표현이 가능하다.)

-(Kolmogorov's Inequality)(link)

:a>0, E[rdv_n]=0

ProbM(sup over 1<=i<=n |S_i|>a) <= E[(S_n)^2]/a^2

(Skorohod's Inequality보단 가정이 쎄서 이론적으로 약하지만, 응용하기엔 좋음)

-(Levy's Theorem)(link)

:{S_n}:pt cv a.e. iff {S_n}:cv in M

(즉 ind인 rdv_n의 S_n은 cv in M만 보여도 pt cv a.e.까지 됨)

-(Kolmogorov's Convergence Criterion, KCC)(link)

:lim n->inf V[S_n]<inf이면 lim n->inf (S_n - E[S_n]):pt cv a.e.

(가정부분이 성립하면 사실상, {S_n - E[S_n]}:cauchy in L2, 따라서 {S_n - E[S_n]}:cv in L2도 됨)

-(Partial Converse)(link)

:{rdv_n}이 uniformly bdd가 되면 역이 성립

-{rdv_n}:uniformly bdd이고 S_n:pt cv a.e.이면 E[S_n]:cv to finite value(link)

-(Kolmogorov's Three Series Theorem, KTS)(link)

:S_n이 pt cv a.e.iff te c>0 s.t.

-sum from n=1 to n=inf ProbM(|rdv_n|>c)<inf

-sum from n=1 to n=inf E[rdv_n * indi_{|rdv_n|<=c}]<inf

-sum from n=1 to n=inf V[rdv_n * indi_{|rdv_n|<=c}]<inf

(한 c에 대해 성립하면 모든 c에 대해서도 성립하고 {rdv_n}:nnn, ind였다면 V[~]조건은 redundant)

 -Convergence

-(Egoroff's Theorem)(link)

:{rdv_n}:finite a.e., pt cv a.e. to rv rdv이면 {rdv_n}:almost uni cv

-{rdv_n}:pt cv a.e. to a rdv이면 {rdv_n}:cv in M(link)

-{rdv1_n}:cv in M, {rdv2_n}:cv in M이면 {rdv1_n * rdv2_n}:cv in M

-{rdv_n}:cv in M iff every subseq of {rdv_n} has a further subseq that pt cv a.e.(link)

-{rdv_n}:cv in M(real-valued) g:(R,C4(TS))->(R,C4(TS)):conti이면 {g(rdv_n)}:cv in M

-{rdv_n}:cv in M(real-valued), monotone이면 {rdv_n}:pt cv a.e.도 된다.

-{rdv_n}:pt cv a.e. to 0이면 표본평균(iid조건없이 general)도 pt cv a.e. to 0

-{rdv_n}:cv in Lp(p>=1) to 0이면 표본평균(iid조건없이 general)도 cv in Lp to 0

-다음 3개는 동치이다.(1<=p<inf)(link1)(link2)

-{MF_n}:cv in Lp

-{MF_n}:cauchy in Lp

-{|MF_n|^p}:u.i. and cv in M (즉 Lp with finite measure, 1<=p<inf는 BS임을 보여준다.)

-(Scheffe's Lemma for DF_n)(link1)(link2)

:{DF_n} with densities {f_n}, DF with density f가 있을 때(즉 DF_n이나 DF 모두가 abs conti with another measure)

sup over E in C4(TS) of R(std) |DF_n(E) - DF(E)| = 1/2 int |f_n - f| (int는 LM에 대해서)

(즉 {DF_n}이 cv in total variance to DF이면 {densities_n}:cv in L1 to density of DF)

역으로 {f_n}:pt cv (another measure)-a.e. to f이면 {f_n}:cv in L1 to f and thus DF_n cv in total variation to DF

-{rdv_n}:pt cv a.e. to rdv이면 {rdv_n}:cv in distrb to rdv(link)

-{rdv_n}:cv in distrb to rdv ({DF_n}, DF)일 때, 

for t s.t. 0<t<1 and DF^(-1):conti at t, {(DF_n)^(-1)(t)}:cv to DF^(-1)(t)(link)

(즉, {rdv_n}:cv in distrb하면 left-conti inverse도 거진 cv in distrb)

-{rdv_n}:cv in distrb to constant이면 cv in M도 됨(link)

({rdv_n}:cv in distrb to constant iff {rdv_n}:cv in M to constant)

-{rdv_n}:cv in distrb to rdv(with DF:conti)이면 DF_n:uni cv to DF(link1)(link2)

-(Baby Skorohod's Theorem)(link)

:{rdv1_n}:cv in distrb to rdv1이면 

te {rdv2_n}, rdv2 s.t.

-{rdv2_n}와 rdv2 defined on ([0,1],C4(TS),LM)

-rdv2_n =_d rdv1_n

-rdv2 =_d rdv1

-{rdv2_n}:pt cv a.e. to rdv2

-(Continuous Mapping Theorem)(link1)(link2)

:{rdv_n}:cv in distrb(pt cv, M) to rdv, MF:R->R with ProbM({rdv in {x s.t. MF is conti at x}})=1이면

{MF(rdv_n)}:cv in distrb(pt cv, M) to MF(rdv)

게다가 MF가 bdd이면 {E[MF(rdv_n)]}:cv to E[MF(rdv)]

(왜 continuous mapping Theorem이라 하냐면, MF가 conti일 때가 자주 쓰이므로)

(따라서 {rdv_n}:cv in distrb to rdv이면 {(rdv_n)^2}:cv in distrb to rdv 등 성립)

(주의해야할 것은, {rdv1_n}:cv in distrb to rdv1, {rdv2_n}:cv in distrb to rdv2한다해서 {rdv1_n + rdv2_n}:cv in distrb to rdv1+rdv2인 것은 아니다. 이러한 주장이 continuous mapping theorem적용해서 얻으려면 먼저 RDV_n의 element의 cv in distrb가 {RDV_n}:cv in distrb to RDV을 보장해주어야 하는데 이게 성립 안함, 따라서 Slutsky's Theorem이 의미가 있는 것)

-(Portmanteau Theorem)(link1)(link2)

:TFAE

-{rdv_n}:cv in distrb to rdv

-for any bdd and conti f, E[f(rdv_n)]->E[f(rdv)]

(bdd and uni-conti f에 대해서도 성립)

(conti and with compact support에 대해서도 성립)

-for any E in C4(TS) of R(std) with DF(bd(E))=0, {DF_n (E)}:cv to DF(E)

-{rdv_n}:cv in M이면 {rdv_n}은 cv in distrb(Using Portmanteau)

-(Slutsky's Theorem)(link)(asymptotically equivalent의 motive)

:{rdv1_n}:cv in distrb to rdv1, {rdv2_n}:cv in M to 0이면 rdv1_n + rdv2_n:cv in distrb to rdv1

(rdv3_n:=rdv1_n + rdv2_n이라두면 다음과 같이 state가능

-{rdv1_n}:cv in distrb to rdv1, {rdv3_n - rdv1_n=rdv_2}:cv in M to 0이면 {rdv3_n}:cv in distrb to rdv1

(즉 seq1가 cv in distrb하고 seq1-seq2가 cv in M to 0이면(asymptotically equivalent라함), seq2:cv in distrb to same of seq1)

-(Second Converging Together Theorem)(link)

:{rdv1_(un)}:cv in distrb to {rdv1_u} as n->inf

{rdv1_u}:cv in distrb to rdv1

for any eps>0, lim u->inf (limsup n->inf ProbM(|rdv1_(un) - rdv2_n|>eps)=0이면

{rdv2_n}:cv in distrb to rdv1

({rdv1_(un)}은 주로 {rdv1_n}의 truncation으로 택해짐)

(3번째 조건때문에 rdv1_(un)과 rdv2_n의 domain with C4가 같아야됨)

-About Convergence in Moments(기본적으로 integral과 limit의 change임, MCT, DCT 등을 이용할 생각)

-{rdv_n}:cv in Lp to rdv이면 ||rdv_n||_p:cv to ||rdv||_p

-{rdv_n}:cv in Lp to rdv이기 위한 충분조건은 {rdv_n}:cv in distrb to rdv and {(rdv_n)^(p+delta)}:u.i. for delta>0

(증명은 baby skorohod and u.i.이용)

-Integration on Probability Measure Space(f-M일 때를 가리킴, 만약 ProbM여야만 한다면 (ProbM일때만 가능)을 적기)

-rdv:integrable iff lim n->inf int over {|rdv|>n} |rdv| = 0(link)

-rdv_n:integrable, uni cv to rdv이면 rdv가 integrable이고 lim과 int change가능

-(Bounded Convergence Theorem)

:{rdv_n}이 uniformly bdd이면 DCT이용가능

-{rdv_i}:u.i. iff (link1)(link2)

sup over i int |MF_i|<inf and

for any eps>0. te delta>0 s.t. for any E in C4 with M(E)<delta, sup over i int over E |MF_i|< eps

-{rdv_i}:u.i.이고 rdv:integrable이면 {rdv_i - rdv}:u.i.이다.(link)

-(Jensen's Inequality)f:R->R, convex이면 E[f(Z)]>=f(E[Z])(ProbM일 때만 가능, 즉 전체 Measure가 1)(link)

-f:inc, g:inc, s:dec, t:dec일 때, 

E[f(rdv)*s(rdv)]<=E[f(rdv)]*E[s(rdv)]

E[f(rdv)*g(rdv)]>=E[f(rdv)*g(rdv)]

E[s(rdv)*t(rdv)]>=E[s(rdv)*t(rdv)]

(직관적으로는 E[f(rdv)]=0, E[s(rdv)]=0일 때, Cov생각)(link)

-Lp-space with f-M

-0<a<b<=inf에 대해 Lb<La(link)

-구체적으로, for f in Lb, ||f||_a <= ||f||_b (link)

(따라서 {MF_n}이 f-M에서 cv in Lb하면 cv in La도 됨)

-lim p->inf ||rdv||_p = ||rdv||_inf(link)

-{rdv_n}:uni cv이면 {rdv_n}:cv in Lp 된다.(0<p<=inf)(link)

-0<a<b<inf에 대해, {rdv_n}:cv in Lb이면 {rdv_n}:cv in La이다.

-About Cov, Cor

-rdv1, rdv2:ind이면 Cov[rdv1,rdv2]=0(역은 성립안함)(둘다 ND이면 역도 성립)

-(-1)<=Cor[rdv1, rdv2]<=1(link)

-Cor[rdv1,rdv2]=1 iff te a>0 s.t. ProbM(rdv2=a*rdv1+b)=1(link)

-Cor[rdv1,rdv2]=(-1) iff te a<0 s.t. ProbM(rdv2=a*rdv1+b)=1(link)

(즉, Cor은 rdv1과 rdv2의 linear 정도를 판단하는 기준이 되며, 주의할 것은 rdv1과 rdv2가 strong relation이 있다하더라도 linear가 아니라면 Cor의 절댓값은 작게 나올 수 있다.)

-몇가지 examples

-sample space J=countable, C4=P(J), 

-PrC1의 Measure(Product Measure보다 general한, using Kernel, or Transition function)

-건설(link1)(link2)

-Step 1 (J1,C4(1),ProbM1), (J2,C4(2)) (J2에는 ProbM가 없음), 에서 transition function을 건설

-Step 2 Prc1을 generating 하는 {all MR}에 PM 건설 using transition function and ProbM1

-Step 3 PM on {all MR}을 PrC1으로 extension(PM이 finite measure이므로 unique하게 extension가능)

-의의

-Transition function을 이용한 Measure on PrC1은 2개의 measure를 이용한 Product Measure on PrC1 보다 general하다.

-성질

-rdv on (J1xJ2,PrC1)이 있으면 Tonelli, Fubini Theorem처럼 rdv의 section의 int가 잘 정의되고, 

rdv의 int=rdv의 section의 int의 int(link1)(link2)

-Conditional Expectation, Conditional Probability

-정의:

-rdv:(J,C4,ProbM)->(ETR,C4(TS)), C:sub sigma-algebra of C4, rdv is in L1(ProbM)일 때, 

rdv로 만든 C에서의 f-sM의 density를 E[rdv|C]라 하고, Conditional Expectation of rdv given C라 읽는다.

(따라서 Conditional Expectation은 density이므로, 항상 적분형태로 써서 이용하도록 버릇들이자.)

-(J,C4,ProbM), E is in C4, C:sub sigma-algebra of C4일 때, ProbM(E|C):=E[indi_E|C]

-E[rdv|rdv_t, t is in T, T:index set]:=E[rdv|C4(rdv_t, t is in T)]

-V[rdv1|rdv2]:=E[(rdv1-E[rdv1|rdv2])^2|rdv2]

-for E1, E2 in C4 s.t. ProbM(E2)>0, ProbM(E1|E2)=ProbM(E1 intersection E2)/ProbM(E2)

-RDV=(rdv1,rdv2)이고 각 density(f)가 존재할 때, density of rdv1을 f1, density of rdv2을 f2라 할 때, 

f(x2|x1):=f(x1,x2)/f1(x1)으로 정의하고 conditional density of rdv2 given rdv1=x1이라 읽는다.

-

-성질

-E[rdv|C]:C-measurable and in L1(rdv:in L1이므로)

-for any E in C, int over E E[rdv|C] dProbM = int over E rdv dProbM

-(J,C4,ProbM)->(rdv1,rdv2) with joint density whose is abs conti with LM일 때, for E in C4(TS) in R(std)

ProbM(rdv2 in E|rdv1)은 marginal density of rdv1을 이용하여 표현된다.

-(linearity), rdv1 in L1, rdv2 in L1, a,b가 실수일 때, E[a*rdv1+b*rdv2|C]=a*E[rdv1|C]+b*E[rdv2|C]

-rdv:C-measurable and in L1이면 E[rdv|C]=rdv a.e.

-E[rdv|{empty, 전체}]=E[rdv]

-(Monotone)

:rdv:nnn and in L1이면 E[rdv|C]>=0 a.e.

-(Modulus Inequality)

-rdv:in L1이면 |E[rdv|C]|<=E[|rdv||C]

-(Monotone Convergence Theorem for Conditional Expectation)(link)

:{rdv_n}:nnn and pt cv a.e. to rdv and in L1, rdv:in L1일 때, E[rdv_n|C]:pt cv a.e. to E[rdv|C]

-(Fatou's Lemma for Conditional Expectation)(link)

:{rdv_n}:nnn and in L1일 때, E[liminf rdv_n|C]<=liminf E[rdv_n|C] a.e.

-(Dominated Convergence Theorem for Conditional Expectation)(link)

:{rdv_n}:pt cv a.e. to rdv and in L1, rdv1:in L1, |rdv_n|<=rdv2 s.t. in L1일 때, E[lim rdv_n|C]=lim E[rdv_n|C] a.e.

-(Product Rule)(link)

:rdv1:in L1, rdv2:C-measurable, rdv1*rdv2:in L1일 때, E[rdv1*rdv2|C]=rdv2*E[rdv1|C] a.e.

-(Smoothing, or Tower Property)(link)

:C*:sub sigma-algebra of C, rdv:in L1일 때, E[E[rdv|C]|C*]=E[E[rdv|C*]|C]=E[rdv|C*]

(특히, E[E[rdv|C]]=E[rdv], 특히 mixtured distribution에 쓰인다.)

-(Projections)(link)

:E[rdv|C] is the projection of rdv onto L2(C) if rdv is in L2(C4)

(즉, L2에선 Conditional Expectation을 Projection으로 볼 수도 있다.)

-C와 C4(rdv)가 ind일 땐 E[rdv|C]=E[rdv](link)

-rdv1, rdv2, rdv1:C-measurable, rdv2:ind wrt C, MF:R^2->R, bdd일 때

E[MF(rdv1,rdv2)|C](w)=E[MF(rdv1(w),rdv2)](link)

-(Jensen's Inequality for Conditional Expectation)(link1)(link2)

:f:R->R, convex, rdv:in L1, f(rdv):in L1일 때, f(E[rdv|C])<=E[f(rdv)|C]

-rdv:in Lp(p>=1)일 때, p-norm of E[rdv|C] <= p-norm of rdv(link)

(따라서, {rdv_n}:cv in Lp to rdv이면 {E[rdv_n|C]}:cv in Lp to E[rdv|C])

-rdv:in L1, {E[rdv|C]}, where collection of conditional expectation over C, is u.i.(link)

-for E in C4(TS) in R(std), (rdv1,rdv2) have joint density일 때 ProbM(rdv2 in E|rdv1)=?(link1)(link2)

-rdv1:in L2, rdv2:in L_inf일 때, E[rdv1*E[rdv2|C]]=E[rdv2*E[rdv1|C]]

-rdv:nnn(or | |취함) and in L1일 때, E[rdv|C]=int over [0,inf] ProbM(rdv>t|C] dt(link)

-(Markov's Inequality, Chebysheff's Inequality for conditional expectation)(link)

:ProbM[|rdv|>=a|C]<=a^(-k)*E[|rdv|^k | C]

-(Conditional Variance Identity)(link)

:V[rdv1]=E[V[rdv1|rdv2]+V[E[rdv1|rdv2]]

-----------------------------------------------------------------------------------------------------------

-Conditional Expectation을 알 경우 전체 Expectation을 구할 수 있음

(1반과 2반의 평균과 학생수를 알면 1반+2반 전체의 평균을 구할 수 있단 소리)

(Conditional variance는 위와 같은 성질이 만족하지 않음)

(반대로 E[Z]구함에 있어서 E[Z|X]를 이용할 수도 있다. unconditional mean=mean of conditional mean)

-E[Z1|Z2]:rdv, Z2->R->R

-E[Z1+Z2|Z3]=E[Z1|Z3]+E[Z2|Z3]

-E[aZ1|Z2]=aE[Z1|Z2]

-E[Z|Z]=Z

-E[Z1|Z1,Z2]=E[Z1], E[Z1|Z2,f(Z2)]=E[Z1|Z2]

-(unconditional mean=mean of conditional mean)E[E[Z1|Z2]]=E[Z1]

-E[E[Z1|Z2,Z3]]=E[Z1|Z2], E[E[Z1|Z2]|Z2,Z3]=E[Z1|Z2]

-V[Z1]=E[V[Z1|Z2]]+V[E[Z1|Z2]]

-----------------------------------------------------------------------------------------------------------

-About Distribution Function, DF, PDF

-DF의 정의:R(std)->[0,1], right-conti, inc, F(-inf)=0, F(inf)=1

(F(-inf)=0이나 F(inf)=1 둘 중 하나가 성립하지 않고 나머진 다 성리한다면, defective DF라 하자.)

-DF의 motive는 rdv:(J1,C4, ProbM)->(ETR,C4(TS)), ProbM과 rdv를 이용하여 (ETR,C4(TS))에 ProbM에 주는 것

(특히 ETR을 generating하는 closed left rays에 관해서)

-Distribution의 정의:ProbM2(E)=ProbM(rdv^(-1)(E)) for any E in C4(TS)

(즉 DF는 Distribution(Measure)의 정의역이 제한된 형태)

-DF((a,b]):=DF(b)-DF(a)

-rdv1 =_d rdv2란, rdv1과 rdv2의 DF가 같음을 의미한다.

-{DF_n}:cv to DF(which is DF or defective DF)

-{DF_n}:cv vaguely to DF 

:for I=(a,b] s.t. DF is conti at a and b, DF_n (I) cv to DF(I) (pt cv 랑 비슷하게 임의의 I fixed하고 n을 inf로)

-{DF_n}:cv properly to DF

:{DF_N}:cv vaguely to DF and DF:non-defective

-{DF_n}:cv weakly to DF

:{DF_n}:pt cv to DF for x s.t. DF:conti at x

-{DF_n}:cv completely to DF

:{DF_n}:cv weakly to DF and DF:non-defective 

(위 4개의 cv의 definition은 DF가 non-defective이기만 하면 4개 모두 equivalent)

(DF_n, DF 모두 rdv에서 induced된거인 경우, 위의 4개 모두 equivalent하다.)(link)

(그때 {DF_n}의 cv를 cv in distrb 혹은 {rdv_n}:cv in distrb라 하자.)

-{DF_n}:cv in total variation to DF

:{sup over E in C4(TS) of R(std) |DF_n(E) - DF(E)|}:cv to 0(real numbers seq의 cv) 

(rdv_n, rdv로 induced된 DF_n, DF의 cv를 논할 땐 rdv_n과 rdv의 domain이 일치할 필요가 없다.)

-DF의 성질({DF_n}의 cv관련해서는 {rdv_n}의 convergence란에 적기로 한다.)

-DF is determined on a dense set of R(std)(link)

(즉 DF1과 DF2가 dense set에서 같다면, R에서도 같음)

-inc이므로 불연속점이 at most countable

-right-conti

-{x in R s.t. DF(x)>=y} is closed in R(std)

-DF가 conti이면 uni conti도 됨

-DF가 conti이고 rdv with DF라면, DF(rdv)~UD([0,1])(link)

-DF:conti iff ProbM(X=a)=0 for any a in R

-rdv1 =_d rdv2이면 E[rdv1^n]=E[rdv2^n] 따라서 V[rdv1]=V[rdv2]도 앎

-rdv1 =_d rdv2이면 MF(rdv1) =_d MF(rdv2) where MF:(R, C4(TS))->(R, C4(TS)), measurable

-Continuous rdv의 FR(Failure Rate, Hazard Rate라 하기도 한다.)

-정의:for x>0, FR(t):=lim x->0+ {ProbM(t<=rdv<t+x|rdv>=t)/x}

-의미:rdv가 the failure time of an item일 때, FR(x)는 the rate of instantaneous failure을 가리킨다.

-성질:(rdv:the failure time of an item, DF:the rdv의 DF, pdf:the rdv의 density)

-FR(t)=pdf(t)/(1-DF(t))

-{DF}, family of DF(defective일 수 있음)의 성질

-E:countable dense in R(std), {DF_n}:seq of DF(defective일 수도 있음)일 때, 

te subseq {DF_(n_k)} s.t. weakly cv to DF(defective일 수도 있음)(link)

-(Selection Theorem)

:Any seq {DF_n} contains a weakly cv subseq(defective일 수도 있음)(증명은 바로 위 문장 이용)

-Collection of DF(not defective)관련

-Collection of DF(not defective)가 relatively compact의 정의

:every seq in the collection has a subseq weakly cv to DF(not defective)(즉 complete cv도 됨)

-Collection of DF가 tight의 정의

:for all eps>0, te K in R(std) s.t. for all DF in the collection, 1-DF(K)<eps

-{rdv_n}이 stochastically bdd의 정의

:{DF_n}이 tight

-(Prohorov's Theorem)(link)

:collection of DF(not defective)가 relatively compact iff the collection is tight

-{rdv_n}관련해서 stochastically bdd 충분조건

-{rdv1_n}, {rdv2_n} 둘 다 stochastically bdd이면 {rdv1_n + rdv2_n}도 stochastically bdd

-te a>0 s.t. limsup n->inf E(|rdv_n|^a)<inf

-{rdv_n}이 [a,b]에서만 함숫값을 가질 때(for all n)

-rdv_n =_d rdv2_n s.t. rdv2_n ~ND(mu_n, (sigma_n)^2), 이 때 {mu_n}, {sigma_n}이 bdd일 때

-DF(x)가 ProbM on (R(std), C4(TS))(즉, DF(E) for E in C4(TS))를 정의할 수 있다. using LM on (0,1]

-DF가 있으면 left-conti inverse of DF(DF^(-1)라 하자)를 생각할 수 있다.

-DF^(-1)의 성질

-DF^(-1):(0,1)->R(std)

-DF가 y값을 가지는 구간이 [x1,x2)일 때, DF^(-1)은 y에서 jumping

-DF가 x1에서 jumping이면(DF(x1-)<DF(x1)=y), DF^(-1)은 (DF(x1-),DF(x1)]에서 x1값을 갖는다.

-inc

-left-conti(link)

-DF(DF^(-1)(y))>=y

-DF(x)>=y iff DF^(-1)(y)<=x

(따라서 DF(x)<y iff DF^(-1)(y)>x도 성립)

(정리하면

DF(x)>=y이면 x>=DF^(-1)(y)

DF(x)>y이면 x>=DF^(-1)(y)

DF(x)<=y이면 x<=DF^(-1)(y)

DF(x)<y이면 x<DF^(-1)(y), 마지막 결과가 중요, 'x<...'에 등호가 안붙음

마찬가지로 DF^(-1)(y)<x일 때가 중요, y<DF(x)가 성립, 등호없이)

-for E in C4(R(std)), the inverse image of E of DF^(-1) is in C4(TS), TS=(0,1] as subspace of R(std) 

-{arbitrary개의 rdv_t} with index set T가 있을 때, E:finite subset of T이라 하면 f-dim DF for E를 정의 가능

-f-dim DF for E로 {arbitrary개의 rdv_t}의 ind 판정 가능(iff로써)

-About MGF

-정의:

-MGF_(rdv)(t):=E[exp(t*rdv)]

-MGF_(rdv)(t):exists if te a>0 s.t. (-a,a)에서 MGF_(rdv)가 finite

-성질:

-MGF_(rdv)(t):exists iff te K>0, c>0 s.t. for any x>0, ProbM(|rdv|>x) <= K*exp((-c)*x) (link)

-MGF_(rdv)(t):exists이면 

-kth-moment:finite(for all k=1,2,3,...), 즉 rdv in Lp for all p(link)

-MGF_(rdv)(t)의 t에 대한 taylor expansion에서 degree n의 계수=E[rdv^k]/k!(link)

-MGF_(rdv1)(t)=MGF_(rdv2)(t) for all t in R iff rdv1 =_d rdv2이다.

(MGF_(rdv1)(t)=MGF_(rdv2)(t) for all t in some neighborhood containing 0 이기만해도 ->성립)

-rdv1, rdv2:ind일 때, MGF_(rdv1+rdv2)=MGF_(rdv1)*MGF_(rdv2)

(모든 moments가 존재하더라도, MGF는 not exist가능)

-(Convergence of MGFs)

MGF_(rdv_n)(t):exists for all n, lim n->inf MGF_(rdv_n)(t)=MGF_(rdv)(t) for t in a nbd(0)이면 

rdv_n:cv in distrb to rdv

(rdv_n이 cv in distrb하는 지랑, limit의 distrb를 알 수 있게 해준다.)

-About chf

-정의:

-chf_(rdv)(t):=E[exp(i*t*rdv)] (iv function이고 항상 modulus가 1보다 같거나 작음)

-성질:

-elementray properties(modulus, uni-conti, etc)(link1)(link2)

-{chf_(rdv)}^2은 rdv - rdv*의 chf이다. where rdv*:iid with rdv

-rdv in L1이면 chf으로 E[|rdv|]구할 수 있다.(prob path책 p324, #9-(f)참고)

-MGF_(rdv)(t) exists for all t in R, 이면 Taylor Expansion가능 using exp(ix)(link1)(link2)

(MGF_(rdv)(t)가 exists하지 않더라도 어느 정도까지 expansion가능하기도 하다.)

-k-th abs moment가 finite이면 chf는 k번 미분가능하고, 

chf_(rdv)(t)를 k번 미분하면 E[(i*rdv)^k * exp(i*t*rdv)] for all t in R (link)

-for any rdv1 rdv2, rdv1 =_d rdv2 iff DF1=DF2 iff chf_(rdv1)=chf_(rdv2)(link1)(link2)(link3)

(rdv, DF, chf s.t. chf:integrable이면 bdd, conti인 density가 존재하고 chf를 적분함으로써 구할 수 있음도 앎)

-(Easy Part of Continuity Theorem for chf)

:{rdv_n}:cv in distrb to rdv이면 대응되는 chf_(rdv_n)(t) cv to chf_(rdv)(t) for all t in R

(continuous mapping theorem이용하면 바로 증명됨, deeper가 자주쓰임)

-(Deeper Part of Continuity Theorem for chf)(link1)(link2)

:lim n->inf chf_(rdv_n)(t)가 exist for all t in R, 일 때

-limit function이 0에서 conti이면 {DF_n}:cv in distrb to DF(not defective)

(이 때 DF는 limit function을 chf로 갖는 것)

(즉 cv in distrb의 충분조건이 될 수 있다. 역도 성립, 역이 바로 밑 문장)

-About Laplace Transform of densities

-성질:

-density1, density2가 다르면 laplace transforms도 각각 다르다. 

(단, density1, density2 둘 중 하나가 [0,inf)에서 0인 경우 제외)

->따라서 laplace transform of density를 보고 density를 알 수도 있다.

-Family of densities

-(Curved, or Full)Exponential families, Natural Parameter Space

-정의:(link)

(natural parameter space는 link안에서 w_i(theta)를 eta_i로 reparametrization해서 얻음)

-의미:어떠한 properties을 만족하는 densities의 family, 구체적인 density가 exponential families의 원소라면, 성질에 의해 moment계산등이 간편해짐

-curved exponential family란, exponential family와 같은 형태의 densities를 갖지만, parameter사이 restriction이 존재해서 dim(parameter)<k일 때를 가리킴, dim(parameter)=k일 때를 full exponential family라 함.

(즉, curved든 full이든 모두 exponential family이므로 일단 exponential family의 성질을 따름?)

-성질:

-어느 family of densities에서 원소의 support가 parameter vector에 depend하면 대게 exponential family되기 힘듦

(여기서 support는 pmf나 pdf가 양수인 정의역의 영역) 

-(Interchange differentiate and integral)(link)

-density function에 ln취하고 partial diff wrt theta한 뒤 pmf나 pdf에 x말고 X를 대입해서 E취하면 0

-density function에 ln취하고 partial diff wrt theta한 뒤 pmf나 pdf에 x말고 X를 대입해서 V취했을 때

-(Population의 density가 exponential families의 원소라면 statistic의 densities의 형태)

-Cramer-Rao Inequality에서의 Information Number를 구하기가 쉽다.

-Natural parameter space의 경우

-Natural parameter space는 항상 convex이다.

-Natural parameter space 또한 exponential families이므로 exponential families성질 만족

-E[t_i(X)]를 C^*(eta)로 구할 수 있다.(link)

-curved exponential family란, exponential families처럼 densities형태

-not exponential family의 예

-UD(0,theta)

-BD(n,p) with n:vary

-TD(n)

-Beta-binomial(a,b,n,p)

-Dirichlet-multinomial

-FD(n,m)

-CD(l,s)

-HGD(N,n,K)

-logistic distribution

-Location families, Scale families, Location-Scale families of the standard density 

-정의:density하나를 평행이동한 것들의 모임, scale한 것들의 모임, 둘다 한 것들의 모임(link)

-성질:

-families의 원소의 ProbM는 Standard density로 구할 수 있다.

-f:density이면 1/a*f((x-b)/a)) 또한 density(for any b, any a>0)

-rdv1 have density f1일 때, rdv2=b+(a*rdv1)은 density를 1/a*f((rdv2-b)/a))를 갖는다.

-복원추출 관련 분포

-Bernoulli-Distr(rdv~BrnD(p)로 표현)

-의미:rdv가 0,1(일반적으론 2개의 값)만 가질 때의 distribution 

-DF, MGF, moment(link)

-Exponential family됨

-chf(link)

-Binomial-Distr(rdv~BD(n,p)로 표현)

-의미:동일한 그리고 독립인 시행을 n번 했을 때 사건 A가 발생하는 횟수의 distribution

-DF, MGF, moment(link)

-Exponential family됨(n이 known이라 not in parameter vector일 때)

-rdv_n~BrnD(p)이고 iid이면, rdv=sum from i=1 to i=n rdv_i, rdv~BD(n,p)

-Characteristic, 

-rdv~B(n,p)일 때, Y=(rdv/n)이라 하면, E[Y]=p, V[Y]=p*(1-p)/n, 즉 n이 커질수록 Y는 p에 가까운 값을 가질 확률이 증가한다. 

-approximation by ND(np,npq) using CLT가능

-p=0.5이면 symmetric해서 approximation이 이해가 될 수 있으나

-예를 들어 p=0.3인경우 오른쪽 tail이 ignorable 

-np>3이면 ND로 approximation, np<=3이면 PD로 approximation

(PD(lambda=np)로 근사가 가능한 이유는 PD는 non-overlapping intervals에선 발생이 ind인 점과 lambda가 1초 동안 poisson process에서의 평균발생횟수임을 이용)

-approximatio할 때, rdv~BD(n,p), P[rdv<=30] approximated, P[ND<=30.5]로 한다. 0.5 correction필요

-Geometric-Distr(rdv~GD(p))

-의미:첫번째 사건 A가 일어날 때까지 시행하는 독립시행의 횟수의 distribution

-독립시행의 횟수의 분포이므로, memoryless property가짐

-DF, MGF, moment(link)

-Exponential family됨

-Characteristic, 

-Negative Binomial-Distr(rdv~NBD(r,p), r은 기준횟수, p는 1번 시행에서 A가 일어날 확률)

-의미:사건 A가 일어난 횟수가 r번이 될 때까지 시행하는 독립시행의 횟수(적어도 n)의 distribution

(사건 A가 r번 나오는 순간, 더이상의 시행은 없는 상황)

(혹은 사건 A가 r번 나오는 순간까지의 실패횟수로 rdv를 정의할 수도 있고, 그때도 NBD(r,p)라 한다. NBDF(r,p)라 적자)

-DF, MGF, moment(link)

-(Hwang)(link)

:rdv~NBDF(r,p), g(rdv):in L1, g(-1):finite일 때, E[(1-p)*g(rdv)]=E[rdv*g(rdv - 1)*(1/r+rdv-1)]

-r이 known이면 Exponential family됨

-Uniform-Distr(rdv~UD(interval), conti Uniform Distrb도 참고)

-의미:n회의 독립시행에서 단 한번 사건 A가 일어났다고 했을 때, A가 발생한 시행의 분포, 이 경우 1/n으로 동일(link)

-Multinomial-Distr(RDV~MND(n,E1,p1,E2,p2,...,Ek,pk)), {E1,E2,...,Ek}는 partition of sample space,ProbM(Ei)=pi)

-의미:n회의 독립시행에서, (E1이 일어난 횟수, ..., Ek가 일어난 횟수)의 분포

(Binomial-Distr는 n=사건A일어난 횟수+사건A^C일어난 횟수 인 경우다. 따라서 Binomial은 Multinomial의 특수한 경우)

-Exponential family됨(n:known이어서 n:not in parameter vector일 때)

-RDV~MND(n,E1,p1,...Ek,pk)의 conditional distrb on (rdv_1,...,rdv_g) 또한 MND을 따른다.(link)

(normalizing 과정 실수 주의)

-비복원추출 관련 분포

-Hypergeometric-Distr(rdv~HGD(N,n,K))

-의미:N개 중 K개의 관심대상이 있는데 n번 비복원으로 추출할 때, 관심대상의 개수의 분포

-PMF, Expectation, Variance(link)

-Negative Hypergeometric-Distr

-의미:사건A가 일어난 횟수가 n이 될 때 까지의 시행횟수(추출 횟수)의 distribution

-Multivariate Hypergeometric-Distr

-의미:n회의 비복원 추출시, n=사건A1일어난 횟수+...+사건Ak일어난 횟수=j1+...+jk, (j1,j2,...,jk)의 분포

note:

Binomial<->Hypergeometric(복원이냐 비복원이냐)

Binomial<->Negative Binomial(총 시행횟수:fixed이고 일어난횟수 관심<->일어난 횟수:fixed이고 시행횟수 관심)

Binomial<->Multinomial(사건A만 관심<->여럿 사건 관심)

Hypergeometric<->Negative Hypergeometric(시행횟수:fixed, 일어난횟수 관심<->일어난 횟수:fixed, 시행횟수 관심)

Hypergeometric<->Multivariate Hypergeo(사건 A만 관심<->여럿 사건 관심)

Multinomial<->Multivariate Hypergeo(복원이냐 비복원이냐)

...비교하며 이해하고 외우기 필요

-Poisson Process 관련 Distribution

-Poisson-Distr(rdv~PD(lambda), poisson process with lambda,t에서 t=1일 때 사건발생횟수의 분포)

-Exponential family의 원소 됨

-PMF, MGF, Moment(link)

-chf

-rdv_n~PD(lambda_n):cv in distrb to rdv~PD(lambda) iff parameter의 cv(link)

-[{PD(n)-n}/sqrt(n)]:cv in distrb to ND(0,1)(link)

-S_n~BD(n,p)에서 p->0, n->inf, 단 np=lambda이면 S_n:cv in distrb to PD(lambda)(link)

-ProbM(rdv=a+1)=lambda/(a+1) * ProbM(rdv=a)(link)

-(Hwang)(link)

:rdv~PD(lambda), g(rdv):in L1, g(-1):finite일 때, E[lambda*g(rdv)]=E[rdv*g(rdv - 1)]

-rdv1~PD(lambda1), rdv2~PD(lambda2), rdv1, rdv2:ind이면 rdv1+rdv2~PD(lambda1+lambda2)(using MGF)

-rdv1~PD(lambda1), rdv2~PD(lambda2), rdv1, rdv2:ind이면 

rdv1|(rdv1+rdv2)~BD(rdv1+rdv2,lambda1/(lambda1+lambda2)가 성립

-Exp-Distr(rdv~ED(lambda))

-의미:Poisson Process에서 첫 사건A가 일어날 때까지의 걸리는 T의 분포

(GMD의 special case로 간주 가능)

-DF, MGF, Moment(link)

-chf(link)

-Exponential family됨

-특징:

-rdv~U((0,1))일 때, -log(rdv)~ED(1)이다.

-FR(t)=lambda

-memoryless property를 갖는다.

-{rdv_n}:iid, {rdv_n}~ED(1)이면 ProbM(limsup rdv_n/ln(n) = 1)=1이다.(link)

-{rdv1_n}:iid, {rdv1_n}~ED(1), M_n:=sup over 1<=i<=n (rdv1_i), {M_n - ln(n)} =_d rdv2

s.t. DF(of rdv2)(x)=exp(exp(-x))

-태생적으로, rdv1~ED(lambda), rdv2~PD(x/lambda)일 때, P[rdv1>=x]=P[rdv2=0]을 만족

-Double Exp-distr(rdv~DED(mu, sigma))

-의미:

-ED를 평균을 중심으로 reflection시킨 형태, 따라서 symmetric이고 tail이 fat(ND보다 훨씬) 하지만 moment도 다 가짐(CD처럼 moment가 없을정도의 tail은 아님)

-혹은 X1~ED(lambda), X2~ED(lambda), X1,X2:iid일 때, X1-X2의 distribution이 motive(합하면 GMD)

-density, Moment(link)

-Erlang-Distr(rdv~ERLD(lambda, n))

-의미:Poisson Process에서 사건 A가 n번째 일어날 때까지의 걸리는 T의 분포

-rdv_n ~ ED(lambda)이고 iid일 때, rdv=sum from i=1 to i=n rdv_i, rdv ~ ERLD(lambda,n)

-Density(link)

-rdv1~ERLD(lambda,n), for any x, ProbM(rdv1<=x)=ProbM(rdv2>=n) where rdv2~PD(lambda*x)(link)

-Gamma-Distr(rdv~GMD(lambda, y))

-의미:Poisson Process에서 사건 A가 y번째 일어날 때까지의 걸리는 T의 분포(y는 실수)

(이때 gamma function필요, 실수!을 위해)

-lambda^(-1)는 scale parameter라 불리고 y는 GMD의 pdf의 shape parameter라 한다. 

-DF, MGF, moment(link)

-Exponential family됨

-using GMD(lambda, y-1), Computation가능, identity(link)

(y=0일 땐 지수분포이므로(상대적으로 쉬운), 반복해나가면 확률 구할 수 있음)

-태생자체가, PD랑 관련있어서, 다음과 같은 부등식 성립

:rdv1~GMD(lambda,y), rdv2~PD(lambda*x)일 때, P[rdv1<=x]=P[rdv2>=y]

-rdv1~GMD(lambda,y1), rdv2~GMD(lambda,y2), rdv1,rdv2:ind일 때 

rdv1+rdv2~GMD(lambda,y1+y2)를 따른다. using MGF

-Weibull-distr(rdv~WBD(lambda, n)

-의미:(ED(lambda))^(1/n)해서 얻은 것

-lambda는 scale parameter라 불리고 n은 shape parameter라 한다.

-DF, MGF, Moment(link)

-Exponential family됨

-FR(t)=(lambda)*n*t^(n-1)

-주로 사용되는 모델형태

-기계의 수명의 분포(각 부품들마다 WBD(lambda, n)대응 시켜버림)

(왜냐하면 FR(t)가 간단함, ProbM(rdv>t)따위도 간단하게 나옴)

(Distribution 관계도 link)

-Conti Uniform-Distr(rdv~UD(interval)

-의미:interval=(0,s)동안에 한번 사건 A가 발생했을 시, (T,T+dt)에서 발생했을 확률은 모든 (T,T+dt)에 대해서 dt/s로 동일한, T의 분포(link)

-DF, MGF, moment(link)

-Beta-Distr(rdv~BTD(a,b), a>0, b>0)

-의미:(0,1)동안에 Poisson Process에서 사건 A가 a+b-1번 발생시 (T,T+dt)에서 a번째 A가 발생할 확률을 가진 시간 T의 분포

(dt->0, a,b는 양의 실수이고 이 때 a!, b!을 위해 gamma function, beta function필요)

(a,b모두 shape parameter라 한다.)

-성질:

-Density유도(link)

-Density, DF, Moment(link)

-Exponential family됨

-a=b=1일 때, rdv~BTD(a,b)=UD([0,1])된다.

-Dirichlet-Distr(RDV~DD(vec{theta_K}) where theta의 성분은 positive real, theta의 dimension은 K)

-의미:

-BTD의 일반화된 것, RDV의 성분의 값들이 각각 (0,1)사이에 놓이는 경우이고 성분의 값 합이 1이 됨

-MND의 probability들의 conjugate prior로써 사용됨

-vec{theta}의 dimension=K라 하면 RDV은 dimension이 K-1(RDV의 마지막 성분:=1-(나머지성분합))

-성질:

-RDV~DD((theta_1,theta_2,theta_3))라 하자. 이 때를 bivariate DD라 한다.

-marginal RDV_1~BTD(theta_1, theta_2+theta_3)

-marginal RDV_2~BTD(theta_2, theta_1+theta_3)

-Normal Distribution(rdv~ND(expectation, variance))

-의미:{Z_1,...,Z_n}이 iid이고 E[Z_1]<inf, V[Z_1]<inf일 때, Sample mean은 ND(E[Z_1],V[Z_1]/n)을 따른다.

(Z_1이 무슨 분포이든 상관없다.)

-성질

-DF, density, MGF, moment(link)

(특이하게 density에 평균과 분산이 포함되어있다.)

-Exponential family됨

-chf

-rdv_n~ND(mu_n,(sigma_n)^2):cv in distrb to rdv~ND(mu,sigma^2) iff 각 parameters의 cv(link)

-X~ND(E[X],V[X])일 때

-E[X]+SD[X]에서 변곡점을 갖는다.

-E[X]에서 선대칭인 density를 갖는다.

-X_n~ND(mu, sigma^2)일 때 sample mean~ND(mu, sigma^2/n)이 된다.

-E[g'(rdv)]을 위한 identity(link)

(g가 특히 polynomial일 때가 유용, Stein's Lemma라 하고, Stein의 shrinkage estimator만들 시에 알게된 identity)

-ND와 관련 분포

-Cauchy Distribution(rdv~CD(l,s))

-의미:이론적인 의미가 큼, moment of any order가 존재하지않는 distribution

-l:location parameter, s:scale parameter, (l,s)=(0,1)일 때, standard cauchy distribution이라 한다.

-rdv1~ND(0,1), rdv2:iid with rdv1일 때, rdv1/rdv2~CD(0,1)(link)

(증명에서 꼭 |rdv2|로 정의하지않아도 됌, V=rdv2로 절댓값없이 해도 결과는 같음)

-성질

-density, DF, chf(link)

-rdv1~CD(0,s1), rdv2~CD(0,s2), rdv1, rdv2:ind일 때 rdv1+rdv2~CD(0,s1+s2)

-rdv~CD(0,s)일 때 a*rdv~CD(0,a*s)(using chf)

-Chi-Squared-Distr(rdv~CSD(d), d은 degrees of freedom이라고 rdv_k~ND(0,1)인 것의 개수)

-의미:rdv_n~ND(0,1)인 iid인 것의 d개의 각각 제곱의 합으로 볼 수도 있고, GMD의 특수한 경우로도 볼 수 있다.

-성질

-Exponential family됨

-sample variance의 distribution approximation때 사용

-density, DF, Moment(link)

-E[h(rdv_d)]=d*E[h(rdv_(d+2))/rdv_(d+2)], where rdv_d~CSD(d), rdv_(d+2)~CSD(d+2)(link)

-활용

-model화한 distribution과 empirical density사이의 거리가 CSD를 따를 수 있다. 그것을 통해, hypothesis test하기도 함

-Noncentral Chi-Squared-Distr(rdv~NCSD(d,lambda)), d는 degrees of freedom, lambda는 noncentrality parameter)

-의미:총 N개,rdv_n~ND(mu_n,sigma^2_n), {rdv_n}:ind일 때, Z=sum from n=1 to n=N (rdv_n/sigma_n)^2의 분포

-성질:

-lambda=sum from n=1 to n=N (mu_n/sigma_n)^2

-rdv1~PD(lambda), rdv2|rdv1~CSD(d+2*rdv1)으로 hierarchy를 구성하면 

-marginal rdv2는 NCSD(d,lambda)임을 알 수 있다.

-E[rdv2], V[rdv2]를 쉽게 구할 수 있다. 

-t-Distr(rdv~TD(d))

-의미:population~ND(mu,sigma^2)일 때, 얻은 random sample로서 mu을 inference할 때, sigma도 모른다. 이 때 standard ND에 sigma자리에 sqrt(V_n)을 넣었을 때 얻는 distribution이고 sample size가 n일 때 TD(n-1)을 따르며 이것을 이용해 mu추정함

-성질

-의미로부터 density 유도 가능(link)

-MGF 존재 안함

-rdv~TD(d)일 때, d-1번째 까지의 moments만 존재

-rdv~TD(d)일 때, E[rdv]=0, V[rdv]=(d/d-2) for d>2

-rdv~TD(d)일 때, rdv^2 ~ FD(1,d)

-F-Distr의 특수한 경우로도 볼 수 있다.

-F-Distr(rdv~FD(n,m))

-의미:population1~ND(mu1,(sigma1)^2), population2~ND(mu2,(sigma2)^2), population1과 population2가 ind일 때, sigma1, sigma2을 비교하고자 {(V1_n)/(sigma1)^2}/{(V2_m)/(sigma2)^2}을 조사하고 싶고, 이것의 distribution이 F-Distr, FD(n-1,m-1)을 따른다. 이것을 이용해 두 populations의 sigma ratio을 추정할 수 있다.

(두 population이 굳이 ND을 따르진 않더라도, 어떠한 조건이 성립하면  

{(V1_n)/(sigma1)^2}/{(V2_m)/(sigma2)^2}은 FD(n-1,m-1)을 따르기도 한다.(Kelker)

-성질

-rdv~FD(n,m)이면 rdv^(-1)~FD(m,n)

-rdv~FD(n,m)이면 {(n/m)*rdv}/{1+(n/m)*rdv)} ~ BTD(n/2, m/2)

-Lognormal-Distr(rdv~LND(mu, sigma^2))

-의미:rdv~ND(mu, sigma^2)인 rdv에 exp을 씌우면 exp(rdv)~LND(mu,sigma^2)

(right-skewed인 모델에 사용, 예를 들면 income~LND(mu, sigma^2))

-성질

-rdv~LND(mu, sigma^2)일 때, log(rdv)~ND(mu sigma^2)이다.

(즉, rdv~LND(mu, sigma^2)에서 mu와 sigma는 log(rdv)의 평균과 표준편차지 rdv의 평균과 표준편차는 아님)

-DF, density, MGF, moment, variance(link)

(모든 moments가 존재하는데 MGF는 exist하지 않는 예)

-Multivariate Normal Distribution(RDV~ND_k(mu, ∑))

-정의

-RDV=(rdv1,rdv2,...,rdvk)인 random vector, every linear combination of its component ~ ND일 때, RDV~ND_k라 한다. (k는 random vector RDV의 size)(link)

-RDV~ND_k(mu, ∑)일 때, ∑가 pdHMT(주로 pdSMT겠지만)일 때, non-degenerate라 한다.(link)

(별말 없으면 non-degenerate만 다루기로 하자.)

-성질

-non-degenerate RDV~ND_k(mu, ∑)일 때 density function은 간편하게 나타내진다.(link)

-rdv1~ND, rdv2~ND라 해서 RDV=(rdv1,rdv2)~ND_2 인것은 아니다.

-특히 Bivariate Normal Distribution((rdv1,rdv2)~BND(mu, ∑)

-rdv1|rdv2또한 ND를 따른다.(link)

-E[rdv1|rdv2]은 rdv2에 의존, V[rdv1|rdv2]은 rdv2값과 무관(link)

-Brownian Motion, Random walk 관련 Distribution

-arcsine-Distb(rdv~arcsine-distrb)

-의미:rdv의 값이 [0,1]까지만 가지고 rdv의 DF, DF(x)=(2/pi) * arcsine(sqrt(x))일 때를 가리킨다.

-Mixture Distribution

-어느 distribution을 보고 hierarchy를 만들 수 있다. 예를 들면 BD(n,p)의 pmf를 보면, p^a*(1-p)^b의 형태를 포함하고 있어서 이것을, p의 분포로써 BTD를 도입하면 hierarchy를 만들 수 있다.

-위의 사실을 이용해, X~distrb1의 평균, 분산 계산등이 용이하지 않을 때, Y~distrb2, X|Y~distrb3 형태로 분석해보고 이 때, distrb3가 비교적 간편하게 나온다면, X의 expectation, variance 등을 distrb1대신 distrb3를 이용 with tower property

(예를 들면 NSCD가 있다.)

-대표적인 예

-rdv1~NCSD(d,lambda), rdv2~PD(lambda), rdv1|rdv2~CSD(d+2*rdv2)

-rdv1~BD(n,p), rdv2~BTD(a,b), rdv1|rdv2~Beta-binomial distribution(rdv2는 p를 결정하는 rdv)

-Beta-binomial distrbution(a,b,n)(rdv~BBD(a,b,n))

-not exponential family(n:known이라면 어떻게 될 까?)

-RDV1~MND(n,E1,p1,E2,p2,...,EK,pK)), RDV2~DD(vec{theta_K}), RDV2|RDV1~Dirichlet-Multinomial

-Dirichlet-Multinomial Distribution(RDV~DMND(vec{theta_K})

-not exponential family

-About 통계량 계산, 의의

-평균과 기댓값의 차이

-평균은, 총 변량/총 개수

-기댓값은 확률변수가 가질 값의 가중치인 확률을 곱해서 모두 더해 놓은 것

-둘이 같을 수도 있으나 태생이 다름

-평균과 중앙값(median)

-N개의 data, z_1<z_2<...<z_N이라 하고 각각이 발생할 확률이 1/N으로 같다고 하자. 

-이때 z의 평균은 z_i들로부터의 거리를 제곱한 값의 합이 최소가 되는 값이다.

-이때 z의 중앙값은 z_i들로부터의 거리의 절댓값의 합이 최소가 되는 값이다.

(N이 홀수이면 중앙값은 z_{(N+1)/2}이고 N이 짝수일 땐 관례상, z_(N/2)와 z_{(N/2)+1}의 평균으로 정의한다.

-Z1과 Z2가 not ind일 때

-(Cauchy-Schwartz Inequality)E[Z1Z2]<={E[(Z_1)^2]*E[(Z_2)^2]}^(1/2)

-V(Z1+Z2+Z3+...+Zn)=sum over i,j cov(Zi,Zj)=sum V(Zn) + sum over i≠j cov(Zi,Zj)

-V(aZ1+bZ2)=a^2V(Z1)+b^2V(Z2)+2abcov(Z1,Z2)

-V(aZ1-bZ2)=a^2V(Z1)+b^2V(Z2)-2abcov(Z1,Z2)

(X=Y1+Y2, A에 투자, B에 투자한 금액이 각각 1억이고 1년 뒤 Y1,Y2억이 된다 했을 때를 생각하면, 투자할 때 cov(Y1,Y2)<0인 곳에 투자를 해야 V(X)가 작아진다. 즉 risk가 작아진다.)

-cov(Z1,Z2)=E[(Z1-E(Z1))(Z2-E(Z2))]=E(Z1Z2)-E(Z1)E(Z2), 중간의 식으로 cov의 의미를 생각할 수 있다.

-cov(Z,Z)=V(Z), 따라서 분산은 cov의 일종을 볼 수 있다.

-cov(sum a_i X_i, sum b_j Y_j)=sum sum a_i b_j cov(X_i, Y_j)가 성립

(i와 j의 ending index가 같을 때, cov(sum a_i X_i, sum b_j Y_j)=0 iff sum a_i b_i =0, 이때 sum a_i X_i와 sum b_j Y_j가 orthogonal이라고 통계학에선 부른다.)  

-cor(Z1,Z2)=cov(Z1,Z2)/[SD(Z1)*SD(Z2)]

(cor은 Z1과 Z2의 선형종속성의 척도, |cor|가 1에 가까울수록 Z1과 Z2는 선형종속에 가까움, i.e. Z1=aZ2+b꼴에 가까움)

(Z1=aZ2+b, a가 양수이면 cor(Z1,Z2)=1, a가 음수이면 cor(Z1,Z2)=(-1))

-About Stochastic Process(SP)

-정의:

-(J,C4,P):Probability Space, (S,C4):MAS가 있을 때, 

S-valued stochastic process(S-SP)란 collection of S-valued random variables on J, indexed by a totally ordered set T

(S를 State Space라 하고, T를 time이라 한다.)

-S-SP(X라 하자.)가 있을 때, for every finite seq T'=(t1,t2,...,tk) in T^k, X_T'의 distribution on (R^k, C4(TS))을 f-dim distribution of X라 한다. 

-Independent Increment

-Stationary Increment

-Markov Property

-

-분류방법

1. Time이 discrete이냐 continuous이냐

2. State Space가 discrete이냐 continuous이냐

3. Special

-AR Process

-Branching Process

-Brownian Motion

-Cox Process

-Covariance Stationary(=2nd Order Stationary=Weakly Stationary)

-Gaussian Process

-Linear Process

-MA(q), MA(inf)

-Markov Process

-Markov Shot Noise Process

-Martingale

-Poisson Process

-Renewal Process

-Random Walk

-Stationary Process

-Semi-Markov Process

-WN, IWN

-성질(time, state의 discrete여부로 성질분류해보고, 이후 중요 Process별로 성질 정리)

-

-Discrete Time

-(Duality Principle)

:{rdv_n}:iid이면 (rdv_1,rdv_2,...,rdv_n) has the same (multivariate) distribution (rdv_n,...,rdv_2,rdv_1). 

(이것으로써 다른 events이지만 같은 ProbM값을 갖는 경우를 만들 수 있다. 문제 해결이 더 쉬운 것으로 change가능)

-Discrete State

-

-Continuous State

-

-Continuous Time

-

-Discrete State

-

-Continuous State

-

-Using Filter and Lag Operation

-filter with {x_n}란 x_0 + x_1 L + x_2 L^2 +..., where L:lag operator

-p-th degree lag polynomial (1) of {x_n}란 filter with {x_n}에서 L^p까지만 

-p-th degree lag polynomial (2) of {x_n}란, 1 - x_1 L - x_2 L^2 - ... - x_p L^p

-abs summable filter with {x_n}란 {x_n}이 abs summable일 때

-inverse of a filter with {x_n}란, (~)*(filter with {x_n})=1인 ~를 가리킴

-multivariate filter with {MT_n}란, 각 성분이 filter with {성분 in MT_n}을 따르는 것(MT가 square일 필요는 없음)

-성질

-filter with {x_n conv y_n}=product of filter with {x_n} and filter with {y_n}(multivariate filter일 때도 성립)

-따라서 filter는 multiplication에 대해 commutative(multivariate filter일 때는 성립안함)

-x_0가 nonzero이기만하면 inverse of a filter with {x_n}이 항상 존재

-abs summable filter with {x_n}이고 inverse가 존재한다해서 inverse가 abs summable임은 보장안됨

-p-th degree lag polynomial (2) of {x_n}의 inverse가 abs summable할 충분조건은 the polynomial에 L대신 z 넣고 = 0 해서 얻은 방정식의 모든 근의 절댓값>1이면 된다. stability condition

-Autocovariance-Generating Function of weak stationary process

-정의:autocovariance를 계수로하는 -inf에서 inf의 power series(centered at 0)

-성질:

-weak stationary process만을 다룬다면, series의 index를 j=1 to j=inf로 one-side로 표현가능

-

-주요 Process

-AR(1)

-정의:SP(={X_n}, n:integer)가 AR Process란, {eps_n=X_n - lambda*X_(n-1)}가 uncorrelated, E[eps_n]=0, V[eps_n]=sigma^2일 때 {X_n}을 AR Process of order 1이라 한다.(deviation-from-the-mean form)

(즉, 다른 form으로는 X_n=c+lambda*X_(n-1)+eps_n, {eps_n}:WN

-성질

-|lambda|<1일 때

-Y_k:=sum from j=1 to j=k (lambda)^j * eps_(n-j)라 할 때, {Y_k}:cv in L2 to X_n(link)

(즉, AR(1) with |lambda|<1은 MA(inf) representation을 갖는다.)

-Cov(X_n,X_(n+k))=(sigma)^2 * lambda^k * (1/(1-(lambda)^2)(link)

(즉 n에는 independent하고 k에만 dependent함)

(사실상 AR(1)을 MA(inf)로 표현해서 MA(inf)에서 cov구하는 방법따른 것)

-|lambda|>1일 때

-AR(1) with |lambda|>1은 future values of eps_n의 MA(inf)로 표현된다.

-|lambda|=1일 때

-AR(1)은 weak stationary process solution을 갖지 않는다. random walk됨

-AR(p)

-정의:

-성질:

-phi_t:Stability Condition을 만족하면 

-MA(inf) 표현가능

-Autocovariance-GF가짐

-weak stationary

-

-ARMA(p,q)(no common root일 때만 다룸)

-정의:

-성질:

-phi_t:Stability Condition을 만족하면

-MA(inf) 표현가능

-Autocovariance-GF가짐

-weak stationary

-theta_t:Stability Condition을 만족하면

-AR(inf) 표현가능 

-Stationary Process

-정의:SP(={X_t})가 stationary process란, for any h>0, for any finite seq T', X_(T') =_d X_(T'+h)

-성질

-for any t, E[X_t]:finite, V[X_t]:finite이면 E[X_t]=constant, V[X_t]:constant이다.(over t)

-Cov[X_t1,X_t2]=R(|t2-t2|), where R(h)=E[(X_h - E[X_h]*(X_0 - E[X_0])]

-Autocorrelation(h)=R(h)/R(0)로 표현가능

-Covariance Stationary Process(second order stationary, weakly stationary라고도 한다.)

-정의:SP(={X_t})가 Covariance Stationary Process란, 

for any t, E[X_t]=constant, Cov[X_t1,X_t2] depends on |t2-t1|

(따라서 Stationary Process일 때처럼 R(h)란게 존재)

-성질

-E[(X_t)^2]=constant over t(따라서 first two moment에 대해서 constant over t라서 second order라고도 함)

-{X_t}:covariance stationary, X_n predict하고 싶을 때 {a_1*X_(n-1)+a_2*X_(n-2)+...+a_p*X_(n-p)|a_i:real}중에서 Mean Square Error(L2 norm error)가 최소인 estimator가 존재하고 estimator을 구할 수 있다.(link)

-(Mean Square Ergodic Theorem)(link)

:{X_t}:covariance stationary with R(h)일 때

lim n->inf (sum from i=0 to i=(n-1) R(i))/n = 0 iff {S_n / n}:cv in L2 to E[X_1]

-abs summable filter with {x_n}은 mapping, {weak stationary process}->{weak stationary process}

(X_t가 vector process이고 multivariate filter여도 성립한다.)

-{X_t}:weak stationary with abs summable autocovariance and Autocovariance-GF이면

for any abs summable {a_n}, a(L)X_t 또한 weak stationary with abs summable Autocovariance-GF 

(X_t가 vector process이고 multivariate filter여도 성립한다.)

-Gaussian Process

-정의:SP(={X_t, t>=0}가 Gaussian Process란, for any finite T'=(t_1,...,t_n), X_T'~ND_n

-Linear Process

-정의:{eps_t}:WN이고 X_t=mu+[sum from j=(-inf) to j=inf (theta_j * eps_(t-j))] with theta_0 =1, {X_t}를 Linear Process라 한다.

-MA(q)

-정의:

-{eps_t}:WN이고({eps_t}:weak stationary이기만해도 정의하기도 함)

X_t=mu + [sum from j=0 to j=q (theta_j * eps_(t-j))] with theta_0 = 1, {X_t}를 MA(q)라 한다.

-성질:

-{X_t}:weak stationary

-MA는 기본적으로 not stochastic, initial condition만 주어지면 이후 값은 not random

-Autocovariance-GF이 존재

-MA(inf)

-정의:{eps_t}:WN이고({eps_t}:weak stationary이기만해도 정의하기도 함)

X_t=mu+[sum from j=0 to j=inf (theta_j * eps_(t-j))] with theta_0=1, {X_t}를 MA(inf)라 한다.

-성질:    

-{theta_j}가 square-summable이면 

-[sum from j=0 to j=inf (theta_j * eps_(t-j))]:cv in L2, 즉 정의 잘됨

-{X_t}:weak stationary

-E[X_t]=mu

-{theta_j}가 abs summable이면 

-{X_t}의 jth autocovariance=sigma^2 * sum from k=0 to k=inf {theta_(j+k) * theta_k}

-{eps_t}의 autocovariance가 abs summable이면, {X_t}의 autocovariance도 abs summable됨

-{eps_t}가 iid이면 {X_t}는 stationary and ergodic됨

-Autocovariance-GF존재

-Markov Process, discrete-time

-정의:Stochastic Process {Z_n}이, P(Z_(n)=j_(n)|Z_(n-1)=j_(n-1),...,Z_0=j_0)=P(Z_(n)=j_(n)|Z_(n-1)=j_(n-1))을 만족할 때, {Z_n}을 Markov Process라 한다.

-성질:

-어떤 Stochastic Process가 Independent Increments라면, Markov Process가 된다.

(역은 성립 안함)

-Markov Decision Process, discrete-time

-정의:(S,A,{transition probability P_a(s,s') depending action a at time t from state s at time t to state s' at time t+1}, R), where S:set of state, A:set of actions, R:set of reward

-Martingale({mg_n}을 martingale로 표현하겠다. 그냥 stochastic process는 {rdv_n}으로)

-정의:

-mg, supermg, submg, fair seq, superfair seq, subfair seq

{C4_n}:Filtration of C4이고

{rdv_n}:(J,C4)->(ETR,C4(TS))이 integrable and adapted이고

for 0<=m<n, E[rdv_n | C4_m] = rdv_m a.e.일 때 {(rdv_n,C4_n)}을 martingale이라 한다.(mg) 

(마지막 조건은 for any n>=0, E[rdv_(n+1) | C4_n] = rdv_n a.e.와 동치이다.)

(E[rdv_n | C4_m] >= rdv_m a.e.일 때는 {(rdv_n, C4_n)}을 submartingale이라 한다.(submg))

(E[rdv_n | C4_m] <= rdv_m a.e.일 때는 {(rdv_n, C4_n)}을 supermartingale이라 한다.(supermg)

(대게는 {Z_n}이 mg, submg, supermg라고 한다. Filtration은 생략하고 적기로 함)

특히 1,2번째 만족하면서 3번째 조건이 다음과 같을 땐 fair seq라 하고 {(d_n,C4_n)}으로 적는다.

"for 0<=m<n, E[rdv_n | C4_m] = 0" (>=일 땐 subfair, <=일 땐 superfair라 한다.)

-{(rdv_n,C4_n)}:predictable이란, rdv_0:C4_0-measurable, rdv_n:C4_(n-1)-measurable

-{(rdv_n,C4_n)}:increasing process(inc process)란, predictable and 0=rdv_0<=rdv_1<=rdv_2<=...(a.e.)

-τ:J->{0,1,2,3,...,inf} wrt filtration {C4_n}가 stopping time이란, for any n in {0,1,2,3,...,inf}, {τ=n} is in C4_n

-C4(τ):={E in C4(C4_n) s.t. for any n in {0,1,2,3,...,inf}, ([τ=n] intersection E) in C4(C4_n)}

(따라서 C4(τ)는 C4(C4_n)의 sub sigma algebra가 된다.)

-{(mg_n,C4_n)}:closed란, lim n->inf mg_n이 exist a.e.이고 E[lim n->inf mg_n |B_m]=mg_m

-regularmg_n란, mg_n이 rdv:in L1, E[rdv|C4_n]=mg_n되는 rdv가 존재하는 mg_n을 regularmg_n이라 한다.

-성질:

-general한 mg, seq만들기

-(From rdv in L1 with Filtration)

:rdv:in L1(C4-measurable), C4_n:inc(to C4)일 때, rdv_n:=E[rdv|C4_n]하면 {(rdv_n,C4_n)}:mg

-(From {rdv_n} in L1)

:C4_0:=Trivial, C4_n:=C4(rdv_1,...,rdv_n)일 때, {(rdv_n-E[rdv_n|C4_(n-1)],C4_n)}:fairseq

-(From {rdv_n} in L1 s.t. ind, mean zero)

:{rdv_n}:ind, in L1, E[rdv_n]=0, rdv_0:=0, C4_n:=C4(rdv_0,...,rdv_n)일 때, 

{(sum from i=1 to i=n (rdv_i),C4_n)}:mg

-(From fairseq with predictable rdv_n)

:{(d_n * U_n, C4_n)}:fairseq if U_n:predictable

-(From {rdv_n}:iid, {0,1,2,3,...} valued, C4_0=trivial, C4_n=C4(rdv_1,...,rdv_n), using generating function)

:{(mg_n(t),C4_n)}:mg where mg_n(t) := {t^(S_n)}/{generating function (t)}^n, 0<=t<=1

-(From State Space = integer인 Markov Chain {Y_n} with transition prob matrix P)

:a=egv(P), f=egv(P,a)라 할 때, {(f(Y_n)/a^n,C4(Y_1,...,Y_n)}은 mg

-Stopping Times(filtration생략하고 τ라 적자.)관련 성질

-τ:C4(τ)-measurable, and C4(C4_n)-measurable

-[τ=n],[τ<n],[τ>n],[τ<=n],[τ>=n] 모두 in C4_n(in C4(τ)은 당연)

-sup τ_n, inf τ_n 모두 stopping time이 된다.

-τ_n이 monotone이면 lim n->inf τ_n은 존재하고 stopping time도 된다.

-τ_1 + τ_2:stopping time이 된다.

-[τ_1 < τ_2], [τ_1 = τ_2], [τ_1 <= τ_2] 모두 C4(τ_1) intersection C4(τ_2)에 속한다.

-for E in C4(τ_1), E intersection [τ_1 <= τ_2]는 C4(τ_2)에 속한다.

-for E in C4(τ_1), E intersection [τ_1 < τ_2]는 C4(τ_2)에 속한다.

-τ_1 <= τ_2 on J이면 C4(τ_1) < C4(τ_2)

-rdv:in L1이면 E[rdv|C4(τ)]=sum from i=0 to i=inf E[rdv|C4_i]*indi_(τ=i)(link)

-{rdv_n}:adapted, in L1일 때 {rdv_n}:mg 

iff for any bdd, predictable {U_n}, for any N, E[sum from i=0 to i=N U_n*d_n]=0 where d_n:mg difference, d_0=rdv_0 - E[rdv_0](link)

-supermg(supermg_n)의 성질(별말 없으면 같은 filtration에 대한 내용임)

-(Pasting Two Supermgs)(link)

:{supermg1_n}, {supermg2_n}, τ s.t. supermg1_τ >= supermg2_τ on {τ<inf}일 때, 

{rdv_n:=supermg1_n * indi_{n<τ} + supermg2_n * indi_{n>=τ}}은 supermg가 된다.
-(Freezing)(link)

:rdv_n:=supermg_min(n,τ)은 supermg이다.

-Positive Supermg({supermg_n}이 nnn라 하자. 생각)에 대해서

-(Boundedness of positive supermg)(link)

:a>0 or C4_0-measurable rdv일 때, 

ProbM(sup over n (supermg_n)>=a|C4_0) <= min(supermg_0/a, 1)이고

sup over n (supermg_n) < inf a.e.

-(Dubin's Inequality, with upcrossing)(link1)(link2)

:0<a<b, k>=1일 때

ProbM(beta(a,b)>=k|C4_0)<=(a/b)^k*min(supermg_n/a , 1)이고 beta(a,b)<inf a.e.

(beta(a,b)란, supermg_n이 a->b을 upcrossing하는 횟수, link참조)

-(Convergence Theorem for a positive supermg)(link1)(link2)

:{supermg_n}은 limit을 갖고 supermg property가 limit에서도 적용, (limit in L1)

-τ_1<=τ_2 a.e.일 때 E[supermg_(τ_2)|C4_(τ_1)]<=supermg_(τ_1) a.e.(link1)(link2)

-submg(submg_n)의 성질

-(Doob Decomposition)(link)

:for any submg_n, te! {mg_n} and {inc process_n} s.t. submg_n = mg_n + inc process_n

-f:R->R, convex, inc, E[|f(mg_n)|]<inf일 때, {(f(mg_n))}:submg(link)

-(Krickeberg's Decomposition)(link1)(link2)

:{submg_n} with sup over n E[(submg_n)^+]<inf에 대해 

te {mg_n}, {supermg_n} s.t. mg_n:nnn, supermg_n:nnn, submg_n = mg_n - supermg_n

-(Submg Convergence Theorem)(link)

:{submg_n} with sup over n E[(submg_n)^+]<inf에 대해

te limit of submg_n whose is in L1

(만약 submg_n가 mg_n이었다면 closed mg_n도 된다.)

-{rdv_n}이 mg이면({mg_n}이라 적자)

-iff {mg_n}:submg and supermg(따라서 submg, supermg 성질들 다 만족함)

-E[mg_n]=E[mg_(n-1)]=...=E[mg_1], 즉 E[mg_n]:constant over n

-te fairseq(subfair, superfair) iff te mg(submg, supermg)(link)

(즉, martingale <-> fairseq, 둘중 하나를 체크하든, 둘중 하나를 만들든...)

-fairseq {(d_n,C4_n)}의 각 d_n이 in L2였으면 d_n은 orthogonal(link)

(이때 {(d_n,C4_n)}으로 induced된 mg_n, E[(mg_n)^2]=E[sum from i=1 to i=n (d_i)^2])

-f:R->R, convex, E[|f(mg_n)|]<inf일 때, {(f(mg_n))}:submg(link)

-rdv:nnn, in L1, {C4_n}:filtration, {mg_n=E[rdv|C4_n]}:pt cv a.e. and cv in L1 to E[rdv|C4(C4_n)]

-About Regularmg_n

-{(mg_n,C4_n)}에 대해 TFAE(link)

-{mg_n}:cv in L1

-{mg_n}:sup over n E[|mg_n|]<inf and E[lim n->inf mg_n|C4_n]=mg_n(closable)

-te rdv in L1 s.t. E[rdv|C4_n]=mg_n , 즉 regularmg_n

-{mg_n}:u.i.

-τ에 대해 mg_τ is in L1(link)

-τ_1 <= τ_2이면 E[mg_(τ_2)|C4(τ_1)]=mg_(τ_1) a.e.(link)

-f:R->R, convex, {f(mg_n)}은 submg by Jensen's Inequality

(따라서 {|mg_n|}, {(mg_n)^2}은 submg됨)

-for any eps>0 and any fixed n in N, 

P(max{|mg_1|,...,|mg_n|}>eps)<=E[|mg_n|]/(eps)

P(max{|mg_1|,...,|mg_n|}>eps)<=E[(mg_n)^2]/(eps)^2

-n<m에 대해 E[mg_n * mg_m]=E[(mg_n)^2](link)

-(Martingale Convergence Theorem)

:sup over n {E[(mg_n)^2]}<=M for some 0<=M<inf이면 lim n->inf mg_n은 exist and finite w.p.1

-(Extended Martingale Convergence Theorem)

:sup over n {E[|mg_n|]<=M<inf for some M>=0이면 lim n->inf mg_n은 exist and finite w.p.1

(따라서 nnn {mg_n}은 반드시 lim n->inf mg_n은 exist and finite w.p.1)

-(Azuma's Inequality)(link)

:mg_0=E[mg_1], -α_i <= mg_i - mg_(i-1) <= β_i for some α_i, β_i >=0 for any a>0이면

ProbM(mg_n - E[mg_n] >= a)<=exp((-2a^2)/sum from i=1 to i=n (α_i+β_i)^2)

ProbM(mg_n - E[mg_n] <= -a)<=exp((-2a^2)/sum from i=1 to i=n (α_i+β_i)^2)

-{rdv_n}이 submg이면({submg_n}이라 하자.)

-iff {-submg_n}이 supermg

-E[submg_n]:inc over n

-(Kolmogorov's Inequality)

:for any eps>0 and {Z_n}:nnn submartingale, ProbM(max{Z_1,...,Z_n}>eps)<=E[Z_n]/eps

-te {mg_n}, {rdv_n} s.t. submg_n = mg_n + rdv_n and {rdv_n}:inc(link)

-{rdv_n}이 supermg이면({supermg_n}이라 하자.)

-E[supermg_n]:dec over n

-mg만들기

-{rdv_n}:iid, integrable, E[rdv_n]=0일 때, 처음부터 n까지 합 S_n, {S_n}:mg

-{rdv_n}:iid, rdv_n=sum from i=1 to i=n rdv_i, E[e^(a*rdv_1)]=1인 a가 존재하면 {e^(a*S_n)}:mg(link)

-{rdv_n}:iid, integrable, E[rdv_n]=1일 때, k=1 to k=n까지 rdv_k의 곱 P_n, {P_n}:mg

-{rdv1_n}:integrable, {rdv2_n=rdv1_n - E[rdv1_n|rdv1_1,rdv1_2,...,rdv1_(n-1)]}일 때 

S_n=sum from i=1 to i=n Y_i, {S_n}:mg

-Branching Process

-Doob Martingale

-정의:rdv1:integrable, {rdv2_n}가 있을 때, 

{E[rdv1|rdv2_1,rdv2_2,...,rdv2_n]}:mg가 되고, Doob martingale이라 한다.(D-mg라 하자.)

-{rdv_n}:D-mg iff {rdv_n}:u.i.(link1)(link2)

-About Random Time(꼭 {mg_n}이 주어진건 아닌 상황)

-정의:

{rdv_n}:(J,C4)->(ETR, C4(TS))

N:(J,C4)->(ETR, C4(TS)), integer-valued or inf-valued인 rdv

{N=t} depends on only values of rdv_1, rdv_2, ..., rdv_t일 때, N을 random time for {rdv_n}이라 한다.

(ProbM(N<inf)=1이면 random time N for {rdv_n}을 stopping time for {rdv_n}이라 한다.)

(random time N for {rdv_n}에 대해, bar{rdv_n}:=rdv_n(if n<N) or rdv_N(if n>=N), 이 때 bar{rdv_n}을 stopped process with N이라 한다.)

-성질:

-N이 random time for {rdv_n}일 때 

-{N>=n}은 rdv_1, rdv_2,..., rdv_(n-1)만 주어지면 determined(여사건 생각)

-N이 stopping time for {rdv_n}일 때

-lim_n->inf bar{rdv_n}=rdv_N w.p.1

-bar{rdv_n} - rdv_N = [bar{rdv_n} - rdv_N]*indi_{n<N}

-rdv_N = rdv_1 * indi_{N=1} +rdv_2 * indi_{N=2} +....

-(Wald's Equation)(link)

:{rdv_n}:iid, quasi-integrable이고 N:stopping time for {rdv_n}, integrable이면 

E[sum from i=1 to i=N X_i]=E[N]*E[X_1]

(P(N<inf)=1보다 E[N]<inf가 강한 조건이다.)

-{mg_n}과 N:random time for {mg_n}, {submg_n}, {supermg_n} 이 주어지면

-stopped process {bar{mg_n}}도 martingale이다.(link)

(따라서 E[bar{mg_n}]=E[bar{mg_(n-1)}]=...=E[bar{mg_1}]=E[mg_1]이다.)

-N:stopping time for {mg_n}이기도 할 때

-{bar{mg_n}}:uniformly bdd이면 lim n->inf E[bar{mg_n}]=E[mg_N](=E[mg_1])(link)

-N:bdd w.p.1이면 lim n->inf E[bar{mg_n}]=E[mg_N](=E[mg_1])(link)

-N:integrable and te M<inf s.t. E[|mg_(n+1)-mg_n| | mg_1, ..., mg_n]<=M for all n이면

limE[bar{Z_n}]=E[Z_N](=E[Z_1])(link1)(link2)

(for all n을 for all n s.t. n<N으로 바꿔도 상관 없음)

-N:stopping time for {submg_n}

-stopped process bar{submg_n}도 submg이다.

-{bar{submg_n}}:uniformly bdd이면 E[submg_N]>=E[submg_1]

-N:bdd w.p.1 by (n_0)이면 E[submg_(n_0)]>=E[submg_N]>=E[submg_1]

-N:integrable and te M<inf s.t. E[|submg_(n+1)-submg_n| | submg_1, ..., submg_n]<=M for all n이면 

E[submg_N]>=E[submg_1]

(for all n을 for all n s.t. n<N으로 바꿔도 상관 없음)

-N:stopping time for {supermg_n}

-stopped process bar{supermg_n}도 supermg이다.

-{bar{supermg_n}}:uniformly bdd이면 E[supermg_N]<=E[supermg_1]

-N:bdd w.p.1이면 E[supermg_N]<=E[supermg_1]

-N:integrable and te M<inf s.t. E[|supermg_(n+1)-supermg_n| | supermg_1, ..., supermg_n]<=M for all n이면 E[supermg_N]<=E[supermg_1]

(for all n을 for all n s.t. n<N으로 바꿔도 상관 없음)

-About Random Walk

-{rdv_n}:iid, E[rdv_1]>0, S_0=0, S_n:=sum from i=1 to i=n rdv_i, N=min{n|S_n>0}이면 E[N]<inf이다.(link1)(link2)

-{rdv_n}:iid, E[|rdv_1|]>0, S_0=0, S_n:=sum from i=1 to i=n rdv_i, A>0, B>0, N=min{n|S_n>A or S_n<(-B}이면 E[N]<inf이다.(link)

-(Spitzer's Identity){S_n}:random walk, {Max_n=max{0,S_1,...,S_n}}일 때, E[Max_n]=sum from k=1 to k=n E[S_k^+]*1/k

-WN(White Noise)

-정의:E[X_t]=0, E[(X_t)^2]=sigma^2, Cov[X_t,X_(t-j)]=0 for j not equal to t

-성질:

-Covariance Stationary 성립

-iid이면서 WN을 IWN이라 한다.

-VWN(Vector White Noise)

-정의:{X_t, column vector}, E[X_t]=0, E[X_t * ct(X_t)]=positive-definite(fixed for t), E[X_t * ct(X_(t-j))]=0

-성질:

-E[X_t * ct(X_t)]의 대각성분이 다 같다라는 제한이 없다.

-X_t의 성분끼리의 perfect correlation은 있을 수 없다.(positive-definite때문)

-VMA(inf)(Vector MA(inf) process)

-정의:MA(inf)와 유사, 단지, mu, theta_j(seq of square matrix), {eps_t}:VWN, theta_0=IMT일 뿐

-성질:

-{theta_j}가 abs summable이라함은 각 성분들이 각각의 series가 abs summable이란 것

-MA(inf)의 성질들이 모두 만족함

-Continuous-time Process

-{Z_t, t>=0}가 continuous time stochastic process on the probability space (J,C4,M) whose paths are continuous인 경우, rdv_1:(J,C4)->[0,inf)가 있다면 Z_rdv_1는 rdv가 된다. P(rdv_1<inf)=1이라는게 중요

-Counting Process{N(t):t>=0}

-정의:[0,t]까지 사건 A가 일어난 횟수가 N(t)

-몇가지 용어들

-N(t)가 independent increments:for any two disjoint time intervals I1,I2, 각각에서 A가 일어난 횟수는 independent

-N(t)가 stationary increments:사건 A가 일어난 횟수의 distribution on any interval은 interval의 길이에만 dependent(interval의 위치와는 independent)

(즉 N(t2+s)-N(t1+s)와 N(t2)-N(t1)의 distribution이 같음, t1<t2, s>0)

-성질

-N(t)>=0

-N(t) integer valued

-t1<t2이면 N(t1)<N(t2)

-t1<t2이면 N(t2)-N(t1)은 (t1,t2]에 일어난 횟수

-Poisson Process with lambda>0

-정의:counting process N(t)가 N(0)=0 and independent increments and 길이가 dt인 interval에서 사건 A가 일어난 횟수가 poisson distributed with mean (lambda*dt)인 counting process을 Poisson Process라 한다.

혹은 (link)처럼 건설 가능

-성질

-counting process의 성질들을 만족한다.

-stationary increments

-counting process N(t)가 poisson process with lambda>0 

iff N(0)=0, stationary increments, independent increments, P{N(h)=1}=lambda*h+o(h), P{N(h)>=2}=o(h)

(이 성질로써 어떠한 counting process가 poisson process인지 확인 하기 쉬워짐)

-Brownian Motion

-Motive:(link1)(link2)

-Definition

-X_0=0

-{X_t}:stationary increments, independent increments

-X_t~ND(0,c^2 * t) for some fixed constants c(c=1일 때, Standard Brownian Motion이라 한다.)

-Properties

-{X_t}:Brownian Motion이면 {X_t * 1/c}:Standard Brownian Motion이 된다.

(Standard Brownian Motion에 대해서만 공부해도 됨, 따라서 이하 별말 없으면 Standard인 경우만 고려)

-{X_t (w) : t>=0}, sample path, 모든 sample path는 continuous over t

-모든 Sample path는 nowhere differentiable

-X_t의 density는 f_t(x)=1/sqrt(2*pi*t) * exp(-x^2/2t)

-{X_(t_1), X_(t_2), ..., X_(t_n)}의 joint density f(x_1,x_2,...,x_n)은 

f_(t_1)(x_1)*f_(t_2 - t_1)(x_2)*...*f_(t_n - t_(n-1))(x_n)

-for s<=t, Cov(X_s, X_t)=s(link)

-Markov Process가 된다.

-Gaussian Process가 된다.

-{X_s|s<t, X_t = b}의 분포는 ND((b*s)/t, s*(t-s)/t)을 따른다.(link)

(b=0, t=1일 때, {X_s}을 Brownian Bridge라 한다. {X_t}:Standard Brownian Motion, {X_s}:Brownian Bridge)

-Gaussian Process이다.X_s~ND(0, s*(1-s))

-0<a<=b<1일 때, Cov[X_a, X_b|X_1 =0]=a*(1-b)(link)

-Z_t = X_t - t*X_1로 표현가능하다.(Z_t는 Brownian Bridge)(link)

-About Hitting Time

-a>0, T_a :=inf{t>0|X_t =a}, 즉 T_a는 {X_t}가 a를 hit하는 최소시간일 때

-(Reflection Principle)(link)

:Y_t:=(X_t) * indi_(t<=T_a) + (2*X_(T_a) - X_t) * indi_(t>T_a)도 standard brownian motion

-ProbM(T_a<inf)=1(link1)(link2)

-ProbM(T_a<=t)도 앎(link1)(link2)

-ProbM(T_a<=t)=2*ProbM(X_t>=a)=ProbM(|X_t|>=a)=ProbM(sup over s in [0,t] X_s >=a)

(link1)(link2)

(따라서 |X_t| =_d sup over [0,t] X_s)

-E[T_a]=inf(link1)(link2)

-(Absorbed Brownian Motion)

-X_t:=X_t for t<=T_a, a for t>T_a일 때, X_t를 absorbed brownian motion이라 한다.

-Absorbed Brownian Motion의 CDF(link)

-t1<t2에 대해 E(t1,t2):={x in J s.t. X_t hits 0 at least one in (t1,t2)}

-ProbM(E(t1,t2))=1 - {(2/pi) * arcsine(sqrt(t1/t2))}(link)

(따라서, for 0<x<1, ProbM(X_t has no zeros in (xt,t))=(2/pi)*arcsine(sqrt(x)))

-(Arcsine Law)

-L:=sup{t in [0,1] s.t. X_t = 0}, L~arcsine-distrb(link)

-M*:=argmax over t in [0,1] (X_t), M*~arcsine-distrb(link)

-(Occupation Time)

-A_t:=the amount of time in [0,t] s.t. X_t>0일 때, {A_t / t}~arcsine-distrb

-About Reflected Brownian Motion

-|X_t|를 reflected brownian motion이라 한다.

-reflected brownian motion의 CDF, Expectation, Variance(link)

-About Maximum process {sup over s in [0,t] X_s}

-ProbM(sup over s in [0,t] X_s >= a) = ProbM(T_a <= t)=ProbM( |X_t| >= a) = 2*ProbM(X_t>=a)

({sup over s in [0,t] X_s}과 |X_t|은 have the same law라 한다.)

-(Levy's Theorem on the maximum process)

:{(sup over s in [0,t] X_s) - X_t} is a reflected brownian motion

-About Geometric Brownian Motion

-exp(X_t)를 Geometric Brownian Motion이라 한다.

-Expectation, Variance(link)

-About Integrated Brownian Motion

-int over [0,t] X_s ds(pathwise integration)을 Integrated Brownian Motion이라 한다.

-

-About Brownian Motion with drift mu

-X_0=0, {X_t}:stationary increment and independent increment, X_t~ND(mu*t, t)일 때 

{X_t}를 Brownian Motion with drift mu라 한다.

-Approximation by random walk(link)

-About Hitting time 

-A>0, B>0, P(X_t hits A before -B)=(1-exp(-2*mu*B))/(1-exp(-2*mu*(A+B)))

-

-About Queueing Theory(A/B/C model이란, A는 Customer arrive의 분포, B는 Service time의 분포, C는 server개수)

-G/G/1 Model

-Situation:

-Customer arrive at time C_1, C_2, ...

-Interarrival time X_1=C_1, X_2=C_2-C_1,...

-Service time C_1 has Y_1, C_2 has Y_2, ...

-{X_n}:iid, {Y_n}:iid

-D_n:=n번째 손님이 도착했을 때, 남아있었던 workload, 즉 D_n:=max(D_(n-1)+Y_(n-1)-X_n,0)

-성질

-U_n:=Y_n - X_(n+1)이라 할 때

-E[U_1]>0이면 D_n->inf w.p.1

-E[U_1]<0이면 D_n->D_inf w.p.1 for some rdv D_inf

-for any C>0, P(U_1>0)>0 이고 te theta>0 s.t. E[exp(theta*U_1)]=1이면 

-P(D_inf>=C)<=exp((-theta)*C)(link1)(link2)

-(G/M/1)게다가 {Y_n}~ED(mu)라면 P(D_inf>=C)={(mu-theta)*e^(-theta*c)}/(mu), P(D_inf = 0)=(theta)/(mu)(link1)(link2)

-(M/M/1)게다가 {X_n}~ED(lambda)라면 

-lambda<mu

-P(D_inf>0)=(lambda)/(mu)

-About Statistics

-기초

-Sample(표본)을 이용하여 Population(모집단)의 Characteristic(성질)을 Inference(추론)하는 것

-Inference는 estimation(추정)과 hypothesis test(검정)으로 이루어짐

-prediction(or forecasting, 예측)은 대게 시간이 지나면 실제값이 알려지나 안 알려질 수도 있다.

-population은 '필요한 정보'가 무엇이고 '얻을 수 있는 정보'가 무엇인지에 달려있다.

-통계학의 주요과제는 통계적 추론의 목적에 적합한 통계량(statistic)을 찾은 다음, 그 분포(표본분포, 통계량의 분포)를 구하는 것인데, 이 때 likelihood function이 핵심적인 역할을 한다. (sample {Z1,...,Z_n}이 iid인 경우)

LF는 통계량의 분포를 구하는데에만 쓰이는 게 아니라, 적합한 통계량을 찾는데에도 쓰인다.

-Data Type, categorical(=nominal, category가 2개이면 binary), numerical

-Data Presentation

-categorical data용

-bar chart

-Pareto chart

-pie chart(각 category의 total data set에서의 proportion 강조)

-numerical data용

-histogram

-box plot

-"복원 추출", "독립 시행"과 관련된 모든 것이 독립인 것은 아님

-About Sample

-정의:

-(Z_1,Z_2,...,Z_n), random sample(of size n from the population), if {Z_1,Z_2,...,Z_n}:iid일 때

-(Z_1,Z_2,...,Z_n), simple random sampling, if 비복원 from a finite population(별 언급없으면 random sample)

-S(Z_1,Z_2,...,Z_n)을 statistic이라 한다. (rdv, RDV 가능)

(즉 random sample의 function(scalar-valued일 수도, vector-valued일수도)

(S의 distribution을 sample distribution of S라 한다. 대표적인 statistic으론 sample mean, sample median, sample trimmed mean, sample mode, sample variance, sample quantile 등이 있다.)

-SS(Z_1,Z_2,...,Z_n), sufficient statistic for theta란, (Z_1,...,Z_n)|SS(Z_1,Z_2,...,Z_n), 즉 conditional distribution이 not depend on theta일 때의 statistic

-minimal SS(Z_1,Z_2,...,Z_n)란, 임의의 SS(Z_1,Z_2,...,Z_n) for same parameter의 function으로 표현되는 SS(Z_1,...,Z_n)을 가리킨다.

-AS(Z_1,Z_2,...,Z_n), ancillary statistic for theta란, the statistic의 distribution이 not dependent on theta일 때를 가리킨다.

-{densities of statistic along theta}:complete란 

for any theta, for any MF인 g s.t. independent of theta 

E[g(the statistic)]=0이면 ProbM(g(the statistic=0))=1 for any theta. 

그리고 이 때 statistic을 complete statistic이라 한다.

-Order Statistic, (Z_(1),Z_(2),...,Z_(n)), random sample을 ascending순으로 나열한 것

-sample range, Z_(n) - Z_(1)을 가리키며 population의 dispersion의 indicator가 될 수 있음

-sample median, Z_({(n+1)/2})(n이 odd일 때), (Z_({n/2})+Z_({n/2 + 1}))/2, sample mean보다 outlier에 덜 영향을 받는게 주요특징 

-sample midrange, (Z_(1)+Z_(n))/2

-estimate error란 estimator of parameter - parameter를 가리키고, estimator - parameter는 확률변수가 된다. 왜냐하면 estimator가 확률변수이므로, parameter는 확률변수 아님, 단지 모를 뿐임

-estimate error가 양수이면 overestimation, 음수이면 underestimation이라 한다.

-Notation:

-observed(or realized) sample의 표현은 {z_1,z_2,...,z_n}으로 나타낸다.(각각은 real number)

-모집단의 평균을 mu, 표준편차 sigma, 그냥 density는 모집단의 density

-S_n:=Z_1+Z_2+...+Z_n

-bar{Z}:=(sum from i=1 to i=n Z_i)/n, 즉 sample mean

-V_n:=(sum from i=1 to i=n (Z_i - bar{Z})^2)/(n-1), 즉 sample variance

-성질:

-simple random sampling의 경우 ind는 보장안되지만 identically distributed는 됨

-simple random sampling이더라도 population의 size N이 n에 비해 많이크면 random sample취급 가능

-About Sample Distribution

-About Sample mean, bar{Z}(Sample Variance의 내용도 많이 포함됨)

-E[bar{Z}]=mu

-V[bar{Z}]=(sigma)^2/n

-bar{Z}는 d((z_1,z_2,...,z_n),(bar{Z},bar{Z},...,bar{Z}))가 최소가 되게한다. 

where d:euclidean metric

-Population의 density가 Location-Scale Family의 원소였다면, standard의 sample mean에 대해서만 조사해도 나머지 family의 원소의 density를 따를 때도 sample mean의 distribution쉽게 앎

-{Z_n}:iid일 때 TFAE(link)

-Z_1:integrable

-for any eps>0, sum from n=1 to n=inf ProbM(|Z_1|>eps*n)<inf

-|Z_n / n|:pt cv a.e. to 0

(처음거랑 두번째거는 iid와는 무관하게 equivalent, 걍 하나의 rdv에 관한 이야기)

(Kolmogorov's S-LLN과도 연관있음)

-(Weak Law of Large Number, W-LLN)(bar{Z}의 cv in M)

:{Z_n}:iid, V[Z_1]:finite일 때(finite mean도 됨, finite variance->L2->L1->finite mean)

-bar{Z}:cv in M to mu(link)

-V_n:cv in M to (sigma)^2(link)

-(General W-LLN)(identically distribution과 finite mean, finite variance조건이 없어짐)(link)

:{Z_n}이 ind이고 

lim n->inf sum from i=1 to i=n ProbM(|Z_i|>n) = 0이고 

lim n->inf [sum from i=1 to i=n E[(Z_i)^2 * indi_{|Z_i|<=n}]]/n^2 = 0이면

for a_n=sum from i=1 to i=n E[(Z_i)*indi_{|Z_i|<=n}], S_n=sum from i=1 to i=n (Z_i)

[S_n - a_n]/n : cv in M to 0

note)(General W-LLN의 배경)

-finite mean 조건 약화시키기

-Z:integrable(즉 finite mean과 동치)이면 lim n->inf n*ProbM(|Z|>n) = 0 (역은 거짓)(link)

-Z:integrable iff for any eps>0, sum from n=1 to n=inf ProbM(|Z_1|>eps*n)<inf)(link)

note)(General W-LLN으로 나머지 W-LLN체크)

-{Z_n}:iid with finite variance(link)

-(Khintchin's W-LLN){Z_n}:iid with finite mean(link)

-{Z_n}:iid with finite mean using chf(link)

-(Feller's W-LLN){Z_n}:iid with lim x->inf x*ProbM(|Z_1|>x)=0(link)

-(Strong Law of Large Number, S-LLN)(bar{Z}:pt cv a.e.)

:{Z_n}:ind, {a_n}:inc with lim n->inf a_n = inf, sum from i=1 to i=inf V[Z_i / a_i] <inf이면

{S_n - E[S_n]}/a_n:pt cv a.e. to 0

(Kronecker's Lemma+Kolmogorov's Convergence Criterion 이용하여 증명)

(a_n = n일 때를 생각해보라.)

-(S-LLN Using MGF)

:{Z_n}:iid with MGF(Z_1)(t) is finite for |t|<=T for some T>=0이면

[S_n/n]:pt cv a.e. to mu(link1)(link2)

-(Kolmogorov's S-LLN)(link1)(link2)

:{Z_n}:iid일 때

-te c in R s.t. [S_n/n]:pt cv a.e. to c iff Z_1:integrable in which case E[Z_1]=c

(만약 Z_1 in L2라면, [(sum from i=1 to i=n (Z_i - E[Z_i])^2)/n]:pt cv a.e. to V[Z_1])

(cv in L1도 된다.)(link)

(Generalizd version은 Ergodic Theorem이 있다.)

-(Central Limit Theorem, CLT)(link1)(link2)

:{Z_n}이 iid이고 in L2일 때

bar{Z}:cv in distrb to Z, Z~ND(mu, [sigma^2]/n)

(S_n=sum from k=1 to k=n (Z_k):cv in distrb to ND(n*mu, n*sigma^2))

(S_n/sqrt(n):cv in distrb to ND(sqrt(n)*mu, sigma^2))

-(Delta Method, using first-order derivative)(parameter의 function을 inference할 때)(link)

:{rdv_n}이 sqrt(n)*(rdv_n - theta):cv in distrb to rdv1, rdv1~ND(0,sigma^2)이고

for g and specific theta_0, g'(theta_0):exist and nonzero이면

sqrt(n)*(g(rdv_n)-g(theta_0)):cv in distrb to rdv2, rdv2~ND(0,sigma^2*[g'(theta_0)]^2)

(쉬운 예로는 rdv_n이 bar{Z}이고 추정 대상이 모평균 mu의 function일 때)

(일반화하면 rdv1~ND일 필요 없다. 단지 가정을 만족하는 경우가 bar{Z} with CLT일 때가 많음)

-(Delta Method, using second-order derivative)

:{rdv_n}이 sqrt(n)*(rdv_n - theta):cv in distrb to rdv1, rdv1~ND(0,sigma^2)이고

for g and specific theta_0, g'(theta_0)=0 and g''(theta_0):exist and nonzero이면

n*(g(rdv_n)-g(theta_0)):cv in distrb to rdv2, rdv2~sigma^2*g''(theta_0)*0.5*CSD(1)

(Delta Method using first-order derivative에서 first-order derivative가 0일 때 사용)

-(Delta Method for Multivariate)

:나중에 필요할 때 정리

-(Demoivre-Lapalce Theorem)

:{Z_n}:iid, 각각이 BrnD(p)을 따를 때, S_n:cv in distrb to ND(np,np(1-p))

(S_n ~ BD(n,p))

(물론 n이 무한대로 가므로 ND(np,np(1-p))로 approximation이 가능하다는 것을 뜻함)

-simple random sample인 경우

-E[bar{Z}]=mu

-V[bar{Z}]=[(sigma)^2/n]*[(N-n)/(N-1)], N은 모집단의 크기(link)

-About Sample Variance, V_n

-E[V_n]=(sigma)^2

-(n-1)*(V_n) = {sum from i=1 to i=n (Z_i)^2} - n*(bar{Z})^2(link)

-V[V_n] cv to 0 as n->inf이면 V_n:cv in M to sigma^2(using chebysheff inequality and W-LLN)

-About Order Statistic

-성질

-discrete population으로 얻은 random sample order statistic인 경우

-각 order statistic의 pmf(link)

-conti population으로 얻은 random sample order statistic인 경우

-각 order statistic의 DF와 density(link)

-order statistic에서의 joint DF와 joint density(link)

-About Generating a Random Sample

-의미:어떠한 distribution(원하는)을 따르는 random sample을 만드는 방법

-과정

-기본적인 fact:UD을 따르는 random sample은 만들 수 있다.

-Direct Method(U_n~UD((0,1))이라 하자.)(구체적인 DF^(-1)을 이용하는 방법)

-ED(lambda)을 만드는 방법(random sample)(link)

-CSD(2d)을 만드는 방법(1개의 rdv)(link)

-GMD(lambda,y)을 만드는 방법(y가 integer일때만, 즉 ERLD(lambda,y))(1개의 rdv)(link)

-BTD(a,b)을 만드는 방법(a,b가 integer일때만)(1개의 rdv)(link)

-(Box-Muller Algorithm)

:rdv1~ND(0,1), rrdv2~ND(0,1) s.t. rdv1과 rdv2는 ind인 rdv1, rdv2 만드는 방법

-BD, NBD, PD 등 discrete distribution 만드는 방법

-Indirect Method

-(Accept/Reject Algorithm)(link)

원하는 distribution의 density과 ind인 UD(0,1), UD(0,1) 두개로 원하는 rdv~the distribution을 만들 수 있다.

(Criteria인 M<inf도 중요하고(즉 V선택이 중요함), 원하는 rdv가 heavy-tail distrb인 경운 힘듦)

-(Markov Chain Monte Carlo Method)

-(Metropolis Algorithm)

:heavy-tail인 rdv도 만들 수 있지만, 정확한 density를 만들기보단 그 density로 수렴하는 rdv_n을 얻을 수 있다.

-About Data Reduction

-의미:적절한 statistic으로, sample모두의 value말고 statistic의 value만으로 parameter의 inference가능

-About SS(Z_1,Z_2,...,Z_n), sufficient statistic

-Joint density of (Z_1,...,Z_n)과 density of S(Z_1,...,Z_n)로써 S(Z_1,Z_2,...,Z_n)이 SS(Z_1,...,Z_n)인지 판단가능

-exponential family의 원소가 아닌 경우(population의 density) 혹은 nonparametric density인 경우, Order Statistic말곤 SS(Z_1,Z_2,...,Z_n)찾기가 어렵다. 크게 Reduction되지 않음

-(Factorizatioon Theorem)

:Joint density of (Z_1,Z_2,...,Z_n)을 보고 적절한 SS(Z_1,...,Z_n)을 찾을 수 있다.

:

-population의 density가 exponential family의 원소였다면, SS(Z_1,Z_2,...,Z_n)을 쉽게 알 수 있다.

(게다가 parameter space가 open set을 포함한다면 complete이기도한 statistic 얻음)

-(Lehman-Scheffe's Theorem)(SS(Z_1,Z_2,...,Z_n)이 minimal인지 판단하는Theorem)

:

(minimal SS(Z_1,Z_2,...,Z_n)이라 할지라도 dimension이 parameter의 dimension보다 클 수도 있다.)

(minimal SS(Z_1,...,Z_n)은 not unique)

-About AS(Z_1,Z_2,...,Z_n), ancillary statistic

-parameter가 location-parameter인 경우, sample range는 ancillary statistic이 된다.(link)

-parameter가 scale-parameter인 경우, (Z_1/Z_n, Z_2/Z_n,...,Z_(n-1)/Z_n)으로 이루어진 function(즉 statistic)은 ancillary statistic of scale-parameter가 된다. (link)

(특히, rdv1~ND(0,sigma^2), rdv2~ND(0,sigma^2), rdv1,rdv2:iid이면 rdv1/rdv2~CD(0,1) for any sigma)

-(Basu's Theorem)(직관적으론 sufficient가 ancillary랑 ind일 것 같은데 completeness필요)

:statistic이 complete and sufficient이면 ind of every ancillary statistic이 된다.

(그리고 the complete and sufficient statistic은 minimal임도 알 수 있다.)

(두 statistic이 ind임을 보일 때 유용, 하지만 complete임을 보이는게 문제인데...바로 밑 theorem이용)

-Using Likelihood Function

-(Likelihood Principle)(한 population에서 2개의 random sample을 얻었을 때)

-In the inference about parameter, after (Z_1,Z_2,...,Z_n) is observed, all relevant experimental information is contained in the likelihood function for the observed (Z_1,...,Z_n).

-(Z_1,Z_2,...,Z_n), (Z'_1,Z'_2,...,Z'_n) 두개의 random sample1, random sample2을 얻었을 때, for all parameter, LF from (Z_1,Z_2,...,Z_n) = LF from (Z'_1,Z'_2,...,Z'_n) * C(random sample1, random sample2)로 표현된다면, random sample1으로 parameter를 inference하나 random sample2으로 parameter를 inference하나 같은 결론을 얻는다. 

-한 random sample에서 parameter1, parameter2 각각이 LF1<LF2라면 parameter2가 더욱 plausible

(그리고 LF2/LF1만큼 plausible하다는 결론을 내릴 수 있다.

-4 Principles(link1)(link2)(link3)

-Equivariance Principle을 따른다면, 

-About Inference(population의 parameter에 관한 지식 from sampling,은 population 전체 density에 관해서 알려준다. 따라서 parameter을 estimate하는게 관건, 동시에 이 parameter의 function을 estimate할 수도 있다.)

-About Point Estimation

-About Finding Estimator

(MM, MLE, Bayes Estimator, EM-Algorithm, min MSE, MVUE)

-정의:

-theta, theta란 parameter of population를 가리킨다고 하자.

-모집단의 property(예를 들면, 모평균, 모분산, 모집단의 density의 parameter 등)을 parameter라 한다.

-추정용 statistic을 estimator라 하고

-검정용 statistic을 test statistic이라 한다.

-bias of a statistic for a parameter:=|E(statistic) - the parameter|, 작을수록 better statistic

(절댓값없이 정의하기도하고 절댓값을 포함해서 정의하기도함)

-bias=0인 statistic을 unbiased statistic이라 한다.

(표본분산(n)대신에 표본분산(n-1)을 이용하면 unbiased됨)

-MSE of a point estimator of a parameter란 parameter의 function, E[(estimator-parameter)^2]

(parameter와 관련된 population의 density형태는 이미 modeled됐을 때)

-MVUE:Minimum Variance Unbiased Estimate(좋은 statistic이 됨)

-efficiency of statistic:=V[parameter]/V[statistic] where statistic=MVUE

-relatively efficiency of (statistic1 for parameter, statistic2 for the same):=V[statistic1]/V[statistic2] where both statistics are unbiased 

(unbiased인 2개의 statistics 중 어느게 variance가 작아서 좋은지 비교시 쓰임, 작은걸 efficient라 한다.)

-statistic_n for a parameter depending on sample size n이 consistent란, 

as n->inf, {the statistic_n}:cv in M to the parameter

-asymptotic bias of statistic for a parameter란, cv in M limit of (statistic - parameter)

-statistic ~_a Distribution이란, n이 커질수록 statistic의 DF의 approximation(cv in distrb가 보장된)

-consistent estimator_n(statistic)이 asymptotically normal이란, sqrt(n)*(estimator - parameter):cv in distrb to ND일 때를 가리키고, 이때의 estimator를 sqrt(n)-consistent라 한다. 혹은 CAN estimator라 한다. 그리고 이때 ND의 variance matrix을 asymptotic variance라 하고 Av[estimator_n]라 하자.

-E_theta란 expectation function of theta를 가리킨다고 하자.

-UMVUE of f(theta)란, E_theta [UMVUE]=f(theta)인 것중 the smallest variance를 갖는 것

-Method of Moments(MM)

-방법:sample의 moment랑 population의 moment(parameter의 function)을 = 두고 equation풀어 estimator 얻는 방법

-특징:

-MM으로 얻은 estimator의 range와 estimating하는 parameter의 range가 일치하지 않을 수 있다.

-Method Maximum Likelihood Estimators(MMLE)(얻은 Estimator나 Estimate모두 MLE라 적자.)

-방법:

-likelihood function을 argumax하는 parameter를 estimator로 함

-일단 first-derivative로 필요조건 구함(log 이용하기도)

-Hessian 등 이용해서 maximum인지 minimum인지 판단

-Bd에서 Check해서 Global Maximum인지 판단

-특징:

-MLE의 range와 estimating하는 parameter의 range가 일치함

-parameter의 range내에서만 MLE를 찾아야한다. parameter의 어떠한 physical한 assumption이 들어가 있을 때, global maximum이 estimator의 값에 따라 달라질 수 있음,

-MLE 자체를 구하기가 어려울 수 있음, 그래도 Numerical Method이용하면 됨

-sample이 약간만 달라져도 MLE가 크게 달라질 수 있음(Maximization의 problem)

(이럴 경우 MLE로 얻은 Estimator의 신뢰도가 떨어짐)

-(Invariance Property of MLE)

:MLE for parameter가 있을 때 MLE for g(parameter) for any transformation g는 g(MLE for parameter)

(즉 sqrt(V_n*(n-1)/n)이 모표준편차의 MLE가 된다.)

-CLT를 이용하면 MLE ~_a ND가 된다.

-Bayes Estimator

-방법:

-parameter가 어떠한 distribution을 따른다는 생각이 있다면,

-sample로써 parameter의 distribution을 update하고

-conditional expectation of parameter given sample이 estimator가 된다.

-특징:

-parameter에 따른 sample의 distribution의 collection C1과 parameter의 distribution의 collection C2, 이때 C2가 conjugate family for C1이란, prior distribution이 update되서 posterior되서도 다시 C2에 속할 때를 가리킨다. 이경우 계산이 편리해진다는 장점이 있다.

-parameter의 분포와 sample의 data를 합한 정보를 준다는 특징이 있다.

-EM-Algorithm(Incomplete-data가 있을 때, Estimator를 만드는 방법)

EMalgorithmpdf.pdf

(Statistical Inference, 2nd edition보고 작성한 글)

-About Evaluating Estimators

(위에 4가지 방법으로 만든 Estimator가 다를 수가 있다. 이경우 어느 게 좋은지 판단기준필요)

-Mean Square Error(MSE)(Finding Estimator의 한방법이 되기도 함, MSE가 최소인 estimator를 찾는다거나, MVUE를 찾는다거나 등)

-방법:estimator of parameter가 있을 때, (The estimator - parameter)의 L2-norm을 재서, L2-norm이 작은게 좋은 것

-특징:

-L2-norm이 analytically tractable, bias란 개념도입가능한 해석가능해서 좋음

-MSE는 estimator의 variance와 bias 둘다 다룸, unbaised이면 estimator의 variance만 고려

-MSE가 낮을수록 좋은 estimator같지만, 항상 그런 것만은 아님

-unbiased estimator가 좋을 것 같지만, bias를 약간 늘리고 variance를 확 줄일 수도 있기도 하다.

(예를 들면, population~ND(mu,sigma^2)일 때, MLE로 얻은 estimator of (population의 variance)가 MM으로 얻은 estimator of (population의 variance)보다 더 MSE가 낮다, 비록 전자가 biased이고 후자가 unbiased일지더라도. unbiased이면 평균적으로 parameter 전후로 놓여진다. biased이면 평균적으로 parameter 전후중 한방향에만 놓이게 된다. 이런 이유로 MLE로 얻은 estimator of (population의 variance)보다 MM으로 얻은게 더 많이 이용된다.)

-MSE는 parameter의 function이므로 best estimator가 1개만 있는 것은 아니다.

-estimator1이 estimator2보다 uniformly better하지 않을 수 있다. parameter의 distribution이나 n에 따라서

-MSE는 group of transformation이 주어진 equivariance principle을 따르는 estimator중에서 best estimator를 찾는데 도움이 되기도 함

-Unbaised Estimator중에서만 생각하면(or, E_theta [estimator]=f(theta)인 class만 생각, 으로 확장가능)

-for any parameter value, the smallest variance인 게 최고 좋음

-(Cramer-Rao Inequality)

:estimator of theta의 variance의 lower bound를 제공해준다. 

((Z_1,Z_2,...,Z_n)에 apply하면, lower bound를 take하는 estimator가 UMVUE가 될 수 있다.)

(discrete case도 사용 가능)

(Information Number가 크면 theta에 관한 정보가 많다는 뜻이며 동시에 variance lower bound가 작아짐)

(General한 Inequality로는 Information Inequality가 있다.)

(Assumption, interchangble of int and diff, 이 성립안할 때도 있다. 체크필요)

-Cramer-Rao Inequality를 쓰더라도 정작 lower bound가 attainable인진 모를 수 있다. 

(좀 더 look into해야할 지, 어떠한 estimator도 lower bound를 take안할지 모른다는 게 단점)

하지만 필요충분조건 있음

-Cramer-Rao를 이용못하는 population density인 경우 Stuart, Ord, and Arnold책 참조

-구체적인 Population의 Distribution class를 알 때

-population이 CD(0,1)을 따를 때

-bar{Z}~CD(0,1)

-population이 ND(mu, (sigma)^2)을 따를때

-bar{Z}, V_n:ind(link)

-{(n-1)*(V_n)}/(sigma)^2 ~ CSD(n-1)(link)

-(bar{Z}, V_n):SS(Z_1,Z_2,...,Z_n) for (mu, sigma^2)이 된다.

(SS(Z_1,...,Z_n)은 model-dependent이다. population이 ND(mu, (sigma)^2)이 아닐 땐, SS(Z_1,Z_2,...,Z_n)이 (bar{Z},V_n) 보다 더 많이 필요할 수 있다.)

(V_n:SS(Z_1,Z_2,...,Z_n) for (sigma^2)이 되는진 모른다. 그런데 Equivariance Principle을 따른다면 알 수 있다.) 

-bar{Z}, V_n 모두 unbiased estimator

-MSE of bar{Z}=(sigma)^2/n

-MSE of V_n=2*(sigma)^4 / (n-1)

-About Bayesian Statistics

-

-About Estimate

-정의:

-구체적인 Sample Distribution

-Sample Proportion(hat(p))

-Estimate Quantile, DF

-상황, DF를 모르는 모집단에서 random sample을 통해 quantile, DF을 Estimate할 수 있을까?

-정의:

-Empirical Cumulative Distribution Function DF_n이란, 

DF_n(x):=(1/n)*sum from i=1 to i=n indi_{X_i<=x}, (w는 생략)

(when, {X_i}:random sample일 때, 즉 iid with DF)

-(Glivenko-Cantelli Lemma)(link1)(link2)

:Empirical CDF는 DF에 uni cv(a.e. Empirical CDF 또한 rdv인 것을 상기)

-(Empirical CDF)^(-1)는 DF^(-1)를 estimate한다.(cv in M)

-(Kolmogorov-Smirnov Test)

:나중에 보충,CLT+Hypothesis Testing 익숙해지고나서 복습

-About Hypothesis Test

-About LRT(Likelihood Ratio Test)

-LF(x)/L_max가 significance level보다 이상이면 X=x라는 주장을 받아들인다.

-{0,1,2,...,n-1} is not laplacian realizable for any n>=2, (즉 S를 Spec(Lap(G))로 갖는 graph는 존재하지 않는다.)

-

-λ_G(2) <= 2 * λ_G(1)

-About Weighted Graph

-About Matrices

-About Lap(wG)

-Lap(wG):exactly psd

-(Matrix Tree Theorem for wG)

:the sum over all spanning trees of wG (prod of all weights of the spanning tree)

= |the cofactor of Lap(wG)|

-About a(wG)

-for wG, any r >= 0, f:Fiedler vector, M(r):={vi|fi + r >= 0}, induced subgraph on M(r) is connected(link)

-for wG, any r <= 0, f:Fiedler vector, M(r):={vi|fi + r <= 0}, induced subgraph on M(r) is connected

-for wG, f:Fiedler vector, any 0 <= c < max{fi}, M:={vi|fi < c}, induced subgraph on M is connected

-for wG, f:Fiedler vector s.t. for all i, fi:nonzero, then {vivj s.t. fi*fj < 0}:subset of E(G)를 제거하면 components가 2개가 나온다.

-if G:unweighted, te a subset E' of E(G) s.t. G - E' have two connected components, then te weight on G s.t. f:Fiedler vector, fi:nonzero for all i and {vivj s.t. fi*fj <0 }=E'(link)

-for G:connected wG, f:Fiedler vector, if fi > 0, then te j s.t. vi~vj, and fj < fi(link)

-About Lap(G), egv of Lap(G), μ

-sum of all egv = 2m

-Lap(G):not invertible(모든 row sum = 0이므로)

-rank(Lap(G))= n - |# of connected components|

-Lap(G) + Lap(bar(G)) = Lap(K_n)

-n >= μ_G(1) >= μ_G(2) >= ... >= μ_G(n)=0 (using Gershgorin Circle Theorem)

-Lap(G):exactly psd, 즉, not positive-definite(nnn egv가지면서 not invertible이므로)

-(Factoring Lap(G))Lap(G) = ct(A) * A where A:(-1,0,1)-(e,v) incidence matrix, (link)

-if μ_G:nonzero, then the sum of components of egv corresponding μ_G is 0(link)

-μ:symmetric인 μ의 개수 = the number of orbits of Aut(G)

(characteristic function on orbit으로 eigenvector를 span함을 생각하면 됨)

-μ:symmectric인 μ찾는 방법(link참조)(link)

-μ:alternating iff te egv(μ) s.t. orthogonal all characteristic functions of the orbits of Aut(G)

-About perm(Lap(G))

-if G:bipartite, then perm(x*IMT - Lap(G)) = perm(x*IMT - sLap(G))

-(Relation with λ(G), edge-connectivity)

λ(G) = min over J:nontrivial proper subset of V(G) (sum over i in J, j in V(G)-J)|Lap(G)_(i,j)|

-About a(G), f:fiedler vector(link1)(link2)(link3)

-G:connected이고 vi:point of articulation일 때, G-v의 components G1,G2,...,Gr에 대해

-fi > 0 일 땐 te! Gj s.t. Gj contains a negative eigencomponent(다른 component들은 모두 fi보다 큰 eigencomponents를 가짐)

-fi = 0이고 어떤 Gj가 positive eigencomponent and negative eigencomponent모두 가진다면 Gj만 그렇고 나머지 components은 0 eigencomponents를 가짐

-fi = 0이고 te no Gj having positive eigencomponent and negative eigencomponent이면 each Gi contains either only negative or only positive or only 0 eigencomponents

-(Interlacing, deleting edges, adding edges)

-G'=G-e일 때, μ_G(1)>=μ_G'(1)>=μ_G(2)>=μ_G'(2)>=...μ_G(n)>=μ_G'(n)>=0(link)

-G'=G-e, e=vivj이고 μ_G(n) = μ_G'(n) <= μ_G(n-1) = μ_G'(n-1) <= ... <= μ_G(p) = μ_G'(p) for some p<=2일 때, for each r in {n,n-1,...,p} G and G' have the same orthonormal eigenvector corresponding to μ(r) of which the ith and jth entries are equal(link)

-N(vi)=N(vj)이고 vj,vi:not adjacent인 e=vivj추가했을 때 생각 가능, same neighbors파트 참고

-TFAE(link)

-the spectral integral variation of G occurs in one place by adding edge e=vivj

-N_G(vi)=N_V(vj)

-(0,0,...0,1,0,0,...,0,-1,0,...,0):eigenvector corresponding to |N_G(vi)|, where ith=1, jth=(-1)

-If adding edge e=vivj and the spectral integral variation of G occurs in two places(μ_G(k), μ_G(l))

then, μ_G(k) + μ_G(l)) = d(vi) +d(vj) + 1 and μ_G(k) * μ_G(l) = d(vi)*d(vj) + |N_G(vi)교N_G(vj)|(link)

-for |V(G1)|<=|V(G2)| and G1,G2:disjoint connected graphs, TFAE(link)

-the spectral integral variation of G1+G2 occurs in two places by adding an edge e=uv, where u in V(G1), v in V(G2)

-|V(G1)|=1 and |V(G2)| >= 2 and d(v)=|V(G2)| - 1

-(Interlacing, deleting vertices, adding vertices)

-G':subgraph from deleting 1 vertieces from G,

then μ_G'(i) >= μ_G(i+1) - 1 for i=1,2,...,n-2(link)

-G':subgraph from deleting k vertices from G, then a(G') >= a(G) - k(link)

(link, 혹은 위에 걸로 증명됨)

-V(G)=UUV(decomposition), then a(G) <= min(a(G[U])+|V|, a(G[V])+|U|)

-G':subgraph from deleting cutvertex v from G, then μ_G(2) <= 1 + |largest components의 vertices개수|(link)

-G:connected, U={v1,v2,..,vs}, s>=2, U:subset of V(G), G[U]:induced subgraph of G, (μ,x):eigenvalue, eigenvector

-if G[U]=K_s and N_G(v1) - U = N_G(v2) - U = ... = N_G(vs) - U and μ != d(vi) + 1 for any i=1,2,...,s

then x1 = x2 = ... = xs(link)

-if G[U]=sK_1 and N_G(v1) = ... = N_G(vs)

then x1 = x2 = ... = xs(link)

-if G[U]=sK_1 and for any 0<=t<=C(s,2) edges, G_t:=a graph obtained from G by adding any t edges among U,

then μ_G(1) = μ_(G_t)(1)(link)

-Let s>=2 new paths with equal length k, Pi:(v,v_ik,v_i(k-1),...,v_i1), i=1,2,...,s, are attached to G at v respectively, to form a new graph (G_(s,k)), let G_(s,k,t1,t2,...,tk) be the graph obtained from G_(s,k) by adding 0<=tj<=C(s,2) edges among {v1j, v2j, ..., vsj}. If Δ(G_(s,k)) >= s+3,

then μ_(G_(s,k,t1,t2,...,tk))(1) = μ_(G_(s,k))(1)(link1)(link2)

-G:connected, G_k:=the graph obtained from G by attaching a new path P:(v0,v1,v2,...,vk) at v0, where v1, v2,...,vk are distinct new vertices. Let X be a unit eigenvector of G_k crpd to μ_(G_k)(1). If μ_(G_k)(1)>=4,

then(link)

-for any 0<=i<=(k-1), |x_(i+1)| <= |x_i| and x_i * x_(i+1) <= 0 with = iff x_0 = 0

-x_0 = 0 iff x_k = 0

-G:connected, u,v:disticnt vertices of G, G_t:=the graph obtained from G by attaching t new paths (v,v_(i,1),v_(i,2),...,v_(i,qi)) (i=1,2,...,t) at v. Let X be a unit eigenvector of G_t crpd to μ_(G_t)(1) >= 4.

Let G_u be G_t - vv_(1,1) - vv_(2,1) - ... - vv_(t,1) + uv_(1,1) + uv_(2,1) + ... + uv_(t,1).(link)

-if |x_u| >= |x_v|, then μ_(G_u)(1) >= μ_(G_t)(1)

-if |x_u| > |x_v|, then μ_(G_u)(1) > μ_(G_t)(1)

-(Upper Bound of a(G))

-(n, δ, m)a(G) <= (n/(n-1)) * δ <= 2m/(n-1)(link)

-(κ, λ, δ)G:not graph-iso K_n이면 a(G) <= κ(G) <= λ(G) <= δ(G)

-(independent vertex)if G contains an independent set of k vertices, then a(G) <= n-k(증명은 bar(G)생각하면됨)

-if G:not graph-iso K_n, then a(G) <= n-2

-(m)if G:not graph-iso K_n, then a(G) <= ]]-1 + sqrt(1+2m)[[ for all m >= 2

(증명은 Variable Neighborhood search for...참고)

-(n, α) a(G) <= n - α(G)(증명은 complement와 subgraph생각)

-(genus(G)) if genus(G)=0, then a(G)<=4, with = iff G:K_4 or G:K_(2,2,2)

-

-(Lower Bound of a(G))

-(n, δ)2δ - n + 2 <= a(G)(link)

-(n, λ),a(P_n)*λ(G) <= a(G)

-(n, κ, Δ)2*cos(pi/n - cos(2pi/n))*κ(G) - 2*cos(pi/n * (1-cos(pi/n)))*Δ <= a(G)

-(n, D(G)) 4/(D(G)*n) <= a(G)

-(Upper Bound of a(bar(G))

-(n, α)a(bar(G)) <= n*(1 - 1/α(bar(G)), with = iff α|n and G has α개 components equal to K_(n/α)

-(Given m, te G s.t. a(G)=maximum)

-Given m>=2, te n, G s.t. G:connected and not graph-iso K_n with maximum a(G) and bar(G) is the disjoint union of K_1, K_2, K_3, P_3(여기서 maximum a(G)란, fixed m이고 n을 변화시킬 때를 가리킴, 단 G:not K_n이면서)

(a(G)는 n-2이거나 n-3이다.)

VARIABLE NEIGHBORHOOD SEARCH FOR EXTREMAL GRAPHS. XI. BOUNDS ON ALGEBRAIC CONNECTIVITY .pdf

-(Given n, te G s.t. a(G)=maximum)

-Given n>=4, te (n-1)개의 m s.t. G:not graph-iso K_n with maximum a(G), order n

(여기서 maximum a(G)란, fixed m이고 n을 변화시킬 때를 가리킴, 단 G:note K_n이면서)

(그리고 처음의 [[(n-1)/2]]개는 a(G)=n-2, 나머진 a(G)=n-3

(증명은 위의 Variable..참고)

-(Upper Bound of μ_G(1))

-μ_G(1) <= max i~j |N_G(vi) U N_G(vj)| <= n(link)(link가 잘못된게 xj잡을 때, i와 adjacent한 것 중 잡아야)

-If G:connected, = holds iff ... link참고

Characterization on graphs which achieve a Das’upper bound for Laplacian spectral radius.pdf

-μ_G(1) <= q_G(1) <= max over i {d(vi)+m(vi)}(link)

-if G:connected, = holds iff G:regular bipartite or G:semiregular bipartite(link)

-μ_G(1) = n iff G:join of two graphs( ->방향 증명은, bar(G)생각)

-If G':subgraph of G, then μ_G'(i) <= μ_G(i) for any i

(edge를 지웠으면 weyl's inequality생각, vertex지우면 interlacing생각)

-G:connected bipartite일 때 μ_G'(1) = μ_G(1)  iff G'=G(link)

-About m_(G,L)

-if G:connected, n > 2, q(G)*2 = n,

then m_(G,L)([0,1))=q(G), m_(G,L)([1,2))=0, m_(G,L)(2)=1, m_(G,L)((2,n])=q(G)-1(link)

-If G:connected, n > 2, n > q(G)*2,

then m_(G,L)((2,n]) >= q(G)(link)

-(Connected Sum and m_(G,L))

-H:connected sum of G, K_(1,k-1)이면 m_(G,L)(k)=m_(H,L)(k)(link1)(link2)

(Reduction관점으로 보기 좋음, 특히 P_3나 P_2를 없애는 관점으로)

-H:connected sum of G, P_3, s.t. G의 1개 점과 P_3의 pendant와 이은 경우이면 m_(G,L)(1)=m_(H,L)(1)(link)

-H:connected sum of G, P_3, s.t. G의 1개 점과 P_3의 중간점을 이은 경우이면

m_(G,L)(1) <= m_(H,L)(1) <= m_(G,L)(1) + 2(link)

-(the number of Not Faria vectors)a:=m_(G,L)(1) - p(G) - q(G), S:induced subgraph of G by inner vertices(inner vertices란, V(G)에서 pendant랑 quasipendant 모두 빼고 남은 것)

-Lap(S) = Lap(G)의 inner vertices part - IMT

-a = nullity of Lap(S) = am(1) of Lap(G)의 inner vertices part

-a <= τ(G)

-a <= k where k:the number of components of S, if each of the k components of S satisfies *(link)

(*:complete graph or for any nonadjacent vi,vj, d(vi)+d(vj) >= n)

-(Upper Bounds for m_(G,L))

-m_(G,L)(n) <= [[δ/(n-Δ)]](link)

-if δ=0, then n must not egv of Lap(G)

-if δ=1, then am(n)=1 or 0

-σ(G) <= n - p(G)

-m_(G,L)([0,1)) <= γ(G)

-(Lower Bounds for m_(G,L))

-m_(G,L)([0,1)) >= q(G)(link)

-m_(G,L)((1,inf)) >= q(G)(link)

-m_(G,L)(1) >= p(G) - q(G)(pendants pair에 (1,-1)주고 나머진 0주는 방식으로 eigencomponent만들면됨) -m_(G,L)([δ,n]) >= α(G)

-m_(G,L)([0,Δ]) >= α(G)

-m_(G,L)([1,n]) >= n - γ(G)

-m_(G,L)((2,n]) >= [[l/2]], where l:the length of the longest path in G.(link)

-G:connected일 때, for V'={v1,v2,...,vk} of V(G), G'=G[V']=(V',E'), If E':consists of r pairwise disjoint edges이면

μ_G(1)+μ_G(2)+...+μ_G(k) >= d(v1) + d(v2) + ...+ d(vk) + k - r(link1)(link2)(link3)

-(Lower Bound of μ_G(1))

-k=1대입하면 μ_G(1) >= Δ + 1 (G:connected일 때, = iff Δ = (n-1)(link))

-μ_G(1) >= (n-1)/n * Δ(link)

-(Lower Bound of μ_G(1) + μ_G(2)), n >= 3일 때

-μ_G(1) + μ_G(2) >= Δ_1 + Δ_2 + 1

-if d(v1)=Δ_1, d(v2)=Δ_2, v1,v2:not adjacent, then μ_G(1) + μ_G(2) >= Δ_1 + Δ_2 + 2

-(Brouwer Conjectures)

-m + 1/2*(k^2 + k) >= μ_G(1)+μ_G(2)+...+μ_G(k)

-Holds for cograph(증명은 inductive 과정이 부등식을 만족함을 보이면 된다.)

-Holds for regular증명은 아래 참고

On variants of the Grone-Merris Conjecture.pdf

-(Lower Bound of μ_G(2))

-if G:connected and n>=3, then μ_G(2) >= Δ_2,

with = if G:K_(r,s) or G:tree with n:even and degree (n/2, n/2, 1,1,...,1)(link)

-(Necessary condition for μ_G(1)=(n-1))

On the Conjecture for Certain Laplacian Integral Spectrum of Graphs.pdf

-G:connected일 때, μ_G(1)=(n-1)이면 for any i, d(vi) <= n-3

-G:connected일 때, μ_G(1)=(n-1)이면 max i~j |N_G(vi) U N_G(vj)| = n

-G:connected일 때, μ_G(1)=(n-1)이면 D(G)=2 or 3

-μ_G(1)=(n-1) and a(G)=1이면 D(G)=D(bar(G))=3

-(Matrix Tree Theorem)t(G)=1/n * μ_G(1)*μ_G(2)*...*μ_G(n-1) = the cofactor of any element of Lap(G)

-G:disconnected iff t(G)=0 iff a(G)=0

-the number of connected components = the multiplicities of zero egv of Lap(G)

-n*t(G) = charP(Lap(G),x)의 x의 계수 = μ_G(1)*μ_G(2)*...*μ_G(n-1)(charP(MT)의 계수 성질 참고)

-(Using equitable partition){V1,V2,...,Vk}:equitable partition of G with d_(i,j), and B = (b_(i,j)) where b_(i,j)=(-d_(i,j)) for i != j, b_(i,i) = {sum over s d_(i,s)} - d_(i,i) for i=j, 일 때 egv of B는 egv of Lap(G)도 된다.(link)

(더 size낮은 matrix의 egv로써 더 size큰 Lap(G)의 egv를 구한다는 것이 의의)

-Lap(bar(G)) = DegMT(bar(G)) - AdMT(bar(G)) = {(n-1)*IMT - DegMT(G)} - {1 - IMT - AdMT(G)}

-spec(Lap(G))={n >= μ_G(1) >= ... >= μ_G((n)=0}일 때,

spec(Lap(bar(G))={n-μ_G(n-1) >= n-μ_G(n-2) >= ... >= n-μ_G(1) >= 0}, 즉 complement의 spec(Lap)도 알 수 있다.(link)

-About G1xG2, G1=(V1,E1,n1,m1,...), G2=(V2,E2,n2,m2,...)

-spec(Lap(G1xG2))={all possible sums of μ_G1(i) + μ_G2(k) for 1<=i<=n1, 1<=k<=n2}(link)

-a(G1xG2)=min{a(G1),a(G2)}

-About DS(G1,G2)

-Lap(DS(G1,G2)) = Lap(G1) + Lap(G2)

-a(G1)+a(G2) <= a(DS(G1,G2))

-About VD(G), V(G)=UUV

-a(G) <= min(a(G[U])+|V|, a(G[V])+|U|)

-(Same Neighborhoods)

-sub-vertex set V' having same set of neighbors Ν with |V'|=k and |Ν|=j 이면 j:egv of Lap(G) with am(j)=at least k-1

-sub-vertex set V'에서 몇몇 edges E'를 없애서 having same set of neighbors N with |V'|=k and |N|=j이고 spec(Lap((V',E'))={a1>=a2>=...>=aκ=0}일 때, j+ai:egv of Lap(G) for i=1,2,3,...,(k-1)이고 remaining egv는 same

(증명은 eigenvalue, eigenvector관련 equation잘잡아서)

-vi,vj:not adjacent, e=vivj를 추가했을 때, 역도 성립, 즉 egv가 +2만 됐다면 same neighbors(link)

-(Neighbor of several pendants)

-v1, v2:pendant이고 same neighbor를 갖는다면, μ( != 1)에 대응되는 eigencomponents는 same

-If (μ_G,x):(egv,egv) for Lap(G)이고 x_i:the largest eigencomponent of egv이고 x_j:the smallest eigencomponent of egv일 때 then min over k~i {x_k} >= (1 - μ_G)x_i and max over k~ i {x_k} <= (1- μ_G)x_i(link)

-(0 < μ_G < 1)If 0 < μ_G <1

-the eigencomponents corresponding to the neighbors of vi are the same sign of x_i, also the eigencomponents corresponding to the neighbors of vj are the same sign of x_j

-if vi, vj are not adjacent, then N_G(vi)교N_G(vj):empty

(위에서 결정한 vi, vj에 대해서임)

-if G:connected, then D(G)>=3

-If (μ_G(1),x):(egv,egv) for Lap(G)이고 x_i:the largest(modulus가) eigencomponent of egv이고 x_j:the second largest eigencomponent(modulus가) of egv일 때(link)

-d(vi) >= μ_G(1)/2

-if μ_G(1)=Δ_1 +Δ_2,

-d(vi)=Δ_1

-if Δ_1 != Δ_2, then vi~vj and |xj| >= (Δ_2 / Δ_1)|xi|

-G:connected이고 Δ_1 != Δ_2이면 μ_G(1) = Δ_1 + Δ_2 iff G:graph iso K_(1,n-1)(link)

-(Adding an pendant edge)If we add an pendant edge e to G, then a(G+e) <= a(G)

-(Joining K_1)(link)

:If G'=GVK_1, then

μ_G'(1) = n+1 >= μ_G'(2) = μ_G(1) + 1 >= μ_G'(3) = μ_G(2) + 1 >= ... >= μ_G'(n) = μ_G(n-1) + 1 >= μ_G'(n+1) = 0

(증명은 bar(G') = bar(G) + K_1 이용)

-(Joining General G)

:{μ_G1(1) >= μ_G1(2) >= ... >= μ_G1(n1) = 0}, {μ_G2(1) >= ... >= μ_G2(n2) = 0}일 때 G1VG2의 spectrum of laplacian은 {n1+n2, n1+μ_G2(j), n2+μ_G1(i), 0 | i=1,...,n1-1, j=1,...,n2-1}(link)

-a(G1VG2) = min (n1+a(G2), n2+a(G1))

-(subdividing some edges)

Let P:(v1,v2,...,vk):internal path(정의는 link참조)

Let G' be a graph obtained from G by subdividing some edge of P(1개 edge만 subdividing)

then μ_G'(1) < μ_G(1)(link1)(link2)

-(Subdividing a general edge)

Let G' be a graph obtained from G by subdividing one edge of G

then a(G') <= a(G)(link1)(link2)

-(Identifying two verices)

Let G1, G2, v1 in G1, v2 in G2, G:=formed by identifying v1 and v2 into v1

then a(G)<=min(a(G1),a(G2))(link)

-About Lnergy(G)

-Lnergy(G)

= 2* (sum from i=1 to i=σ μ_G(i)) - (4*m*σ)/n(link)

= max over 1<=i<=(n-1) {2 * (sum from j=1 to j=i μ_G(j)) - 4*m*j/n}(link)

-(Lower Bound of Lnergy(G))

-if G:connected, then Lnergy(G) >= 2 * (1 + Δ - d(G)), with = iff G:K_(1,n-1)(link1)(link2)

-(Upper Bound of Lnergy(G))

-if m >= n/2, then Lnergy(G) <= 4m - 2Δ - 4m/n + 2, with = iff G:K_(1,n-1) or K_(1,Δ) + bar(K_(n-Δ-1)(link)

-Lnergy(G) <= 4m*(1 - 1/n), with = iff G:K_2 + bar(K_(n-2))

-(Lower Bound of Lnergy(G) + Lnergy(bar(G)))

-Lnergy(G) + Lnergy(bar(G)) >= 2*(n-1), with = iff G:K_n or G:bar(K_n)

-Lnergy(G) + Lnergy(bar(G)) >= 2*(n-1 + Δ - δ)(link1)(link2)

, with iff G:K_n or G:bar(K_n) or G:K_(1,2) or G:(K_2 + K_1) V K_1

-(Upper Bound of Lnergy(G) + Lnergy(bar(G)))

-Lnergy(G) + Lnergy(bar(G)) <= n*sqrt(n^2 - 1)

-Lnergy(G) + Lnergy(bar(G)) <= 8m - 4Δ +2n -12m/n, with = iff G:K_(1,n-1)(link1)(link2)(link3)

-(Extremal Lnergy among Connected Threshold Graphs with n:fixed >= 5)

-PA_(n,]](2n+1)/3[[):has the maximal Lnergy among connected threshold Graphs with n:fixed > 5

Extremal Laplacian energy of threshold graphs.pdf

-About Specific Cases

-G:r-regular이면 spec(Lap(G)) = {r - λ_G(1), r - λ_G(2), ..., r - λ_G(n)}

-spec(Lap(K_n))={n,n,n,...,n,0}

-spec(Lap(K_(1,n-1))={n,1,1,...,1,0}

-spec(Lap(P_n))={2 - 2cos((pi*k)/n), k=0,2,...,n-1}

-spec(Lap(C_n))={2 - 2cos((2*pi*k)/n), k=n-1,n-2,...,0, not ordered임}

-spec(Lap(K_(r,s))={r+s, r, r, ..., r,s,s,...,s,0}, r이 s-1, s가 r-1개

-spec(Lap(PA(n,w))={n,w,w,...,w,1,1,...,1,0}, w가 w-2개, 1이 n-w개
-μ_(r,s)-semiregular bipartite(1) = r+s(link개)

-about Tree(G:tree)

-if μ:integral egv of Lap(G), μ >= 2, then(link)

-μ | n

-am(μ) = 1, 즉 m_(G,L)(μ)=1 for G:Tree, μ>=2 if μ:eigenvalue of G

-no coordinate of egv corresponding to μ is zero

-(Lower bound of μ_G(1))

-if te v s.t. e(v)<=2,

then μ_G(1) >= 1/2 * {(d(v)+m(v)+1) + sqrt((d(v)+m(v)+1)^2 - 4(d(v)m(v)+1))

, with = iff for any vi, vj s.t. vi~v and vj~v, d(vi)=d(vi)(link1)(link2)

-μ_G(1) >= max over i 1/2 * {(d(vi)+m(vi)+1) + sqrt((d(vi)+m(vi)+1)^2 - 4(d(vi)m(vi)+1))

-μ_(P_n)(1) <= μ_(G)(1) <= μ_(K_(1,n-1))(1) = n with left = iff G:graph-iso P_n, with right = iff G:graph-iso K_(1,n-1)(link1)(link2)

-if x:Fiedler vector, then exactly one of the following two cases occurs:

(A)

-No entry of x is 0

-te! vi~vj s.t. xi > 0 and xj < 0

-any p(vi,~) which doesn't contain vj, entries are inc

-any p(vj,~) whcih doesn't contain vi, entries are dec

(B)

-te zero entries of x

-U={vi s.t. xi=0}, then G[U]:connected

-te! vi s.t. xi=0 and vi~vj with xj:nonzero(vj가 unique하진 않을 수 있음)

-any path p(vi,~), entries are either inc, dec, identically 0

(We say T is type-(I) if T satisfies (B), We say T is type-(II) if T satisfies (A))

-Lap(G) - vi is invertible for any vi(using matrix-tree theorem)

-the (i,j)-entry (Lap(G) - vk)^(-1) = the number of edges of G which are on both the path from vi to v and the path from vj to v

-(Lower Bound of μ_G(2) for tree)

-if n>2(link1)(link2)(link3)(link4)

-if Δ_1 ~ Δ_2, then μ_G(2) >= Δ_2, with = if(not iff) G:T1(Δ_1 - 1,Δ_2 - 1)

-if Δ_1, Δ_2 are not adjacent, then μ_G(2) >= {(Δ_2 + 1) + sqrt((Δ_2+1)^2 - 4)}/2, with = if(not iff) G:T2(Δ_1 - 1, Δ_2 - 1)

-if n>2 and Δ_1 = Δ_2 = μ_2(G), then G:T1(d-1,d-1)(link)

-(Lower Bound of μ_G(1)+μ_G(1) for tree) n >= 3

-if d(v1)=Δ_1, d(v2)=Δ_2 and vi~vj, then

μ_G(1) + μ_G(2) >=

-1/2 * {Δ_1 + 2*Δ_2 + m(v1)+1) + sqrt((Δ_1 + m(v1) + 1)^2 - 4*(Δ_1 * m(v1) + 1))}

-Δ_1 + 1/2 * {Δ_2 + 2 + sqrt((Δ_2 +2)^2 - 8))}(link1)(link2)

-if d(v1)=Δ_1, d(v2)=Δ_2 and vi,vj:not adjacent, then

μ_G(1) + μ_G(2) >=

-1/2 * {Δ_1 + Δ_2 + m(v1) + 2 +sqrt((Δ_2 + 1)^2 - 4) + sqrt((Δ_1 + m(v1) +1)^2 - 4*(Δ_1 * m(v1) + 1))}

-Δ1 + 2 + 1/2 * {sqrt((Δ_2 - 1)^2 + 4 * |N(v1)교N(v2)|) + sqrt((Δ_2 + 1)^2 - 4 * |N(v1)교N(v2)|)}(link1)(link2)

-(Upper Bound of a(G) with n >= 6)

-if G:not K_(1,n-1), then a(G) < 0.49(증명은 tree with 6 vertices중에서 가장 큰 a(G)=0.48...near star, 그리고 adding pendant edges 생각)

-(Upper Bound of a(G) with D(G))

-a(G) <= a(P_(D(G)+1)), 즉 diameter가 같은 path의 a(G)가 최대이다. tree의 경우

-(Lower Bound of a(bar(G)))

-(n, α) a(bar(G)) > n - 2*α(T)

-(Upper Bound of μ_G(k) for tree)

-μ_G(k) <= [[n/k]] for k=1,2,3,...,n

-About T1(a,b), G=T1(a,b)

-0 < a(G) < 1, and other μ >= 1

-for 1 <= a <= (n-2)/2, fixed n, a(G):strictly decreasing of a

(즉, n이 고정되어 있을 때, 양쪽으로 vertex가 골고루 있을 수록 a(G)가 낮다.)

(증명은 Ordering trees by algebraic connectivity, Grone, Merris참고)

-About TZ(k), G=TZ(k)

-m_(G,L)(k) = 1, eigencomponents가 pendant는 1, quasipendant는 -1, center는 1 - (k)^2

-About m_(T,L)

-n>=2이고 for any μ, m_(T,L)(μ) <= p(T) - 1(link)

-m_(T,L)((0,2)) >= [[D(G)/2]](link)

-m_(T,L)((2,inf) >= [[D(G)/2]](link)

-About sLap(G), egv of sLap(G), q

-x^(m-n) * charP(sLap(G),x) = charP(AdMT(L(G)),x-2)(link)

-(Factoring sLap(G))sLap(G) = IcMT(G) * ct(IcMT(G))

-sLap(G):psd

-q_G(i)>=0, for all i

-(Interlacing, deleting one edge)G'=G-e일 때, q_G(1)>=q_G'(1)>=q_G(2)>=q_G'(2)>=...q_G(n)>=q_G'(n)>=0

(증명은 line graph와의 관계+interlacing, deleting vertex, in AdMT사용)

-(Same Neighborhoods)

-sub-vertex set V' having same set of neighbors Ν with |V'|=k and |Ν|=j 이면 

j:egv of sLap(G) with am(j)=at least k-1

-About perm(sLap(G))

-sd(G) = the multiplicity of perm(x*IMT - sLap(G))

-G has pendant stars with more than one pendant vertex iff 1 is a root of perm(x*IMT - sLap(G))

-About q_G(1)

-(Upper Bound of q_G(1)

-μ_G(1) <= q_G(1) <= max i {d(vi)+m(vi)}(증명은 -μ_G <= max i {d(vi)+m(vi)}와 유사)

-if G:connected, then right = hold iff G:regular or semiregular bipartite iff d(vi)+m(vi):fixed(link)

(증명을 보면, G:bipartite이면 spec(sLap(G))=spec(Lap(G))임을 알 수 있다. (usim이라), 그리고 역도 성립)

-if G:connected, then left = hold iff G:bipartite

(따라서 left = and right = holds iff G:regular bipartite or semiregular bipartite)

-if G:connected, then q_G(1) <= Δ_1 + Δ_2, with = iff G:regular or G:graph-iso K_(1,n-1)

-(Lower Bound of q_G(1))

-q_G(1) >= Δ + 1

-if G:connected, then = hold iff G:graph-iso K_(1,n-1)

-About q_G(2)

On conjectures involving second largest signless Laplacian eigenvalue of graphs.pdf

-(Lower bound of q_G(2))

-if Δ_1 ~ Δ_2, then q_G(2) >= {Δ_1 + Δ_2 - sqrt((Δ_1 - Δ_2)^2 + 4)}/2

-if Δ_1, Δ_2 are not adjacent, then q_G(2) >= Δ_2

-q_G(2) >= Δ_2 - 1, if = holds, then Δ_1=Δ_2 and corresponding vertices are adjacent

(왜냐하면 Δ_2 >= {Δ_1 + Δ_2 - sqrt((Δ_1 - Δ_2)^2 + 4)}/2 >= Δ_2 - 1)

-if G:connected, then q_G(2) >= d(G) - 1 with = iff G:graph-iso K_n

-if G:connected, then q_G(2) >= δ - 1 with = iff G:graph-iso K_n

-if G:connected and n>=4, G:not graph iso K_n, then q_G(2) >= a(G)

with = iff

-G:K_(1,n-1)

-G:K_(1,3,3)

-G:K_(n-δ, n-δ, ..., n-δ), complete p-partite graph, n-δ>=2

-G:K_(1,1,...,1,2,2,...,2), complete (k+t)-partite graph, 1이 k개, 2가 t개

-(Upper bound of q_G(2))

-If G:connected and n>=3, then q_G(2) <= n + δ - 3, with = iff G:graph-iso Ki_(n,n-1)

-If G:connected, then q_G(1) - q_G(2) <= n, with = iff G:graph-iso K_n

-If Δ_2 = n-1, then q_G(2) = n-2

-(Lower Bound, Related with the index)

-n>2, G:not K_3 and not K_4이면 1- sqrt(n-1) <= q_G(2) - λ_G(1), with = G:K_(1,n-1) or K_5

Proof of conjecture involving the second largest signless Laplacian eigenvalue and the index of graphs.pdf

-About q_G(n)

-If G:connected, q_G(n) < δ(G)(증명은 Rayleigh에 (0,0,...,1)넣어서)

-G:connected and non-bipartite with q_G(i):integer for all i이면 G has no pendant vertices.

-G:connected일 때, q_G(n) = 0 iff G:bipartite(증명은 incidence로 표현해서)

-G:connected and te vi~vj s.t. N_G(vi) - {vj} != N_G(vj) - {vi}이면, q_G(n) < (d(vi) + d(vj) - 2)/2

-About Specific Cases

-G:r-regular일 때

-G:connected이면 q_G(n) <= r-1 with = holds iff G:K_n

-sLap(K_n)={2n-2, n-2, n-2, ..., n-2}

-spec(sLap(P_n))=spec(Lap(P_n))

-spec(sLap(C_n))={2 + 2cos((2*pi*k)/n), k=n-1,n-2,...,0, not ordered임}

-sLap(CS(n,w))...link참고

-sLap(K_(n-δ,n-δ,...,n-δ), n-δ가 p개) 

= {2δ, δ,..., δ, (n-δ)(p-2), (n-δ)(p-2), ..., (n-δ)(p-2), δ:p(n-δ-1)개, (n-δ)(p-2):p-1개}(link)

-About Tree(G:tree)

-if n>=4, then q_G(1) - q_G(2) <= n-1, with = iff K_(1,n-1)

-Graph distance

*Distance, Index

-about W(G)

-W(G) 

= sum over k>=1 (k*d(G,k))

= [sum over all i,j DistMT(G)_(i,j)] * 1/2

-about MTI(G)

-MTI(G)

=1-Zagreb(G) + DD(G)

=1-Zagreb(G) + sum over entries [AdMT(G)*DistMT(G)]

=sum over all entries [AdMT(G)]^2 + sum over all entries [AdMT(G)*DistMT(G)]

-For G:tree

-MTI(G) = 4*W(G) - (n-1)(n-2) + 2*(# of paths of length 2)

-about DD(G)

-DD(G)

=sum over entries [AdMT(G)*DisMT(G)]

-For G:tree

-DD(G) = 4*W(G) - n(n-1)

-about GG(G)

-Among G with n vertices, K_n is the graph with minimum GG(G)

-Among bipartite G with n vertices, K_([n/2], ]n/2[) is the graph with maximum GG(G)

-Among T with n vertices, P_n is the tree with minimum GG(T)

-Among T with n vertices, K_(1,n-1) is the tree with maximum GG(T)

-about NGG(G)

-If G:bipartite, then GG(G)=NGG(G)*sqrt(n-2)

-lim n->inf NGG(P_n) = pi

-about RD(G), max-RD(G), HM(G)

-max-RD(G) <= HM(G) <= RD(G), by simple calculation

-(Hansen)χ(G) <= 2*RD(G) with = iff G:complete, possibly with some additional isolated vertices

-(Deng)χ(G) <= 2*HM(G) with = G:complete, possibly with some additional isolated vertices

-(Wu, Yan, Yang)If G without isolated vertices, then col(G) <= 2*RD(G) with = iff G:K_n

-(Wu, Elphick)If G without isolated vertices, then

col(G) <= 2*max-RD(G) with = iff G is formed by K_k and K_(1,n-k) identifying one vertex in K_k with the center of K_(1,n-k) for some k

χ(G) <= 2*max-RD(G) with = iff G is formed by K_k and K_(1,n-k) identifying one vertex in K_k with the center of K_(1,n-k) for some k

χ_l(G) <= 2*max-RD(G) with = iff G is formed by K_k and K_(1,n-k) identifying one vertex in K_k with the center of K_(1,n-k) for some k

col(G) <= 2*HM(G) with = iff G is K_n

-(Tang)aχ(G) <= 2*RD(G)

-G:connected일 때 d(vi)+m(vi):fixed for all iff G:regular or G:semiregular bipartite(link)

-max{d(vi)+m(vi)} <= (2m/n-1) + (n-2) with equality iff G graph-iso S_n or G graph-iso K_(n-1) U K_1(link1)(link2)

-(Upper Bound of 1-Zagreb(G))

-G:connected일 때 1-Zagreb(G) <= m*max{d(vi)+m(vi)}

with equality iff G:regular or G:semiregular bipartite(link)

-1-Zagreb(G) <= m*{2m/n-1 + (n-2)/(n-1)*Δ +(Δ-δ)*(1 - Δ/(n-1))}

with equality iff G:K_(1,n-1) or regular or K_(Δ+1) with n-Δ-1 isolated vertices

Maximizing the sum of the squares of the degrees of a graph.pdf

-1-Zagreb(G) <= 2m*(2m+(Δ-δ)(n-1))/(n+(Δ-δ)) 

with equality iff G:regular or K_(Δ+1) with n-Δ-1 isolated vertices, (증명은 Maximizing the sum of...참고)

-1-Zagreb(G) <= 2m*(Δ-δ) - n*Δ*δ

with equality iff G has only two type of degree Δ, δ(증명은 Maximizing the sum of...참고)

-1-Zagreb(G) = sum over i sum over j (Adj)^2_(i,j)(link)