Feeds:
Posts
Comments

Archive for October, 2010

Given n strings consisting of alphabets. How to concatenate all the strings to make a alphabetically smallest string? The algorithm is a simple greedy algorithm. Sort all strings by A <~ B. A <~ B iff AB < BA alphabetically. The proof seems not trivial. We need to prove the binary relation A <~ B is a totally ordered relation. It further reduces to proving that it is transitive, which seems to need a tedious discussion case by case.

Advertisements

Read Full Post »

假设检验是给定一组来自某个未知参数的分布的样本(x[1],x[2].,,,x[n]),检验分布的参数是否满足某个条件。通常是给出显著水平a检验正态分布N(u,Q^2)的期望u是否等于某个常数u0。对Q已知和未知分情况构造统计量进行检验。
~x是样本均值,~Q^2是Q^2的无偏估计 Sigma{ (x[i] – ~x)^2 }/ (n-1)。 假设H0u=u0

  1. Q已知的情况下,在H0为真时,统计量X=( ~x – u0)/(Q / sqrt(n)) 服从标准正态分布N(0,1)X 如果偏离N(0,1)的中间1-a部分时拒绝H0
  2. Q未知的情况下,在H0为真时,统计量T=(~x-u0)/(~Q / sqrt(n)) 服从自由度为n-1的t分布。T如果偏离T(n-1)的中间1-a部分时拒绝H0。这时称为t检验。

卡方(X^2)分布可以用来构造统计量作对方差Q^2的假设检验。
t检验还可以通过两个正态母体的样本(x[1],…,x[n])(y[1],…,y[m])来检验他们的均值是否相等,这里要求两个正态分布的方差是相等的,但是可以是未知的。构造统计量T=( ~x – ~y )/ ( S * sqrt(1/n, 1/m) ),T是服从自由度n+m-2的t分布,其中S= ( ( n-1 ) * ~Qx^2, (m-1) * ~Qy^2 ) / (n+m-2),~Qx^2~Qy^2分别是两个分布的方差的无偏估计。

而所谓的paired t-test则是对一一对应的两组来自正态样本(Xi,Yi),对它们的差Zi=Xi-Yi作t test。

在前面检验u=u0的两种情况时,如果u0也是未知的,则统计量XT其实是含有一个未知参数u0的,如果要求XT落到对应的分布的置信区间1-a内,那么我们计算得到u0的一个区间[u1,u2],于是这个区间可以作为对u0的一个估计区间,其置信度为1-a
这里对置信区间很容易误解,u0是未知的确定量,不是随机变量,所以不能说u01-a的概率落在置信区间。实际上XT,依赖于随即样本,是随机量,所以对应的置信区间也是随即量,正确的理解是多次抽取样本构造多个置信区间,其中将大约有1-a的区间包含u0。进一步可以说,做若干次任何置信区间为1-a的参数区间估计实验(可以估计不同分布的任何参数),其中将大约有1-a个区间包含对应的被估计参数。

Read Full Post »