Wahrscheinlichkeitsrechnung Kombinatorik herangehensweise

27.06.2017, 14:22

sunrise52

Wahrscheinlichkeitsrechnung Kombinatorik herangehensweise

Meine Frage:
Ich stehe schon lange mit Wahrscheinlichkeitsrechnung und Kombinatorik auf Kriegsfuß, möchte es aber nun endlich richtig lernen, da ich mich derzeit auch mit Data-Mining beschäftige.

Die Aufgabe sieht in etwa wie folgt aus:
Es geht um das finden von potenziellen Terroristen.

- Zur Untersuchung liegen die Einkäufe von 100 Millionen Personen vor.
- Jede Person geht 100 Mal im Jahr Einkaufen und kauft 10 der 1000 möglichen Produkte
-> Wir glauben, dass Terroristen exakt die gleichen 10 Produkte (Möglicherweise die Komponenten für eine Bombe?) an irgendeinem Zeitpunkt im Jahr kaufen werden.

Meine Ideen:
Zur Lösung habe ich bereits folgende Wahrscheinlichkeiten berechnet:

$\begin{eqnarray*} P(Person.geht.in.den.Supermarkt[und.kauft.10.Produkte]) = \frac{1}{100} \end{eqnarray*}$

Anzahl Produkte, die eine Person im Jahr kauft: $\begin{eqnarray*} 100 * 10 = 1000 \end{eqnarray*}$
Mögliche Itemsets: $\begin{eqnarray*} \begin{pmatrix} 1000 \\ 10 \end{pmatrix} \end{eqnarray*}$ approximiert mit Stirlingformel: $\begin{eqnarray*} \frac{10^{8}}{10!} \end{eqnarray*}$

$\begin{eqnarray*} P(Person.kauft.10.bestimmte.Produkte)=1:\frac{10^{8}}{10!} = \frac{10!}{10^{8}} \end{eqnarray*}$

$\begin{eqnarray*} P(Person.geht.in.den.Supermarkt.und.kauft.10.bestimmte.Produkte) = 10^{-2} * \frac{10!}{10^{8}} \end{eqnarray*}$

-

Ab dieser Stelle weiß ich nicht mehr so richtig, wie ich weiter vorgehen soll. Man könnte als nächstes die Anzahl von Paaren mit $\begin{eqnarray*} \begin{pmatrix} 10^{8} \\ 2 \end{pmatrix} \end{eqnarray*}$ berechnen, aber wie macht man dann weiter?

Ich bedanke mich für jeden Hilfreichen Beitrag.

27.06.2017, 14:42

HAL 9000

Auf diesen Beitrag antworten »

Ich lese da eine Situationsbeschreibung - aber sehe keine Aufgabe, die zu lösen ist. verwirrt

27.06.2017, 14:56

sunrise52

Auf diesen Beitrag antworten »

Naja die Aufgabe steht implizit dort:

Gesucht sind ja die potenziellen Terroristen; also die Paare von Personen, welche die exakt gleichen 10 Produkte an einem beliebigen Zeitpunkt im Jahr kaufen werden.

*Nachtrag: ich habe tatsächlich in der Beschreibung vergessen zu erwähnen, dass Terroristen Paare von Personen sind, welche die exakt gleichen 10 Produkte an einem beliebigen Zeitpunkt im Jahr kaufen werden.
Sorry!

27.06.2017, 15:44

HAL 9000

Auf diesen Beitrag antworten »

Das ist dennoch noch keine Aufgabe. Was willst du denn konkret wissen:

Die Wahrscheinlichkeitsverteilung der Anzahl Terrorverdächtiger, unter der Annahme, dass die Leute total "zufällig" einkaufen? Oder was anderes?

Und wieso "Paare" von Personen? Gibt es keine einzelnen Terroristen?

Insgesamt eine sehr unausgegorene Darstellung.

-------------------------------------------------------------------------------------

Ich versuche dennoch mal darzulegen, was ich aus deinen Angaben herauslese:

Jede der 100 Millionen Personen geht 100mal im Jahr einkaufen. Dabei nimmst du an, dass diese insgesamt 10 Milliarden Einkaufsvorgänge i.i.d. (unabhängig und identisch verteilt) anzusehen sind.

Jeder einzelne Einkaufsvorgang besteht in der zufälligen Auswahl von 10 aus 1000 Produkten (ohne Wiederholung).

Am Ende des Jahres stufst du eine Person als Terrorverdächtigen ein, wenn sie die von dir vorgemerkten 10 Produkte jeweils mindestens einmal gekauft hat. Das geschehe mit Wahrscheinlichkeit $\begin{align*} p \end{align*}$ .

Vermutlich liegt dein Fokus erstmal darauf, dieses $\begin{align*} p \end{align*}$ zu berechnen, also für eine einzelne Person.

$\begin{align*} N \end{align*}$ ... Anzahl verfügbarer Produkte [1000]
$\begin{align*} n \end{align*}$ ... Anzahl terrorverdächtiger Produkte [10]
$\begin{align*} M \end{align*}$ ... Anzahl Einkaufsvorgänge [100]
$\begin{align*} m \end{align*}$ ... Anzahl Einkäufe pro Einkaufsvorgang [10]

Betrachten wir das Ereignis

$\begin{align*} A_k \end{align*}$ ... Terrorprodukt $\begin{align*} k \end{align*}$ ist in keinem der $\begin{align*} M \end{align*}$ Einkäufe dabei ( $\begin{align*} k=1,\ldots,n \end{align*}$ )

Dann ist $\begin{align*} p = 1-P\left( \bigcup_{k=1}^n A_k \right) \end{align*}$ , und wegen Siebformel sowie Symmetrie der Ereignisse bedeutet dies

$\begin{align*} p = \sum_{i=0}^n (-1)^i \binom{n}{i} P\left( \bigcap_{k=1}^i A_k \right) = \sum_{i=0}^n (-1)^i \binom{n}{i} \left( \frac{\binom{N-i}{m}}{\binom{N}{m}} \right)^M\qquad (*) \end{align*}$ .

Für die obigen $\begin{align*} N=1000,n=10,M=100,m=10 \end{align*}$ ergibt das $\begin{align*} p \approx 0.01033 \end{align*}$ , also ca. 1%. Das macht dann im Erwartungswert ca. 1 Million Verdächtige - da wird Freude aufkommen bei den Ermittlungsbehörden. smile

Für sehr große $\begin{align*} N,M \end{align*}$ und vergleichsweise kleine $\begin{align*} n,m \end{align*}$ gilt für (*) die Näherungsformel $\begin{align*} p \approx \left( 1 - \exp\left(-\frac{Mm}{N}\right) \right)^n \end{align*}$ , im vorliegenden Fall etwa ergibt dies $\begin{align*} p\approx 0.01018 \end{align*}$ , also nicht gar zu weit weg.

27.06.2017, 20:41

sunrise52

Auf diesen Beitrag antworten »

Zunächst einmal vielen Dank für die Antwort.

Ich stimme dir zu, dass die Aufgabe recht schwammig formuliert ist.
Ich habe sie aus einem Buch und dort steht leider auch nicht sehr viel mehr drin.

Das ist der Originaltext: "Suppose we have information about the supermarket purchases of 100 million people. Each person goes to the supermarket 100 times in a year and buys 10 of the 1000 items that the supermarket sells. We believe that a pair of terrorists will buy exactly the same set of 10 items (perhaps the ingredients for a bomb?) at some time during the year. If we search for pairs of people who have bought the same set of items, would we expect that any such people found were truly terrorists?"

So wie ich es verstehe geht es darum, zu ermitteln wie viele Paare von Personen sich in dem gegebenem Zeitraum finden lassen, die in dem Jahr bei einem beliebigen Einkauf die selben 10 Produkte gekauft haben.

--

Davor gab es in dem Buch eine ähnliche Aufgabe, bei der es darum ging potenzielle Verbrecher zu finden. Ich habe die Aufgabe und den Lösungsweg mal als Anhang hinzugefügt.

Vielleicht hilft die vorherige Aufgabe ja beim Verständnis der obigen Aufgabe.

27.06.2017, 21:29

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von sunrise52
So wie ich es verstehe geht es darum, zu ermitteln wie viele Paare von Personen sich in dem gegebenem Zeitraum finden lassen, die in dem Jahr bei einem beliebigen Einkauf die selben 10 Produkte gekauft haben.

Tja, und oben hattest du es eben anders dargestellt: Da war von festen 10 Produkten die Rede, die den Terrorverdacht begründen sollen - nicht davon, dass sich diese Produkte erst im Vergleich mehrer Leute ergeben. Das meine ich eben mit "unausgegoren": Aus allem möglichen eine (vermeintliche) Aufgabe zusammenflicken, vieles halb, nichts ganz.

27.06.2017, 23:15

sunrise52

Auf diesen Beitrag antworten »

Dann habe ich mich wohl missverständlich ausgedrückt.

Liegt vermutlich unter Anderem daran, dass ich wie gesagt in dem Bereich Wahrscheinlichkeitsrechnung und Kombinatorik nicht weiß wo vorne und hinten ist und daher aus den Aufgabenstellungen nicht richtig erschließen kann, was genau gesucht ist und was eben nicht.

Ich entschuldige mich für das Missverständnis und würde mich freuen, wenn du mir trotzdem Behilflich sein könntest.

28.06.2017, 10:23

HAL 9000

Auf diesen Beitrag antworten »

OK, noch etwas habe ich wohl oben falsch verstanden:

"The same set of 10 items at some time during the year" soll wohl bedeuten, dass beide (nicht notwendig zum selben Zeitpunkt) jeweils einen Einkaufsvorgang vornehmen, bei dem sie die exakt gleichen 10 Produkte kaufen. Ich hatte es oben so aufgefasst, dass es insgesamt 10 Produkte gibt, die zu irgendeinem Zeitpunkt des Jahres (und ggfs. verteilt auf viele einzelne Einkaufsvorgänge) erworben werden - das ist natürlich deutlich wahrscheinlicher und allerdings auch komplizierter in der Berechnung.

In der ersten Variante kann man sofort folgendermaßen abstrahieren: Es ist überhaupt nicht wichtig, dass es 1000 Produkte sind und 10 Produkte pro Einkauf - maßgeblich sind die daraus resultierenden $\begin{align*} N=\binom{1000}{10} \end{align*}$ (das kann man übrigens direkt ausrechnen, es besteht keine Notwendigkeit einer Näherung über Stirling) verschiedenen möglichen Einkaufsvorgänge, ansonsten gehen diese beiden Werte 1000 und 10 nicht weiter in die Rechnung ein.

Jetzt fragen wir nach der Wahrscheinlichkeit $\begin{align*} p \end{align*}$ , dass es unter insgesamt $\begin{align*} K=100\,000\,000 \end{align*}$ Kunden bei $\begin{align*} M=100 \end{align*}$ Einkäufen im Jahr mindestens zwei Kunden gibt, die denselben Einkaufsvorgang vornehmen, das aber nicht notwendig zum selben Zeitpunkt, sondern nur irgendwann im Verlauf dieses Jahres. Das ist ein strukturell anderes Problem als das zweite von dir angeführte, dennoch kann man gewisse Prinzipien bei der Lösung auch hier anwenden.

Betrachten wir zwei konkrete Kunden und fragen nach der Wahrscheinlichkeit $\begin{align*} q \end{align*}$ , dass just diese beiden nicht ein solches Paar sind. Die ist näherunsgweise

$\begin{align*} q \approx \left(1-\frac{1}{N}\right)^{M^2} \approx \exp\left(-\frac{M^2}{N}\right) \end{align*}$ basierend auf $\begin{align*} \left(1-\frac{1}{N}\right)^N\approx e \end{align*}$ .

gültig für $\begin{align*} N\gg M \end{align*}$ . Nun gibt es $\begin{align*} \binom{K}{2} \end{align*}$ Paare von Kunden, bei Unabhängigkeit (was nicht stimmt, aber mal approximativ angenommen wird) folgt daraus

$\begin{align*} p \approx 1-q^{\binom{K}{2}} \approx 1-\exp\left(-\frac{M^2K^2}{2N} \right) \end{align*}$

Für deine Werte oben bedeutet das $\begin{align*} p\approx 0.00019 \end{align*}$ , es ist also eher unwahrscheinlich, ein solches Paar zu finden.

29.06.2017, 14:14

sunrise52

Auf diesen Beitrag antworten »

Vielen Dank für den einleuchtenden und gut erklärten Lösungsweg.

Ich verstehe die Lösung und habe auch grade so einen "achja"-Effekt, wäre aber von selbst niemals drauf gekommen...Das ist irgendwie generell mein Problem in diesem Bereich.

Hast du eventuell Tipps für mich, wie ich da sicherer werden kann?

29.06.2017, 14:31

HAL 9000

Auf diesen Beitrag antworten »

"Üben, üben, üben" und "Beispiele, Beispiele, Beispiele" - klingt abgegriffen, ist aber so.

Neue Frage »

Antworten »

Wahrscheinlichkeitsrechnung Kombinatorik herangehensweise

Verwandte Themen