Schrittproblem

baker333

Bekanntes Mitglied
Servus,

es geht um das Schrittproblem: es gibt einen Zahlenstrahl von -n bis n. Eine Spielfigur wird auf die Position 0 gesetzt und die Figur kann sich genau n mal entweder um eine Position nach links oder rechts bewegen. Dies mit der Wahrscheinlichkeit nach links p und nach rechts 1-p.

Ich soll nun eine iterative Bottom-Up Lösung schreiben und die sieht laut Musterlösung wie folgt aus:

Ich kapiere allerdings gerade nicht die arrayIndex Methode, obwohl sie den korrekten Array-Index für die Position x auf dem Zahlenstrahl von -n bis n wiedergeben soll. Muss wieder so ein dummer Denkfehler sein, aber wenn ich Position x = 5 und sagen wir n = 5 habe: Wieso ist der Array Index für die Position x 11?

Java:
    private static int arrayIndex(int x, int n) {
        return n+x+1;
    }
    
    
    public static double schrittproblem(int n, double p, int x) {
        if (n < 0) {
            throw new IllegalArgumentException("Ungültige Eingabe!");
        }
        if (n<x) {
            return 0;
        }
        if (n < -x) {
            return 0;
        }
        
        /*
         * erster Index des Feldes: Position auf dem Zahlenstrahl
         * zweiter Index des Feldes = Anzahl der Schritte
         */
        
        double [] [] s = new double [2*(n+1)+2][n+1];
        //Schritte
        for (int i = 0; i <= n; ++i) {
            //Positionen
            for (int j = -i; j<= i; ++j) {
                if (i==0) {
                    s[arrayIndex(j, n)] [i] = 1;
                }
                
                else {
                    s[arrayIndex(j,n)][i] =
                            //von links
                            s[arrayIndex(j-1,n)][i-1]*(1-p)+s[arrayIndex(j+1,n)][i-1]*p;
                            //von rechts
                            
                }
            }
        }
        return s[arrayIndex(x,n)][n];
    }
 

abc66

Top Contributor
Na gut, dabei gibt es auch einen Schreibe- und Lesekopf, der an einer bestimmten Position auf einem Band steht, sich nach links und rechts einen Schritt bewegen kann und dabei 0oder1 lesen oder schreiben kann.
 

baker333

Bekanntes Mitglied
Okay, aber warum erhalte ich dann trotzdem den o.g. Wert 11? Dies macht für mich nur Sinn, wenn man den ganzen strahl inkl. Negativer Werte (also -n) betrachtet?
 

abc66

Top Contributor
Sorry, die Wahrscheinlichkeit, dass sich die Spielfigur nach nach n Schritten auf Position x befindet.
Java:
	public static float wahrscheinlichkeit(int n, int x1, int x2) {
		int d = Math.abs(x1 - x2);
		if (d > n) {
			return 0;
		}
		double w = Math.pow(0.5, d);
		return (float) w;
	}

	public static int position(int n, int x1) {
		for (int i = 0; i < n; i++) {
			if (x1 == 0) {
				x1++; // linker Rand
			} else if (x1 == 20) {
				x1--; // rechter Rand
			} else if (Math.random() < 0.5) {
				x1++;
			} else {
				x1--;
			}
		}
		return x1;
	}

	public static void main(String[] args) {
		System.out.println(wahrscheinlichkeit(51, 5, 10));
		int x = 0;
		for (int i = 0; i < 100; i++) {
			int p = position(51, 5);
			if (p == 10) {
				x++;
			}
		}
		System.out.println(x / 100.0);
	}

Aber warte mal einen Moment, denn die Wahrscheinlichkeit stimmt noch nicht (wegen den Rändern ).
 

abc66

Top Contributor
Also, wenn man davon absieht, dass es KEINE Ränder gibt, dann wäre die Wahrscheinlichkeit:
Java:
	public static float wahrscheinlichkeit(int n, int x1, int x2) {
		int d = Math.abs(x1 - x2);
		if (d > n) {
			return 0;
		}
		double w = Math.pow(0.5, d / 2.0) / 2.0;
		return (float) w;
	}

/e Quatsch, wenn man annimmt, es gebe/gäbe keine Ränder. :D
 

abc66

Top Contributor
@baker333 Habe jetzt die korrekte Wahrscheinlichkeit... Angenommen, wir starten auf einem Zahlenstrahl von 0 bis 20 bei 5 und bewegen uns genau 11 Schritte. Wie hoch ist die Wahrscheinlichkeit, beim 11. Schritt bei 2 stehen zu bleiben? (0.18799... nach Adam Riese....)
Java:
	public static float wahrscheinlichkeit(int n, int x1, int x2) {
		if (n == 0)
			if (x1 == x2)
				return 1;
			else
				return 0;
		if (x1 == 0)
			return wahrscheinlichkeit(n - 1, x1 + 1, x2);
		if (x1 == 20)
			return wahrscheinlichkeit(n - 1, x1 - 1, x2);
		return (wahrscheinlichkeit(n - 1, x1 + 1, x2) + wahrscheinlichkeit(n - 1, x1 - 1, x2)) / 2f;
	}

	public static int position(int n, int x1) {
		for (int i = 0; i < n; i++) {
			if (x1 == 0) {
				x1++; // linker Rand
			} else if (x1 == 20) {
				x1--; // rechter Rand
			} else if (Math.random() < 0.5) {
				x1++;
			} else {
				x1--;
			}
		}
		return x1;
	}

	public static void main(String[] args) {
		System.out.println(wahrscheinlichkeit(11, 5, 2));
		int x = 0;
		for (int i = 0; i < 1_000_000; i++) {
			int p = position(11, 5);
			if (p == 2) {
				x++;
			}
		}
		System.out.println(x / 1_000_000.0);
	}
 

abc66

Top Contributor
Vllt sind im Skript auch Fehler :D
Möglich, aber ich kann das durch bloßes Daraufschauen nicht verifizieren...

/e Wir können uns noch "Pruning" zunutze machen:
Java:
	public static float wahrscheinlichkeit(int n, int x1, int x2) {
		if (n == 0)
			if (x1 == x2)
				return 1;
			else
				return 0;
		if (Math.abs(x1 - x2) > n)
			return 0; // Pruning
		if (x1 == 0)
			return wahrscheinlichkeit(n - 1, x1 + 1, x2);
		if (x1 == 20)
			return wahrscheinlichkeit(n - 1, x1 - 1, x2);
		return (wahrscheinlichkeit(n - 1, x1 + 1, x2) + wahrscheinlichkeit(n - 1, x1 - 1, x2)) / 2f;
	}

	public static int position(int n, int x1) {
		for (int i = 0; i < n; i++) {
			if (x1 == 0) {
				x1++; // linker Rand
			} else if (x1 == 20) {
				x1--; // rechter Rand
			} else if (Math.random() < 0.5) {
				x1++;
			} else {
				x1--;
			}
		}
		return x1;
	}

	public static void main(String[] args) {
		System.out.println(wahrscheinlichkeit(21, 5, 2));
		int x = 0;
		for (int i = 0; i < 10_000; i++) {
			int p = position(21, 5);
			if (p == 2) {
				x++;
			}
		}
		System.out.println(x / 10_000.0);

		System.out.println(wahrscheinlichkeit(21, 5, 8));
		x = 0;
		for (int i = 0; i < 10_000; i++) {
			int p = position(21, 5);
			if (p == 8) {
				x++;
			}
		}
		System.out.println(x / 10_000.0);
	}
 
Zuletzt bearbeitet:

abc66

Top Contributor
@mihe7
Java:
	public static float wahrscheinlichkeit(int n, int x1, int x2, float toRightProbability) {
		if (n == 0)
			if (x1 == x2)
				return 1;
			else
				return 0;
		if (Math.abs(x1 - x2) > n)
			return 0; // Pruning
		if (x1 == 0)
			return wahrscheinlichkeit(n - 1, x1 + 1, x2, toRightProbability);
		if (x1 == 20)
			return wahrscheinlichkeit(n - 1, x1 - 1, x2, toRightProbability);
		return wahrscheinlichkeit(n - 1, x1 + 1, x2, toRightProbability) * toRightProbability
			 + wahrscheinlichkeit(n - 1, x1 - 1, x2, toRightProbability) * (1 - toRightProbability);
	}

	public static int position(int n, int x1, float toRightProbability) {
		for (int i = 0; i < n; i++) {
			if (x1 == 0) {
				x1++; // linker Rand
			} else if (x1 == 20) {
				x1--; // rechter Rand
			} else if (Math.random() < toRightProbability) {
				x1++;
			} else {
				x1--;
			}
		}
		return x1;
	}

	public static void main(String[] args) {
		float toRightProbability = 0.25f;
		int n = 10_000;

		System.out.println(wahrscheinlichkeit(21, 5, 2, toRightProbability));
		int x = 0;
		for (int i = 0; i < n; i++) {
			int p = position(21, 5, toRightProbability);
			if (p == 2) {
				x++;
			}
		}
		System.out.println(x / (double) n);

		System.out.println(wahrscheinlichkeit(21, 5, 8, toRightProbability));
		x = 0;
		for (int i = 0; i < n; i++) {
			int p = position(21, 5, toRightProbability);
			if (p == 8) {
				x++;
			}
		}
		System.out.println(x / (double) n);
	}

"Es" bewegt sich mit einer Wahrscheinlichkeit von 0.75 nach links. Wenn man bei 5 startet, ist es viel wahrscheinlicher, bei 2 stehen zu bleiben, als bei 8 stehen zu bleiben....
 

abc66

Top Contributor
@abc66 jetzt noch als "iterative Bottom-Up Lösung" geschrieben, dann dürftest Du auf die Musterlösung kommen.
Müsstest Du machen, ich verstehe nur Top-down. :) (Wir hatten das auch mal zum Ende einer Vorl., aber dabei hab ich nicht aufgepasst)

Aber ich hab das mal umgesetzt und wenn ich es richtig sehe, dann werden die Ränder bei der Berechnung der Wahrscheinlichkeiten noch nicht bedacht.
 

abc66

Top Contributor
@mihe7 Wenn die Anzahl der Schritte größer als die Länge des Zahlenstrahles ist, dann gibt es eine etwas höhere Wahrscheinlichkeit, an einer der Randpositionen stehen zu bleiben... (Wenn die Ränder natürlich gar nicht erreicht werden können, weil die Anzahl der Schritte kleiner ist, so natürlich nicht...) ;)
 

mihe7

Top Contributor
und wenn ich es richtig sehe, dann werden die Ränder bei der Berechnung der Wahrscheinlichkeiten noch nicht bedacht.
Das Array in der Musterlösung hat links und rechts ein 0-Element :) Deswegen entfallen dort die if-Abfragen.

Wenn die Anzahl der Schritte größer als die Länge des Zahlenstrahles ist, dann gibt es eine etwas höhere Wahrscheinlichkeit, an einer der Randpositionen stehen zu bleiben...
Die Wahrscheinlichkeit muss etwas geringer sein, weil es nur eine Richtung gibt, aus der man das Randelement erreichen könnte.
 

abc66

Top Contributor
Ok, ändern wir das Problem mal (damit es interessanter wird)... Auf einem Stapel liegen 10 blaue Zettel. Ein Mitarbeiter kann entweder mit einer Wahrscheinlichkeit von 60 % den obersten Zettel vom Stapel nehmen und diesen bearbeiten (insofern der Stapel nicht leer ist) - oder der Chef legt mit einer Wahrscheinlichkeit von 40 % einen roten Zettel auf den Stapel. An einem Tag passieren genau 20 solcher Ereignisse. Wie hoch ist die Wahrscheinlichkeit, dass am Ende eines Tags genau 2 rote Zettel auf dem Stapel liegen?
~ 4,5 %
Java:
import java.awt.Color;
import java.util.ArrayList;

public class Handler extends HandlerA<ArrayList<Color>> {
	ArrayList<ArrayList<Color>> temp = new ArrayList<ArrayList<Color>>();

	Handler(int n, float a, float b, ArrayList<Color> theStart, ArrayList<Color> theGoodEnd) {
		super(n, a, b, theStart, theGoodEnd);
	}

	@Override
	public float getProbabilityA() {
		return this.theStart.isEmpty() ? 1 : a;
	}

	@Override
	public float getProbabilityB() {
		return this.theStart.isEmpty() ? 0 : b;
	}

	@Override
	public void doA() {
		super.doA();
		temp.add(new ArrayList<Color>(theStart));
		theStart.add(Color.red);
	}

	@Override
	public void doB() {
		super.doB();
		temp.add(new ArrayList<Color>(theStart));
		theStart.remove(theStart.size() - 1);
	}

	@Override
	public void undoA() {
		super.undoA();
		theStart = temp.remove(temp.size() - 1);
	}

	@Override
	public void undoB() {
		super.undoB();
		theStart = temp.remove(temp.size() - 1);
	}

	public static float probability(Handler h) {
		if (!h.hasNext())
			if (h.isGoodEnd(h.getEnd()))
				return 1;
			else
				return 0;
		float f1 = h.getProbabilityA();
		float f2 = h.getProbabilityB();
		if (f1 != 0) {
			if (f2 != 0) {
				h.doA();
				float f3 = probability(h);
				h.undoA();
				h.doB();
				float f4 = probability(h);
				h.undoB();
				return f1 * f3 + f2 * f4;
			} else {
				h.doA();
				float f3 = probability(h);
				h.undoA();
				return f3;
			}
		} else {
			if (f2 != 0) {
				h.doB();
				float f4 = probability(h);
				h.undoB();
				return f4;
			} else {
				return 0;
			}
		}
	}

	public static void main(String[] args) {
		ArrayList<Color> theGoodEnd = new ArrayList<Color>();
		theGoodEnd.add(Color.red);
		theGoodEnd.add(Color.red);
		Handler h;
		do {
			ArrayList<Color> l = new ArrayList<Color>();
			for (int i = 0; i < 10; i++) {
				l.add(Color.blue);
			}
			h = new Handler(20, 0.4f, 0.6f, l, theGoodEnd);
			System.out.println(probability(h));
			while (h.hasNext()) {
				if (Math.random() < h.getProbabilityA()) {
					h.doA();
				} else {
					h.doB();
				}
			}
			System.out.println(h.getEnd());
			System.out.println(h.isGoodEnd(h.getEnd()));
		} while (!h.isGoodEnd(h.getEnd()));
	}
}

interface HandlerI<T> {
	float getProbabilityA();

	float getProbabilityB();

	void doA();

	void doB();

	void undoA();

	void undoB();

	boolean hasNext();

	T getEnd();

	boolean isGoodEnd(T t);
}

abstract class HandlerA<T> implements HandlerI<T> {
	int n;
	float a;
	float b;
	T theStart;
	T theGoodEnd;

	public HandlerA(int n, float a, float b, T theStart, T theGoodEnd) {
		this.n = n;
		this.a = a;
		this.b = b;
		this.theStart = theStart;
		this.theGoodEnd = theGoodEnd;
	}

	public void doA() {
		n--;
	}

	public void doB() {
		n--;
	}

	public void undoA() {
		n++;
	}

	public void undoB() {
		n++;
	}

	public boolean hasNext() {
		return n > 0;
	}

	public T getEnd() {
		return theStart;
	}

	public boolean isGoodEnd(T t) {
		return theGoodEnd.equals(t);
	}
}

Zusatzfrage: Wie hoch wäre die Wahrscheinlichkeit, dass am Ende eines Tags genau 2 blaue Zettel auf dem Stapel liegen?
 

Neue Themen


Oben