Bierzemy liczbę startową n i robimy z tego random(n),
otrzymujemy nową liczbę - mniejszą od n, i powtarzamy tak, aż do końca - do zera;
n_i = random(n_i-1);
n = 1361129467683753853853498429727072845824; // 2^130
k = 0; // liczba randoms aż do zera!
for(; n; k++)
n = random(n);
jaka jest średnia tej liczby k - spadku sukcesji od n aż do zera?
wersja z real:
n = 1.0; // 1000 cyfr precyzji
k = 0;
for( ; n; k++) n = rnd_unity()*n;
k = ? // średnio
Masz to zrobić teoretycznie, matematycznie - czy zaprogramować w realnym języku?
Bo komentarz o 1000 cyfr precyzji pachnie (brzydko) Zelentem.
Nie wiem co tu teoria pomoże.
Moje wyniki do miliarda:
n=2^ 7 = 128 : 5.44
2^ 8 = 256 : 6.15
2^ 9 = 512 : 6.78
2^10 = 1024 : 7.52
2^11 = 2048 : 8.21
2^12 = 4096 : 8.90
2^13 = 8192 : 9.64
2^14 = 16384 : 10.26
2^15 = 32768 : 10.98
2^16 = 65536 : 11.66
2^17 = 131072 : 12.37
2^18 = 262144 : 13.10
2^19 = 524288 : 13.78
2^20 = 1048576 : 14.37
2^21 = 2097152 : 15.19
2^22 = 4194304 : 15.86
2^23 = 8388608 : 16.50
2^24 = 16777216: 17.18
2^25 = 33554432: 17.90
2^26 = 67108864: 18.55
2^27 = 13421772 : 19.32
2^28 = 268435456: 19.88
2^29 = 536870912: 20.65
2^30 = 1073741824: 21.34
2^31 = 2147483648: 21.91
co to za funkcja?
2^64 : k = ?
Wersja dokładna (a nie symulacyjna):
def K(n):
ks = [0, 1]
while len(ks) < n:
ks.append(1+sum(ks)/len(ks))
return ks[-1]
To co masz to jest basically łańcuch Markova, a wzór który użyłem to wzór na średnią czas dotarcia:
http://smurf.mimuw.edu.pl/node/713
Twierdzenie 8.17
Edit: teraz widzę, że to się po prostu upraszcza do liczby harmonicznej, tj.
k(n) = 1 + 1/2 + 1/3 + ... + 1/n
Wynika to z faktu, że
K(n-1) = 1 + 1/(n-1) * (K(0) + K(1) + ... + K(n-2)) => K(0) + K(1) + ... + K(n-2) = (K(n-1) - 1) * (n-1)
Podstawiamy sobie tę częściową sumę do
K(n) = 1 + 1/n * (K(0) + K(1) + ... + K(n-1))
by dostać
K(n) = 1 + 1/n * (K(n-1) + (K(n-1) - 1) * (n-1))
i to się upraszcza do
K(n) - K(n-1) = 1/n
nowewww napisał(a):
co to za funkcja?
To jakiś logarytm 2 chyba.
Z bardzo grubsza:
n = 128, k(0) = 64 (centrum dzwona Gausa jest chyba na środku?)
n = 64, k(1) = 32
n = 32, k(2) = 16
n = 16..
n = 8..
n = 4..
n = 2..
n = 1...
n = 0
Czyli ogólnie dla dowolnego n liczba kroków będzie dążyła do wartości
a = log2(n) + c
Może jakiś matematyk albo kto jeszcze coś pamięta z matmy by to dokładniej / precyzyjniej opisał.
Może @enedil?
chyba pasuje: k(n) = suma 1/n
H(n) = 1 + 1/2 + ... 1/n = ...
2^ 7 = 128 : 5.44 - H(128) = 0.011
2^ 8 = 256 : 6.15 - H = 0.030
2^ 9 = 512 : 6.78 - H = -0.036
2^10 = 1024 : 7.52 - H = 0.014
2^11 = 2048 : 8.21 - H = 0.006
2^12 = 4096 : 8.90 - H = 0.008
2^13 = 8192 : 9.64 - H = 0.051
2^14 = 16384 : 10.26 - H = -0.023
2^15 = 32768 : 10.98 - H = 0.006
2^16 = 65536 : 11.66 - H = -0.004
2^17 = 131072 : 12.37 - H = 0.009
2^18 = 262144 : 13.10 - H = 0.050
2^19 = 524288 : 13.78 - H = 0.032
2^20 = 1048576 : 14.37 - H = -0.073
2^21 = 2097152 : 15.19 - H = 0.057
2^22 = 4194304 : 15.86 - H = 0.036
2^23 = 8388608 : 16.50 - H = -0.017
2^24 = 16777216 : 17.18 - H = -0.035
2^25 = 33554432 : 17.90 - H = -0.008
2^26 = 67108864 : 18.55 - H = -0.048
2^27 = 134217728 : 19.32 - H = 0.028
2^28 = 268435456 : 19.88 - H = -0.103
2^29 = 536870912 : 20.65 - H = -0.031
2^30 = 1073741824 : 21.34 - H = -0.036
chociaż te różnice są dość dziwne.
///////////////////////
Pozostaje do wyliczenia suma tego typu - losowo spadająca:
x = 1.0; s = 0.0;
while ( x ) s += (x=rnd_unity()*x);
s = ?
dobra zagadka?
Wyniki z sum losowych spadających: od 1 do 0:
2^ 7 = 128 : 1.01
2^ 8 = 256 : 0.95
2^ 9 = 512 : 0.98
2^10 = 1024 : 0.99
2^11 = 2048 : 0.98
2^12 = 4096 : 1.00
2^13 = 8192 : 1.00
2^14 = 16384 : 0.99
2^15 = 32768 : 0.98
2^16 = 65536 : 0.97
2^17 = 131072 : 0.98
2^18 = 262144 : 0.97
2^19 = 524288 : 0.96
2^20 = 1048576 : 1.00
2^21 = 2097152 : 0.98
2^22 = 4194304 : 1.00
2^23 = 8388608 : 1.03
2^24 = 16777216 : 0.95
2^25 = 33554432 : 0.99
2^26 = 67108864 : 1.02
2^27 = 134217728 : 1.04
2^28 = 268435456 : 0.96
2^29 = 536870912 : 0.99
2^30 = 1073741824 : 0.98
zabawne: suma jest stała = 1.0
losowa z przedziału od 1 do 0 = 1/2.
zatem suma kolejnych jest równa: 1/2 + 1/4 + 1/8 + ... = 1
pomimo że to powinno być = oo, bo zero jest nieosiągalne: prawdopodobieństwo zera = 0.
O co tu chodzi?
Chodzi o sumę tych kolejnych liczb z losowań, aż do zera.
w wersji ciągłej:
x = 1.0; // start
for( ; x > 0; )
s += x = rand(0.0, x); // random od 0 do x, czyli to samo co: rand1 * x;
W dyskretnej podobnie -
wtedy ta suma zawsze jest n: s = n, więc: s/n = 1.0, to samo co na ciągłych.