Události s předem danou pravděpodobností

Cajova_Houba_2

Události s předem danou pravděpodobností
« kdy: 28. 04. 2015, 13:15:00 »
Zdravim, mám následující problém.
Mám několik událostí (na těch nezáleží) a kadžá z nich má přiřazenou určitou pravděpodobnost. Součet pravděpodobností je 1. V programu budu náhodně generovat čísla v <0;1) a podle vygenerovaného čísla se vykoná událost. Nejsem si uplně jistej, jak to udělat. Zatim mě napadlo následující
mam události a k nim pravděpodobnosti např A(p_a), B(p_b), C(p_c), .....
Budu generovat náhodná čísla r z intervalu <0;1*max(p)).
Pak budu r postupně porovnávat s pravděpodobnostma od nejnižší a pokud bude r<=p, vykoná se příslušná událost.

Když bych to měl ukázat na konkrétním příkladu:
A(0.1), B(0.2), C(0.7) r je z intervalu <0;0.7)
r= 0.47 => C
r= 0.1   => A
r= 0.15  => B
...a tak dál

Nejsem si ale uplně jistej správností mýho řešení, takže bych vás rád požádal o nějakou radu.
Díky


libcha

Re:Události s předem danou pravděpodobností
« Odpověď #1 kdy: 28. 04. 2015, 13:34:55 »
Jestli to správně chápu, chceš něco jako (pseudokod):

double nahoda = get_random_between_0_and_1();
double jevy[pocet_jevu] = get_all_cases_probabilities(); // soucet vsech jevu je 1.0
double mezisoucet = 0.0;

foreach jev in jevy {
  if (nahoda - mezisoucet <= jev) zasah(); // muzes pouzit < misto <=
  else mezisoucet += jev;
}

Neříkám že je to nejjednodušší nebo nejhezčí, ale dá se to tak ;)

Cajova_Houba_2

Re:Události s předem danou pravděpodobností
« Odpověď #2 kdy: 28. 04. 2015, 13:40:16 »
Jo, trochu sem se v tom rejpal a nakonec sem došel k stejnmýu principu, jenom tak nějak z druhý strany  :D Vypadá to, že je to ono, takže díky za pomoc

none_

Re:Události s předem danou pravděpodobností
« Odpověď #3 kdy: 28. 04. 2015, 13:43:03 »
asi nejrychlejsi a pritom relativne jednoduche je si vytvorit serazene pole tech jevu. Takze napr:

pole[0]=jev<0.0;0.1)
pole[1]=jev<0.1;0.3)
pole[2]=jev<0.3;0.5)
...

A pak vyber pulenim:
1. dostanu pole,
2. strelim na stred
3. jsem tam, kde chci byt?
  a. ano - konec
  b. chci mensi, vezmi vsechno nalevo ode me jako pole a jdi do bodu 1.
  c. chci vetsi, vezmi vsechno napravo ode me jako pole a jdi do bodu 1.

gamer

Re:Události s předem danou pravděpodobností
« Odpověď #4 kdy: 28. 04. 2015, 13:59:42 »
Tyhle řešení nebudou fungovat, když budu mít A(0.25), B(0.25), C(0.25), D(0.25). Správné řešení je udělat to přes diskrétní rozložení pravděpodobnosti:
http://www.cplusplus.com/reference/random/discrete_distribution/


none_

Re:Události s předem danou pravděpodobností
« Odpověď #5 kdy: 28. 04. 2015, 14:44:59 »
Jen takovy dotaz, proc by ten vas pripad nefungoval? Jen proste nageneruju tu tabulku takhle:
pole[0]=A<0.0;0.25) pro A(0.25)
pole[1]=B<0.25;0.5) pro B(0.25)
pole[2]=C<0.5;0.75) pro C(0.25)
pole[3]=D<0.75;1.0) pro D(0.25)

pseudonym neni anonym

Re:Události s předem danou pravděpodobností
« Odpověď #6 kdy: 28. 04. 2015, 14:46:03 »
Proc nestaci jednoduse vygenerovat nahodne cislo r z (0,1) a podle jeho velikosti rozhodnout?
r < 0.1 => A (delka intervalu je 0.1)
0.1 < r < 0.3 => B (delka intervalu je 0.2)
0.3 < r < 1 => C (delka intervalu je 0.7)
Tedy pokud toto opravdu odpovida zadani. Z toho, co je napsano v puvodni prispevku neni uplne jasne, ceho vlastne chce dosahnout.

none_

Re:Události s předem danou pravděpodobností
« Odpověď #7 kdy: 28. 04. 2015, 14:53:34 »
To je to, co presne delam. Jen potrebujete nejak najit ten sprany prvek. Tzn. musim je mit nekde ulozeny a pak je projit. Prvni moznost je zkusit postupne vsechny a vybrat ten, ktery odpovida (linearni slozitost). Druha moznost je ta moje, je trochu slozitejsi, ale pro velka pole zarucene rychlejsi (logaritmicka slozitost).

gamer

Re:Události s předem danou pravděpodobností
« Odpověď #8 kdy: 28. 04. 2015, 15:12:49 »
Ono to bude fungovat za předpokladu, že vygenerované náhodné číslo má uniformní rozložení pravděpodobnosti (což je většinou pravda, ale obecně to neplatí). Řešení none_ selže, pokud bude existovat událost s pravděpodobností 0, protože má uzavřený interval <0, N), takže mu to bude generovat i události s pravděpodobností 0. Obecně je lepší nevynalézat znovu kolo a použít ověřené řešení, které netrpí podobnými neduhy.

Cajova_Houba_2

Re:Události s předem danou pravděpodobností
« Odpověď #9 kdy: 28. 04. 2015, 17:41:26 »
To diskrétní rozdělení pravděpodobnosti vypadá (a nejspíš taky bude) nejspolehlivěji, takže použiju to. Díky za rady  :)

Re:Události s předem danou pravděpodobností
« Odpověď #10 kdy: 28. 04. 2015, 22:10:33 »
Součet pravděpodobností je 1.
...
Budu generovat náhodná čísla r z intervalu <0;1*max(p)).

Když bych to měl ukázat na konkrétním příkladu:
A(0.1), B(0.2), C(0.7) r je z intervalu <0;0.7)
r= 0.47 => C
r= 0.1   => A
r= 0.15  => B
...a tak dál
No to si snad děláš legraci, ne? :)
Musíš generovat čísla z intervalu <0;1):
0----0.1----0.3----1
teprve teď velikosti intervalů jsou v poměru 1:2:7

Správné řešení je udělat to přes diskrétní rozložení pravděpodobnosti:
http://www.cplusplus.com/reference/random/discrete_distribution/
discrete_distribution je jenom obálka, která udělá to, co chtěla čajová houba udělat ručně v úvodním příspěvku.
"Správnost řešení"  záleží na tom a pouze na tom, jestli použitý RNG (ať už se jedná o RNG použitý v discrete_distribution nebo o RNG použitý při "ručním" řešení) skutečně generuje rovnoměrné rozdělení pravděpodobnosti.

O generátorech náhodných čísel nic nevím, ale selským rozumem předpokládám, že každý generátor, který rovnoměrné rozdělení negeneruje, je považován za vadný, a čekal bych že generátory zabudované v C++ vadné nebudou.

Pokud se toho ale bojíš, pak místo generátoru který generuje typ real, použij generátor typu integer (pro tvou vzorovou úlohu s pravděpodobnostmi 0.1, 0.2, 0.7 by generoval čísla 0 až 9). Ten by snad mouchy mít neměl
Filip Jirsák: "Úplně stejně se ale jedná o podvod, když uživatel zamlčí provozovateli webu, že blokuje reklamu."

Re:Události s předem danou pravděpodobností
« Odpověď #11 kdy: 29. 04. 2015, 02:20:41 »
píšu moc zkratkovitě:
discrete_distribution je jenom obálka, ve které je ten RNG. A o ten jde.
Filip Jirsák: "Úplně stejně se ale jedná o podvod, když uživatel zamlčí provozovateli webu, že blokuje reklamu."

gamer

Re:Události s předem danou pravděpodobností
« Odpověď #12 kdy: 29. 04. 2015, 04:46:12 »
discrete_distribution je jenom obálka, která udělá to, co chtěla čajová houba udělat ručně v úvodním příspěvku.
Ano, udělá to přesně to, co chtěl autor udělat ručně v úvodním příspěvku. To je ta pointa, nemusí to dělat ručně :)

O generátorech náhodných čísel nic nevím, ale selským rozumem předpokládám, že každý generátor, který rovnoměrné rozdělení negeneruje, je považován za vadný, a čekal bych že generátory zabudované v C++ vadné nebudou.
Tak to předpokládáš špatně, jen na ukázku:
http://en.cppreference.com/w/cpp/numeric/random/normal_distribution
http://en.cppreference.com/w/cpp/numeric/random/poisson_distribution
http://en.cppreference.com/w/cpp/numeric/random/binomial_distribution

Re:Události s předem danou pravděpodobností
« Odpověď #13 kdy: 29. 04. 2015, 12:37:13 »
Tak to předpokládáš špatně, jen na ukázku:
http://en.cppreference.com/w/cpp/numeric/random/normal_distribution
http://en.cppreference.com/w/cpp/numeric/random/poisson_distribution
http://en.cppreference.com/w/cpp/numeric/random/binomial_distribution

A to dokládá co? To jsou rozdělení, nikoli RNG

Mimochodem, všechna ta rozdělení budou pravděpodobně fungovat úplně stejně jako discrete_distribution: budou využívat ten stejný vestavěný RNG jako využívá discrete_distribution.
Filip Jirsák: "Úplně stejně se ale jedná o podvod, když uživatel zamlčí provozovateli webu, že blokuje reklamu."

gamer

Re:Události s předem danou pravděpodobností
« Odpověď #14 kdy: 29. 04. 2015, 14:22:02 »
A to dokládá co? To jsou rozdělení, nikoli RNG

std::normal_distribution není žádné rozdělení, je to *generátor* náhodných čísel s normálním (Gaussovým) rozložením pravděpodobnosti. Jak je to implementováno je nepodstatné, může to být adaptér nad generátorem s uniformním rozdělením nebo cokoliv jiného. Důležité je, k čemu se to používá, a to je generování náhodných čísel s normálním (Gaussovým) rozložením pravděpodobnosti.