Pseudo-willekeurige getallengenerator – exponentiële verdeling

Ik zou graag wat pseudo-willekeurige getallen willen genereren en tot nu toe was ik erg tevreden met de Random.Next(int min, int max)-functie van de .Net-bibliotheek. PRNG’s van deze variant worden verondersteldom een ​​uniforme distributie, maar ik zou heel graag wat getallen willen genereren met een Exponentiële distributie.

Ik programmeer in C#, hoewel ik pseudocode of C++, Java of iets dergelijks accepteer.

Enige suggesties / codefragmenten / algoritmen / gedachten?

Antwoord 1, autoriteit 100%

Omdat je toegang hebt tot een uniforme generator voor willekeurige getallen, is het genereren van een willekeurig getal dat wordt gedistribueerd met andere distributie waarvan je weet dat het CDF eenvoudig is met behulp van de inversiemethode.

Genereer dus een uniform willekeurig getal, u, in [0,1)en bereken vervolgens xdoor:

x = log(1-u)/(-λ),

waarbij λde snelheidsparameter van de exponentiële verdeling is. Nu is xeen willekeurig getal met een exponentiële verdeling. Merk op dat loghierboven lnis, de natuurlijke logaritme.

Antwoord 2, autoriteit 14%

De fundamentele stelling van Sampling stelt dat als je de gewenste verdeling kunt normaliseren, integreren en inverteren, je thuis bent.

Als je een gewenste distributie hebt F(x)genormaliseerd op [a,b]. Jij berekent

C(y) = \int_a^y F(x) dx

inverteer dat om C^{ -1}te krijgen, gooi zuniform op [0,1) en zoek

x_i = C^{ -1}(z_i)

die de gewenste distributie zal hebben.

In jouw geval: F(x) = ke^{ -kx}en ik ga ervan uit dat je [0,infinity]wilt. We krijgen:

C(y) = 1 - e^{ -ky}

wat omkeerbaar is om te geven

x = -1/k  ln(1 - z)

for z uniform gegooid op [0,1).

Maar eerlijk gezegd is het slimmer om een ​​goed gedebugde bibliotheek te gebruiken, tenzij je dit voor je eigen doeleinden doet.

Antwoord 3, autoriteit 10%

Dit is de formule die ik op Wikipedia heb gevonden:

T = -Ln(u) / λ

We maken een willekeurig getal met een uniforme verdeling (u) in [0,1]en we krijgen x :

Willekeurige R = nieuwe Willekeurige();

double u = R. NextDouble();

dubbel x = -Math.Log(u)/(λ);

Antwoord 4, autoriteit 6%

Als je goede willekeurige getallen wilt, overweeg dan om te linken naar de gsl-routines: http://www.gnu .org/software/gsl/. Ze hebben de routine gsl_ran_exponential. Als u willekeurige getallen wilt genereren met behulp van een ingebouwde generator met een uniforme verdeling op [0, 1) (bijv. u=Random.Next(0, N-1)/N, voor een grote N), gebruik dan gewoon:

-mu * log (1-u)

Zie randist/exponential.c in de gsl-bron.

EDIT: alleen ter vergelijking met enkele latere antwoorden – dit komt overeen met mu = 1/lambda. mu hier is het gemiddelde van de distributie, ook wel de schaalparameter genoemd op de wikipedia-pagina waarnaar het OP is gelinkt, en lambda is de snelheidsparameter.

Antwoord 5, autoriteit 4%

Een interessante eigenschap van de exponentiële verdeling: overweeg een aankomstproces met exponentiële interaankomsttijden. Neem een ​​willekeurige tijdsperiode (t1, t2) en de aankomsten in die periode. Die aankomsten zijn UNIFORM verdeeld tussen t1 en t2. (Sheldon Ross, Stochastische processen).

Als ik een pseudo-willekeurige nummergenerator heb en om de een of andere reden (mijn software kan bijvoorbeeld geen logbestanden berekenen), wilt u de bovenstaande transformatie niet uitvoeren, maar wilt u een exponentiële r.v. met een gemiddelde van 1,0.

U kunt:

1) Maak 1001 U(0,1) willekeurige variabelen.

2) Sorteer op volgorde

3) Trek de tweede van de eerste af, de derde van de tweede,… om 1000 verschillen te krijgen.

4) Die verschillen zijn exponentiële RV’s met een verdeling met gemiddelde = 1,0.

Minder efficiënt, denk ik, maar een middel tot hetzelfde doel.

Antwoord 6

De open-source Uncommons Maths-bibliotheek van Dan Dyerbiedt generatoren voor willekeurige getallen, kansverdelingen, combinatoriek en statistieken voor Java.

Naast andere waardevolle klassen heeft ExponentialGeneratorin wezen het idee geïmplementeerd dat is uitgelegd door @Alok Singhal. In zijn tutorialblog, wordt een codefragment gegeven om een ​​willekeurige gebeurtenis te simuleren die gemiddeld 10 keer per minuut plaatsvond:

final long oneMinute = 60000;
Random rng = new MersenneTwisterRNG();
// Generate events at an average rate of 10 per minute.
ExponentialGenerator gen = new ExponentialGenerator(10, rng);
boolean running = true;
while (true)
{
    long interval = Math.round(gen.nextValue() * oneMinute);
    Thread.sleep(interval);
    // Fire event here.
}

Als u de voorkeur geeft aan de tijdseenheid per second(in plaats van a minutehier), hoeft u natuurlijk alleen final long oneMinute = 1000.

Dieper ingaan op de broncodevan de methode nextValue()van ExponentialGenerator, vindt u de zogenaamde inverse transform samplingbeschreven in Generating_exponential_variates [wiki]:

public Double nextValue()
{
    double u;
    do
    {
        // Get a uniformly-distributed random double between
        // zero (inclusive) and 1 (exclusive)
        u = rng.nextDouble();
    } while (u == 0d); // Reject zero, u must be positive for this to work.
    return (-Math.log(u)) / rate.nextValue();
}  

P.S.:Sinds kort gebruik ik de Uncommons Maths-bibliotheek. Bedankt Dan Dyer.

Antwoord 7

Er is een andere manier om een ​​exponentiële (rate) willekeurige variatie te genereren, hoewel het tegenwoordig niet zo handig is als het gebruik van logaritmen. Het komt van een algoritme van John von Neumann (1951) en gebruikt alleen vergelijkingen.

1. Laat scale1/ratezijn. Zet highpartop 0.
2. Genereer een uniforme (0, scale) willekeurige variatie (zoals NextDouble()*scale), noem deze u.
3. Stel valin op uen stel acceptin op 1.
4. Genereer een uniforme (0, scale) willekeurige variatie, noem het v.
5. Als ugroter is dan v, stel dan uin op ven stel vervolgens accepttot 1 min accept, ga dan naar stap 4.
6. Als accepteren 1 is, retourneer val + highpart.
7. Voeg scaletoe aan highparten ga naar stap 2.

REFERENTIES:

• Von Neumann, J., “Verschillende technieken die worden gebruikt in verband met willekeurige cijfers”, 1951.

Antwoord 8

Als ik uw probleem begrijp en u een eindig aantal PRNG’s kunt accepteren, kunt u een benadering volgen als:

• Maak een array waarin elk element in je exponentiële verdeling zit
• Genereer een PRNG die een integer-index is in de array. Retourneer het element in de array op die index.

Antwoord 9

Dit was wat ik gebruikte toen ik met vergelijkbare vereisten werd geconfronteerd:

// sorry.. pseudocode, mine was in Tcl:
int weighted_random (int max) {
    float random_number = rand();
    return floor(max - ceil( max * random_number * random_number))
}

Dit is natuurlijk de formule om het willekeurige getal te kwadrateren, zodat je een willekeurig getal langs een kwadratische curve genereert.