随机化序列算法分析

Two algorithms of randomize array of size n,

Algorithm A:

1. assign 1:n to array A of size n


2. step i=1:n-2


3. generate random number k ~ U[0, n-1-i]


4. B[i] = k


5. for j=k, n-2, A[j]=A[j+1]


6. repeat 2-5 on i

Algorithm B:

1. array A of 1:n


2. for i=0, n-1


3. generate k ~U[0, n-1]


4. swap A[i], A[k]

Algorithm A needs two array storage, averagely sum(1, (n-1)/2) assignments, that is (1+(n-1)/2)*(n-1)/2/2, leads to (n^2-1)/8, i.e. an O(n^2/8) algorithm.

Algorithm B needs one array storage, 2n assignments (n swaps), an O(2n) algorithm

Let n^2-1=8*2n, n approximates 16, i.e., when n <17, A is better, else, B is better

该blog的功能

科学读书笔记，学吧！学海无涯……

Zhongyan 

Xijiang in Germeny 

Test 

The integration about VC results continues today

Numerical stuff for LR first.

Single family,
E(NCP) = n•q²/e²/4
if we take the comparison of QTL allele ^~q² as a variable, then ^~q²/q² follows a χ² distribution with 1 degree of freedom.
Then the power = ∫Pχ²₍₁₎•[1-F_cdf(threshold, df1, df2, c•χ²₍₁₎)] dχ²₍₁₎.
where, c = E(NCP)
Above obtained very good results for single families.

It is easy to consider multiple families like this:
E(NCP) = Σ(c•^~q²_i/q²) = c•(Σ^~q²_i/q²) = c•χ²_(nf)
where nf is the number of families.

The theoretical results turned out much larger than empirical results.

To explore the source of difference, I calculated some results as below:
nf: 2
n: 30
df1: =nf
df2: =nf•(n-2)
q²: .2
h²: .4
Then:
ENCP=3.53
Ev


To be continued ....

Today's tasks

1. Numerical integeration about LR method.
2. Approximation about VC method

Both above are about random model.

btw, Peter's guess about VC NCP is great. I will put it here later.

Starting of the blog

This blog will keep a track of my progresses on the bioinformatics studying. Comments from collaborators and peers are welcomed.