Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Funktionsvorschrift finden
Thema eröffnet 2018-09-23 11:53 von mhipp
Druckversion
Druckversion
Seite 2   [1 2]   2 Seiten
Autor
Schule J Funktionsvorschrift finden
MartinN
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 05.08.2016
Mitteilungen: 1198
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.40, eingetragen 2018-09-28


@mhipp
Du weißt schon, dass nicht \(P(n) = A(n+2)\) gesucht ist (also du Wahrscheinlichkeit in einer speziellen Runde zu gewinnen) - sondern \(\sum{A(n)}\), also wie wahrscheinlich es ist, dass Max insgesamt gewinnt :D

Mein Programm start1 spuckt nach 2000 Runden für die Summe 0.7878787878787868 aus.
JavaScript
function start1 () {
  var Varu = 1; Vara = 0; Varo = 0; VarA = 0; VarO = 0; VarS = 1; sum = 0
  for (n = 1; n <= 2000; n++) {
    Varu = 3*VarS/4
    VarA = Vara/6
    VarO = Varo/12
    Vara = (VarS-Vara)/6
    Varo = (VarS-Varo)/12
    VarS = Varu+Vara+Varo
    sum += VarA
    document.write(n+": "+VarA+" | "+VarS+" | "+VarO+"<br>")
  }
  document.write(sum)
}


Bzw:
\(\sum A(n) = \sum f_1 b_1^n (\frac{11}{6b_1} + \frac{1}{8b_1^2} − 2) + f_2 b_2^n (\frac{11}{6b_2} + \frac{1}{8b_2^2} − 2) + f_3 b_3^n (\frac{11}{6b_3} + \frac{1}{8b_3^2} − 2)\\
= \frac{f_1}{1-b_1} (\frac{11}{6b_1} + \frac{1}{8b_1^2} − 2) + \frac{f_2}{1-b_2} (\frac{11}{6b_2} + \frac{1}{8b_2^2} − 2) + \frac{f_3}{1-b_3} (\frac{11}{6b_3} + \frac{1}{8b_3^2} − 2)\)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1720
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.41, eingetragen 2018-09-28


2018-09-28 07:31 - mhipp in Beitrag No. 38 schreibt:
Hallo.
Ich prüfe mein P(5) = 15475/746496 nochmal.
Rätsel kommt von
Da wird also auch das System aus #15 gebastelt.  😁



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
mhipp
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 30.08.2018
Mitteilungen: 299
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.42, vom Themenstarter, eingetragen 2018-09-28


@Martin vielen Dank für deine ganze Mühe. Leider kann ich mit Programmsprache nicht viel anfangen. Ist es möglich, dieses Programm in eine rekursive Funktion umzuwandeln? Wenn ich dann noch die Verbindung zu meinem Problem finden, wäre dieses Thema geklärt :-)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.43, eingetragen 2018-09-28


2018-09-27 23:21 - tactac in Beitrag No. 37 schreibt:
@mhipp: Deine Zahlen kann ich jedenfalls nachvollziehen.
...

Richtig muss es lauten: "... nur die ersten 3 Zahlen kann man damit nachvollziehen!"
{nicht 15475/746496 sondern 8021/373248 hatte ich ja bereits begründet}

Und wer sich wundert, warum die Zahlen von Beitrag 38 nicht mit Beitrag 28 übereinstimmen:
tactac hat
1. andere Startwerte Init: aB[0]=0;aC[0]=1/6;aD[0]=0;
2. andere Iteration: aB[i+1]=aB[i]*3/4+aC[i]/6+aD[i]/12;aC[i+1]=aB[i]*3/4+0/6+aD[i]/12;aD[i+1]=aB[i]*3/4+aC[i]/6;
also +0/6 statt +1/6 aus Beitrag 15!

Wenn man neben 0/6 auch noch Init: aB[0]=1/36;aC[0]=0;aD[0]=1/36;
anpasst, stimmen die Werte und Index mit MartinN's expliziter Folge
aus Beitrag 35 exakt überein!

Nun zur eigentlichen Aufgabe, die uns so lange verschwiegen wurde:
Quelle der Aufgabe

Dort interessiert sich keiner für Einzelwahrscheinlichkeiten, sondern für die Summen bis zum eingeschwungenen Zustand - auch Grenzwert genannt.
Wie MartinN bereits richtig erkannte, ist das die Summe
der Folge P(n) - also aD[i] aus Beitrag 35.

Da nur der Grenzwert interessiert, kann man auch einfach
die Iteration aus Beitrag 28 (also mit dem +1/6)
heranziehen - was ich bereits dort schon bemerkte- , und bekommt 0.7878787878787...=26/33.

Wie auf der Quell-Seite angegeben, kann man bei Grenzwerten auch einfach:
We can substitute the third equation into the second:
w = (3/4)d + (1/6) + (1/12)((3/4)d + (1/6)(w))
w = (3/4)d + (1/6) + (1/12)(3/4)d + (1/12)(1/6)(w)
 (71/72)w = (39/48)d + 1/6
w = (117/142)d + 12/71
... und kommt direkt ohne Startwerte & Iterationen zu d = 26/33.

Für mich war neu, dass WolframAlpha diese per Matrix-Form berechnen kann:
Wolfram's Matrix Syntax



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
mhipp
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 30.08.2018
Mitteilungen: 299
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.44, vom Themenstarter, eingetragen 2018-09-28


Mir ist schon klar wie die Lösung in diesem Video geht, aber ich habe es wie gesagt bevor ich die Lösung gesehen habe anders versucht und würde aus reinem Interesse gerne wissen, die ich diese beenden könnte ;-)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.45, eingetragen 2018-09-28


2018-09-28 13:02 - mhipp in Beitrag No. 42 schreibt:
@Martin vielen Dank für deine ganze Mühe. Leider kann ich mit Programmsprache nicht viel anfangen. Ist es möglich, dieses Programm in eine rekursive Funktion umzuwandeln? Wenn ich dann noch die Verbindung zu meinem Problem finden, wäre dieses Thema geklärt :-)

Zwar habe ich alles schon gesagt, aber da Du weiterhin den Iterationsrechner ignorierst, hier einfach Klicken:
hier
und dann Button "Berechnungen starten" fertig. Einfacher geht's doch wirklich nicht!
2 Algorithmen per Iterationsrechner

Die ganze Lösung in 2 Zeilen, die JEDE Programmiersprache versteht:
Init: aB[0]=1/36;aC[0]=0;aA[0]=1/36;
Iteration: aB[i+1]=aB[i]*3/4+aC[i]/6+aA[i]/12; aC[i+1]=aB[i]*3/4+0/6+aA[i]/12; aA[i+1]=aB[i]*3/4+aC[i]/6;

Das aA statt aD hatte ich nur wegen der Aufsummierung in Spalte aD
und das if(i>0) aB[i-1]=aB[i-1].toString()+'='+GetBruchNenner(aB[i-1],9e10)+addstr(' ',max(9-i,0));
ist nur für zusätzliche Anzeige des Bruches.

Selbst wenn Du nichts mit Arrays anfangen kannst, schreibe einfach statt
aB[...]=... ein  B=... und am Ende jeder Iteration ein Print B
dann kommt das selbe raus:

Init: B=1/36;C=0;D=1/36;
Iteration:  merkC=C;merkD=D;C=B*3/4+D/12; D=B*3/4+merkC/6; B=B*3/4+merkC/6+merkD/12; print B



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1720
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.46, eingetragen 2018-09-28

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\)
@HyperG wegen dem fehlenden Sechstel: In #15 ging es wirklich um die totalen Wahrscheinlichkeiten, nicht nur um solche für Spiele bestimmter Länge.
Ein nahe verwandtes Problem lässt sich so formulieren. Man betrachte den Automaten
<math>\begin{tikzpicture}[->,>=stealth",shorten >=1pt,auto,node distance=2.8cm,
semithick]
\node[state] (p)                    {$p$};
\node[state] (q) [below left  of=p] {$q$};
\node[state] (r) [below right of=p] {$r$};
\node[state] (1) [below of=q]       {$1$};
\node[state] (0) [below of=r]       {$0$};

\path (p) edge [loop above] node {$p$} (p)
edge              node {$q$} (q)
edge [bend left]  node {$r$} (r)
(q) edge [bend left]  node {$p$} (p)
edge              node {$q$} (1)
edge              node {$r$} (r)
(r) edge              node {$p$} (p)
edge [bend left]  node {$q$} (q)
edge              node {$r$} (0);
\end{tikzpicture}</math>

Jetzt sei
$P(n)$ die Menge aller Wörter über $\Sigma=\{p,q,r\}$ der Länge $n$, die der Automat akzeptiert, wenn man $p$ als Startzustand nimmt und 1 als einzigen Endzustand. Analog für Q, R, I und O (1 ist immer Endzustand). Die Wörter in $P(n)$ "sind" gerade die von Max gewonnenen Spiele mit $n$ Runden.
Es ergeben sich nach 3 Sekunden Überlegen die Gleichungen
$P(0) = \emptyset; P(n+1) = p\cdot P(n) \cup q\cdot Q(n) \cup r\cdot R(n)$,
$Q(0) = \emptyset; Q(n+1) = p\cdot P(n) \cup q\cdot I(n) \cup r\cdot R(n)$,
$R(0) = \emptyset; R(n+1) = p\cdot P(n) \cup q\cdot Q(n) \cup r\cdot O(n)$,
$I(0) = \{\varepsilon\}; I(n+1) = \emptyset$,
$O(n) = \emptyset$.

Es ergibt sich weiter, wenn man sich bei $P,Q,R$ nur für Wörter der Länge > 0 interessiert, und "vereinfacht" (dass $I(0)=\{\varepsilon\}$ ist dabei aber wichtig) dann ein Analog der Listen aus meinem Haskell-Programm (ich bekräftige nochmal: in den folgenden Gleichungen ist immer $n\geq 1$):
$P(1) = \emptyset; P(n+1) = p\cdot P(n) \cup q\cdot Q(n) \cup r\cdot R(n)$,
$Q(1) = \{q\}; Q(n+1) = p\cdot P(n) \cup r\cdot R(n)$,
$R(1) = \emptyset; R(n+1) = p\cdot P(n) \cup q\cdot Q(n)$.

Nun das Analog von #15:
$P^*$ sei die Menge *aller* Wörter über $\Sigma$, die akzeptiert werden, wenn $p$ Startzustand ist und $1$ einziger Endzustand; analog für $Q^*$ etc. Hier ergibt sich
$P^* = p\cdot P^* \cup q\cdot Q^* \cup r\cdot R^*$,
$Q^* = p\cdot P^* \cup q\cdot I^* \cup r\cdot R^*$,
$R^* = p\cdot P^* \cup q\cdot Q^* \cup r\cdot O^*$,
$I^* = \{\varepsilon\}$,
$O^* = \emptyset$.
Bzw., "vereinfacht":
$P^* = p\cdot P^* \cup q\cdot Q^* \cup r\cdot R^*$,
$Q^* = p\cdot P^* \cup \{q\} \cup r\cdot R^*$,
$R^* = p\cdot P^* \cup q\cdot Q^*$.

Wie kommt man von hier zu etwas mit Zahlen statt Wortmengen? Nun, wir tun so, als hätten Buchstaben, Wörter und Wortmengen eine "Semantik", und die ist eine Zahl - nämlich eine Wahrscheinlichkeit. Die Semantik von Buchstaben $\sem - \colon \Sigma \to \IR$ ist vorgegeben: $\sem p = \frac 34$, $\sem q = \frac 16$, $\sem r = \frac 1 {12}$. Bei Worten ist die Semantik $\sem -\colon \Sigma^* \to \IR$ das Produkt der Buchstabensemantik: $\sem {(x_1,\ldots,x_n)} = \sem{x_1}\cdot\ldots\cdot\sem{x_n}$. Und bei Wortmengen summiert die Semantik-Funktion $\sem-\colon \mathcal P(\Sigma^*) \to \IR$ einfach auf: $\sem L := \sum_{w\in L}\sem w$. (Fragen der Konvergenz ignorieren wir erstmal; eine Wortmenge kann ja auch unendlich sein, und da würde das wichtig werden.)
Für disjunkte Wortmengen $L,M$ haben wir dann $\sem{L\cup M} = \sem L + \sem M$,  und für Buchstabenjuxtaposition von $x\in \Sigma$ an eine Wortmenge $L$: $\sem {x \cdot L} = \sem x \cdot \sem L$.

Damit hat man z.B.
$\sem{P^*} = \sem{p\cdot P^* \cup q\cdot Q^* \cup r\cdot R^*}
           = \sem p\cdot \sem{P^*} + \sem q\cdot \sem{Q^*} + \sem r\cdot \sem{R^*}$ und kann daher zusammen mit den anderen Gleichungen schon $\sem{P^*}$ etc. ausrechnen, ohne $P^*$ ausrechnen zu müssen.  😁
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
mhipp hat die Antworten auf ihre/seine Frage gesehen.
mhipp hat selbst das Ok-Häkchen gesetzt.
mhipp wird per Mail über neue Antworten informiert.
Seite 2Gehe zur Seite: 1 | 2  
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]