suma szeregu liczb losowych

0

Proste zadanie:

dana jest liczba n, np. n = milion, i teraz tworzymy taką zabawną sumę liczb losowych:

i1 = random(n); // losowa od 0 do n-1
następnie:
i2 = random(i1);
i dalej:
i3 = random(i2);
itd.
finalnie dojdziemy do: i_k = 0.

Należy obliczyć sumę (statystyczną):
s = i1 + i2 + i3 + ... = ?

0

I w czym problem?

0

No i co tam słychać - takie to trudne znowu?

Weźmy wersją ciągłych losowych od 0 do 1, wtedy:
k1 = 1/2 średnio - zgadza się?
zatem
k2 = 1/4 - tak?
k3 = 1/8 ...

co razem daje sumę: 1/2 + 1/4 + 1/8 + ... = 1

zatem w wersji dyskretnej powinno być chyba 'n' po prostu... może ktoś to sprawdzi.

int s = 0, k = n;
do s += (k = random(k)); while( k ); 
2

Wydaje się sensowne. Losujesz najpierw od 0 do n, więc średnio n/2. Każde następne losowanie daje średnio /2, więc masz n/2 + n/4 + n/8 + ... więc masz zależność geometryczną z q=1/2

0
Shalom napisał(a):

Wydaje się sensowne. Losujesz najpierw od 0 do n, więc średnio n/2. Każde następne losowanie daje średnio /2, więc masz n/2 + n/4 + n/8 + ... więc masz zależność geometryczną z q=1/2

Tyko że w testach wychodzi 3n. :)

0

Mi na Wolfram (nie)wychodzi (pi^2)/6, ale może coś nie ogarniam (tak, to pomyłka - uwaga autora).

0
vpiotr napisał(a):

Mi na Wolfram wychodzi (pi^2)/6, ale może coś nie ogarniam.

Pokaż to - podaj link do wolframa z tym wynikiem, albo sama formuła.

Mi jak byk wychodzi 3, zamiast 1.

gdyby to był geometryczny, wówczas:
x/(1-x) = 3 => x = 3-3x => 4x = 3 => x = 3/4, czyli q = 3/4.
tylko że to na pewno nie jest geometryczny.

 double w = 0; // suma z N losowań
 for(int i = 0; i < N; i++) // N - liczba prób, np. milion
  {
    double s = 0, k = 1.0;
    do{ s += (k*=rndf()); }while( k > 1e-6); // 1/1e-6 = milion; to nie ma wpływu na wynik - można podstawić 1e-3, albo 1e-9.
     w+=s;
  }

 return w/N; // taki jest tu wynik - średnia

Osobne ciekawe zagadnienie: jak rozkład ma ta zmienna losowa?

Zwyczajna średnia (niezależnych) zmiennych losowych: (x1 + x2 + x3 + ...)/n, ma rozkład normalny.

2

@wil ale w jakich testach? jak sobie puścisz pętlę? To raczej mało miarodajne ;) Może ci się od razu wylosować 0 na przyklad ;]

0

No i się rąbnąłem, rzeczywiście wychodzi 1. Pomyliłem kolejność działań.

0

Wyliczasz tę sumę n razy, więc średnia będzie zbiegać do szukanej wartości, dla dużych n; w praktyce wystarczy zwykle n = milion.
Niekiedy otrzymasz 0.0, ale z prawdopodobieństwem 0+, więc to nie ma istotnego wpływu na wynik dla dużych n.

No i się rąbnąłem, rzeczywiście wychodzi 1. Pomyliłem kolejność działań.

Niemożliwe - mi wychodzi 3, z minimalnym rozrzutem: 2.999, itp.

0

@wil no to zafixuj pierwsze kilka losowań na 1/2 i zobacz jaki będzie efekt. Takie "testy" które robisz nie są miarodajne raczej.

0

suma = 1.

BTW.
jest to bardzo pozytywny wynik w kontekście problemu kolizji milionów kul:
złożoność prostego algorytmu, z listą minimalnych czasów kolizji, jest liniowa a nie nlogn!

0

Hej,
w testach wychodzi statystycznie 1... ale może pominąłem jakiś warunek... odpal może poniższy kod (lub równoważnik w innym języku):
[code]
import random

z = 0
w = 1
a = []
for j in range(10000):
z = 0
w = 1
for i in range(1000):
w = w*random.random()
z += w
a.append(z)
print(sum(a)/10000)
[/code]
PS. jak zachować wcięcia ? jest jakaś sztuczka techniczna, aby to zrobić wpisując tutaj kod ?? :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1