Keskustelu: Ohjelmointikysymykset: C++: Soluautomaateilla satunnaislukuja

Kaikella kunnioituksella FooBat:n ”tehokkaampaa” satunnaislukugeneraattoria kohtaan, mutta se ei toimi sitten kirveelläkään. Seuraavassa perustelut:

Satunnaisluvut ovat äärimmäisen mielenkiintoinen lukuteoreettinen kysymys. Mikä todella on satunnaissykli, ja mikä on ns. pseudosatunnaissykli. Luonnollinen satunnaissykli saadaan ainakin silloin, kun hattuun laitetaan korttipakka, hattua sekoitetaan, ja vedetään yksi kortti. Kortti voi olla mikä tahansa kortti. Sitten kortti laitetaan takaisin hattuun, sekoitetaan uudelleen, ja vedetään uusi kortti. Tällainen toiminta on hyvin lähellä sellaista luonnollista satunnaisuutta, jota tietokoneella on melko vaikea imitoida.

Soluautomaatit tuottavat selvästi luonnollisempia satunnaissyklejä, kuin näyttämäsi esimerkki, jonka perustana on jossain määrin kertolaskun kongruenssi. Huomattavin ero on siinä, että esimerkkisi pörrää vain yhdellä attraktorilla. Asia on helppo osoittaa graafisesti. Kokeile esimerkiksi seuraavanlaista:

unsigned int seed = 0;
int rnd() {
  const unsigned int offset = 12923; //joku alkuluku
  const unsigned int multiplier = 4079; //toinen alkuluku

  seed = seed * multiplier + offset;
  return seed;
}

void RndTest(HWND hWnd)
{
   int x, y;
   HDC hdc=GetDC(hWnd);
   for (long i=0; i<10000000L; i++)
   {
      x=rnd()%getmaxx(); /* ikkunan leveys */
      y=rnd()%getmaxy(); /* ikkunan korkeus */
      SetPixel(hdc, x, y, RGB(255,255,255));
   }
}

Harrastukseni puolesta olen syventynyt melko paljon soluautomaatteihin ja yleensäkin malleihin, millä koneen saisi imitoimaan jotain inhimillistä. Helppoa se ei ole, koska ongelmakenttä on niin laaja. Laajuudestaan huolimatta se on kuitenkin niin mielenkiintoinen, että asian parissa saa helposti vierähtämään vuosikymmeniä (ei asiaa tietenkään jaksa koko ajan fundeerata, ja aina välissä tulee tehtyä paljon muunlaisia juttuja).

Aika on kuitenkin hyvin suhteellista, kun puhutaan koodeista. Jotta sain toimimaan soluautomaattiin perustuvan teho-randomin, niihin riveihin ja asian tutkimiseen upposi vuosikymmen. Vasta nyt olen funktioon tyytyväinen, koska voin osoittaa, että teho-random poukkoilee kaoottisesti likimain 10 potenssiin 19 eri attraktorilla. Tästä seuraa, että satunnaisjakaumat asettuvat tasapainoon missä tahansa sfääreissä ja millä tahansa moduloilla.

No tuon esimerkin löysin jostain googlen ensimmäisestä linkistä ja siinä taitaa olla liian pienet alkuluvut vakioina.

Sama idea on kuitenkin näissä viralllisissakin vakiokirjastoissa mukana, joskin niissä tehdään yleensä jotain ylimääräisätä varmistaakseen, että luvut tasaisesti jakautuneita.

Esim. Javadoc Random-luokalle (48 bittinen seed, josta käytetään maksimissaan 32 bittiä)

synchronized protected int next(int bits) {
      seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
      return (int)(seed >>> (48 - bits));
}
This is a linear congruential pseudorandom number generator, as defined by D. H. Lehmer and described by Donald E. Knuth in The Art of Computer Programming, Volume 2: Seminumerical Algorithms, section 3.2.1.

Testailin tuota sinun koodiesimerkkiä ja ainakin lukujen yläbitit eivät ole kovin satunnaisesti jakautuneita. Se selviää, kun skaalataan satunaisluku välille [0..1), kerrotaan halutulla luvulla ja katsotaan lukujen (integerien) jakaumaa. Suurella testijoukolla jakauma vaihteli noin 10% odotusarvon molemmilla puolilla ja luvut pääasiassa painottuivat lukualueen keskikohtaan.

Moduluilla tehdessä tuo näytti kyllä ihan hyvältä, vaikka en testannutkaan kovin monia moduloita.

Terve FooBat, ihan hyvä näkökulma testata satunnaislukujen jakaumaa tuolta kantilta. Ero on nyt siinä, että minä saan tasaisen jakauman, ja sinun testikoodisi antaa ilmeisesti epätasaisen jakauman. Oletko nyt varma, että testikoodisi huomioi kaikki luvut [0, 1) välille? Kokeile tuolla mun testikoodilla, vieläkö jakauma heittää odotusarvon ulkopuolelle. Vedin jakauman kooksi hihasta arvon 31313, mutta ainakin itse saan tasaisen jakauman kaikilla arvoilla:

#include <stdio.h>
#include <conio.h>
#include <values.h>
#include <memory.h>

#define MAX_RND ((unsigned)((MAXINT<<4)|0x0f))

int rnd(void)
{
   static long r1=1L; /* voi olla mikä tahansa alkuarvo */
   static long r2=2L; /* voi olla mikä tahansa alkuarvo */
   r1 -= 0x012357bfL; /* 16 bittiä sisältävä alkuluku */
   r2 += 0xfedca201L; /* 16 bittiä sisältävä alkuluku */
   r1 += (r1>>16)^(r2<<16); /* sekoitetaan */
   r2 -= (r1<<16)^(r2>>16); /* sekoitetaan */
   return (int)(r1^r2); /* kerran vielä kiellon päälle */
}

void main(void)
{
   long i;
   int laskuri, tauko;

   unsigned long *jakauma=new unsigned long[31313];
   memset(jakauma, 0, sizeof(unsigned long)*31313);

   for (i=0; i<100000000L; i++)
   {
      unsigned luku=(unsigned)rnd();
      double x=(double)luku/(double)MAX_RND;
      unsigned y=(unsigned)(x*31313);
      ++jakauma[y];
   }

   printf("paina aina jotain nappainta, niin tulostus jatkuu...\n");

   for (laskuri=31313-1, tauko=0; laskuri>=0; laskuri--)
   {
      printf("%10u", jakauma[laskuri]);
      if ((++tauko)==64)
      {
         tauko=0;
         getch();
      }
   }

   delete[] jakauma;
}

Oma testikoodini. Luvut painottuivatkin reunoille (muistin väärin kun aluksi skaalasin luvut hiukan eri tavalla).

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define N 10

int rnd(void)
{
   static long r1=1L; /* voi olla mikä tahansa alkuarvo */
   static long r2=2L; /* voi olla mikä tahansa alkuarvo */
   r1 -= 0x012357bfL; /* 16 bittiä sisältävä alkuluku */
   r2 += 0xfedca201L; /* 16 bittiä sisältävä alkuluku */
   r1 += (r1>>16)^(r2<<16); /* sekoitetaan */
   r2 -= (r1<<16)^(r2>>16); /* sekoitetaan */
   return (int)(r1^r2); /* kerran vielä kiellon päälle */
}
int main(void) {
  int test[N]= {0}, i;

  printf("rnd test\n");

  for (i = 0; i < 100000000; i++) {
    double r = (unsigned)rnd();
    r /= ((double)UINT_MAX)+1;
    test[(int)(r*N)]++;
  }

  for (i = 0; i < N; i++)
    printf("%d\n", test[i]);
  return EXIT_SUCCESS;
}

Tuossa näkyy 10% eroja odotusarvosta eikä mielestäni skaalaustavassani ole vikaa.

Terem FooBat, testikoodissasi on kaksi heikkoa lenkkiä. Ensinnäkin taulukosta test[N] pitäisi alustaa kaikki alkiot nolliksi. (Tosin ilmeisesti jotkin kääntäjät tekevät sen automaattisest, mutta yleensä pinosta varataan vain sopivan kokoinen pläntti, ja arvot ovat silloin, mitä pinossa sattuu olemaan.)

Toisekseen random funktion maksimi ei ole ((double)UINT_MAX)+1, vaan se on 32-bittisessä mööpelissä 0xffffffff ja 16 bittisessä vekottimessa 0xffff.

Tämän vuoksi itse "varmistan" maksimin esikääntäjällä pöljästi:

#define MAX_RND ((unsigned)((MAXINT<<4)|0x0f))

Tämä siis shiftaa MAXINT vakion ensimmäisen äffän (0x0f:n) vasemmalle huidsin nevadaan, ja lykkää alimmat neljä bittiä päälle, jolloin lopputuloksena on 32-bittisessä 0xffffffff ja vastaavasti 16-bittisessä koneessa 0xffff.

Kokeilepa noilla korjauksilla, alkaako saamasi jakauma tasaantumaan :-)

Mä en vieläkään osaa korjata painovirheitä, mutta enköhän opi. Siis MAXINT arvosta tietenkin shiftataan ensimmäinen seiska (0x07) huidsin nevaan, jolloin se korvautuu 0x0f:llä ja sitten niihin neljään alimpaan tyhjään bittiin lykätään vielä se 0x0f.

JoinTuanJanohon kirjoitti:

Terem FooBat, testikoodissasi on kaksi heikkoa lenkkiä. Ensinnäkin taulukosta test[N] pitäisi alustaa kaikki alkiot nolliksi. (Tosin ilmeisesti jotkin kääntäjät tekevät sen automaattisest, mutta yleensä pinosta varataan vain sopivan kokoinen pläntti, ja arvot ovat silloin, mitä pinossa sattuu olemaan.)

Tuo alustaa taulukon alkiot nollaksi ainakin kaikissa minun käyttämissä ympäristöissä ja niin se opetettiin jopa eräällä kohtuullisella C-kurssilla.

int test[N] = {0};

JoinTuanJanohon kirjoitti:

Toisekseen random funktion maksimi ei ole ((double)UINT_MAX)+1, vaan se on 32-bittisessä mööpelissä 0xffffffff ja 16 bittisessä vekottimessa 0xffff.

UINT_MAX on käsittääkseni koneesta riippuen juurikin tuo 0xffffffff tai 0xffff, koska ne ovat unsigned int tyyppisen muuttujan maksiarvot. Se ykkönen on siellä perässä estämään, että jakolaskun tulos ei koskaan ole 1 edes sillä maksimiarvolla.

JoinTuanJanohon kirjoitti:

Tämän vuoksi itse "varmistan" maksimin esikääntäjällä pöljästi:

#define MAX_RND ((unsigned)((MAXINT<<4)|0x0f))

Tämä siis shiftaa MAXINT vakion ensimmäisen äffän (0x0f:n) vasemmalle huidsin nevadaan, ja lykkää alimmat neljä bittiä päälle, jolloin lopputuloksena on 32-bittisessä 0xffffffff ja vastaavasti 16-bittisessä koneessa 0xffff.

Käyttäisit vai suoraan UINT_MAX arvoa, jossa se ensimmäinen 7 on jo valmiiksi f.

Testikoodissasi oli muuten vielä yksi ajatusvirhe. Ohessa korjaukset:

int main(void) {
  int test[N+1], i;
  unsigned max=(unsigned)0xffffffffL;

  for (i=0; i<N; i++) {
    test[i]=0;
  }

  printf("rnd test\n");

  for (i = 0; i < 100000000; i++) {
    double r = (unsigned)rnd();
    r /= (double)max;
    test[(int)(r*N)]++;
  }

  for (i = 0; i < N; i++)
    printf("%d\n", test[i]);
  return EXIT_SUCCESS;
}

Mä en näe muuta eroa mun koodiin kuin, että se on pidempi ja siellä on yksi turha alkio taulukossa :). Tuloksetkin ovat ihan samat.

Hyvä huomio. En muuten ole habainnut, että tuommoinenkin kätevä vakio on olemassa, jossa ne kaivatut bitit ovat kaikki päällä. Pitää ruveta jatkossa käyttämään tuota vakiota, silloin kun unsigned maksimia tarvitsee.

PS. Jos haluat nostaa jakauman offsettia yhdellä pykälällä, tarkempi tulos on tavalla;

for (i = 0; i < 100000000; i++) {
  double r = (unsigned)rnd();
  r /= ((double)UINT_MAX); /* ei tässä +1; */
  test[(int)(r*N)+1 /* vaan täällä */]++;
}

for (i = 1; i <= N; i++) /* nyt 0 ei kuulu joukkoon, mutta N vielä kuuluu */
  printf("%d\n", test[i]);

En halunnut nostaa offsettia yhdellä vaan varmistaa, että jakolaskun tuloksena ei tule ykköstä, kun rnd() palauttaa UINT_MAX arvon. Tällöin taulukossa tapahtuisi ylivuoto, koska (int)(1*N) olisi N, mikä on suurenpi kuin taulukon maksimiindeksi.

Tässä vielä minun testikoodini. Tämän mukaan oma funktioni toimii hyvin tasaisesti, mutta tuo JoinTuanJanohonin funktio painottuu hieman liikaa minun makuuni.

Ja tuo oma funktioni (Randomi) mukamas onnistuu kiertämään kaikki 2³² lukua ennen kuin saa taas saman... Kokeilkaa ja kertokaa, onko tosiaan näin?

#include <stdlib.h>
#include <stdio.h>

// ============================================================================
int RInt;

// ============================================================================
int Randomi(void)
{
    RInt = (RInt * 2089L) + 536870911L;
    return RInt;
}

// ============================================================================
int rnd(void)
{
   static long r1; /* voi olla mikä tahansa alkuarvo */
   static long r2; /* voi olla mikä tahansa alkuarvo */
   r1 -= 0x012357bfL; /* 16 bittiä sisältävä alkuluku */
   r2 += 0xfedca201L; /* 16 bittiä sisältävä alkuluku */
   r1 += (r1>>16)^(r2<<16); /* sekoitetaan */
   r2 -= (r1<<16)^(r2>>16); /* sekoitetaan */
   return (int)(r1^r2); /* kerran vielä kiellon päälle */
}

#define rajoja 16
#define skaalaaja 2147483648.0
#define maara_prosentit (Maara * 0.01)

double luku;
double rajat[rajoja+1];
int maarat_1[rajoja];
int maarat_2[rajoja];

// ============================================================================
int main(int argc, char **argv)
{
    long long a, b;
    long long Maara = 1;
    Maara <<= 24; // kauanko jaksat odottaa? :)

    /* Rajat tasaisesti */
    for (a = 0; a < rajoja; a++)
    {
        rajat[a] = (double)(a-(rajoja >> 1)) / (double)(rajoja >> 1);
        maarat_1[a] = maarat_2[a] = 0;
    }
    rajat[a] = 9.999; // Tätä ei ainakaan ylitetä.

    /* Arvotaan */
    for (a = 0; a < Maara; a++)
    {
        luku = rnd() / skaalaaja;
        for (b = 0; luku > rajat[b]; b++);
        maarat_1[--b]++;
    }

    /* Arvotaan toiset */
    for (a = 0; a < Maara; a++)
    {
        luku = Randomi() / skaalaaja;
        for (b = 0; luku > rajat[b]; b++);
        maarat_2[--b]++;
    }

    /* Tulostus */
#define merkki(x) ((x) < 0 ? '-' : ' ')
#define merkiton(x) ((x) < 0 ? -(x) : (x))

    printf("Otos: %i%i\n\n", (int) (Maara / 1000), (int) (Maara % 1000));
    printf("Raja                        rnd()               Randomi()\n\n");

    for (a = 0; a < rajoja; a++)
    {
        printf("%c%1.3f <= x < %c%1.3f: %10i (%1.2f%%), %10i (%1.2f%%)\n",
        merkki(rajat[a]), merkiton(rajat[a]),
        merkki(rajat[a+1]), merkiton(rajat[a+1]),
        maarat_1[a], maarat_1[a] / maara_prosentit,
        maarat_2[a], maarat_2[a] / maara_prosentit);
    }

    return 0;
}

Skaalaus menee siis välille -1,0 <= x < 1,0, ja se on tarkoituskin. Käsittääkseni tuolla 16 ryhmän tekniikalla jokaiseen ryhmään kuuluu yhtä monta alkuperäisistä kokonaisluvuista, eikö? (4294967296 / 16 = 268435456)

Jep, sori, kun ajatukseni karkasi. Silti tossa mun test[N+1] virityksessä ajatuksena oli, ettei taulukko menisi yli, koska jakolaskun tulos siinä voi olla maksimissaan tasan +1.00000...

Ja sitten siinä tuloksen printtaamisessa olis vielä tarvinnut ottaa N:skin alkio tulostukseen mukaan.

Mutta ollanko me nyt samaa vai erimieltä jakauman tasaisuudesta? Mulla on TAMMERTEKNIIKAN kaavasto vuodelta eaa. alias ekr., ja siinä olevia laskuopin kaavoja käyttämällä jakauma on tasan sitä, mitä sen tasaisesti jakautuneessa joukossa pitää olla.

Jos me ollaan eri mieltä, niin sitten mä käytän vähän enemmän aikaa sen osoittamiseen, että jakauma on tasaisesti jakautunut. Tuo on juuri oikea periaate kyseenalaistaa koodinpätkien toimivuus. Mun tapana tehdä koodia on, että koodaamiseen menee ajasta 10 prosenttia, ja loput 90 prosenttia yritän kaikin keinoin osoittaa, ettei se koodinpätkä toimi. Ellei sitten parhaalla tahdollakaan löydä sitä viimeistä piilevää ajatusbugia, niin funktiolle voi antaa viimeisen voitelun ja siunauksen :)

"Siinä olevia laskuopin kaavoja käyttämällä jakauma on tasan sitä, mitä sen tasaisesti jakautuneessa joukossa pitää olla."

Mitähän tuo nyt sitten tarkoittaa? Minusta tasaisesti jakautunut joukko on sellainen, jossa on yhtä monta jokaista lukua (tai lukua tietyltä väliltä, kuten näissä skaalauksissa), ja siinä mielessä tuo sinun tapasi ei toistaiseksi ole osoittautunut vielä tasaiseksi.

Nyt mäni mielenkiintoiseksi :D Metabolix saattaa olla oikeassa tai väärässä. Nyt on pakko aloittaa syvällisempi asian tarkastelu. Sen oon huomannut, että näillä saiteilla on koko koodaajien kirjo. Sielä pylvään toisessa päässä on sen verran enemmän koodanneita hemmoja, että nyt ei enää uskalla tämän enempää puolustaa omaa jakaumaa, ennen kuin asian on ensin perinpohjin tutkinut. Palaan siis astialle huomen-illalla tulokien kanssa, jolloin mahdollinen lisäkädenvääntö voi alkaa. Mutta pystyn myös helposti myöntämään tappioni, jos tuo random-koodinpätkä todella painottaa lukuja jotenkin huonommin kuin kääntäjien tehtailemat satunnaisfunktiot...

Pakko vielä vastata Metabolixin kaneettiin. Itse asiassa nyt on vähän käsitteet sekaisin. Eihän satunnaislukujen joukko voi koskaan olla siten jakautunut, että ajanhetkellä delta kaikkia lukuja on yhtä monta? Mitä oikein hait, voitko tarkentaa?

Satunnaislukujen esiintymistä tutkittaessa käytetään aina sopivaa kvantisointia. Toisin sanoen, jos satunnaislukujoukko skaalataan 256 (0-255) alkioon, ja luuppin tulosta tarkastellaan ajanhetkellä t1, ja uudestaan ajanhetkellä t2, niin ajanhetkellä t2 joukon hajonta on pienempi kuin ajanhetkellä t1 otettu mittausarvo.

Tämän matemaattisen faktan aion ottaa todistukseni lähtökohdaksi, että satunnaisjoukon hajonta todella suppenee ihannearvoonsa (kun kysymyksessä on nimenomaan tasaisesti jakautunut satunnaislukujoukko).

No tiedä nyt, voiko minua sanoa "enemmän koodanneeksi" :) Ja tuota matemaattista puolta satunnaisluvuista en tosiaan tiedä, mutta kun testiohjelma kertoo, että 10000000 luvusta skaalattuna alueelle 0-1 ja jaoteltuna samankokoisille lukualueille jollain välillä on liki 5,5% ja toisella vain 4,7%, niin sitä on paha muuksi tulkita, varsinkin, kun oma randomi pistelee tasaisesti 5% kaikkiin. En nyt muista tarkkoja tuloksia; katsotaan, jos tuo ohjelma joskus saa työnsä valmiiksi (2³² satunnaislukua molemmilta :)

Niin ja tarkoitin siis sitä, että jos heitämme noppaa 60 kertaa, meillä on jokaista silmälukua (1-6) 10 kappaletta. Silloin ne ovat jakautuneet tasan. Totta kai tilanne on 57 heiton kohdalla hieman epätasainen, mutta silloinkin löytyisi 3x10 ja 3x9.

Aidossa satunnaisuudessa näin ei toki tapahdu, mutta aidossa satunnaisuudessa ei myöskään ole väkisin lopputuloksena suurempaa määrää joori nelosia, vaan heitto voi olla mihin suuntaan tahansa, vaikka kuutosiin. Sinun algoritmisi taas nähdäkseni tuottaa juuri noita kolmosia ja nelosia enemmän, jos skaalaten katsoo.

Vielä kysymys Metabolix:lle. Ajoin koodisi shiftattuna 24:llä. Tyypin long long muutin __int64 typiksi, eikös long long vastaa 64 bittistä lukua?

Mutta sain oheisen tuloksen. Prosentti jakaumat, ja sitä myötä keskihajonta on käsittääkseni tuolla mun randomilla pienempi. Tarvitseeko sitä ryhtyä edes enää vääntämään rautalangasta? Nyt kaikkien pitää vetää hiukan raikasta happea, jotta tämä väittely ohjautuisi nopeasti sellaisien rajojen sisään, että puhutaan suunnileen samasta asiasta :-) Ohessa kuitenkin Metabolix:in koodiajon tulos omalla läppärilläni:

Otos: 16777216

Raja                        rnd()               Randomi()

-1.000 <= x < -0.875:     949045 (5.66%),    1048338 (6.25%)
-0.875 <= x < -0.750:     957975 (5.71%),    1045822 (6.23%)
-0.750 <= x < -0.625:     992125 (5.91%),    1049579 (6.26%)
-0.625 <= x < -0.500:     995748 (5.94%),    1049780 (6.26%)
-0.500 <= x < -0.375:    1019423 (6.08%),    1050100 (6.26%)
-0.375 <= x < -0.250:    1023319 (6.10%),    1047862 (6.25%)
-0.250 <= x < -0.125:    1055219 (6.29%),    1049419 (6.26%)
-0.125 <= x <  0.000:    1053497 (6.28%),    1050106 (6.26%)
 0.000 <= x <  0.125:    1162530 (6.93%),    1048389 (6.25%)
 0.125 <= x <  0.250:    1138052 (6.78%),    1048379 (6.25%)
 0.250 <= x <  0.375:    1129526 (6.73%),    1047543 (6.24%)
 0.375 <= x <  0.500:    1138850 (6.79%),    1048982 (6.25%)
 0.500 <= x <  0.625:    1051063 (6.26%),    1049280 (6.25%)
 0.625 <= x <  0.750:    1052137 (6.27%),    1046998 (6.24%)
 0.750 <= x <  0.875:    1031426 (6.15%),    1048482 (6.25%)
 0.875 <= x <  9.999:    1027281 (6.12%),    1048157 (6.25%)

Nyt en taas aivan ymmärtänyt? Jos heikoimmalla 5,66% ja vahvimmalla 6,93%, eikö se ole epätasaisempi kuin se, että heikoimmalla on 6,24% ja vahvimmalla 6,26%?

Näin puolen tunnin raksutuksen jälkeen sain omat tulokseni hiukka suuremmalle otokselle. Näyttäisivät olevan sinun osaltasi melkein samat eli hieman painottuneet välille (0 - 0,5), kun minun algoritmillani taas tuli kaikkia saman verran. (Um, yksi näyttää kadonneen jonnekin... mikä lie bugi ohjelmassa... :)

Otos: 4294967296 (1 << 32)

Raja                        rnd()               Randomi()

-1.000 <= x < -0.875:  243073035 (5.66%),  268435456 (6.25%)
-0.875 <= x < -0.750:  245557742 (5.72%),  268435456 (6.25%)
-0.750 <= x < -0.625:  253974924 (5.91%),  268435456 (6.25%)
-0.625 <= x < -0.500:  254816218 (5.93%),  268435456 (6.25%)
-0.500 <= x < -0.375:  261078656 (6.08%),  268435456 (6.25%)
-0.375 <= x < -0.250:  261878832 (6.10%),  268435456 (6.25%)
-0.250 <= x < -0.125:  270382998 (6.30%),  268435456 (6.25%)
-0.125 <= x <  0.000:  269759369 (6.28%),  268435456 (6.25%)
 0.000 <= x <  0.125:  297545960 (6.93%),  268435456 (6.25%)
 0.125 <= x <  0.250:  291301471 (6.78%),  268435456 (6.25%)
 0.250 <= x <  0.375:  288530580 (6.72%),  268435456 (6.25%)
 0.375 <= x <  0.500:  291408536 (6.78%),  268435456 (6.25%)
 0.500 <= x <  0.625:  269056675 (6.26%),  268435456 (6.25%)
 0.625 <= x <  0.750:  269531867 (6.28%),  268435456 (6.25%)
 0.750 <= x <  0.875:  264117785 (6.15%),  268435456 (6.25%)
 0.875 <= x <  9.999:  262952649 (6.12%),  268435455 (6.25%)

PS. Sori, että nyt mulla on kovin ajatus sekaisin (eilen oli pikkujoulut, alkoivat perjantaina ja jatkuivat pitkälle lauantaille, jonka vuoksi ajatus takkuilee.)

Mutta Metabolix:in koodin ajoesimerkki siis osoittaa sitä, että itse asiassa Randomi (siis kertolaskun kongruensilla toimiva sellainen) ajautuu nopeasti itseään toistavalle attaktorille. Luvut muodostavat pseudosatunnaisen joukon, jossa jakauma on ok. Sen sijaan rnd() hyppii niin monella attaktorilla, että sen suppeneminen kohti tasaista jakaumaa kannattaa osoittaa keskihajonnalla siten, että joukon hajonnasta otetaan mittausarvo sopivin ajanhetkin. Mutta tuokin on hurjan hyvä testikoodi ilmentämään satunnaislukukuihin liittyviä ominaisuuksia.

Joo, siitä tuo rnd on ehdottomasti kiinnostava. Mutta taidan silti tyytyä omaani, varsinkin nyt, kun se kiertää kaikki mahdolliset arvot läpi. Se on jo saavutus sinänsä :)

Metabolix:lle vielä. Katsoitko esittämäsi Random-funktiota graafisena? Näytöllä Random() nimittäin käy vain joka toisessa pixelissä! Se on kuitenkin jo parempi tulos, kuin ensimmäinen yritys yrittää osoittaa soluautomaattiin tuottama satunnaijoukko huonoksi :)

Nyt en kyllä rupea turhan takia osoittamaan tämän enempää. Jotta asiaa ja attaktoreita kannattaa ruveta syvemmin tutkimaan ja todistelemaan, niin kyllä sen "paremman" randomin pitää ensin osata käydä yksinkertaisesti ruudun jokainen pikseli läpi! :-)

No sehän riippuu siitä, miten sitä käyttää. Minä en koskaan käytä moduloa, ja sitä pidetään aivan yleisesti huonona tapana jo siksikin, että se muuttaa jakaumaa. Oletetaan, että funktio palauttaa arvon [0, 9]. Jos tästä otetaan modulo 7, todennäköisyydet luvuille [0, 2] on 2 ja muille vain 1.

Minä käytän aina tapaa rnd / maksimi * lukualue.

Ja se, tarvitseeko sen käydä niitä kaikkia, riippuu taas koko funktion tarkoituksesta.

Mun mielstä taas satunnaisluvuista pitää pystyä ottamaan modulo siten, että jakauma pysyy ok:na. Kun sitten tarvitaan oikein huippunopeaa moduloa, yleensä se otetaan 2 potenssiin n miinus 1 tasanteilta. Esimerkiksi jokin peli voisi pisteessä X tarvita arpoa seuraava jatko, silloin modulo:

int seuraava_tapaus=rnd()&0x0f;
switch (seuraava_tapaus)
{
...

antaa ainakin nopeampaa koodia, kuin kertolaskujen käyttö. Tosin tuosta aiheesta luin pitkän artikkelin, kuinka nyky-prosessorit ovat kehittyneet niin tehokkaiksi, ettei enää oikeastaan ole väliä, käyttääkö kertolaskua, vaiko jotain yhden kellojakson operaatioita.

Toista aika oli 286:n ja 64:n aikoina. Silloin tehtiin "hirveitä" optimointeja, jotta kertolaskut ja jakolaskut saatiin pyörimään "reaaliajassa".

Varsinkin teillä monella tuntuu olevan rick-prosessoreita alla. Niisä kaiketi kerolaskut singahtaa yhdellä kellojaksolla, kuten useissa DSP-prosessoreissa.

Hyvä niin. Mutta kuitenkin, kun on vähän tarkemmin fundeerannut, niin pitäähän mun osoittaa vertailupohjaksi ihan konkreettisia juttuja, miksi satunnaisluvuilla on yllättävän yksinkertaisissakin jutuissa tosi paljon väliä. Se outo attaktori, kun se on vain yksin, niin se on tosi outo ja salakavala. Luvut näyttävät satunnaisilta, mutta todellisuudessa toistavat itseään, jolloin esimerkiksi MC-ällin (MC = Monte Carlo) tekeminen on mahdotonta, funktio ei siis osaa ratkaista sitä tehtävää, joka sille on määrätty, koska se ei pääse tutkimaan kaikkia mahdollisia ratkaisuja, koska sen satunnaislukugeneraattori toistaa itseään - että sellaisissa yhteyksissä satunnaisluvuilla ja niiden attaktoreilla viimeistään on väliä.

Muistetaanpas nyt, että modulo ja and ovat aivan eri operaatioita. Modulo on huomattavasti kertolaskua hitaampi. (Toisaalta taas se jakolasku on myös hidas...)

Minulle merkittävämpi käyttö tulee olemaan sellainen, jossa tarvitsen tuloksen desimaalilukuna, joten joudun sen jakolaskun tekemään joka tapauksessa. Mahdollisesti saattaisin laittaa vastauksen 23 alinta bittiä jollakin pointterivippaskonstilla suoraan liukulukuun, tuloksena luku väliltä [0, 1].

JoinTuanJanohon kirjoitti:

se ei pääse tutkimaan kaikkia mahdollisia ratkaisuja, koska sen satunnaislukugeneraattori toistaa itseään

Ja tuolla tavalla pääsee? Minun generaattorini, edelleenkin, käy syklinsä aikana läpi kaikki mahdolliset luvut, aivan varmasti. Kaikki vaihtoehdot siis tulevat käydyiksi, ja varmasti nopeammin kuin tuolla toisella. Vai mitä hait takaa? Moduloa taas?

Mä oon vähän ulkona, miten tähän liitettäisiin linkkejä, joita kannattaisi käydä vilkaisemassa. Kun siihen Googleen kirjoittaa hakusanaksi "Monte Carlo", niin pitäisi päästä alkuun.

Ainakin mulla rupesi löytymään seuraavanlaisia linkkejä:

Monte Carlo-simuloinnit / Monte Carlo simulations
Monte Carlo-simuloinnit, 2+2 ov (4+4 op) / Monte Carlo simulations, 2+2 sw (4+4 op)

Esimerkiski tuolla toi 2+2 sw:tä ja 4+4 op:koa antaa vasta perusteet. Mutta kun asiaa sitten harrastaa pitempään, sieltä löytyy hurjan mielenkiintoisia ja käyttökelpoisia asioita.

Niin muuten Hyvä oikaisu! kyllä toki modulo ja and ovat operaatioina eri planeetoilta. Ei se mun yhtäläisyyden veto tosiaankaan kovin kaksinen ollut. Aikakriittisissä jutuissa joskus pitää vain optimoida and:llä, joka unsigned tapauksessa antaa saman tuloksen, kun tarvitaan jotain 2 potenssin n sarjan moduloa.

Jos nyt tulkitsin tuota oikein
http://random.mat.sbg.ac.at/~charly/server/node3.html
niin ANSIC:n mukana oleva satunnailukugeneraattori on muotoa

#define RAND_MAX 0x7fffffff
unsigned int seed = 12345;
int fast_rnd() {
  const unsigned int offset = 12345;
  const unsigned int multiplier = 1103515245;

  seed = seed * multiplier + offset;
  return seed & 0x7fffffff;
}

Tuon pitäisi jo olla kohtuullisen hyvä. Olisi varmaan pitänyt heti etsiä hiukan luotettavamman näköinen lähde eikä tyytyä vain ensimmäiseen linkkiin.

En sano, että tapasi on huono, mutta se ei tuota mielestäni täysin tasaista satunnaisjakaumaa ja toisaalta huonoja satunnaislukuja saa aikaiseksi hiukan nopeammallakin tavalla. Toisaalta monet tunnetut satunnaislukugeneraattorit tuottavat huonoja tuloksia moduluoperaattorien kanssa, joten jos omasi on erityisesti suunniteltu näitä varten, voi se olla oikein hyväkin ratkaisu joihinkin tarkoituksiin.

Mitä tulee tasaiseen satunnaiseen jakaumaan, niin kyllä ainakin itse odotan, että miljardin kolikon heiton jälkeen kolikko on laskeutunut suunnille yhtä monesti kummallekin puolelle. En tietenkään odota, että kumpiakin olisi täsmälleen yhtä paljon, mutta jos jakauma on 52.03% ja 47.97 % niin voidaan jo sanoa, että kolikko on painotettu ja ainakin itse voisin jo alkaa lyömään suuria summia vetoa ensimmäisen luvun puolesta, jos voitosta edelleen maksettaisiin 1/1.

Metabolix kirjoitti:

Ja tuolla tavalla pääsee? Minun generaattorini, edelleenkin, käy syklinsä aikana läpi kaikki mahdolliset luvut, aivan varmasti. Kaikki vaihtoehdot siis tulevat käydyiksi, ja varmasti nopeammin kuin tuolla toisella. Vai mitä hait takaa? Moduloa taas?

Juuri tuo on se salakavala ja suhteellinen käsite. Käykö ja generoiko sykli kaikki mahdolliset kombinaatiot? Siihen ei voi vastata lonkalta. Jos funktio sen tekee, se pitää osoittaa.

Nyt kyllä rupean työllistämään itseäni aika paljon, kun pitää osoittaa, että hyvän satunnaisyklin pitää ensinnäkin lähestyä sitä tasaista jakaumaa, ja nyt lisäksi, että sykli toimittaa kaikki kombinaatiot, joka voidaan osoittaa Monte Carlo teko-ällillä :-)

Huppista. Ehkä asiaa kannattaisi ruveta lähestymään toisenmoisesta näkökulmasta. Keksisiköhän toimitus sellaista teko-älli tehtävää, jonka ratkaisemiseen kertolaskun kongruenssin pseudosatunnaisuus ei riittäisi?

Hmm... Auttakaa muutkin. Fundeerataan porukalla sellainen ongelma, jossa erilaiset satunnaislukugeneraattorit saataisiin paremmuusjärjestykseen. Mitä mieltä olette?

Pitää tunnustaa karvas tappio! FooBat ja Metabolix olivat täysin oikeutetusti huolestuneet jakauman epätasapainosta. Puolustukseksi sanon, että alunperin käytin funktiossa unsigned tyyppiä. Kääntäjän tekee unsigned-tyypillä loogisen siirron, kun taas signed tyypillä se generoi aritmeettisen siirron. Eli siis bittisiirrossa oikealle toimitetaan etumerkkibitin kopiointia tyhjiksi jääville biteille.

Jakauman on, kuten Metabolix totesi, lähestyttävä rajatta yhtäsuuruutta. Oheinen testikoodi tulostaa sitten jakauman keskihajonnan keskiarvon suppenemista, ja se suppenee alati arvoon 1.0000..., niin kuin pitääkin. Jos ajatte tuota testiä, niin siitä ilmenee, että joka askeleella jakauman keskihajonta on parempi ja parempi.

Tosi isot kiitokset FooBat:lle ja Metabolix:lle virheellisyyden osoittamisesta. Jep, kun rnd-funktion siemenluvut muuttaa unsigned-tyyppisiksi, niin bittisiirrot eivät painota enää painota etumerkillisyyttä.

#include <stdio.h>
#include <math.h>
#include <conio.h>

int rnd(void)
{
   static unsigned long r1=1L; /* voi olla mikä tahansa alkuarvo */
   static unsigned long r2=2L; /* voi olla mikä tahansa alkuarvo */
   r1 -= 0x012357bfL; /* 16 bittiä sisältävä alkuluku */
   r2 += 0xfedca201L; /* 16 bittiä sisältävä alkuluku */
   r1 += (r1>>16)^(r2<<16); /* sekoitetaan */
   r2 -= (r1<<16)^(r2>>16); /* sekoitetaan */
   return (int)(r1^r2); /* kerran vielä kiellon päälle */
}

void main(void)
{
   long tulostaTilanne=0;
   double tapaus[2]={0, 0};
   double tapaustenLkm=0.0;
   double tamaPitaisiSupetaArvoon1=0.0;
   double tamaPitaisiSupetaArvoon1Lkm=0.0;

   for (;;)
   {
      tapaus[rnd()&1]+=1.0;
      tapaustenLkm+=1.0;

      if ((++tulostaTilanne)>=(1L<<28))
      {
         double tilanneTapaus0=tapaus[0]/tapaustenLkm;
         double tilanneTapaus1=tapaus[1]/tapaustenLkm;
         double keskiArvo=(tilanneTapaus0+tilanneTapaus1)/2.0;

         double hajonta_0_nelio=pow(tapaus[0]-keskiArvo, 2);
         double hajonta_1_nelio=pow(tapaus[1]-keskiArvo, 2);

         double suhde_joka_tarttis_supeta=hajonta_1_nelio/hajonta_0_nelio;

         tamaPitaisiSupetaArvoon1+=suhde_joka_tarttis_supeta;
         tamaPitaisiSupetaArvoon1Lkm+=1.0;

         double tulosta=tamaPitaisiSupetaArvoon1/tamaPitaisiSupetaArvoon1Lkm;

         printf("%25.20f\n", tulosta);
         tulostaTilanne=0;

         if (kbhit())
         {
            if ((char)getch()=='q') break;
         }
      }
   }
}

Nyt näyttää ehdottomasti paremmalta.

Niin ja yllä on kyllä mainio esimerkki muuttujien havainnollisesta nimeämisestä :P

No himpskatti, kun pitää sekoilla, en ottana copy-pastea siitä valmiista mainista: tietenkin neliöön korotus parametreillä:

double hajonta_0_nelio=pow(tilanneTapaus0-keskiArvo, 2);
double hajonta_1_nelio=pow(tilanneTapaus1-keskiArvo, 2);

... mutta varmaan huomasitte jo itekin...Pitää päivittää bugin korjaus myös sinne esimerkkiin.

Nyt se näyttää toimivan tosiaan huomattavasti paremmin. Oma pätevyyteni ei riitä sanomaan kuinka hyvä se todellisuudessa on, mutta aivan riittävän hyvä kaikkeen itseni tarvitsemaan.

Tietenkin joku voisi kirjoittaa siitä perustavaa laatua olevan analyysin ja vertailla sitä muihin tunnettuihin satunnaislukugeneraattoreihin. Voisin jopa lukaista tuollaisen läpi; tämä vaikuttaa ihan mielenkiintoiselta tavalta. Olikos tällä tavalle kirjallisuudessa jotain tunnettua nimeä?

Onpas mielenkiintoista keskustelua :P Itse en ole tutustunut satunnaislukuihin ollenkaan, joten mielipiteeni on luultavasti aivan väärä ja kaikkea muuta, mutta esitän sen silti :)
Eli jos esim. heitetään kolikkoa on jokaisella heitolla 50% mahdollisuus, että saadaan klaava(tai kruuna). Joten eikö todellinen ihannne random olisi periaatteessa sellainen, että se voisi antaa vaikka 10 kertaa peräkkäin saman luvun. Tarkoitan siis, että eikö se vastaisi enemmän satunaislukuja kuin sellainen, joka antaa joka kerta eri luvun. En tarkoita, että tämä olisi missään peleissä hyvä juttu (Ei olisi kivaa jos matopelissä omena tulisi 10 kertaa samaan paikkaan). No mutta mitä minä tietämättömänä tulen tänne sanomaan xD. No mielenkiintoista on seurata keskustelua tuollaisten huippu koodareiden välillä(*povistuu ihailusta*) )

Mazuli kirjoitti:

Eli jos esim. heitetään kolikkoa on jokaisella heitolla 50% mahdollisuus, että saadaan klaava(tai kruuna). Joten eikö todellinen ihannne random olisi periaatteessa sellainen, että se voisi antaa vaikka 10 kertaa peräkkäin saman luvun. Tarkoitan siis, että eikö se vastaisi enemmän satunaislukuja kuin sellainen, joka antaa joka kerta eri luvun. En tarkoita, että tämä olisi missään peleissä hyvä juttu (Ei olisi kivaa jos matopelissä omena tulisi 10 kertaa samaan paikkaan). No mutta mitä minä tietämättömänä tulen tänne sanomaan xD. No mielenkiintoista on seurata keskustelua tuollaisten huippu koodareiden välillä(*povistuu ihailusta*) )

Se, että satunnailukugeneraattori antaa vuorotellen jomman kumman luvun ei tosiaa ole hyvää satunnaisuutta, se ei ole oikeasti satunnaisuutta ollenkaan, koska se on ennalta arvattavissa. Tästä ei taidettu edellä edes puhua. Hyvä satunnaislukugeneraattori on sellainen, joka antaa kaikille vaihtoehdoille yhtäsuuren todennäköisyyden riippumatta edellisistä satunnaisluvuista. Tämä ei tietenkään täysin ole asianlaita pseudosatunnaislukugeneraattoreissa, mutta melko hyviin tuloksiin päästään.

Se että suuren heittomäärän jälkeen voidaan olettaa, että molempia tuloksia on suunnilleen yhtä paljon johtuu siitä, että vaikka esim. klaavaa voi tulla 10 kertaa peräkkäin, on myös yhtä suuri todennäköisyys, että kruuna tulee 10 kertaa peräkkäin. Pitkässä juoksussa molempien tuloksien sarjoja on TODENNÄKÖISESTI suunnilleen yhtä paljon ja hyvän satunnaislukugeneraattorin antamien tuloksien jakaumien pitäisi lähestyä oikeita todennäköisyyksiä. Jos näin ei käy, ei satunnaislukugeneraattori ole täysin satunnainen.

Mazuli päättelee ihan oikein. Jos satunnaissykli toimii hyvin (imitoi luontoa), teoriassa voidaan laskea kohtalaisen tarkasti todennäköisyys, koska sykli toimittaa esimerkiksi peräkkäin tasan 273 kertaa kruunun.

Pitää vain laskea yhteen (tässä tapauksessa helppo, kun voi hyödyntää kahden potenssia): 2⁰+2¹+2², ... +2²⁷³ = likimain 10⁸²

Eli siis jos mööpeli generoisi satamiljoonaa satunnaislukua sekunnissa, 273 kertaa kruunun toistavaa kannattaisi ruveta potentiaalisesti tähyilemään vasta joskus 10⁷⁵ vuoden kuluttua!

Tuo on kyllä niin käsittämätön luku verrattuna vaikka siihen, että kuinka monta atomia tarvitaan, että ne täyttäisivät koko Universumin tilan sellaisella atomitiiveydellä, jollainen esimerkiksi vallitsee pulsareissa.

Tähtitiedettä enemmän harrastanut osaisi kyllä varmasti sanoa tuon luvun koosta paremman vertauksen.

Mitähän nyt laskitkaan yhteen? Kun ainakin kahden peräkkäisen todennäköisyys on 1/4 ja kolmen peräkkäisen 1/8 jne, niin eiköhän tuokin mene samalla kaavalla, eli ihan vain 1/2 potenssiin 273. Koska on olemassa 2^273 mahdollisuutta, kuinka niin monella heitolla käy, ja vain yksi niistä on haluttu. Se sitten, missä vaiheessa tuollainen tulee, on aivan eri asia, ja siitäkin voidaan keskustella, pitääkö koneen arpoa kokonaisia syklejä kerralla vai voiko syklin aloittaa mistä tahansa kohdasta arvottua heittosarjaa? Kelpaako, jos ensin tulee yksi klaava ja sitten 273 kruunaa, vai pitääkö sen yhden klaavan jälkeen odottaa, että kaikki 273 heittoa on heitetty, ja vasta sitten aloittaa uusi laskenta?

Mahdollisia sarjoja oli nyt kuitenkin siis suunnilleen 1,5 * 10^82. Vertailukohteena, että maailmankaikkeudessa on arvioitu olevan suunnilleen 10^80 atomia (käsittääkseni).

Tarkkuutta Metabolix, tarkkuutta :-) Laskin yhteen juuri sen, jonka sinä laskit käänteisluvuksi: Eli minun sarjani on yhtä kuin sinun sarjasi käänteisluku! Sinun lukusi exsponentti on negatiivinen, joka siis 10:n potenssina tarkoittaa 1/se himputin suuri jakaja.

Ja vielä rautalankamallina: 10⁸² on likimain 1/(0.5²⁷³). Luvut tosin ovat nyt niin suuria, että sinun kaavasi antaa suunnilleen saman tuloksen kuin minun kaavanikin, vaikka et kaavassasi huomioinut lainkaan 273:n alikombinaatioita :-)

Jees, tämä ei ole matematiikkasaitti, vaikka matematiikka ja ohjelmointi käyvätkin niin perin käsikkäin. Itselleni on ainakin selviö, että ainakin minua kiinnostavissa asioissa, joitta tietokoneella harrastan, matematiikka on vähintään yhtä vahva, kuin algoritmien kirjoittaminenkin.

Siis 1/se himputin PIENI jakaja.

Selitäpä vielä, mitä minä en huomioinut? (Alikombinaatioita..?) En vain millään ilveellä keksi lausekkeellesi (2⁰+2¹+2², ..., +2²⁷³) mitään perustelua tässä tehtävässä. Minusta se todennäköisyys on tasan 1/2²⁷³ eikä mitään muuta, kuten yhdellä "peräkkäisellä" tasan 1/2¹ = 1/2 eikä mitään muuta. Ei ainakaan 1/(2⁰+2¹) = 1/3.

Ja kyllä, jonkin tasoinen matematiikka on ehdottomasti välttämätöntä kunnon ohjelmoinnissa :)

Tarkkuuta JoinTuanJanohon, tarkkuutta :)

Kyllä minunkin laskuoppini mukaan todennäköisyys heittää 273 kertaa sama peräkkäin on juuri tuo 1/2^273 eikä 1 / (2^0 + 2^1 + .. + 2^273 = 2^274 - 1). Tuossahan annat asialle ainoastaan puolet oikeasta todennäköisyydestä.

Terve vielä FooBat ja Metabolix. Sen verran tuossa aloin väittämäänne avaamaan, että olette nyt kumpikin hakoteillä. Mutta ihan totta, mulla on aamulla aikainen herätys, ja mun pitää vääntää teille tuo rautalankamalli ensiviikon iltoina.

Noin alustavasti, mun lähtökohtaha on tietenkin se, että jos tutkitaan esimerkiksi 1-4 bittisiä kombinaatioita, niin ihan takuulla pitää ensin arpoa, tuleeko tilastoon seuraavaksi 1, 2, 3, vai 4 bittinen kombinaatio.

Ellei tällaista olettamusta tehdä, silloin satunnaisyklistä nimenomaan ruvetaan pollaamaan esimerkiksi tarkalleen juuri sitä n-bittistä lukua, joka voi olla mitä tanahsa väliltä 0-2ⁿ-1.

Mutta eihän satunnaissyklissä ole tarkoitus fokusoitua mihinkään tarkalleen n-bittiseen lukuun, vai pitääkö? Jos satunnaissyklejä todella analysoidaan sellaisella ontuvalla logiikalla, niin kuka tai mikä oopus sellaista "korkeampaa" matematiikkaa sitten opettaa.

Voi voi, kun menee työlääksi. Mutta menkööt :-D Osoitan teille tasan yhden kerran rautalankamallin, miten satunnaissyklin minkä tahansa n-bittisen kombinaatio lasketaan käytännössä ja miten se sitten vastaa tuota teoreettista arvoa, joka tässä tapauksessa saadaan yksinkertaisesti sarjan 2ⁿ summasta. Perästä sitten kuuluu :-)

Niin vielä yksi juttu tuli mieleen. Toi on nyt hirveen oleellista, tutkitaanko tasan n-bittistä satunnaislukua, vai lukua, joka on välillä [1, n] bittiä (siis suljetulla 1-n välillä).

Nimittäin silloin, jos höyläpenkkiin alias tietokoneeseen tehdään algoritmi tutkimaan tasan n-bittisen satunnaisluvun jakaumaa, niin se on paljon erisuuri, kuin se, että mööpeliin kirjoitetaan algoritmi tutkimaan kaikkia mahdollisia 1-n bittisiä kombinaatioita.

Tässä nyt jälleen on ilmeisesti pieni kuilu siinä, mistä kukin todella takaa ajaa. Ei siinä ole mitään kyseenalaistamista, että jos noppaa paiskitaan, niin jokaisen silmäluvun todennäköisyys on likimain 1/6.

Mutta entä sitten, kun hattuun laitetaan 1, 2, 3, 4, 5, ja 6 silmäiset nopat? Tottakai 1 silmäinen noppa on aivan pöljä ja triviaali, mutta siis periaatteessa noin.

Ooteko yhä sitä mieltä, että puhutaan samasta asiasta, ja että todennäköisyys nopille, joita hattuun on laitettu 273, ja joissa jokaisessa nopassa on erilainen silmäluku, että se olisi sama asia kuin että hatussa olisi 273 silmäluvultaan samansuuruista noppaa?

Haluaisin nyt vielä tarkentaa tuota edellistä viestiäni :P

Kun te olette noita keskihajontaa ynnä muita tutkineet, niin eikö hyvä random funktion keskihajonta, joskus poikkea normaalista(tai jotenkin noin). Eli jos ajatetaan vaikka funktio 1000x1 000 000 kertaa niin eikö jollain kerralla keskihajonnan tulisi olla painottunut johonkin. Tai no joo ehkä tuo pitäisi tehdä 1 000 000x1 000 000 kertaa, mutta periaatteessa. Eli ei painottuminen ole aina paha juttu jos ajatellaan ns. oikeaa randomia. Edelleenki tämä on minun mielipiteeni ja olen luultavammin väärässä xD

Miljoona toistoa on jo niin paljon, että itse odottaisin jakaumien olevan aika lähellä oikeita todennäköisyyksiä, mutta pieniä vaihteluja sarjojen välillä tietenkin esiintyy.

Jos taas olisit puhut 100 toiston sarjoista, niin hajonta olisi paljon suurenpaa. Ei olisi suuri yllätys, jos jossakin sarjassa jakauma olisi 70/30, jos testattavia sarjoja vain olisi tarpeeksi paljon.

Riippuu ihan siitä miten kysymyksen asettelee. Kysymykseen "Mikä on todennäköisyys, että 273 kertaa peräkkäin heitetty kolikko laskeutuu aina kruunaksi?" vastaus on 1/2^273. Toinen kysymys on "Kuinka monta kertaa kolikkoa pitää heittää, että heittojen aikana kolikko on ainakin kerran laskeutunut 273 kertaa peräkkäin kruunaksi?". Tähän kysymykseen ei ole vastausta ellei kysymykseen liitetä mukaan tapahtuman todennäköisyyttä. Eli "Kuinka monta kertaa kolikkoa pitää heittää, että 50% varmuudella heittojen aikana kolikko on ainakin kerran laskeutunut 273 kertaa peräkkäin kruunaksi?". Tähän kysymykseen on vastaus, mutta jätän sen harjoitustehtäväksi.

Jotenkin tuntuu, että JoinTuonJanohon onnistuu hyvin lahjakkaasti muuttamaan yksinkertaisen asian monimutkaisemmaksi kuin se oikeasti on ja vielä tätä tehdessä kadottaa itse sen punaisen langan, jolla asiansa perustelee itselleen. Jos pitäisi arvata, niin sä olet varmaan jonkun pääkaupunkiseudun yliopiston matematiikan professori :)

Vielä kerran FooBat:lle. Tekisi mieli jo pikkuhiljaa haistattaa, mutta se ei ole näitten asialliseen keskusteluun tarkoitettujen saittien tarkoitus. Sulle voin sanoa, että mun oikea ammatti on levy-seppä, josta oon vielä ylpeäkin. Matematiikkaa ja algoritmeja olen harrastanut silkasta mielenkiinnosta. Professoreista sen verran, että muutaman oon väitellyt maan rakoon. Ei siinä kuule enää koulutusta paljon kaivata, jos asiat on ite selvittäny kantapäänkautta. Toisekseen sitten oon ansainnut mieliammattini ihan niillä konkreettisilla jutuilla, joita oon elämäni värkännyt. Sieltä löytyy shakkia, näköaistin mallinnusta (tein muuten ihan A:sta Ö:hön kirjaston analyyttisen avaruusgeometrian pyörittämiseen. Helppoa se ei ollu, koska en vielä silloin osannut kunnolla laskea, sitten laskin muutaman vuoden yötä päivää, ja algebra alkoi taipumaan, lopulta niin hyvin, että mä pystyin sen geometrian kirjaston vääntämään). Ja vielä ihan noin vinkiksi, niin kyllä noista sun argumenteista paistaa sellainen tietynlainen kateus, jotenkin sitä vain semmone mielikuva jää. Näiltä saiteilta minä löydän kaltaisiani, joiden kanssa samoista jutuista mielipiteitä voi vaihtaa, ja vielä parempi, jos vielä pystyy jotain auttamaan, ja tietenkin se, että näiltä sivuilta saa korvaamatonta apua omiin ohjelmointiin, algoritmeihin ja matematiikkaan liittyviin kysymyksiin.

Jäikö sulle vielä jotain epäselväksi? Toivottavasti ei, koska mä en jaksa enää sun heikkoihin perusteluihin ruveta syventymään, ja yrittää avartaa sun tietotaitoa.

En nyt lukenut ihan tarkasti tätä keskustelua enkä ole ihan varma tuliko jo puheeksi, mutta kiintoisaa luettavaa kuitenkin oli. Joten eikös se loogisen todennäköisyyden mukaan mene niin että jos esim. heitetään vaikka kolikkoa 6 kertaa peräkkäin niin:

                            1. kerta
                           /        \
2. kerta         kruuna(50%)         klaava(50%)
                /          \        /          \
      kruuna(25%)    klaava(75%) kruuna(75%) klaava(25%)
     /          \   /          \/          \ /        \
3. kerta       jne.. jne.. jne..

Eli tässä hain sitä että millaisella todennäköisyydellä sama luku tulisi uudelleen toisen kerran peräkkäin.

Terem, ma en nyt muista sitä termiä, se oli joku kuitenki satunnaisilmiöihin liittyvä "tapahtumien riippumattomuus". Sen perusteella jokaine kolikon heitto jokaisen edellisen kolikon heiton jälkeen olisi riippumaton edellisten heittojen tuloksista. Silloin jokaisen kolikon heiton jälkeen olis yhtä suuri todennäköisyys tulla kruuna tai klaava, olipa edellinen tulos sitten klaava tahi kruuna.

Mun mielestä ainakin tuossa suhteessa tilastomatematiikkaa kannattaa kyseenalaistaa. BruteForceilla noita juttuja voi kokeilla käytännössä, ja sitten verrata tuloksia laskennallisesti saatuihin arvoihin.

Toi kolikkoesimerkki on kyllä jo sinällään niin turtunut esimerkki, kait siihen liittyviä juttuja on fundeerattu jo silloin, kun vielä käytettiin oravannahkoja käypänä valuuttana.

Karskit luolamiehet sitten raapustelivat luolan seiniin erimoisia todennäköisyyksiä, että kummin päin se oravannahka maaha tippuu, kun sen ensin Telluksen pinnalta ylempään sfääriin, ja mitä sitten tapahtuu, kun sen nahan antaa vapaasti pudota.

Tiedä häntä, mun mielestä noissa satunnaisilmiöissä jonkin verran vähemmän kuluneita aiheita on semmoiset suoraan luontoon liittyvät satunnaisilmiöt, ja niiden halinta ja pukeminen funktionaaliseen formaattiin.

Niin, eihän loppujen lopuksi mikään ole sattumaa. Kaikki on laskettavissa, mutta kuitenkin sellaisilla kaavoilla joita on käytännössä mahdoton luoda.

Esim. kolikon heitossa ratkaisuun saatta vaikuttaa kaukaisen tähden gravitaatio kenttä, pölyhiukkasen törmäys ilmassa, ilmavirrat jne...

Yhdessä nämä tekijät vaikuttavat siihen, kumminpäin kolikko tulee.

:-) FooBat :-) Jätit mulle näemmä numeerisen harjoitustehtävän :-) Himpskatti, jos olisin lukenut tuon tarkemmin, niin olisi tullut tosi hauskaa!

Laskepa ensin neliöjuuri 2 niin monella merkitsevällä numerolla kuin haluat. Sen jälkeen laitan sinulle A4:n, joka laskee siihen miljoona merkitsevää numeroa lisää käden käänteessä. Ihan tosissani olen. Kiinteällä pilkulla, tai millä tahansa kannalla.

Sori nyt, kun sulle noin pienestä aloin sättimään. Tuli meinaan huidsin hilpeä olo tuosta "jättämästäsi kotitehtävästä" :-)