Python :: Aufgabe #107

1 Lösung Lösung öffentlich

Stochastisches Problem

Fortgeschrittener - Python von Veigar - 21.05.2016 um 15:01 Uhr
Liebe Menschen,
Wie mein Vorgänger ist mir ein mathematisches Problem eingefallen, es scheint nicht bekannt zu sein und mir ist bis jetzt selber noch keine "echte" Lösung in den Sinn gekommen, also nicht einfach eine sehr gute Annäherung.

Die Aufgabe: Eine Feder liegt in einen 1-Dimensionalen Raum a Längeineinheiten von der einen Kante A und b Längeneinheiten von der anderen Kante B entfernt und wird in jeder Zeiteinheit entweder in die eine Richtung oder in die andere Richtung geweht, vom Wind oder so.

Schreibe ein Programm das dir in einer sehr guten Annäherung oder "exakt" für jedes dieser Probleme in der Problemschar bestimmt wie wahrscheinlich es ist das es von der einen Seite oder von der anderen Seite fällt.

ps: das Bild ist ein Nebenprodukt meines eigenen Lösungsprogrammes gewesen, ich muss sagen ich habe mir die grafische Darstellung deutlich cooler erhofft, aber es zeigt ganz gut das Problem das es unendlich viele, in die Lösung einfließende "Äste"gibt.

es grüßt liebevoll und zärtlich wie immer,
Veigar

Lösungen:

vote_ok
von eulerscheZhl (5230 Punkte) - 25.05.2016 um 21:11 Uhr
Mal eine mathematische Lösung:
Sei p_x die Wahrscheinlichkeit, dass die Feder nach links abstürzt, wenn sie an Stelle x ist. Sei n die Gesamtbreite der Unterlage.
Dann ist p_0 = 1 (die Feder ist schon nach links abgestürzt) und p_(n+1) = 0 (die Feder ist nach rechts gefallen).
Dazwischen gilt: p_i = 0.5 * p_(i-1) + 0.5 * p_(i+1). Die Absturzwahrscheinlichkeit setzt sich also aus den Wahrscheinlichkeiten für die Abstürze vom Feld rechts bzw. links daneben zusammen.
Den Faktor 0.5 kann man anpassen (stärkerer Wind von rechts), in Summe müssen die Faktoren aber 1 ergeben.

Für einen Untergrund der Breite 5 gibt das also folgendes Gleichungssystem:

Konsolenausgabe:

   1*p1 -0.5*p2 +  0*p3 +  0*p4 +  0*p5 = 0.5
-0.5*p1 + 1*p2 -0.5*p3 + 0*p4 + 0*p5 = 0
0*p1 -0.5*p2 + 1*p3 -0.5*p4 + 0*p5 = 0
0*p1 + 0*p2 -0.5*p3 + 1*p4 -0.5*p5 = 0
0*p1 + 0*p2 + 0*p3 -0.5*p4 + 1*p5 = 0


Das zu Lösen ist eine andere Aufgabe (Lösen eines linearen Gleichungssystems), das spare ich mir an dieser Stelle.

Möchte man wissen, wie lange es dauert, bis die Feder herunterfällt, muss man das System nur leicht ändern:
t_0 = t_(n+1) = 0 (die Feder ist schon gefallen)
t_i = 0.5 * t_(i-1) + 0.5 * t_(i+1) + 1. Die +1 kommt, weil das Bewegen einen Schritt kostet.

Konsolenausgabe:

   1*t1 -0.5*t2 +  0*t3 +  0*t4 +  0*t5 = 1
-0.5*t1 + 1*t2 -0.5*t3 + 0*t4 + 0*t5 = 1
0*t1 -0.5*t2 + 1*t3 -0.5*t4 + 0*t5 = 1
0*t1 + 0*t2 -0.5*t3 + 1*t4 -0.5*t5 = 1
0*t1 + 0*t2 + 0*t3 -0.5*t4 + 1*t5 = 1


Ich habe das mal mit dem Mathematikprogramm sage ausgerechnet (gibt es auf sagemath.org kostenlos zum Download, ist von der Syntax weitgehen kompatibel zu python2.7 - mit ein paar Ausnahmen: z.B. ^ ist potenzieren, nicht XOR)
Zusätzlich habe ich noch Zufallsläufe gemacht, die Ergebnisse stimmen überein.
Quellcode ausblenden Python-Code
def probability(n): #diese Funktion ist für sage geschrieben. sagemath.org
	m = matrix(n,n,2)
	for i in range(0,n-1):
		m[i,i+1] = -1
	for i in range(0,n-1):
		m[i+1,i] = -1
	b = [0]*n
	b[0] = 1
	return m\vector(b)

def time(n): #diese Funktion ist für sage geschrieben. sagemath.org
	m = matrix(n,n,2)
	for i in range(0,n-1):
		m[i,i+1] = -1
	for i in range(0,n-1):
		m[i+1,i] = -1
	b = [2]*n
	return m\vector(b)


def simulate(n, pos, repeat):
	time = 0
	left = 0
	for i in range(0,repeat):
		p = pos
		while p >= 0 and p < n:
			if random() < 0.5: p += 1
			else: p -= 1
			time += 1
		if p < 0: left += 1
	print "Wahrscheinlichkeit, nach links zu fallen: " + str(left / repeat + 0.0)
	print "Zeit bis zum Fallen: " + str(time / repeat + 0.0)

print "Wahrscheinlichkeit: " + str(probability(10))
print "Zeit" + str(time(10))
simulate(10,3,10000)

#Ausgabe:
#Wahrscheinlichkeit: (10/11, 9/11, 8/11, 7/11, 6/11, 5/11, 4/11, 3/11, 2/11, 1/11)
#Zeit(10, 18, 24, 28, 30, 30, 28, 24, 18, 10)
#Wahrscheinlichkeit, nach links zu fallen: 0.629300000000000
#Zeit bis zum Fallen: 27.6123000000000


Die Rechnung zeigt (warum das so ist, habe ich jetzt nicht nachvollzogen):
p_i = (n-i)/(n+1)
Die Summe aus dem ganz rechten und dem ganz linken Wert ergibt 1. Das ist plausibel, da der linke Wert aussagt, dass die Feder mit Wahrscheinlihckeit 1/(n+1) nach rechts fällt. Es ist also gleich wahrscheinlich, von ganz links ausgehen nach rechts zu fallen oder von ganz rechts nach links zu fallen.

Die Zeit ist symmetrisch, mit einem Maximum in der Mitte. Auch das scheint logisch.
Die Werte scheinen den Antidiagonalen des 1x1 (OEIS A003991) zu entsprechen.
1801089

Du scheinst einen AdBlocker zu nutzen. Ich würde mich freuen, wenn du ihn auf dieser Seite deaktivierst und dich davon überzeugst, dass die Werbung hier nicht störend ist.