Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Erstaunliches

Erstaunliches

Universität / Fachhochschule

Tags: Wahrscheinlichkeit

Sukomaki aktiv_icon

19:17 Uhr, 21.09.2023

Liebe Community,

als ich noch auf der Universität war, wurde uns folgende Aufgabe gestellt :

Berechnen Sie die Grenzwerte der Wahrscheinlichkeiten, dass

a) eine beliebige Abbildung

{1, 2, 3, \dots, n} \to {1, 2, 3, \dots, n}

fixpunktfrei ist

b) eine Permutation fixpunktfrei ist.

zu a)

Das ist relativ einfach :

Für jedes

a

gibt es für

f (a)

gerade

n - 1

Zahlen, so dass kein Fixpunkt entsteht.

W (f (a) \neq a) = \frac{n - 1}{n}

Die Wahrscheinlichkeiten sind unabhängig voneinander. Daraus folgt

W ((f (1) \neq 1) \land (f (2) \neq 2) \land (f (3) \neq 3) \land \dots) = W (f (1) \neq 1) \cdot W (f (2) \neq 2) \cdot W (f (3) \neq 3) \cdot \dots

Die Wahrscheinlichkeit, dass eine Abbildung fixpunktfrei ist, beträgt demnach

(\frac{n - 1}{n})^{n}

Der Grenzwert für

n \to \infty

ist

lim_{n \to \infty} {(\frac{n - 1}{n})}^{n} = lim_{n \to \infty} {(1 - \frac{1}{n})}^{n} = lim_{n \to \infty} {(1 + \frac{(- 1)}{n})}^{n} = e^{- 1} = \frac{1}{e} \approx 0.36788

zu b)

Zuerst betrachte ich, was herauskommt, wenn ich ein

f (a) = a

festsetze und
die restlichen

f

-Werte beliebig wähle (natürlich im Rahmen einer Permutation).

Für

a

gibt es

n

Möglichkeiten, und für die Verbleibenden

(n - 1)!

Also ist :

F_{1} :=

1

Fixpunkt,

n - 1

beliebige

= (\binom{n}{1}) \cdot (n - 1)!

Dabei zähle ich allerdings

f (a) = a, f (b) = b

doppelt. D.h. um die Anzahl derjenigen

f

, die nicht fixpunktfrei sind, zu bestimmen muss ich zwei Zahlen aus

{1, 2, 3, \dots, n - 1, n}

wählen (

(\binom{n}{2})

Möglichkeiten), sie mit der Anzahl der restlichen Möglichkeiten (

(n - 2)!

)
multiplizieren und von

F_{1}

abziehen.

F_{2} :=

2

Fixpunkte,

n - 2

beliebige

= (\binom{n}{2}) \cdot (n - 2)!

Dadurch habe ich aber zu viel abgezogen. Nämlich solche

f

mit

f (a) = a, f (b) = b, f (c) = c

.

Die muss ich wieder draufrechnen.

F_{3} :=

3

Fixpunkte,

n - 3

beliebige

= (\binom{n}{3}) \cdot (n - 3)!

So geht das hin und her bis zu

F_{n - 1} :=

n - 1

Fixpunkte,

n - (n - 1)

beliebige

= (\binom{n}{n - 1}) \cdot (n - (n - 1))! = (\binom{n}{1}) \cdot 1! = n

F_{n} :=

n

Fixpunkte,

0

beliebige

= (\binom{n}{n}) \cdot (n - n)! = 1 \cdot 0! = 1

Also ergibt sich für

#mehr als 0 Fixpunkte =

F_{1} - F_{2} + F_{3} - F_{4} + \dots = \sum_{j = 1}^{n} (\binom{n}{j}) \cdot (n - j)! \cdot (- 1)^{j - 1}

Fixpunktfrei ist nun die Anzahl aller Permutationen (

n!

) minus der Reihe über die alternierende Folge:

#genau 0 Fixpunkte =

n! - \sum_{j = 1}^{n} (\binom{n}{j}) \cdot (n - j)! \cdot (- 1)^{j - 1} =

n! + \sum_{j = 1}^{n} (\binom{n}{j}) \cdot (n - j)! \cdot (- 1)^{j} =

\sum_{j = 0}^{n} (\binom{n}{j}) \cdot (n - j)! \cdot (- 1)^{j} =

\sum_{j = 0}^{n} \frac{n!}{(n - j)! j!} (n - j)! (- 1)^{j} =

\sum_{j = 0}^{n} \frac{n!}{j!} (- 1)^{j}

Daraus folgt für die Wahrscheinlichkeit(genau 0 Fixpunkte) :

W = \frac{1}{n!} \sum_{j = 0}^{n} (- 1)^{j} \frac{n!}{j!} = \sum_{j = 0}^{n} (- 1)^{j} \cdot \frac{1}{j!}

und für den Grenzwert mit Taylor-Reihe:

lim_{n \to \infty} \sum_{j = 0}^{n} \frac{(- 1)^{j}}{j!} = (lim_{n \to \infty} \sum_{j = 0}^{n} \frac{x^{j}}{j!}) (- 1) = e^{- 1} = \frac{1}{e} \approx 0.36788

Die Grenzwerte sind gleich.

Es liegt hier das bewundernswerte Phänomen vor, dass eine Eigenschaft einer Menge sich auf eine Untermenge überträgt. Noch erstaunlicher finde ich es, dass diese Eigenschaft sich auf verschiedene Wege berechnen lässt.

Wenn ich hiermit auch nur jemandes Interesse an der Mathematik gesteigert habe, dann hat sich die Mühe gelohnt.

Sollte ich hingegen jemanden verschreckt haben, tut mir das aufrichtig leid.

Gruß
Sukomaki

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

HAL9000

20:00 Uhr, 21.09.2023

Freut mich, dass dich dieses interessante Problem so fasziniert hat. Das Problem der fixpunktfreien Permutationen ist (zumindest im deutschen Sprachraum) auch als "Wichtelproblem" bekannt - kannst du mal googeln. Schlägt also regelmäßig in der Vorweihnachtszeit immer wieder auf - jetzt hier im September ist das eher ungewöhnlich. :-D)

Mit demselben "Prinzip von Inklusion und Exklusion" kann man übrigens auch die Wahrscheinlichkeit für GENAU

k

Fixpunkte berechnen, die ist gleich

p_{n, k} = \frac{1}{k!} \cdot \sum_{j = 0}^{n - k} \frac{{(- 1)}^{j}}{j!}

gültig für alle

k = 0, 1, \dots, n

. Im Grenzprozess

n \to \infty

bekommt man mit

p_{k} := lim_{n \to \infty} p_{n, k} = \frac{1}{k!} e^{- 1}

schlicht die Poisson-Verteilung mit Parameter 1.

Sukomaki aktiv_icon

15:46 Uhr, 24.09.2023

Danke für die Formel für genau k Fixpunkte.

Mit Poisson habe ich mich (inspiriert von Deiner Bemerkung und Wikipedia) die Tage beschäftigt, um Fußball-Ergebnisse vorherzusagen.

Tatsächlich ging eines der Spiele Stuttgart - Darmstadt 3:1 aus.

Wie auch immer :

Es ist ja so, dass das Prinzip der Inklusion - Exklusion auch verwendet wird, um die Mächtigkeit von Mengen zu bestimmen.

Z.B. ist

∣ A \cup B \cup C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣

Ich finde es schon interessant, dass diese Beziehung zwischen Wahrscheinlichkeiten und Mengen existiert.

HAL9000

09:57 Uhr, 25.09.2023

> Tatsächlich ging eines der Spiele Stuttgart - Darmstadt 3:1 aus.

Oh, da fehlen mir als Leser wohl ein paar Zwischengedanken, damit ich verstehen kann, inwieweit das mit Poisson zu tun hat. ;-)

> Ich finde es schon interessant, dass diese Beziehung zwischen Wahrscheinlichkeiten und Mengen existiert.

Interessant Ja, erstaunlich Nein: Im einem Laplaceschen Wahrscheinlichkeitsraum ist nun mal

P (A) = \frac{∣ A ∣}{∣ Ω ∣}

, womit diese Verbindung zwischen Prinzip von Inklusion und Exklusion (für Mengen) und Siebformel (für Wahrscheinlichkeiten) direkt folgt. Die Siebformel ist in gewisser Weise etwas allgemeiner, da sie auch in nicht-laplaceschen W-Räumen gilt.

Sukomaki aktiv_icon

11:55 Uhr, 25.09.2023

Was hat Poisson mit Fußball zu tun?

Nun die Poisson-Verteilung

P_{λ} (k) = \frac{λ^{k}}{k!} e^{- λ}

hat ja ihren Peak in der Nähe von

λ

.

(Zu beachten ist, dass Poisson eine diskrete Verteilung ist)

Wenn zwei Poisson-Verteilungen

P_{λ_{1}} (k_{1}) = \frac{λ_{1}^{k_{1}}}{k_{1}!} e^{- λ_{1}}

und

P_{λ_{2}} (k_{2}) = \frac{λ_{2}^{k_{2}}}{k_{2}!} e^{- λ_{2}}

(EDIT :

λ_{1}^{k_{1}}

statt

λ_{1}^{k}

und

λ_{2}^{k_{2}}

statt

λ_{2}^{k}

)

vorliegen, dann hat das Produkt

P_{λ_{1}} (k_{1}) \cdot P_{λ_{2}} (k_{2})

seinen Peak in der Nähe von

(λ_{1}, λ_{2})

.

In diesem Fall sind

λ_{1}

und

λ_{2}

die Tore, die Club1 und Club2 jeweils durchschnittlich erzielt haben (Mein Programm berücksichtigt auch die jeweiligen Gegentore).

Das Ergebnis soll ausgedrückt werden in Begriffen von

(k_{1}, k_{2})

.

Mein Algorithmus berechnet durch Ausprobieren von

(k_{1}, k_{2})

die Wertigkeit von

P_{λ_{1}} (k_{1}) \cdot P_{λ_{2}} (k_{2})

.

Das Maximum über

W e r t i g k e i t (k_{1}, k_{2})

entspricht dem Endergebnis.

Also die Stelle wo

P_{λ_{1}} (k_{1}) \cdot P_{λ_{2}} (k_{2})

sein Maximum annimmt, nicht das Maximum selbst.
_________________________________________________________________________

Als Kind habe ich mir eben diese Frage auch schon gestellt :

Wenn

A

gegen

B

a_{b} : b

spielt und

A

gegen

C

a_{c} : c

spielt.

Wie spielt dann

B

gegen

C

?

Mein naiver Ansatz war :

B

gegen

C

spielt

\frac{b}{a_{b}} : \frac{a_{c}}{c}

wobei die zwei Zahlen gekürzt sein sollen.

(ich hoffe, ich habe diese Formel richtig in Erinnerung)

Aber bei Spielen zu Null gibt klappt diese Methode nicht.

Abgesehen davon müssen die Teams erst mal gegeneinander gespielt haben.

Natürlich ist die Variante mit Poisson erfolgversprechender.
_________________________________________________________________________

Mit den Resultaten

Stuttgart - Darmstadt 3:1
Augsburg - Mainz 2:1

lag mein Programm richtig.

Von den Punkten her lag mein Programm richtig bei

München - Bochum 7:0 (2:0)
Mönchengladbach - Leipzig 0:1 (1:3)
Leverkusen - Heidenheim 4:1 (2:1)
Berlin - Hoffenheim 0:2 (1:2)

Desweiteren hat sich das Programm um höchstens ein Tor geirrt bei

Frankfurt - Freiburg 0:0 (1:0)
Dortmung - Wolfsburg 1:0 (1:1)
Bremen - Köln 2:1 (1:1)

Das ändert natürlich nichts an der Tatsache, dass es im Fußball immer wieder mal zu Überraschungen kommt.

_________________________________________________________________________

Den Zusammenhang zwischen Prinzip der Inklusion/Exklusion und Siebformel schaue ich mir noch genauer an.

HAL9000

16:01 Uhr, 25.09.2023

Ich bleib mal noch bei der Fixpunktzählerei: Sei

X_{n}

die Zufallsgröße Anzahl Fixpunkte einer zufälligen Permutation von

{1, 2, \dots, n}

, dann haben wir dessen Verteilung

P (X_{n} = k) = p_{n, k}

mit dem oben angegebenen

p_{n, k}

schon bestimmt.

Wie lauten nun Erwartungswert und Varianz von

X_{n}

? Natürlich könnte man über

E (X_{n}) = \sum_{k = 0}^{n} k \cdot p_{n, k}

sowie

E (X_{n}^{2}) = \sum_{k = 0}^{n} k^{2} \cdot p_{n, k}

gehen, aber das ist eine ziemlich langwierige Rechnerei. Es gibt aber auch einfachere Berechnungswege...

Sukomaki aktiv_icon

16:33 Uhr, 25.09.2023

Um auf das Thema dieses Threads zurück zu kommen, habe ich hier drei Leckerbissen aus der Welt der höheren Mathematik :
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Manche Funktionen sind überall stetig, aber tatsächlich nirgendwo differenzierbar.

Konstruierbar ist eine solche z.B. mit Hilfe der Tatsache, dass die geometrische Reihe über

\frac{1}{2}

konvergiert, während die geometrische Reihe über

\frac{3}{2}

divergiert.

In Worten lautet eine solche Funktion

f := \sum_{j = 0}^{\infty} \frac{1}{2^{j}} \cdot \cos (3^{j} \cdot x)

(siehe Anhang)

f (x)

wird betragsmäßig von

1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots = 2

majorisiert, konvergiert und ist somit stetig.

Die Ableitung ist gegeben durch

f ʹ (x) = - \sum_{j = 0}^{\infty} {(\frac{3}{2})}^{j} \cdot \sin (3^{j} \cdot x)

. Dieser Ausdruck divergiert.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

* Es gibt eine nicht-triviale Funktion, die überabzählbar viele Nullstellen besitzt.

Ausgangspunkt ist das Fraktal namens Cantor-Menge.

Aus einer Strecke wird das mittlere Stück entfernt. Aus den übrigen zwei Strecken wird wieder das mittlere Stück entfernt, aus den vier neuen Strecken wiederum... (siehe Anhang)

Wo kommen die Nullstellen ins Spiel?

Nun, ich versehe die Cantor-Menge mit einem Abstandsmaß. Dieses besagt, wie weit ein

x

von der Cantor-Menge entfernt ist. Gut zu sehen ist das bei dem Zacken in der Mitte. Liegt

x

links von der Mitte, ist es näher am linken Teil der Cantor-Menge und liegt

x

rechts von der Mitte, ist es näher am rechten Teil der Cantor-Menge.

Da die Cantor-Menge überabzählbar ist, gibt es auch überabzählbar viele

r \in ℝ

, denen das Abstandsmaß Null innewohnt. Ergo, hat die cantorsche Abstandsfunktion überabzählbar viele Nullstellen. Und ist dazu noch stetig.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

* Auch erstaunlich ist das Banach-Tarski-Paradoxon :

Eine Kugel wird auf eine komplizierte Weise - mit Hilfe von Drehungen und Verschiebungen - so zerlegt, dass sich aus den Teilen zwei Kugeln mit exakt dem gleichen Volumen wie der Ausgangskugel erschaffen lassen. So weit ich weiß kann das Verfahren dann auf die zwei Kugeln angewendet werden, um vier Kugeln zu erschaffen, daraus wiederum acht u.s.w.

LG
Sukomaki

Sukomaki aktiv_icon

17:00 Uhr, 25.09.2023

@Hal9000

Ich wette, Du weißt bereits, dass so wohl

E (X_{n})

wie auch

V a r (X_{n})

genau - unabhängig von

n

- gleich Eins sind. Damit hätte ich insbesondere für größere

n

nicht gerechnet. Von daher flasht mich das jetzt ein wenig. :-D)

Mit Rencontres-Zahlen und erzeugenden Funktionen scheint die Berechnung ja einigermaßen überschaubar zu sein.

siehe auch : de.wikipedia.org/wiki/Zuf%C3%A4llige_Permutation#Eigenschaften

HAL9000

09:25 Uhr, 26.09.2023

Ich hatte an folgenden Weg gedacht: Es ist

X_{n} = \sum_{j = 1}^{n} Y_{n, j}

, wobei

Y_{n, j}

die Indikator-Zufallsvarible dafür kennzeichnet, dass an Position

j

ein Fixpunkt vorliegt. Dann gilt wegen

E (Y_{n, j}) = P (Y_{n, j} = 1) = \frac{(n - 1)!}{n!} = \frac{1}{n}

und damit

E (X_{n}) = \sum_{j = 1}^{n} E (Y_{n, j}) = \sum_{j = 1}^{n} \frac{1}{n} = 1

.

Weiterhin ist

E (Y_{n, j}^{2}) = E (Y_{n, j}) = \frac{1}{n}

sowie

E (Y_{n, i} Y_{n, j}) = P (Y_{n, i} = 1, Y_{n, j} = 1) = \frac{(n - 2)!}{n!} = \frac{1}{n (n - 1)}

für

i \neq j

im Fall

n \geq 2

, damit folgt

E (X_{n}^{2}) = \sum_{i = 1}^{n} \sum_{j = 1}^{n} E (Y_{n, i} Y_{n, j}) = n \cdot \frac{1}{n} + n (n - 1) \cdot \frac{1}{n (n - 1)} = 2

,

daraus folgt

V (X_{n}) = E (X_{n}^{2}) - {(E (X_{n}))}^{2} = 2 - 1^{2} = 1

im Fall

n \geq 2

. Für

n = 1

gilt abweichend

V (X_{1}) = 0

- klar, denn dort liegt die konstante Zufallsgröße

X_{1} = 1

vor.

D.h., die Bestimmung dieser Charakteristiken gelingt ohne Kenntnis der relativ komplizierten Einzelwahrscheinlichkeiten.

Sukomaki aktiv_icon

15:36 Uhr, 26.09.2023

Warum schreibst Du zuerst

P (Y_{n, j} = 1) = \frac{(n - 1)!}{n!}

bzw.

P (Y_{n, i} = 1, Y_{n, j} = 1) = \frac{(n - 2)!}{n!}

?

Dass es in Folge dann heißen muss

\frac{1}{n}

bzw.

\frac{1}{n \cdot (n - 1)}

ist klar.

Den Rest verstehe ich soweit.

Die Doppelsumme sieht bei mir etwas komplizierter aus :

\sum_{i = 1}^{n} \sum_{j = 1}^{i - 1} \frac{1}{n \cdot (n - 1)} + \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} \frac{1}{n \cdot (n - 1)} + \sum_{i = 1}^{n} \sum_{j = i}^{i} \frac{1}{n} =

\sum_{i = 1}^{n} \frac{i - 1}{n \cdot (n - 1)} + \sum_{i = 1}^{n} \frac{n - i}{n \cdot (n - 1)} + \sum_{i = 1}^{n} \frac{1}{n} =

\sum_{i = 1}^{n} \frac{i - 1 + n - i}{n \cdot (n - 1)} + \sum_{i = 1}^{n} \frac{1}{n} =

\sum_{i = 1}^{n} \frac{n - 1}{n \cdot (n - 1)} + \sum_{i = 1}^{n} \frac{1}{n} =

\sum_{i = 1}^{n} \frac{1}{n} + \sum_{i = 1}^{n} \frac{1}{n} = 2

Ich kann das halt nicht alles so im Kopf rechnen wie Du. Schon krass :-D)

Wobei : Manchmal überspringe ich auch mehrere Schritte, was auch schon mal dazu führen kann, dass ich mich vertue.

Ah, Du benutzt den Verschiebungssatz. Damit habe ich schon gerechnet.

> D.h., die Bestimmung dieser Charakteristiken gelingt ohne Kenntnis der relativ komplizierten
Einzelwahrscheinlichkeiten.

Und das ist gut? :-)

Insgesamt - würde ich sagen - ist Dein Vorgehen mal wieder recht elegant.

HAL9000

18:40 Uhr, 26.09.2023

> Warum schreibst Du zuerst ...

Laplacesche Wahrscheinlichkeit, d.h. "Anzahl günstig / Anzahl aller Varianten":

Es gibt

n!

Permutationen. Wenn an einer festgelegten Position

j

ein Fixpunkt ist, dann gibt es an der Stelle nix mehr zu variieren, die restlichen

(n - 1)

Stellen können aber beliebig permutieren.

Analog dann bei zwei Fixpunkten an den Stellen

i

und

j

, was ja Ereignis

Y_{n, i} = Y_{n, j} = 1

ausdrückt - hier können nur noch die restlichen

(n - 2)

Stellen beliebig permutieren.

Sukomaki aktiv_icon

19:42 Uhr, 26.09.2023

Ich hätte ja so argumentiert, dass es einen günstigen Fall

π (j) = j

von

π (j) = k, k \in [1, \dots, n]

Fällen gibt, was sofort auf

\frac{1}{n}

führt.

Analog zu zwei Fixpunkten :

P (π (j) = j) = \frac{1}{n}

und

P (π (i) = i) = \frac{1}{n - 1}

(i \neq j)

Gibt im Produkt

P (Y_{n, j} = 1, Y_{n, i} = 1) = \frac{1}{n \cdot (n - 1)}

Sukomaki aktiv_icon

19:45 Uhr, 26.09.2023

Möchte jemand etwas zu den Leckerbissen aus der Welt der höheren Mathematik beitragen?

HAL9000

22:22 Uhr, 26.09.2023

P (π (i) = i) = \frac{1}{n - 1}

ist falsch - warum soll das bei

i

anders sein als bei

j

? Selbstverständlich gilt ebenso

P (π (i) = i) = \frac{1}{n}

.

Was du vermutlich meinst ist die BEDINGTE Wahrscheinlichkeit

P (π (i) = i ∣ π (j) = j) = \frac{1}{n - 1}

, das wäre korrekt.

Sukomaki aktiv_icon

08:20 Uhr, 27.09.2023

Ja, die bedingte Wahrscheinlichkeit. Die meine ich.

Sukomaki aktiv_icon

16:09 Uhr, 02.10.2023

Eine weitere Kuriosität aus dem mathematischen Kabinett :

Es gibt eine Formel, die die fünf wichtigsten Zahlen enthält.

Sie lautet :

e^{i π} + 1 = 0

Mein Tutor an der Uni hat dazu gesagt :

"Die könnt Ihr Euch einrahmen und aufhängen" :-)

Roman-22

16:57 Uhr, 02.10.2023

>

"Die könnt Ihr Euch einrahmen und aufhängen" :-)

Und dann betrachten wie ein Gemälde und darüber sinnieren, wie das Florian Freistetter hier macht:
www.spektrum.de/kolumne/die-schoenste-formel-der-welt/1461437

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1576417

1576028

	Status: nicht eingeloggt	Noch nicht registriert?