Ejemplo
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
4
3
4
5
2
4
3
4
5
1
4
3
4
5
2
4
3
4
Con N=18, encontrar el elemento que estaba en
la posición 0 requiere 4 iteraciones;
El de la posición 6, 3 iteraciones; etc., etc.
i
PI(i)
1
2
3
4
1/N
5
3/N
2/N
4/N
8/N
Probemos con vectores más grandes:
Buscando el ajuste perfecto con R*
E(I) versus log(N) base 2
13
12
9
10
11
mu
8
T=1:100
T=500*T
mu=array(NA, dim=100)
for (i in 1:100) {
F = bbinaria(T[i])
mu[i] = sum(F$x*F$p)
}
lT=log2(T)
mod=lm(mu~lT)
summary(mod)
14
bbinaria = function(N) {
m = floor(log2(N+1))
x = 1:m
u = 2^(x-1)
if (sum(u) < N) {
p = c(u/N, 1-sum(u)/N)
x = c(x, m+1)
} else {
p = u/N
}
return (list(x=x, p=p))
}
9
10
11
12
13
14
15
lT
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) -0.986585
0.027777 -35.52
<2e-16 ***
lT
1.003313
0.001946 515.65
<2e-16 ***
Aproximadamente: mu = log(N) – 1 = log(N/2)
* http://www.r-project.org/
Pseudo-Random vs. True Random
A Simple Visual Example
http://www.boallen.com/random-numbers.html
http://www.microsiervos.com/archivo/azar/
http://est-fib.blog.com/
Descargar

Diapositiva 1