Kleine Beiträge, die die Welt verbessern

24.02.2013, 22:13

2phil.05.phil

Auf diesen Beitrag antworten »

Kleine Beiträge, die die Welt verbessern

Meine Frage:
Letzte Nacht stellte sich mir folgende Frage im Traum:

Wie wahrscheinlich ist es, dass jedem Menschen min. ein Mal geholfen wird, wenn jeder drei von einander verschiedenen Personen (sich selbst ausgenommen) Hilfe leistet?
Außerdem, wie vielen Menschen müsste man helfen, damit die Chance auf 50% steigt?

Meine Ideen:
Anfangs schien mir die Frage so einfach zu klingen doch bei näherer Betrachtung ist das kombinatorische Problem, dass sich dahinter verbirgt für mich leider doch nicht so offensichtlich.

Ich suche eigentlich eine allgemeine Formel für das Problem. Allgemein ergibt sich günstige Ereignisse (also allen wird min. ein Mal geholfen) durch mögliche Ereignisse (ja hier Stocke ich schon mit meiner Formulierung).

Ich weiß, dass mir maximal n*k Aktionen zur Verfügung stehen und ich diese auf n Personen verteilen will. Dabei kann einer Person zwischen 1 und n-mal geholfen werden.

Für die Anzahl der möglichen Ereignisse habe ich folgende Formel (von deren Richtigkeit ich aber noch nicht 100%ig überzeugt bin):
$\begin{eqnarray*} <br /> \begin{pmatrix} n-1 \\ k \end{pmatrix}^{n} <br /> \end{eqnarray*}$

Ich suche also die Anzahl der gerichteten Graphen mit n Knoten und k Kanten.

Für die günstigen Ereignisse möchte ich nur die Graphen in denen es keine Quellen gibt.
(bzw könnte man auch die Gegenereignisse suchen, dh alle Graphen in denen es genau eine bis n-(k+1)-Quelle gibt, falls das leichter sein sollte.

So nun habe ich auch noch mein bisschen wundervolles Halbwissen über Graphentheorie eingebracht und komme dennoch nicht weiter. Habt ihr vielleicht Ideen dazu?

PS: ich gehe bei der Frage von einem mathematischen Idealzustand aus, dass Menschen nicht mal eben so anderen Menschen helfen wollen das weiß ich, ebenso dass der Nenner meines Terms bei 7Mrd Menschen vermutlich Explodieren wird und man k unvorstellbar groß wählen müsste um ihn im Zaum zu halten. Aber mich würden mal genaue Zahlen interessieren und nicht immer noch Abschätzungen. Herzlichen Dank smile

smile

24.02.2013, 23:24

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von 2phil.05.phil
Wie wahrscheinlich ist es, dass jedem Menschen min. ein Mal geholfen wird, wenn jeder drei von einander verschiedenen Personen (sich selbst ausgenommen) Hilfe leistet?

Wirklich jedem? Diese Wahrscheinlichkeit hängt aber von der Gesamtzahl $\begin{eqnarray*} n \end{eqnarray*}$ der Leute ab, und verschwindet für $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ .

Wenn es dagegen nur um einen bestimmten geht, dann konvergiert diese Wahrscheinlichkeit für $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ gegen einen (natürlich von $\begin{eqnarray*} k \end{eqnarray*}$ abhängigen) Wahrscheinlichkeitswert ungleich Null.

24.02.2013, 23:53

2phil.05.phil

Auf diesen Beitrag antworten »

Also ja rein theoretisch jedem: also aktuell ca. 7 Mrd. und wir gehen davon aus, dass jeder an dieser Aktion teil nimmt.

Ich war inzwischen dabei zu überlegen ob es nicht wirklich besser ist die Gegenwahrscheinlichkeit zu bestimmen und halt auszurechnen wie wahrscheinlich es ist, dass genau einem Menschen nicht geholfen wird, bzw man einen Knoten aus dem gerichteten Graphen löscht. Klar ist, dass das jedem der n Leute treffen kann, was mir leider nicht klar ist, wie ich im restlichen Graphen sicherstelle, dass jede Quelle auch min. einen eintreffende Kante hat. Sodass meine Überlegung bisher das Problem lediglich um einen Menschen reduziert hat, die Frage aber die selbe bleibt (bloß für n-1 dann eben)

Dass die Chancen dafür schlecht sind und gegen 0 gehen ist mir bewusst, aber ich hätte halt gern eine genaue Größenvorstellung

25.02.2013, 10:29

HAL 9000

Auf diesen Beitrag antworten »

Ich lass mal die Graphentheorie Graphentheorie sein und konzentriere mich auf den stochastischen Aspekt:

Sei $\begin{eqnarray*} A_i \end{eqnarray*}$ das Ereignis, dass Person $\begin{eqnarray*} i \end{eqnarray*}$ von mindestens einer der anderen $\begin{eqnarray*} (n-1) \end{eqnarray*}$ Personen geholfen wird. Das Gegenereignis $\begin{eqnarray*} A_i^c \end{eqnarray*}$ tritt dann ein, wenn alle diese $\begin{eqnarray*} (n-1) \end{eqnarray*}$ Personen nicht helfen, d.h. jeder seine $\begin{eqnarray*} k \end{eqnarray*}$ Hilfestellungen auf $\begin{eqnarray*} (n-2) \end{eqnarray*}$ Personen (d.h. alle außer sich selbst und Person $\begin{eqnarray*} i \end{eqnarray*}$ ) verteilt. Das ergibt

$\begin{eqnarray*} P(A_i) = 1-P(A_i^c) = 1-\left( \frac{\binom{n-2}{k}}{\binom{n-1}{k}} \right)^{n-1} = 1-\left( 1-\frac{k}{n-1} \right)^{n-1} \to 1-e^{-k} \end{eqnarray*}$ für $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ .

Leider sind nun die $\begin{eqnarray*} A_i \end{eqnarray*}$ untereinander nicht unabhängig, allerdings kann man (schwer begründbar) für "große" $\begin{eqnarray*} n \end{eqnarray*}$ (also $\begin{eqnarray*} n\gg k \end{eqnarray*}$ ) mit näherungsweiser Unabhängigkeit rechnen. Für das dich interessierende Ereignis $\begin{eqnarray*} A = \bigcap\limits_{i=1}^n A_i \end{eqnarray*}$ gilt dann somit für diese großen $\begin{eqnarray*} n \end{eqnarray*}$ die Abschätzung

$\begin{eqnarray*} P(A) \approx \prod_{i=1}^n P(A_i) \approx \left( 1-e^{-k} \right)^n \end{eqnarray*}$ .

Das sollte dir helfen, zumindest die Größenordnung einzuschätzen.

25.02.2013, 12:13

2phil.05.phil

Auf diesen Beitrag antworten »

Vielen vielen Dank schon mal!

...aber eine kleine Frage habe ich noch: Und zwar ist $\begin{eqnarray*} A_i^c \end{eqnarray*}$ jetzt ja erst mal bloß der Fall, dass genau einem nicht geholfen wird. Allerdings erfüllen ja auch 2 Ungeholfenen ... bis n-(k+1) Menschen denen nicht geholfen wurde meine Bedingung nicht.
Kann ich die Formel dann einfach additiv nach gleichem Schema erweitern?

$\begin{eqnarray*} P(A^c)= 1- \left( \left( \frac{\begin{pmatrix} \\ n-2\\k \end{pmatrix}}{\begin{pmatrix} \\ n-1\\k \end{pmatrix}}\right) ^{n-1} + \left( \frac{\begin{pmatrix} \\ n-3\\k \end{pmatrix}}{\begin{pmatrix} \\ n-1\\k \end{pmatrix}}\right) ^{n-1}+...+\left( \frac{\begin{pmatrix} \\ n-(k+1)\\k \end{pmatrix}}{\begin{pmatrix} \\ n-1\\k \end{pmatrix}}\right) ^{n-1}\right) \end{eqnarray*}$

25.02.2013, 13:04

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von 2phil.05.phil
Und zwar ist $\begin{eqnarray*} A_i^c \end{eqnarray*}$ jetzt ja erst mal bloß der Fall, dass genau einem nicht geholfen wird.

Nein: Wie ich oben deutlich geschrieben habe, bedeutet $\begin{eqnarray*} A_i^c \end{eqnarray*}$ nur, dass Person $\begin{eqnarray*} i \end{eqnarray*}$ nicht geholfen wird - was mit den anderen (n-1) Personen da geschieht, ist da überhaupt nicht gesagt. unglücklich

unglücklich

Und dass $\begin{eqnarray*} A = \bigcap\limits_{i=1}^n A_i \end{eqnarray*}$ das von dir gesuchte Ereignis darstellt, steht völlig außer Frage, wenn du mal ein wenig genauer drüber nachdenkst, was der Durchschnitt von Ereignissen inhaltlich bedeutet.

Anzeige

25.02.2013, 13:08

2phil.05.phil

Auf diesen Beitrag antworten »

... so ganz bin ich von der Lösung nicht überzeugt, denn sieht man sich den Plot dazu an für ein festes $\begin{eqnarray*} n \end{eqnarray*}$ (n=7Mrd) in Abhängigkeit von $\begin{eqnarray*} k \end{eqnarray*}$ , dann hat man für $\begin{eqnarray*} k\geq0 \end{eqnarray*}$ diese wunderschöne sigmoidale Kurve, die für $\begin{eqnarray*} k=23 \end{eqnarray*}$ eine $\begin{eqnarray*} 50% \end{eqnarray*}$ ige Chance lieft, für $\begin{eqnarray*} k=24 \end{eqnarray*}$ bereits über $\begin{eqnarray*} 75% \end{eqnarray*}$ und ab ca 30 guten Taten, wird jedem geholfen und davon bin ich absolut nicht überzeugt, dass das stimmen kann, denn man kann diese 30 Taten ja auch auf nur 31 bis n-1 Menschen verteilen und da sollte es wohl genug Kombinationsmöglichkeiten geben um die Wahrscheinlichkeit wieder in den Keller zu treiben...

Ah ... ja der Durchschnitt ist ja gerade das eine kleine Ereignis, dass sie alle gemeinsam haben. Ja ok...du hast natürlich völlig recht

25.02.2013, 13:38

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von 2phil.05.phil
und davon bin ich absolut nicht überzeugt, dass das stimmen kann

Vielen Dank für das Vertrauen.

Ich warte aber noch auf eine Begründung für dein Misstrauen, die auf etwas soliderer Grundlage als bloßem Glauben steht. Finger2

Finger2

25.02.2013, 14:07

2phil.05.phil

Auf diesen Beitrag antworten »

ich habe vermutlich deinen Lösungsvorschlag noch nicht so ganz verstanden, aber betrachte ich die Funktion
$\begin{eqnarray*} <br /> f(k)=(1-e^{-k})^{7*10^9}<br /> \end{eqnarray*}$
dann dachte ich, dass sie mir die Wahrscheinlichkeit in Abhängigkeit von k gibt, dass jedem geholfen wird. Würde die Funktion das tun, würde das bedeuten, dass wenn man 30 Menschen hilft jedem der 7Mrd min. einmal geholfen wird.

Da man aber nun die Leistung auch auf nur 31 Menschen verteilen kann und man diese 31 Menschen aus den 7 Mrd. gezogen werden, gibt es ja schon wieder min. $\begin{eqnarray*} \begin {pmatrix} 7Mrd \\31 \end{pmatrix} \end{eqnarray*}$ -Fälle in denen die Bedingung nicht erfüllt ist und das sollte dann doch für eine Wahrscheinlichkeit fern ab der 100% ausreichend sein.

Aber wie gesagt ich glaube ich hab mich da in was verrannt

25.02.2013, 14:43

HAL 9000

Auf diesen Beitrag antworten »

Du könntest zur Bestätigung - oder vielleicht auch Widerlegung Augenzwinkern

Augenzwinkern

- eine Simulation anwerfen: 7 Milliarden Menschen passen bei "1 Bit pro Mensch" in ein Feld der Größe 835 MByte, das ist auf einem gut ausgestatteten modernen PC kein Problem, zumindest in C/C++.

25.02.2013, 15:25

Mystic

Auf diesen Beitrag antworten »

Ich hätte mir jetzt dazu Folgendes überlegt, wieder unter der Voraussetzung, dass es um n Personen geht, wovon jeder genau k der anderen Personen Hilfestellung leistet und k<<n. Dann ist doch die gesuchte Wahrscheinlichkeit P(A) näherungsweise gegeben durch

$\begin{eqnarray*} P(A) \approx 1-(1-\frac kn)^n \approx 1-e^{-k} \end{eqnarray*}$

oder bin ich komplett am falschen Dampfer? verwirrt

verwirrt

25.02.2013, 15:30

HAL 9000

Auf diesen Beitrag antworten »

Du bist insofern auf dem falschen Dampfer, dass du damit nur $\begin{eqnarray*} P(A_i) \end{eqnarray*}$ berechnest bzw. abschätzt, nicht aber das tatsächlich gesuchte $\begin{eqnarray*} P(A) \end{eqnarray*}$ - siehe mein obiger Beitrag von heute, 10:29.

25.02.2013, 15:45

2phil.05.phil

Auf diesen Beitrag antworten »

Big Laugh

eigentlich eine wirklich coole Idee... leider kann ich kein C/C# ... aber ich kann es ja mal in MATLAB versuchen und mit Hilfe der wundervollen codegen-Funktion spuckt er mir ja den C-Code aus, damit ich eine Chance auf eine halbwegs erträgliche Laufzeit habe... denn nur in MATLAB wird es wohl nichts werden

25.02.2013, 15:46

Mystic

Auf diesen Beitrag antworten »

@HAL

Ja, sorry, hätte mir das besser durchlesen sollen... unglücklich

unglücklich

Zitat:

Original von 2phil.05.phil
Big Laugh

Big Laugh

eigentlich eine wirklich coole Idee... leider kann ich kein C/C# ...

Du kannst ja anfangs n noch variabel halten und kleinere Werte von n ausprobieren, einfach um nur mal zu sehen, wie gut die Ergebnisse mit den vorgesagten übereinstimmen... Augenzwinkern

Augenzwinkern

25.02.2013, 16:08

HAL 9000

Auf diesen Beitrag antworten »

Wenn man wirklich genau rechnen möchte, dann geht das (wie kann es anders sein) über die Siebformel:

$\begin{eqnarray*} P(A) = 1-P(A^c) = 1-P\left( \bigcup\limits_{i=1}^n A_i^c \right) = \sum_{j=0}^{n-k-1} (-1)^j \binom{n}{j} \left( \frac{\binom{n-1-j}{k}}{\binom{n-1}{k}} \right)^{n-j} \left( \frac{\binom{n-j}{k}}{\binom{n-1}{k}} \right)^j \end{eqnarray*}$ .

Allerdings heißt es da ziemlich aufzupassen, wenn man da zwecks Auswertung $\begin{eqnarray*} n=7\,000\,000\,000 \end{eqnarray*}$ einsetzen will, es kommt da zu ziemlich heftigen numerischen Auslöschungseffekten bei Anwendung dieser Formel: Beim "mittleren" Summanden etwa taucht als Faktor der Binomialkoeffizient

$\begin{eqnarray*} \binom{7\,000\,000\,000}{3\,500\,000\,000} \approx 4.2\cdot 10^{2107209964} \end{eqnarray*}$

auf, aber als Endergebnis muss jedoch ein Wahrscheinlichkeitswert stehen, also ein Wert zwischen 0 und 1. Teufel

Teufel

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

EDIT: Ich hab mal für kleinere $\begin{eqnarray*} k,n \end{eqnarray*}$ die drei Formeln

$\begin{eqnarray*} p_0(k,n) = \sum_{j=0}^{n-k-1} (-1)^j \binom{n}{j} \left( \frac{\binom{n-1-j}{k}}{\binom{n-1}{k}} \right)^{n-j} \left( \frac{\binom{n-j}{k}}{\binom{n-1}{k}} \right)^j \end{eqnarray*}$

$\begin{eqnarray*} p_1(k,n) = \left( 1 - \left( 1 - \frac{k}{n-1} \right)^{n-1} \right)^n \end{eqnarray*}$

$\begin{eqnarray*} p_2(k,n) = \left( 1 - e^{-k} \right)^n \end{eqnarray*}$

ausprobiert:

$\begin{eqnarray*} p_0(5,100) \approx 0.5475 \end{eqnarray*}$

$\begin{eqnarray*} p_1(5,100) \approx 0.5527 \end{eqnarray*}$

$\begin{eqnarray*} p_2(5,100) \approx 0.5086 \end{eqnarray*}$

Diese und andere Werte legen den Schluss nahe, dass man mit $\begin{eqnarray*} p_1 \end{eqnarray*}$ doch deutlich besser fährt als mit $\begin{eqnarray*} p_2 \end{eqnarray*}$ . Díe eigentlich exakte Formel $\begin{eqnarray*} p_0 \end{eqnarray*}$ ist ja leider für exorbitant große $\begin{eqnarray*} n \end{eqnarray*}$ numerisch kaum beherrschbar (s.o.).

Die gute Nachricht ist aber, dass sich etwa $\begin{eqnarray*} p_1(24,7\cdot 10^9) \end{eqnarray*}$ und $\begin{eqnarray*} p_2(24,7\cdot 10^9) \end{eqnarray*}$ kaum noch unterscheiden, der Unterschied ist kleiner als $\begin{eqnarray*} 10^{-8} \end{eqnarray*}$ . Es lässt sich vermuten, dass das auch für den Abstand zwischen $\begin{eqnarray*} p_0(24,7\cdot 10^9) \end{eqnarray*}$ und $\begin{eqnarray*} p_1(24,7\cdot 10^9) \end{eqnarray*}$ zutrifft.

26.02.2013, 02:12

2phil.05.phil

Auf diesen Beitrag antworten »

Vielen Dank für die tollen Lösungen. Nach der Lösung mit der Siebfunktion habe ich gesucht, die kann ich nachvollziehen. Die Näherungen noch nicht so, aber du hast natürlich völlig recht unter den Bedingungen sind sie super.

Ich entschuldige mich daher aufrichtig für meine unberechtigten Zweifel! Bauchgefühl hat halt in der Mathematik nichts zu suchen Big Laugh

Big Laugh

Nun kann ich wieder ruhig schlafen und brauche nur jeden Menschen davon zu überzeugen in seinem Leben 30 gute Taten zu vollbringen (na wenn's weiter nichts ist Big Laugh

Big Laugh

), danke!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »