Sylvestersche Siebformel/Berechnen der Teilmengen

30.09.2013, 10:13

Hm...

RE: Silvestersche Siebformel/ Berechnen der Teilmengen

Hi Leute,

ich versuche gerade die Silvestersche Siebformel zu implementieren, schaffe es aber nicht einen passenden Algo. für folgendes problem zusammen zu basteln:

gegeben: Eine Menge M von Ereignissen und eine natürliche Zahl k
Gesucht: Alle Teilmengen N von M mit |N|=k

habt ihr eine idee?

Zwei Beiträge zusammengeführt. Steffen

eigendlich suche ich direkt ne idee wie man die silvestersche siebformel implementieren könnte ohne das es viel laufzeit verbraucht...

meine idee wäre:

M={p1,p2,....,pk}

k=1: trivial

k=2: p1*p2, ..., p1*pk, p2*p3, ..., p2*pk, ... , p(k-1)*pk

k=3: wie k=2 nur das immer der letzte indize verschoeben wird

aber das sieht schon so nach hoherlaufzeit aus ^^

meine grundlegende methode wäre:

private static Double silvesterscheSiebformel(Double[] probilitys)
{
Double p=0.0;

for(int k=1;k<=probilitys.length;k++)
{
Double z = (k % 2 == 0 ? -1.0 : 1.0);
Double n = 0.0;

ArrayList<Double> kombis = getKombisNew(probilitys,k);
for(int i=0; i<kombis.size(); i++)
{
n += kombis.get(i);

}
p += z * n;
}

return p;
}

in getKombisNew berechne ich die entsprechenden produkte (was derzeit nicht funktioniert)....

30.09.2013, 11:19

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Hm...
gegeben: Eine Menge M von Ereignissen und eine natürliche Zahl k
Gesucht: Alle Teilmengen N von M mit |N|=k

Hier sprichst du davon, dass du Teilmengen suchst - später dann berechnest du aber irgendwelche Wahrscheinlichkeiten? Reichlich verworren. verwirrt

In dieser Form passt das eben überhaupt nicht zu dem, was du im folgenden dann ausführst. Ich versuche mal zu "übersetzen", was du allem Anschein nach wirklich willst:

Zitat:

Du hast eine Menge $\begin{eqnarray*} M \end{eqnarray*}$ von $\begin{eqnarray*} k \end{eqnarray*}$ unabhängigen (!) Ereignissen $\begin{eqnarray*} A_1,\ldots,A_k \end{eqnarray*}$ , deren Wahrscheinlichkeiten $\begin{eqnarray*} p_1,\ldots,p_k \end{eqnarray*}$ du kennst.

Du suchst nun die Wahrscheinlichkeit von deren Vereinigung, also $\begin{eqnarray*} P(A_1\cup\ldots\cup A_k) \end{eqnarray*}$ .

Die Siebformel ist das richtige Mittel für dieses Problem, wenn die Wahrscheinlichkeit aller möglichen Durchschnitte der $\begin{eqnarray*} A_i \end{eqnarray*}$ bekannt bzw. leicht berechenbar ist - soweit hast du Recht, und damit könnte man die hier auch theoretisch gut anwenden.

Allerdings ist die Siebformelanwendung hier der reinste Berechnungsoverkill, da es ja auch wesentlich einfacher geht:

Bei deinen Voraussetzungen sind ja auch die Gegenereignisse $\begin{eqnarray*} A_1^c,\ldots,A_k^c \end{eqnarray*}$ unabhängig, es folgt sofort

$\begin{eqnarray*} P(A_1\cup\ldots\cup A_k) &=& 1- P((A_1\cup\ldots\cup A_k)^c) = 1- P(A_1^c\cap\ldots\cap A_k^c) \\ &\stackrel{!}{=}& 1-P(A_1^c)\cdot P(A_2^c)\cdot \ldots \cdot P(A_k^c) = 1-(1-p_1)\cdot (1-p_2)\cdot \ldots \cdot (1-p_k) \end{eqnarray*}$ .

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

Eine andere Vermutung wäre noch diese - die liegt näher an deiner oben zitierten Problemstellung, ist aber in deinem Programm-Quelltext gar nicht mehr erkennbar:

Zitat:

Du hast eine Menge $\begin{eqnarray*} M \end{eqnarray*}$ von $\begin{eqnarray*} n \end{eqnarray*}$ unabhängigen Grundereignissen $\begin{eqnarray*} A_1,\ldots,A_n \end{eqnarray*}$ , deren Wahrscheinlichkeiten $\begin{eqnarray*} p_1,\ldots,p_n \end{eqnarray*}$ du kennst.
Und du suchst nun die Wahrscheinlichkeit des Ereignisses, dass genau $\begin{eqnarray*} k \end{eqnarray*}$ der $\begin{eqnarray*} n \end{eqnarray*}$ Grundereignisse erfüllt sind.

Das haben wir vor nicht allzu langer Zeit hier diskutiert

Wahrscheinlichkeit auf n Erfolge bei unterschiedlichen Wahrscheinlichkeiten

ebenfalls völlig ohne Siebformel. Nicht dass ich was gegen diese Formel habe (frag mal Mystic Augenzwinkern

), aber nicht überall ist es sinnvoll und effizient, auf sie zu bauen. smile

30.09.2013, 11:49

Hm...

Auf diesen Beitrag antworten »

danke, das funktioniert!

ich habs vorher mit den bonferoni ungleichungen versucht (aber die sind ganz schöner mist!):

private static Double bonferroniUngleichungen(Double[] probilitys)
{
Double p = 0.0;
Double overbound = 0.0;
Double underbound = 0.0;

for(int i=0; i<probilitys.length; i++)
{
overbound += probilitys[i];
//underbound += probilitys[i];
for(int j=0; j<i; j++)
underbound -= ( probilitys[i] + probilitys[j] - probilitys[i] * probilitys[j]);
}
System.out.println("obere schranke: "+ overbound + " untereschranke: "+ (overbound + underbound));
p = Math.abs(2*overbound + underbound) / 2;
return p;
}

die liefern für die eingabe {0.5,0.5,0.5} ein intervall von [1.5,-0.75] Hammer

30.09.2013, 11:57

HAL 9000

Auf diesen Beitrag antworten »

Ich hatte eigentlich erwartet, dass du mal Licht in das Chaos deiner Problemstellung bringst, d.h. verständlich äußerst, was deine wirkliche Problemstellung ist (ich hab ja zwei zur Wahl gestellt, aber es ist ja vielleicht eine ganz andere). Das sollte doch bei dieser anscheinend doch ziemlich übersichtlichen Situation möglich sein - ist es zuviel verlangt, das zu erfahren? unglücklich

30.09.2013, 12:05

Hm...

Auf diesen Beitrag antworten »

achso, dass hatte ich überlesen, sorry smile

mein problem war jenes, welches du zuerst vorgestellt hast.

konkret:

Gegeben waren $\begin{eqnarray*} n \end{eqnarray*}$ verschiedene wahrscheinlichkeiten $\begin{eqnarray*} p_i \end{eqnarray*}$ ,

und gesucht war die wahrscheinlichkeit, dass dieser kunde mindestens einmal im zeitraum t=1,...,n in das geschäft geht

wobei $\begin{eqnarray*} p_i \end{eqnarray*}$ die wahrscheinlichkeit dafür ist, dass ein vorherfestgeleter kunde an einem Tag i in ein geschäft geht. diese $\begin{eqnarray*} p_i \end{eqnarray*}$ habe ich über einen markovgraphen berechnet (was ziemlich aufwendig war)

30.09.2013, 14:08

HAL 9000

Auf diesen Beitrag antworten »

Dann also doch das einfache Problem ... Ok.

Zitat:

Original von Hm...
wobei $\begin{eqnarray*} p_i \end{eqnarray*}$ die wahrscheinlichkeit dafür ist, dass ein vorherfestgeleter kunde an einem Tag i in ein geschäft geht. diese $\begin{eqnarray*} p_i \end{eqnarray*}$ habe ich über einen markovgraphen berechnet

Ein leichtes Stirnrunzeln befällt mich bei dieser Beschreibung (speziell dem Verweis auf "Markovgraph") dann doch: Sobald es irgendwelche Abhängigkeiten zwischen den zugehörigen Ereignissen

$\begin{eqnarray*} A_i \end{eqnarray*}$ ... Kunde betritt an Tag $\begin{eqnarray*} i \end{eqnarray*}$ das Geschäft

gibt, ist die obige Formel null und nichtig, das ist dir hoffentlich in aller Deutlichkeit bewusst!

Neue Frage »

Antworten »

Sylvestersche Siebformel/Berechnen der Teilmengen

Verwandte Themen