Kolmogorov-Smirnov test (KS test)

KS test 是一非参数检验，用于检验某一个样本是否来自于某一特定分布，或者比较两个样本是否来自于相同的分布。这里我们先介绍检验样本是否来自于某一分布的KS检验，假设我们的样本为 $X_{1}$ , ... , $X_{n}$ ，要检验的分布函数为 $F(x)$ , null hypothesis为 X来自于分布 $F(x)$ .

在介绍KS检验之前，我们需要几点预备知识：

1. random step function

设 $\xi _{1}$ , ... , $\xi _{n}$ 为 i.i.d 的random variable，均值为0，方差为1. 对于每一个n，我们定义如下的连续时间随机过程：

$W_{n}(t) = \frac{1}{\sqrt{n}} \sum_{1 \leq k \leq [nt]} \xi _{k}$ , $t \in [0,1]$ .

$W_{n} (t)$ 被称作random step function.

（random step function有一些性质，比如说，对于足够大的n, $t \geq s$ ，根据中心极限定理， $W_{n}(t) - W_{n}(s)$ 接近于分布 $N(0,t-s)$ ; 当n趋向于无穷大时，Donsker's theorem表明 $W_{n} (t)$ 接近Wiener process,记为 $W_{t}$ ,是一均值为0方差为t的正态分布，Norbert Wiener在研究一维 Brownian motion的一些性质的时候发现的）

2. Brownian bridge

设 $W_{t}$ 为一标准 Wiener process，则定义Brownian bridge为：

$B(t) = W(t) - \frac{t}{T} W(T)$ , $t \in [0,T]$

(Brownian bridge有一些性质，如可以证明 $B(t)$ 与 $W(T)$ 相互独立。其均值为0，方差为 $\frac{t(T-t) }{T}$ )

接下来介绍KS test的内容。

n个相互独立的随机样本 $X_{1}$ , ... , $X_{n}$ ，其经验分布函数为:

$F_{n}(x) = \frac{1}{n} \sum_{i=1}^n I_{[-∞,x]} (X_{i} )$ , 其中 $I_{[-∞,x]}(X_i)$ 为indicator function，等于1 if $X_{i} \leq x$ ，等于0 otherwise.

构造Kolmogorov-Smirnov统计量 $D_n = \sup_{x} |F_n(x) - F(x)|$ .(根据Glivenko-Canteli theorem, 若样本来自于分布 $F(x)$ ,则当n趋向于无穷大时， $D_n$ 应该almost surely收敛到0)

下一步是构造服从Kolmogorov distribution的随机变量 K，定义：
$K = \sup_{t \in [0,1]} |B(t)|$ ，其中 $B(t)$ 为Brownian bridge.

根据Kolmogorov theorem， $\sqrt{n} D_n \rightarrow \sup_{t} |B(F(t))|$ as $n \rightarrow \infty$ . 取 $K_\alpha$ 为一实数使得 $Pr(K \leq K_{\alpha}) = 1- \alpha$ ,则，若 $\sqrt{n} D_n > K_{\alpha}$ ,以 level $\alpha$ 拒绝null hypothesis。

此检验在R等软件中都有运算包，可以直接使用。