Kombinatorik für Fortgeschrittene?

Offtopic wär' nicht schlecht gewesen.
Oder einfach im Unterricht zuhören.

blablub schrieb:
> Jedoch habe ich experimentell eine Wahrscheinlichkeit von 25% bestimmt ...

Zeigt doch bitte dein Experiment.

Ah ja und was hat das mit Kombinatorik zu tun?
Und dann noch "fortgeschritten", du bist mir ja ein lustiger.

Martin Schwaikert schrieb:
> Mit zurücklegen liegt die Chance beide male bei 1:64, also 1:(64*64),
> ohne Zurücklegen bei 1:64*1:63. Wahrscheinlichkeiten werden
> multipliziert.

Martin Schwaikert schrieb:
> Mit oder ohne zurücklegen?
>
> Mit zurücklegen liegt die Chance beide male bei 1:64, also 1:(64*64),
> ohne Zurücklegen bei 1:64*1:63. Wahrscheinlichkeiten werden
> multipliziert.

Noch einmal die Aufgabe lesen.

Martin Schwaikert schrieb:
> Mit oder ohne zurücklegen?
>
> Mit zurücklegen liegt die Chance beide male bei 1:64, also 1:(64*64),
> ohne Zurücklegen bei 1:64*1:63. Wahrscheinlichkeiten werden
> multipliziert.

Es wird quasi auf einmal eine zufällige Anzahl entnommen. Daher nicht 
eine Binominalverteilung, sondern viele...

Jürgen schrieb:
> blablub schrieb:
>> Jedoch habe ich experimentell eine Wahrscheinlichkeit von 25% bestimmt ...
>
> Zeigt doch bitte dein Experiment.

also im pseudocode:

while(lange)
{
uint64 a = rand64();
if (2bestimmte bits gesetzt)
  good++;
else
  bad++;
}

good/(bad+good) = 25%;


Electronics'nStuff schrieb:
> Ah ja und was hat das mit Kombinatorik zu tun?
> Und dann noch "fortgeschritten", du bist mir ja ein lustiger.

ah ja und deine Lösung?

blablub schrieb:
> ah ja und deine Lösung?

Oh, ich entschuldige mich. Habe das auch so verstanden wie Martin.

be stucki schrieb:
> bei unendlich vielen
> Durchgängen

Ich glaube da liegt der Fehler, er spricht (soweit ich das verstanden 
habe) von einem einzelnen Durchgang.

Und abgesehen davon, wird die Wahrscheinlichkeit nicht als Prozentzahl 
anzugeben sein, sondern im Verhältnis zu Anzahl gezogener Kugeln X nehme 
ich an?

Weil sonst ist das ja irgendwie nicht möglich.

Also sowas wie X * 0.1347%

blablub schrieb:
> Anmerkung:
> Eigentlich erwarte ich eine recht niedrige Wahrscheinlichkeit. Jedoch
> habe ich experimentell eine Wahrscheinlichkeit von 25% bestimmt und
> wundere mich über die Herkunft dieses hohen Wertes...

Ich wäre extrem erstaunt wenn 25% die Lösung ist!
Da scheint das Experiment wohl nicht ganz mit der Aufgabenstellung zu 
korrelieren;-)

blablub schrieb:
> also im pseudocode:
>
> while(lange)
> {
> uint64 a = rand64();
> if (2bestimmte bits gesetzt)
>   good++;
> else
>   bad++;
> }
>
> good/(bad+good) = 25%;

Dass da 25% rauskommt, ist ja kein Wunder. Für die zwei Bits gibt es 
vier Möglichkeiten:
0 und 0
0 und 1
1 und 0
1 und 1 <- der Fall wird gezählt.

Alle vier Fälle sind gleich wahrscheinlich => 25% Wahrscheinlichkeit.

Das ist aber erstmal nicht die korrekte Simulation für die 
Fragestellung. Du müsstest erst mal eine zufällige Zahl zwischen 1 und 
64 generieren und dann entsprechend viele zufällige Bits auf 1 setzen. 
Danach kannst Du schauen, ob die beiden ersten Bits gesetzt sind.

Könnte aber gut sein, dass am Ende (fast) das gleiche rauskommt, weil ja 
im Schnitt 32,5 Kugeln gezogen werden (Bits gesetzt sind). Wenn man auch 
0 Kugeln ziehen könnte, wärens im Schnitt 32 Bits, also wie oben. Bin 
mir aber nicht 100% sicher, ob das man das so rechnen darf.

@xfr

bingo, das ist die Lösung. In der Zwischenzeit wurde ich schon von 
Kollegen ausgelacht, dass ich nicht draufgekommen bin, da es ja so 
"eindeutig" ist :)

Grund für die Eindeutigkeit ist die Gleichverteilung aller Bits

xfr schrieb:
> Das ist aber erstmal nicht die korrekte Simulation für die
> Fragestellung. Du müsstest erst mal eine zufällige Zahl zwischen 1 und
> 64 generieren und dann entsprechend viele zufällige Bits auf 1 setzen.
> Danach kannst Du schauen, ob die beiden ersten Bits gesetzt sind.

inwieweit würde sich das vom pseudocode unterscheiden?

xfr schrieb:
> Das ist aber erstmal nicht die korrekte Simulation für die
> Fragestellung. Du müsstest erst mal eine zufällige Zahl zwischen 1 und
> 64 generieren und dann entsprechend viele zufällige Bits auf 1 setzen.
> Danach kannst Du schauen, ob die beiden ersten Bits gesetzt sind.

So isses. Die Anzahl/Wahrscheinlichkeit der gesetzten Bits entspricht 
bei seinem Experiment nicht der Aufgabenstellung.


> Könnte aber gut sein, dass am Ende (fast) das gleiche rauskommt, weil ja
> im Schnitt 32,5 Kugeln gezogen werden (Bits gesetzt sind). Wenn man auch
> 0 Kugeln ziehen könnte, wärens im Schnitt 32 Bits, also wie oben. Bin
> mir aber nicht 100% sicher, ob das man das so rechnen darf.

Das Ergebnis ist signifikant anders;-)

blablub schrieb:
> Aus einer Urne mit 64 durchnummerierten Kugeln werden eine zufällige
> Anzahl an Kugeln gezogen

Wenn du zufälligerweise immer 64 Kugeln ziehen musst, liegt die 
Wahrscheinlichkeit bei 1.

Mal im Ernst, die Angabe zufällige Anzahl Kugeln ziehen" ist Mist. Das 
macht den Zufall nicht wahrscheinlicher.

http://de.wikipedia.org/wiki/Geburtstagsparadoxon

Floh schrieb:
> blablub schrieb:
>> Aus einer Urne mit 64 durchnummerierten Kugeln werden eine zufällige
>> Anzahl an Kugeln gezogen
>
> Wenn du zufälligerweise immer 64 Kugeln ziehen musst, liegt die
> Wahrscheinlichkeit bei 1.

??? ja ich könnte auch immer im Lotto richtig tippen...

>
> Mal im Ernst, die Angabe zufällige Anzahl Kugeln ziehen" ist Mist. Das
> macht den Zufall nicht wahrscheinlicher.

ja genau da lag auch mein Denkfehler.

Floh schrieb:
> Mal im Ernst, die Angabe zufällige Anzahl Kugeln ziehen" ist Mist. Das
> macht den Zufall nicht wahrscheinlicher.

Ob das nun 'Mist' ist oder nicht, es ist auf jeden Fall wichtig für die 
Aufgabe bzw. das Ergebnis!

Michael Roek schrieb:
> Doch, diese Wahrscheionlichkeit ist 0.25!
>
> Wenn die Anzahl der beim Experiment gezogenen Kugeln gleichverteilt ist,
> ist die Wahrscheinlichkeit, dass dei "1" dabei ist = 0.5
> Ebenso die (unabhaengige) Wahrscheinlichkeit, dass eine "2" dabei ist.
> Damit ist die Ergebniswahrscheinklichkeit fuer das Experiment ("1" UND
> "2") = 0.25!

Wenn wir mal keine Annahmen machen, sondern die ursprüngliche 
Aufgabenstellung nehmen, dann würde ich das mit den 25 % noch einmal 
überdenken! ;-)

blablub schrieb:
> inwieweit würde sich das vom pseudocode unterscheiden?

So in etwa könnte man es simulieren:

1

while (lange) {

2

  uint64_t bitfeld = 0;

3

  int anzahl_gezogen = rand_zwischen(1, 64);

4

5

  for (int i = 0; i < anzahl_gezogen; i++) {

6

    position = rand_zwischen(0, 63);

7

    while (bit_ist_gesetzt(bitfeld, position)) {

8

      // Bit ist schon gesetzt, nimm nächste Position

9

      position = (position + 1) % 64;

10

    }

11

    setze_bit(bitfeld, position);

12

  }

13

14

  if (bit_ist_gesetzt(bitfeld, 0) && bit_ist_gesetzt(bitfeld, 1)) {

15

    good++;

16

  } else {

17

    bad++;

18

  }

19

}

xfr schrieb:
> int anzahl_gezogen = rand_zwischen(1, 64);

Entspricht nicht der Aufgabenstellung!

OK, nicht Geschwindigkeitsoptimiert, dafür aber lesbar...

1

#!/usr/bin/env python

2

# -*- coding: utf-8 -*-

3

4

import random

5

6

Versuche = 100000

7

Treffer = 0

8

Kugelanzahl = 64

9

10

# Originalurne mit Kugeln Nr1 - Nr{Kugelanzahl} füllen

11

Originalurne = [x for x in range(1,Kugelanzahl+1)]

12

13

for i in range(Versuche):

14

    Anzahl_ziehen = random.randint(0,Kugelanzahl)  # 0 - {Kugelanzahl} Kugeln ziehen

15

    noch_zu_ziehen = Anzahl_ziehen

16

17

    Urne = Originalurne[:]                # Kopie des Originalbeutels

18

    Gezogen = []                          # 'Gezogene' leeren

19

    while noch_zu_ziehen > 0:

20

        n = random.randint(0,len(Urne)-1) # welche Kugel ziehen wir?

21

        Kugel = Urne.pop(n)               # aus der Urne nehmen

22

        Gezogen.append(Kugel)             # zu den Gezogenen hinzufügen

23

        noch_zu_ziehen -= 1

24

25

    if (1 in Gezogen) and (2 in Gezogen):

26

        Treffer += 1

27

28

print Versuche,Treffer

Hehe, cool, läuft ja sogar. :)

Und ist wirklich ein anderes Ergebnis. Also Merke: Mit solchen 
Vereinfachungen wie "im Schnitt werden 32 Kugeln gezogen, also rechne 
ich damit" sollte man sehr vorsichtig sein ...

xfr schrieb:
> Hehe, cool, läuft ja sogar. :)

Das war der zugrunde liegende Plan ;-)

Konnte gerade nicht widerstehen, meinen Pseudocode auch noch lauffähig 
zu machen. Es kommt auch das gleiche raus, nur um einiges schneller. :D

Interessanterweise darf man allerdings nicht einfach die nächste 
Bitposition benutzen, falls die erste generierte Stelle schon belegt 
ist, sondern muss ein neue Zahl generieren. Ansonsten erhält man ein 
leicht höheres Ergebnis.

Hier der Code (quick and dirty ...):

1

#include <stdint.h>

2

#include <stdio.h>

3

#include <stdlib.h>

4

#include <time.h>

5

6

#define set_bit(var, bit) ((var) |= (1ULL<<(bit)))

7

#define bit_is_set(var, bit) ((var) & (1ULL<<(bit)))

8

9

int main(void)

10

{

11

  uint64_t bitfeld;

12

  int anzahl_gezogen;

13

  int position;

14

  int versuch;

15

  int versuche = 100000;

16

  int treffer = 0;

17

18

  srand(time(NULL));

19

20

  for (versuch = 0; versuch < versuche; versuch++) {

21

    bitfeld = 0;

22

    anzahl_gezogen = rand() % 65;

23

24

    int i;

25

    for (i = 0; i < anzahl_gezogen; i++) {

26

      do {

27

        position = rand() % 64;

28

      } while (bit_is_set(bitfeld, position));

29

      set_bit(bitfeld, position);

30

    }

31

    if (bit_is_set(bitfeld, 0) && bit_is_set(bitfeld, 1)) {

32

      treffer++;

33

    }

34

  }

35

36

  printf("Versuche: %i, Treffer: %i\r\n", versuche, treffer);

37

}

xfr schrieb:
> Konnte gerade nicht widerstehen, meinen Pseudocode auch noch lauffähig
> zu machen. Es kommt auch das gleiche raus, nur um einiges schneller. :D
>
> Interessanterweise darf man allerdings nicht einfach die nächste
> Bitposition benutzen, falls die erste generierte Stelle schon belegt
> ist, sondern muss ein neue Zahl generieren. Ansonsten erhält man ein
> leicht höheres Ergebnis.

hmm in deinem code kann doch eine position mehrmals vergeben. also z.b 
die erste und zweite kugel der dritten position
oder übersehe ich da was?

Wenn die Position schon belegt ist, wird so lange ein neue gewürfelt, 
bis man eine freie Stelle trifft:

1

do {

2

  position = rand() % 64;

3

} while (bit_is_set(bitfeld, position));

Ist sicherlich nicht der effizienteste Weg, aber läuft trotzdem deutlich 
schneller als das Python-Programm. ;-)

xfr schrieb:
> Ist sicherlich nicht der effizienteste Weg, aber läuft trotzdem deutlich
> schneller als das Python-Programm. ;-)

Man kann das Python Programm ca. 30-50 mal schneller machen wenn man die 
Listenmanipulationen optimiert und unleserlich macht.

<Lästermodus>
Allerdings siehts's dann ähnlich aus wie C-code (also wie ein 
ungemachtes Bett) ;-)

PS: Setz doch mal beim C-Source die Anzahl der Kugeln auf 2000 :-)
</Lästermodus>

Mathematisch (unter der Voraussetzung dass die Anzahl der gezogenen 
Kugeln (0 bis 64) linear verteilt ist):

 kann man sich natürlich sparen.

Wer kann's beweisen?

> Aus einer Urne mit 64 durchnummerierten Kugeln

In ner Urne iss Asche!!