Schnittmengen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
Hallo,
habe Probleme mit folgender Problemstellung:
Ich habe eine Menge [mm]M[/mm] und Teilmengen von M [mm] s_{1} .. s_{n} \subseteq M[/mm].
Ich interessiere mich fuer die durchschnittliche Anzahl der Elemente in dem Schnitt der Teilmengen [mm] \bigcap_{i=1}^{n} s_{i} [/mm] .
(wenn alle moeglichen Schnitte gleich wahrscheinlich sind)
Beispiele fuer n=2:
[mm]s_{1}[/mm] habe 1 Element
[mm]s_{2}[/mm] habe 10 Elemente
In der Schnittmenge sind demnach 0 oder 1 Element. Im Durchschnitt 0,5 Elemente. (Alle moeglichen Schnitte sind gleich wahrscheinlich: (0+1)/2 )
[mm]s_{1}[/mm] habe 10 Elemente
[mm]s_{2}[/mm] habe 10 Elemente
In der Schnittmenge sind demnach 0 bis 10 Elemente. Im Durchschnitt 5 Elemente.
Soweit sogut. Aber wie verhaelt es sich fuer n>2 ?
[mm]s_{1}[/mm] habe 1 Element
[mm]s_{2}[/mm] habe 10 Elemente
[mm]s_{3}[/mm] habe 10 Elemente
Schnittmenge wieder 0 oder 1 Element. Aber der Durchschnitt sollte sollte ein anderer sein, oder!? Die Wahrscheinlichkeit, dass ein Element in allen drei Teilmenge ist, ist eine andere als, dass es in zwei der Teilmengen ist.
Wie kann man die durchschnittliche Anzahl der Elemente, die in allen Teilmengen sind, berechnen - fuer beliebige n?
Bin fuer jeden Tip dankbar.
Schoene Gruesse,
Bastian
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:02 Di 16.05.2006 | | Autor: | statler |
Auch hallo!
> habe Probleme mit folgender Problemstellung:
>
> Ich habe eine Menge [mm]M[/mm] und Teilmengen von M [mm]s_{1} .. s_{n} \subseteq M[/mm].
> Ich interessiere mich fuer die durchschnittliche Anzahl der
> Elemente in dem Schnitt der Teilmengen [mm]\bigcap_{i=1}^{n} s_{i}[/mm]
> .
> (wenn alle moeglichen Schnitte gleich wahrscheinlich
> sind)
>
> Beispiele fuer n=2:
>
> [mm]s_{1}[/mm] habe 1 Element
> [mm]s_{2}[/mm] habe 10 Elemente
> In der Schnittmenge sind demnach 0 oder 1 Element. Im
> Durchschnitt 0,5 Elemente. (Alle moeglichen Schnitte sind
> gleich wahrscheinlich: (0+1)/2 )
Das glaube ich schon mal nicht! Wenn M sehr groß ist, wird doch in den meistens Fällen der Schnitt leer sein, also der Durchschnitt nahe an 0. Das muß glaube ich noch etwas präziser gefaßt werden.
Auf welches Problem im richtigen Leben willst du das denn loslassen?
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:19 Di 16.05.2006 | | Autor: | BastianBln |
Recht hast Du.
Bezug ist die Informatik (Datenbanken/ Anfragesprachen):
Es muessen mehrere Bedingungen erfuellt sein, damit ein Eintrag der Datenbank im Ergebnis einer Anfrage erscheint. Eine Bedingung A fuehrt zu einer Teilmenge aller Eintraege in einer Tabelle, eine andere B zu einer anderen. Das Ergebnis ist der Schnitt der beiden Teilmengen. Dabei ist es moeglich, dass beide Teilmengen gleich oder disjunkt sind. Darueber ist aber nichts bekannt. Deshalb der Durchschnitt in der Anzahl der Elemente.
Beispiel:
Es gibt 100 Eintraege in einer Tabelle.
Bedingung A (preis < 100 EUR) reduziert die Anzahl der Ergebnisse auf 10
Bedingung B (lagerbestand >3) reduziert die Anzahl der Ergebnisse auf 25
Ueber die Elemete in den Teilmengen ([mm] M_{A} und M_{B} [/mm]) ist nichts weiter bekannt.
Was kann von der Bedingung [mm] A \wedge B [/mm] (preis < 100 und lagerbestand >3) erwartet werden?
Mir fehlt da irgendwie der zuendende Funke, wie ich ueber die Anzahl denken kann.
Es gibt mehrere Moeglichkeiten fuer die Teilmengen:
1. [mm] M_{A} \cap M_{B} = \emptyset [/mm]
2. [mm] M_{A} \cap M_{B} \not= \emptyset und M_{A} \not= M_{B} [/mm]
3. [mm] M_{A} = M_{B} [/mm]
Aber wie kann man die Anzahl der Faelle pro Moeglichkeit abzaehlen bzw. schaetzen?
|
|
|
| |
|
Moin zusammen,
nehmen wir ruhig den Fall mit zwei Teilmengen:
M sei eine Menge mit m Elementen, und es sollen [mm] S_1, S_2 [/mm] zwei unabh. gleichverteilt gewählte
Teilmengen von M der Größe [mm] s_1 [/mm] bzw [mm] s_2 [/mm] sein mit [mm] s_1\leq s_2.
[/mm]
Dann kannst Du die erwartete Kardinalität des Schnittes [mm] S_1\cap S_2 [/mm] wie folgt berechnen:
[mm] E[\: |S_1\cap S_2|\: [/mm] ] [mm] =\sum_{i=0}^{s_1}Pr\{\: |S_1\cap S_2|\: =i\:\}
[/mm]
[mm] =\sum_{i=0}^{s_1} \vektor{n\\i}\cdot \vektor{n-i\\s_1-i}\cdot\vektor{n-i-s_1}{s_2-i}
[/mm]
(die ''Vektoren'' bedeuten n über i usw.).
Das wird nun für n=3 oder allgemeines n nicht einfacher. Oder doch ?
Seien [mm] s_1\leq s_2\leq \ldots \leq s_n [/mm] die Mengengrößen.
Dann müssen doch für den Schnitt der Größe i jeweils [mm] s_j-i [/mm] Elemente für [mm] S_j\setminus\left (\bigcap_{i=1}^nS_i\right [/mm] )
gewählt werden - und zwar unabhängig voneinander. Also
[mm] E[\: |S_1\cap\ldots \cap S_n|\: ]\: =\: \sum_{i=0}^{s_1} \vektor{n\\i}\cdot \prod_{j=1}^n\vektor{n-i}{s_j-i}
[/mm]
Viel Spaß beim Ausrechnen. 
Gruss,
Mathias
|
|
|
| |
|
Wow. Danke fuer Deine Ausfuehrungen. Ich muss aber leider zugeben, dass meine Erfahrungen in Kombinatorik und Wahrscheinlichkeitsrechnung mehr als 6 Jahre zurueckliegen und ich deshalb nicht ganz folgen kann. Koenntest Du die einzelnen Gedanken etwas ausfuehrlicher darstellen (ggf. nur die angewandte Regel/Definition/...). Das waere super.
Es faengt schon bei der ersten Formel an. Du berechnest den Erwartungswert? Aber was ist Pr? Die Wahrscheinlichkeit? Und wie kommst Du auf die rechte Seite der Gleichung?
So gehts dann weiter mit meinen Fragen... Sorry - mein Stochastikkurs ist wirklich lange her und war nicht wirklich gut.
Nochmal vielen Dank.
Bastian
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Mo 22.05.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
