kans op herhaling in willekeurige rij

xansid

stel ik heb een rij met n = 100 willekeurige worpen van een z = 6 zijdige dobbelsteen
hoe groot is de kans dat in deze rij een reeks bestaat met een lengte l = 5 die verderop in de rij nog een keer voorkomt?

xansid

De kans dat ik een specifieke reeks van 5 getallen gooi is

\(\frac{1}{6}^5\)

. Ik gooi in principe 95 keer een reeks van 5 dus is de kans dat ik een specifieke reeks gooi

\(\frac{1}{6}^5*95\)

.
Verder kom ik eerlijk gezegd niet...

xansid

Misschien heb ik de oplossing al:
De reeks die ik in de eerste 5 worpen gooi heeft daarna een kans van

\(90*\frac{1}{6}^5\)

om nogmaals gegooid te worden.
De reeks die ik gooi in worp 2 t/m 6 kan ik nog 89 maal proberen om te gooien, die van 3 t/m 7 nog 88 maal.
Is het dan

\(90!* (\frac{1}{6}^5)^{90}\)

?

Back2Basics

Wat is een 'reeks' bij jou? Een reeks met lengte l, en daarna begint een nieuwe reeks met die lengte? Dat kan ik niet goed terugvinden in je post.
Ik had de indruk dat je in je OP een rij met 100 uitkomsten van 1 tot 6 had, en dan ging kijken of bijvoorbeeld uitkomsten 3-7 nog ergens in je rij voorkomen.

xansid

Ja dat bedoel ik inderdaad. Wat is de kans dat er in een rij met 100 willekeurige uitkomsten twee keer dezelfde reeks van 5 opeenvolgende getallen voorkomt. En het maakt niet uit welke 5 het zijn.

xansid

Mijn antwoord in bericht #3 kan niet kloppen. Ik heb ergens vermenigvuldigd waar ik moet optellen. Ik kom nu uit op

\(\frac{1}{6}^5 * \sum\limits_{i=1}^{90} i \approx 0.52\)

Dus in iets meer dan de helft van de gevallen zou ik in een dubbele reeks van 5 moeten aantreffen. Dit zou wel kunnen kloppen, maar ik ben nog niet helemaal zeker van de juistheid van mijn aanpak.

Back2Basics

Je antwoord zal in deze soortgelijke draad staan:
http://www.wetenschapsforum.nl/index.php/topic/13907-kansberekening/

EvilBro

Jouw methode lijkt me niet correct. Ik heb in Octave de volgende functie geschreven die 100 worpen aanmaakt en dan kijkt of er een volgorde van 5 waarden meer dan 1x voorkomt. Dit is in ongeveer 40% van de aanroepen het geval (en ik heb dit al pakweg 10000 keer gedaan).
Ik zie nog niet direct hoe je dit exact berekent, maar misschien schiet mij later nog iets te binnen...

Code: Selecteer alles

function [retval] = hasDuplicate ()
  N = 100;
  L = 5;
  r = floor(6 * rand(1, N));
  for j = 1 : (N - L), 
    dummy = r(1, j : (j + L - 1));
    for i = (j + 1) : (N + 1 - L),
      dummy2 = r(1, i : (i + L - 1));
      if (sum(dummy == dummy2) == L),
        retval = 1;
        return;
      end
    end
  end
  retval = 0;
endfunction

xansid

dat is een mooiere code dan dat ik zou schrijven! Ik heb je code gechecked en 10duizend maal uitgevoerd en kom natuurlijk ook rond 40 procent uit.

Maar nu testen wij of er in een rij minstens 1 keer een herhaling plaats vind. En volgens mij heb ik berekend dat het gemiddeld 0.52 keer per rij voor komt.

Een test op de computer geeft aan dat er gemiddeld 0.59 reeksen van 5 in een rij van 100 voorkomt. Dat komt iets dichter in de buurt.
Waar ik geen rekening mee heb gehouden is dat als je al weet dat er een reeks is van 5 getallen die overeenkomt dan is er meer kans dat het 6e getal ook overeenkomt. Die reeks van 6 telt dan als 2 keer 5. Nu heb ik wel iets meer inzicht in het probleem dan ik eerst had, en dus weet ik beter wat ik echt wil weten.

Wat ik eigenlijk echt wil weten zijn 2 vraagstukken:
1) In een rij van N getallen wat is de kans dat de LANGSTE reeks lengte L heeft

2) Hoeveel reeksen van precies lengte L kan ik verwachten in een rij van N getallen

EvilBro

Ik denk dat ik niet helemaal snap wat jij nu wil weten.

Wat ik eigenlijk echt wil weten zijn 2 vraagstukken:
1) In een rij van N getallen wat is de kans dat de LANGSTE reeks lengte L heeft

Wat bedoel je hier met de langste reeks? Bedoel je de langste reeks die zich herhaald in de rij?

xansid

Oh ja stom, ik moet er beter op letten om duidelijk te zijn. Daar had moeten staan:

1) In een rij van N getallen wat is de kans dat de langste herhalende reeks lengte L heeft

2) Hoeveel zichzelf herhalende reeksen van precies lengte L kan ik verwachten in een rij van N getallen

Het gaat er om dat ik straks hopelijk in staat ben aan te tonen dat een reeks niet willekeurig is omdat dit soort herhalende reeksen vaak voorkomen.

xansid

Ik had in het begin de mogelijkheid van overlappen over het hoofd gezien, de reeks [2 3 2 3 2 3 2 3] bijvoorbeeld. Deze wil ik niet meerekenen dus heb ik de code aangepast zodat overlappers niet worden meegerekend. Nu lijkt mijn formule wel ongeveer te kloppen, met:
N = aantal worpen
L = reekslengte
Z = aantal zijden dobbelsteen
E = verwachtte waarde van het aantal herhalende reeksen

\(E = \frac{1}{Z}^L * \sum\limits_{i=1}^{N-2*L+1} i \)

Ik heb telkens 10000 maal gesimuleerd

Code: Selecteer alles

N = 100 , Z = 6
L | Formule  | Computer
--|----------|---------
3 | 21.1     | 21.2
4 |  3.37    |  3.35
5 |  0.538   |  0.539
6 |  0.0858  |  0.0907
7 |  0.0137  |  0.0129

EvilBro

1) In een rij van N getallen wat is de kans dat de langste herhalende reeks lengte L heeft

Ik heb hier voor N=100 gekozen. Ik heb de volgende code 10000 keer gerund. Hierbij vind ik voor de verdeling van de lengte van de langste herhalende reeks:
3: 0.0566
4: 0.5804
5: 0.2962
6: 0.0555
7: 0.0098
8: 0.0014
9: 0.0001

Code: Selecteer alles

function [retval] = findL()
  N = 100;
  r = floor(6 * rand(1, N));
  retval = 3;
  for L = 4 : 50,
    if scan(r, L),
      retval = L;
    else
      return;
    end
  end
endfunction
function [a] = scan(r, L)
    N = length(r);
    for j = 1 : (N - (2 * L) + 1), 
      dummy = r(1, j : (j + L - 1));
      for i = (j + L) : (N + 1 - L),
        dummy2 = r(1, i : (i + L - 1));
        if (sum(dummy == dummy2) == L),
          a = 1;
          return;
        end
      end
    end
    a = 0;
endfunction

Wetenschapsforum

Laatste berichten

Nieuwsberichten

kans op herhaling in willekeurige rij

kans op herhaling in willekeurige rij

Re: kans op herhaling in willekeurige rij

Re: kans op herhaling in willekeurige rij

Re: kans op herhaling in willekeurige rij

Re: kans op herhaling in willekeurige rij

Re: kans op herhaling in willekeurige rij

Re: kans op herhaling in willekeurige rij

Re: kans op herhaling in willekeurige rij

Re: kans op herhaling in willekeurige rij

Re: kans op herhaling in willekeurige rij

Re: kans op herhaling in willekeurige rij

Re: kans op herhaling in willekeurige rij

Re: kans op herhaling in willekeurige rij