Meet Our Team
home

Proof of the Chi Squared Test

오태호 (Taeho Oh)
오태호 (Taeho Oh)

Intro

안녕하세요. 오태호입니다.
이 글에서는 Chi Squared Test의 수식을 증명해 보도록 하겠습니다. 교과서에 식만 나와 있고 증명이 생략되어 있는 경우가 많아서 정리해 보았습니다.
이 글을 이해하기 위해서는 Linear Algebra, Statistics에 대한 기초지식이 필요합니다.
Matrix나 Vector는 굵은 글꼴로 표현하도록 하겠습니다. 그리고 Vector는 특별히 언급이 없으면 Column Vector를 의미합니다.

Chi Squared Test

kk개의 상자에 nn개의 공을 던져서 넣는 상황을 생각해 봅니다.
공 하나가 각각의 상자에 들어갈 확률은 p1,p2,,pkp_1, p_2, \cdots, p_k입니다. 공은 어딘가의 한 상자에 들어가야 하기 때문에 j=1kpj=1\sum_{j=1}^kp_j=1이 됩니다.
X1,X2,,Xn\mathbf{X}_1, \mathbf{X}_2, \cdots, \mathbf{X}_n는 각각의 공이 어느 상자에 들어있는지를 One Hot Vector 형태로 가집니다. 공은 어딘가의 한 상자에 들어가야 하기 때문에 Xi\mathbf{X}_i는 kk Dimension으로 되어 있는 Vector이고 11개의 11과 k1k-1개의 00으로 이루어져 있습니다. 즉, ii번 째 공이 jj번째 상자에 공이 들어갔다면 Xi\mathbf{X}_i Vector에서 jj번 째 Element만 11이고 나머지 Element는 00이 됩니다. XijX_{ij}는 Xi\mathbf{X}_i Vector에서 jj번 째 Element를 의미합니다. 각 공은 다른 공에게 영향을 주지 않으며 모든 공은 동일한 형태로 동작합니다. 즉, X1,X2,,Xn\mathbf{X}_1, \mathbf{X}_2, \cdots, \mathbf{X}_n은 iid입니다. ii번 째 공은 던질 때마다 다른 상자에 들어갈 수 있기 때문에 XijX_{ij}는 Random Variable입니다.
Xˉ\bar{\mathbf{X}}는 다음과 같이 정의합니다.
Xˉ=1ni=1nXi\bar{\mathbf{X}}=\frac{1}{n}\sum_{i=1}^n\mathbf{X}_i
Xˉj\bar{X}_j는 Xˉ\bar{\mathbf{X}} Vector에서 jj번 째 Element를 의미합니다. XijX_{ij}가 Random Variable이기 때문에 Xˉj\bar{X}_j도 Random Variable입니다.
이 상황에는 nn이 충분히 크면 다음과 같은 식이 성립합니다. 참고로 이 글에서는 다음 식이 성립하는 이유를 뒤에서 증명할 예정입니다.
j=1k(nXˉjnpj)2npjχk12\sum_{j=1}^k\frac{(n\bar{X}_j-np_j)^2}{np_j} \sim \chi_{k-1}^2
이 식은, Oj=nXˉjO_j=n\bar{X}_j로 정의하고 Ej=npjE_j=np_j로 정의해서 다음과 같이 표현하기도 합니다.
j=1k(OjEj)2Ejχk12\sum_{j=1}^k\frac{(O_j-E_j)^2}{E_j} \sim \chi_{k-1}^2
즉, OjO_j는 각 상자에 들어 있는 공의 갯수이며 EjE_j는 각 상자에 들어 있을 것으로 예상되는 공의 갯수입니다. 여기에서 OjO_j는 공을 던질 때마다 다른 상자에 들어갈 것이므로 Random Variable이 되고 이 식은 Degree of Freedom이 k1k-1인 Chi Squared Distribution을 따릅니다.
Chi Squared Test에서는 공이 각 상자에 들어갈 확률을 추측해서 이를 기반으로 Null Hypothesis를 세우고, Null Hypothesis가 맞다는 가정하에 현재 관측한 각 상자에 들어 있는 공의 갯수가 나올 확률이(혹은 그보다 더 극단적인 상황이 발생할 확률이) 얼마나 되는지 위의 식으로 계산(이것을 P Value라고 함)합니다. P Value가 Significance Level(이것을 α\alpha라고 함)보다 작으면 Null Hypothesis를 기각합니다.

Proof of Chi Squared Test

P(Xij=1)=pjE(Xij)=pjE(Xi)=[p1p2pk]=p\begin{aligned} & P(X_{ij}=1)=p_j \\& E(X_{ij})=p_j \\& E(\mathbf{X}_i)=\begin{bmatrix}p_1 \\p_2 \\\vdots \\p_k\end{bmatrix}=\mathbf{p} \end{aligned}
j=lj = l인 경우 Cov(Xij,Xil)Cov(X_{ij},X_{il})을 계산합니다.
Cov(Xij,Xil)=Var(Xij)=E((XijE(Xij))2)=P(Xij=0)(0E(Xij))2+P(Xij=1)(1E(Xij))2=(1pj)(0pj)2+pj(1pj)2=pj2pj3+pj2pj2+pj3=pj(1pj)\begin{aligned}Cov(X_{ij},X_{il})&=Var(X_{ij}) \\&=E((X_{ij}-E(X_{ij}))^2) \\&=P(X_{ij}=0)(0-E(X_{ij}))^2+P(X_{ij}=1)(1-E(X_{ij}))^2 \\&=(1-p_j)(0-p_j)^2+p_j(1-p_j)^2 \\&=p_j^2-p_j^3+p_j-2p_j^2+p_j^3 \\&=p_j(1-p_j)\end{aligned}
jlj \ne l인 경우Cov(Xij,Xil)Cov(X_{ij},X_{il}) 계산합니다. 공 하나가 여러 상자에 들어갈 수 없기 때문에 XijXilX_{ij}X_{il}은 항상 00이 되는 점을 이용합니다.
Cov(Xij,Xil)=E((XijE(Xij))(XilE(Xil)))=E(XijXilXijE(Xil)E(Xij)Xil+E(Xij)E(Xil))=E(XijXil)E(Xij)E(Xil)E(Xij)E(Xil)+E(Xij)E(Xil)=E(XijXil)E(Xij)E(Xil)=E(Xij)E(Xil)=pjpl\begin{aligned}Cov(X_{ij},X_{il})&=E((X_{ij}-E(X_{ij}))(X_{il}-E(X_{il}))) \\&=E(X_{ij}X_{il}-X_{ij}E(X_{il})-E(X_{ij})X_{il}+E(X_{ij})E(X_{il})) \\&=E(X_{ij}X_{il})-E(X_{ij})E(X_{il})-E(X_{ij})E(X_{il})+E(X_{ij})E(X_{il}) \\&=E(X_{ij}X_{il})-E(X_{ij})E(X_{il}) \\&=-E(X_{ij})E(X_{il}) \\&=-p_jp_l\end{aligned}
정리하면 Xi\mathbf{X}_i의 Covariance Matrix Σ\mathbf{\Sigma}은 다음과 같습니다.
Σ=[p1(1p1)p1p2p1pkp1p2p2(1p2)p2pkp1pkp2pkpk(1pk)]\begin{array}{c} \mathbf{\Sigma}=\begin{bmatrix}p_1(1-p_1) && -p_1p_2 && \cdots && -p_1p_k \\-p_1p_2 && p_2(1-p_2) && \cdots && -p_2p_k \\\vdots && \vdots && \ddots && \vdots \\-p_1p_k && -p_2p_k && \cdots && p_k(1-p_k)\end{bmatrix} \end{array}
Σ\mathbf{\Sigma}을 잘 살펴보면 j=1kpj=1\sum_{j=1}^kp_j=1이기 때문에 모든 Column Vector를 더해 보면 00이 된다는 것을 알 수 있습니다. 즉, Σ\mathbf{\Sigma}는 Full Rank가 아니고 Invertible하지 않습니다. pp에서 kk번 째 Element를 제거한 Vector를 p\mathbf{p}^*라고 정의하고, Xi\mathbf{X}_i에서 kk번째 Element를 제거한 Vector를 Xi\mathbf{X}_i^*라고 정의하며, Xi\mathbf{X}_i^*의 Covariance Matrix를 Σ\mathbf{\Sigma}*라고 정의합니다. Σ\mathbf{\Sigma}*는 Full Rank이며 Invertible합니다.
Σ=[p1(1p1)p1p2p1pk1p1p2p2(1p2)p2pk1p1pk1p2pk1pk1(1pk1)]\begin{array}{c} \mathbf{\Sigma}^*=\begin{bmatrix}p_1(1-p_1) && -p_1p_2 && \cdots && -p_1p_{k-1} \\-p_1p_2 && p_2(1-p_2) && \cdots && -p_2p_{k-1} \\\vdots && \vdots && \ddots && \vdots \\-p_1p_{k-1} && -p_2p_{k-1} && \cdots && p_{k-1}(1-p_{k-1})\end{bmatrix} \end{array}
(Σ)1(\mathbf{\Sigma}^*)^{-1}을 계산하기 위해 Sherman Morrison Woodbury Formula을 이용합니다. Sherman Morrison Woodbury Formula는 다음과 같습니다.
(A+UCV)1=A1A1U(C1+VA1U)1VA1(\mathbf{A}+\mathbf{UCV})^{-1}=\mathbf{A}^{-1}-\mathbf{A}^{-1}\mathbf{U}(\mathbf{C}^{-1}+\mathbf{V}\mathbf{A}^{-1}\mathbf{U})^{-1}\mathbf{V}\mathbf{A}^{-1}
Σ=A+UCV\mathbf{\Sigma}^*=\mathbf{A}+\mathbf{UCV}라고 하면 A,U,C,V\mathbf{A}, \mathbf{U}, \mathbf{C}, \mathbf{V}는 다음과 같이 정할 수 있습니다.
A=[p1000p2000pk1]U=[p1p2pk1]C=1V=[p1p2pk1]\begin{aligned} \mathbf{A}&=\begin{bmatrix}p_1 && 0 && \cdots && 0 \\0 && p_2 && \cdots && 0 \\\vdots && \vdots && \ddots && \vdots \\0 && 0 && \cdots && p_{k-1}\end{bmatrix} \\\mathbf{U}&=\begin{bmatrix}p_1 \\p_2 \\\vdots \\p_{k-1}\end{bmatrix} \\\mathbf{C}&=-1 \\\mathbf{V}&=\begin{bmatrix}p_1 && p_2 && \cdots && p_{k-1}\end{bmatrix} \\ \end{aligned}
A1A1U(C1+VA1U)1VA1\mathbf{A}^{-1}-\mathbf{A}^{-1}\mathbf{U}(\mathbf{C}^{-1}+\mathbf{V}\mathbf{A}^{-1}\mathbf{U})^{-1}\mathbf{V}\mathbf{A}^{-1}을 계산하기 위해 필요한 각 부분을 계산합니다.
A1=[1p10001p20001pk1]A1U=[111]VA1=[111]VA1U=j=1k1pjC1=1C1+VA1U=1+j=1k1pj=pk(C1+VA1U)1=1pk\begin{aligned} \mathbf{A}^{-1}&=\begin{bmatrix}\frac{1}{p_1} && 0 && \cdots && 0 \\0 && \frac{1}{p_2} && \cdots && 0 \\\vdots && \vdots && \ddots && \vdots \\0 && 0 && \cdots && \frac{1}{p_{k-1}}\end{bmatrix} \\\mathbf{A}^{-1}\mathbf{U}&=\begin{bmatrix}1 \\1 \\\vdots \\1\end{bmatrix} \\\mathbf{V}\mathbf{A}^{-1}&=\begin{bmatrix}1 && 1 && \cdots && 1\end{bmatrix} \\\mathbf{V}\mathbf{A}^{-1}\mathbf{U}&=\sum_{j=1}^{k-1}p_j \\\mathbf{C}^{-1}&=-1 \\\mathbf{C}^{-1}+\mathbf{V}\mathbf{A}^{-1}\mathbf{U}&=-1+\sum_{j=1}^{k-1}p_j=-p_k \\(\mathbf{C}^{-1}+\mathbf{V}\mathbf{A}^{-1}\mathbf{U})^{-1}&=-\frac{1}{p_k} \end{aligned}
이렇게 계산한 결과를 이용해서 A1A1U(C1+VA1U)1VA1\mathbf{A}^{-1}-\mathbf{A}^{-1}\mathbf{U}(\mathbf{C}^{-1}+\mathbf{V}\mathbf{A}^{-1}\mathbf{U})^{-1}\mathbf{V}\mathbf{A}^{-1}을 계산합니다.
A1A1U(C1+VA1U)1VA1=[1p10001p20001pk1][111](1pk)[111]=[1p10001p20001pk1]+1pk[111111111]\begin{aligned}&\mathbf{A}^{-1}-\mathbf{A}^{-1}\mathbf{U}(\mathbf{C}^{-1}+\mathbf{V}\mathbf{A}^{-1}\mathbf{U})^{-1}\mathbf{V}\mathbf{A}^{-1} \\&=\begin{bmatrix}\frac{1}{p_1} && 0 && \cdots && 0 \\0 && \frac{1}{p_2} && \cdots && 0 \\\vdots && \vdots && \ddots && \vdots \\0 && 0 && \cdots && \frac{1}{p_{k-1}}\end{bmatrix}-\begin{bmatrix}1 \\1 \\\vdots \\1\end{bmatrix}\left (-\frac{1}{p_k} \right )\begin{bmatrix}1 && 1 && \cdots && 1\end{bmatrix} \\&=\begin{bmatrix}\frac{1}{p_1} && 0 && \cdots && 0 \\0 && \frac{1}{p_2} && \cdots && 0 \\\vdots && \vdots && \ddots && \vdots \\0 && 0 && \cdots && \frac{1}{p_{k-1}}\end{bmatrix}+\frac{1}{p_k}\begin{bmatrix}1 && 1 && \cdots && 1 \\1 && 1 && \cdots && 1 \\\vdots && \vdots && \ddots && \vdots \\1 && 1 && \cdots && 1\end{bmatrix}\end{aligned}
정리하면 (Σ)1(\mathbf{\Sigma}^*)^{-1}은 다음과 같습니다.
(Σ)1=[1p10001p20001pk1]+1pk[111111111]\begin{array}{c} (\mathbf{\Sigma}^*)^{-1}=\begin{bmatrix}\frac{1}{p_1} && 0 && \cdots && 0 \\0 && \frac{1}{p_2} && \cdots && 0 \\\vdots && \vdots && \ddots && \vdots \\0 && 0 && \cdots && \frac{1}{p_{k-1}}\end{bmatrix}+\frac{1}{p_k}\begin{bmatrix}1 && 1 && \cdots && 1 \\1 && 1 && \cdots && 1 \\\vdots && \vdots && \ddots && \vdots \\1 && 1 && \cdots && 1\end{bmatrix} \end{array}
Xˉ\bar{\mathbf{X}}^*를 다음과 같이 정의합니다.
Xˉ=1ni=1nXi\bar{\mathbf{X}}^*=\frac{1}{n}\sum_{i=1}^n\mathbf{X}_i^*
Xˉ\bar{\mathbf{X}}^*와 관련된 값을 계산합니다.
E(Xˉ)=pVar(Xˉ)=Var(Xi)n=Σn\begin{array}{c} E(\bar{\mathbf{X}}^*)=\mathbf{p}^* \\Var(\bar{\mathbf{X}}^*)=\frac{Var(\mathbf{X}_i^*)}{n}=\frac{\mathbf{\Sigma}^*}{n} \\ \end{array}
Central Limit Theorem에 따르면 nn이 충분히 클 때 다음 식이 성립합니다.
n(Σ)12(Xˉp)N(0,Ik1)\sqrt{n}(\mathbf{\Sigma}^*)^{-\frac{1}{2}}(\bar{\mathbf{X}}^*-\mathbf{p}^*) \sim N(\mathbf{0}, \mathbf{I}_{k-1})
Chi Squared Distribution의 정의에 따르면 다음 식은 Degree of Freedom이 k1k-1인 Chi Squared Distribution을 따릅니다.
(n(Σ)12(Xˉp))T(n(Σ)12(Xˉp))=n(Xˉp)T(Σ)1(Xˉp)χk12\begin{aligned}&(\sqrt{n}(\mathbf{\Sigma}^*)^{-\frac{1}{2}}(\bar{\mathbf{X}}^*-\mathbf{p}^*))^{T}(\sqrt{n}(\mathbf{\Sigma}^*)^{-\frac{1}{2}}(\bar{\mathbf{X}}^*-\mathbf{p}^*)) \\&=n(\bar{\mathbf{X}}^*-\mathbf{p}^*)^T(\mathbf{\Sigma}^*)^{-1}(\bar{\mathbf{X}}^*-\mathbf{p}^*) \\&\sim \chi_{k-1}^2\end{aligned}
n(Xˉp)T(Σ)1(Xˉp)n(\bar{\mathbf{X}}^*-\mathbf{p}^*)^T(\mathbf{\Sigma}^*)^{-1}(\bar{\mathbf{X}}^*-\mathbf{p}^*)을 자세히 계산해 보도록 하겠습니다.
n(Xˉp)T(Σ)1(Xˉp)=n[Xˉ1p1Xˉ2p2Xˉk1pk1]T([1p10001p20001pk1]+1pk[111111111])[Xˉ1p1Xˉ2p2Xˉk1pk1]=n[Xˉ1p1Xˉ2p2Xˉk1pk1]T[1p10001p20001pk1][Xˉ1p1Xˉ2p2Xˉk1pk1]+n[Xˉ1p1Xˉ2p2Xˉk1pk1]T1pk[111111111][Xˉ1p1Xˉ2p2Xˉk1pk1]=nj=1k1(Xˉjpj)2pj+n1pk(j=1k1(Xˉjpj))2=j=1k1n(Xˉjpj)2pj+n(j=1k1Xˉjj=1k1pj)2pk=j=1k1n(Xˉjpj)2pj+n((1Xˉk)(1pk))2pk=j=1k1n(Xˉjpj)2pj+n(Xˉkpk)2pk=j=1kn(Xˉjpj)2pj=j=1kn2(Xˉjpj)2npj=j=1k(nXˉjnpj)2npj\begin{aligned}&n(\bar{\mathbf{X}}^*-\mathbf{p}^*)^T(\mathbf{\Sigma}^*)^{-1}(\bar{\mathbf{X}}^*-\mathbf{p}^*) \\&=n\begin{bmatrix}\bar{X}_1-p_1 \\\bar{X}_2-p_2 \\\vdots \\\bar{X}_{k-1}-p_{k-1}\end{bmatrix}^T\left (\begin{bmatrix}\frac{1}{p_1} && 0 && \cdots && 0 \\0 && \frac{1}{p_2} && \cdots && 0 \\\vdots && \vdots && \ddots && \vdots \\0 && 0 && \cdots && \frac{1}{p_{k-1}}\end{bmatrix}+\frac{1}{p_k}\begin{bmatrix}1 && 1 && \cdots && 1 \\1 && 1 && \cdots && 1 \\\vdots && \vdots && \ddots && \vdots \\1 && 1 && \cdots && 1\end{bmatrix}\right )\begin{bmatrix}\bar{X}_1-p_1 \\\bar{X}_2-p_2 \\\vdots \\\bar{X}_{k-1}-p_{k-1}\end{bmatrix} \\&=n\begin{bmatrix}\bar{X}_1-p_1 \\\bar{X}_2-p_2 \\\vdots \\\bar{X}_{k-1}-p_{k-1}\end{bmatrix}^T\begin{bmatrix}\frac{1}{p_1} && 0 && \cdots && 0 \\0 && \frac{1}{p_2} && \cdots && 0 \\\vdots && \vdots && \ddots && \vdots \\0 && 0 && \cdots && \frac{1}{p_{k-1}}\end{bmatrix}\begin{bmatrix}\bar{X}_1-p_1 \\\bar{X}_2-p_2 \\\vdots \\\bar{X}_{k-1}-p_{k-1}\end{bmatrix}\\&+n\begin{bmatrix}\bar{X}_1-p_1 \\\bar{X}_2-p_2 \\\vdots \\\bar{X}_{k-1}-p_{k-1}\end{bmatrix}^T\frac{1}{p_k}\begin{bmatrix}1 && 1 && \cdots && 1 \\1 && 1 && \cdots && 1 \\\vdots && \vdots && \ddots && \vdots \\1 && 1 && \cdots && 1\end{bmatrix}\begin{bmatrix}\bar{X}_1-p_1 \\\bar{X}_2-p_2 \\\vdots \\\bar{X}_{k-1}-p_{k-1}\end{bmatrix} \\&=n\sum_{j=1}^{k-1}\frac{(\bar{X}_j-p_j)^2}{p_j}+n\frac{1}{p_k}\left (\sum_{j=1}^{k-1}(\bar{X}_j-p_j)\right )^2 \\&=\sum_{j=1}^{k-1}\frac{n(\bar{X}_j-p_j)^2}{p_j}+\frac{n(\sum_{j=1}^{k-1}\bar{X}_j-\sum_{j=1}^{k-1}p_j)^2}{p_k} \\&=\sum_{j=1}^{k-1}\frac{n(\bar{X}_j-p_j)^2}{p_j}+\frac{n((1-\bar{X}_k)-(1-p_k))^2}{p_k} \\&=\sum_{j=1}^{k-1}\frac{n(\bar{X}_j-p_j)^2}{p_j}+\frac{n(\bar{X}_k-p_k)^2}{p_k} \\&=\sum_{j=1}^k\frac{n(\bar{X}_j-p_j)^2}{p_j} \\&=\sum_{j=1}^k\frac{n^2(\bar{X}_j-p_j)^2}{np_j} \\&=\sum_{j=1}^k\frac{(n\bar{X}_j-np_j)^2}{np_j}\end{aligned}
다시 정리하면 다음과 같이 j=1k(nXˉjnpj)2npj\sum_{j=1}^k\frac{(n\bar{X}_j-np_j)^2}{np_j}이 Degree of Freedom이 k1k-1인 Chi Squared Distribution을 따르는 것을 확인할 수 있습니다.
n(Σ)12(Xˉp)N(0,Ik1)n(Xˉp)T(Σ)1(Xˉp)χk12n(Xˉp)T(Σ)1(Xˉp)=j=1k(nXˉjnpj)2npjj=1k(nXˉjnpj)2npjχk12\begin{aligned} & \sqrt{n}(\mathbf{\Sigma}^*)^{-\frac{1}{2}}(\bar{\mathbf{X}}^*-\mathbf{p}^*) \sim N(\mathbf{0}, \mathbf{I}_{k-1}) \\ & n(\bar{\mathbf{X}}^*-\mathbf{p}^*)^T(\mathbf{\Sigma}^*)^{-1}(\bar{\mathbf{X}}^*-\mathbf{p}^*) \sim \chi_{k-1}^2 \\ & n(\bar{\mathbf{X}}^*-\mathbf{p}^*)^T(\mathbf{\Sigma}^*)^{-1}(\bar{\mathbf{X}}^*-\mathbf{p}^*)=\sum_{j=1}^k\frac{(n\bar{X}_j-np_j)^2}{np_j} \\ & \sum_{j=1}^k\frac{(n\bar{X}_j-np_j)^2}{np_j} \sim \chi_{k-1}^2 \end{aligned}

Conclusion

이 글에서는 Chi Squared Test의 수식을 증명해 보았습니다. 교과서에 식만 나와 있고 증명이 생략되어 있는 경우가 많아서 교과서만 가지고는 이해가 쉽지 않습니다만 이 글을 통해 조금이라도 이해하는데 도움이 되었으면 좋겠습니다.
작성자
관련된 글 더 보기