Erste Schritte Rekursion

[Default]

Ich habe eine Frage über die Rekursion anhand folgender Aufgabe (broken telephone):

Ich erhalte durch einen Scanner zuerst 2 Werte, welche durch einen Abstand voneinander getrennt sind. Der erste Wert bedeuted dabei die Anzahl an Personen, die zweite Zahl die Nachricht (0 oder 1). Nun stehen alle diese Personen in einer Reihe und geben die übermittelte Nachricht der nächsten Person weiter. Durch den Scanner wird mir nach den vorherigen beiden Werten die Wahrscheinlichkeiten gegeben, mit welcher die Person der nächst folgenden die falsche Nachricht übermittelt. Die Frage dabei ist nach der Wahrscheinlichkeit mit welcher die korrekte Nachricht von der letzten Person ausgegeben wird. Wie kann ich dies durch Rekursion lösen? Ich habe dabei mal eine Zeichnung erstellt:


Die Wahrscheinlichkeit lässt sicht ja damit berechnen, indem ich folgendes multipliziere sowie addiere: 0.1*0.2*0.7 + 0.1*0.8*0.3 + 0.9*0.8*0.7+ 0.9*0.2*0.3. Die Personenanzahl geht dabei von 1 bis 100000.
Das richige Resultat müsste ja überliefert werden:
> indem der Vorletzte in der Reihe das Richtige erhalten hat, und die letzte Übermittlung korrekt erfolgte,
oder
> indem der Vorletzte in der Reihe das Falsche erhalten hat, und die letzte Übermittlung verfälscht wird.

Kann mir vielleicht jemand helfen, wie ich auf so eine Rekursionsgleichung komme? Die Wahrscheinlichkeiten habe ich in einen double[] array abgespeichert.

 

[httpdigest]

Jeder Rekursionsschritt besteht ja aus einer gewichteten Summe von zwei Wahrscheinlichkeiten, die sich ihrerseits rekursiv berechnen.
Und die Gewichte/Faktoren der beiden Wahrscheinlichkeiten sind die Fehlerwahrscheinlichkeit der i-ten Person (für den i-ten Rekursionsschritt) für den Fall, dass diese Person einen Fehler macht, und das Inverse (also 1.0 - P) der Fehlerwahrscheinlichkeit der i-ten Person für den Fall, dass diese Person keinen Fehler macht. Bei der letzten Person musst du aber wissen, ob er nun die richtige oder die falsche Information erhalten hat, um zu ermitteln, welche der beiden Wahrscheinlichkeiten für ihn nun ermittelt werden sollen. Du brauchst also quasi eine Information, die sagt, durch welchen Zweig im Baum du gerade gehst: Wurde gerade die Wahrscheinlichkeit dafür berechnet, dass die i-te Person einen Fehler gemacht hat, oder, dass die i-te Person alles korrekt gemacht hat.

 

[Default]

 

[Default]

Jeder Rekursionsschritt besteht ja aus einer gewichteten Summe von zwei Wahrscheinlichkeiten, die sich ihrerseits rekursiv berechnen.
Und die Gewichte/Faktoren der beiden Wahrscheinlichkeiten sind die Fehlerwahrscheinlichkeit der i-ten Person (für den i-ten Rekursionsschritt) für den Fall, dass diese Person einen Fehler macht, und das Inverse (also 1.0 - P) der Fehlerwahrscheinlichkeit der i-ten Person für den Fall, dass diese Person keinen Fehler macht. Bei der letzten Person musst du aber wissen, ob er nun die richtige oder die falsche Information erhalten hat, um zu ermitteln, welche der beiden Wahrscheinlichkeiten für ihn nun ermittelt werden sollen. Du brauchst also quasi eine Information, die sagt, durch welchen Zweig im Baum du gerade gehst: Wurde gerade die Wahrscheinlichkeit dafür berechnet, dass die i-te Person einen Fehler gemacht hat, oder, dass die i-te Person alles korrekt gemacht hat.

Also es gibt ja die 4 Möglichkeiten, mit welchen die korrekte Antwort ausgegeben wird bei 3 Leuten. Also dachte ich mir, dass die Gleichung irgendwie in die Richtung aussehen muss:
(n-1)(p[current] * (1-p[vorherigen]) +(1-p[current]) * p[vorherige]) und das ganze immer wieder aufgerufen. Ist mein Ansatz korrekt? (n-1) da es gewisse Zweige doppelt gibt

 

[httpdigest]

Eine Gleichung ist das schonmal nicht, weil du hier nicht zwei Dinge miteinander "gleichsetzt". Salopp gesagt: Es fehlt das Gleichheitszeichen.
Du musst per Gleichung den aktuellen Rekursionsschritt zu den nächsten Rekursionsschritten gleichsetzen.
In etwa so:

success(n, 1) = p[n] * success(n - 1, 0) + (1 - p[n]) * success(n - 1, 1)

 

[Default]

Eine Gleichung ist das schonmal nicht, weil du hier nicht zwei Dinge miteinander "gleichsetzt". Salopp gesagt: Es fehlt das Gleichheitszeichen.
Du musst per Gleichung den aktuellen Rekursionsschritt zu den nächsten Rekursionsschritten gleichsetzen.
In etwa so:

success(n, 1) = p[n] * success(n - 1, 0) + (1 - p[n]) * success(n - 1, 1)

Stimmt nur wollte ich das Ganze mal mit einer simplen Gleichung zuerst aufstellen. Bei mir kommein einfach immer wieder zwei Fragen auf:
Wie gehe ich in einem Array um einen Index zurück?
Wie merkt die Rekursion, dass ich am obersten Punkt angelangt bin?

 

[httpdigest]

Wie gehe ich in einem Array um einen Index zurück?
Wie merkt die Rekursion, dass ich am obersten Punkt angelangt bin?

Für beide Fragen: Indem du dir eine Zahl in der Rekursion merkst, die du bei jedem weiteren Rekursionsschritt immer um 1 dekrementierst (verringerst). Wenn diese Zahl bei 0 angekommen ist, weisst du, dass du am Ende der Rekursion bist. Mit dieser Zahl indexierst du in das Array.

 

[Default]

Für beide Fragen: Indem du dir eine Zahl in der Rekursion merkst, die du bei jedem weiteren Rekursionsschritt immer um 1 dekrementierst (verringerst). Wenn diese Zahl bei 0 angekommen ist, weisst du, dass du am Ende der Rekursion bist. Mit dieser Zahl indexierst du in das Array.

Aahhh okey das macht Sinn! Dann muss ich jetzt nurnoch auf die Rekursionsformel selber kommen.

 

[MoxxiManagarm]

Also dachte ich mir, dass die Gleichung irgendwie in die Richtung aussehen muss:
(n-1)(p[current] * (1-p[vorherigen]) +(1-p[current]) * p[vorherige]) und das ganze immer wieder aufgerufen. Ist mein Ansatz korrekt?

Ich denke nicht. Du musst an Mathe denken wie eine Rekursionsgleichung aussieht. z.B. Falkultät:
f(n) = n * f(n-1)
Es ist das Ergebnis n für den aktuellen Rekursionschrittes verknüpft (hier multipliziert) mit dem Ergebnis der tieferen Rekursionsschritte.

Jetzt denke an deinen Fall. Du kannst einen Teil des rekursiven Problems ohne Probleme lösen. Nämlich den Wert
toggle = p(i)
Also ob das Ereignis toggle Eintritt oder nicht. Das ist ein boolean und kann wiederum als 0 bzw. 1 dargestellt werden. r sei das Ergebnis aus dem aktuellen Schritt. i ist die Position im Array und n die Eingangsnachricht.

n p r
1 1 0
1 0 1
0 1 1
0 0 0

Hier siehst du, dass r eine XOR Operation aus n, also der Nachricht und der Eintrittwahrscheinlichkeit p ist. Der aktuelle Rekursionsschritt berechnet sich also als n ^ p. (das Mathematische Zeichen für XOR kannst du dir ergooglen).

Jetzt musst du dir nur noch überlegen wie du r mit f(i-1) verknüpfst. Das ist wiederum ein XOR. Du erhältst also insgesamt die Rekursionsgleichung:
f(n, i) = n ^ p(i) ^ f(n, i-1)
ODER
Du trägst r als Parameter direkt ein, also
f(n, i) = f(n ^ p(i), i-1)

Wenn du dafür eine Wahrheitstabelle aufstellst sind alle Zeilen mit einer ungeraden Anzahl 1 (verteilt über die 3 Operanten) wiederum 1 (für meine erste Gleichung mit 2 mal XOR). Anhand dieser Tatsache könnte man auch alternative Implementierungen erreichen als XOR. r im Rekusiven Aufruf ist sicherlich die kürzeste Variante

 

[httpdigest]

@MoxxiManagarm ich denke mal, hier sollte die Rekursionsgleichung für das eigentlich zu lösende Problem erstellt werden: Die Wahrscheinlichkeit, dass bei `n` gegebenen Personen mit `n` Fehlerwahrscheinlichkeiten die letzte Person bei dieser "stillen Post" den anfänglichen Wert, der durch die Kette der Personen geht, richtig zurückgibt. Wo genau wird in deiner XOR-Berechnung die Wahrscheinlichkeit ermittelt?

 

[MoxxiManagarm]

Achso, hab ich falsch verstanden. Ich dachte die resultierende Nachricht selbst ist wichtig, warum sonst sollte in der Input Datei die gesendete Nachricht 0/1 eine Rolle spielen? Wenn es um die gesamte Wahrscheinlichkeit geht, ob die resultierende Nachricht anders ist, dann ist es doch egal ob 0 oder 1 durch die Leitung geschickt wird.

Wo genau wird in deiner XOR-Berechnung die Wahrscheinlichkeit ermittelt?

Bei p. Da ja mein Ansatz vermutlich der Aufgabenstellung widerspricht hier mal als Code, was ich dachte:

public class BrokenTelegram {

    private double[] glitches;

    public BrokenTelegram(double[] glitches) {
        this.glitches = glitches;
    }

    public void send(int n) {
        System.out.print(n + "-->");
        System.out.println("-->" + send(n, glitches.length - 1));
    }

    public int send(int n, int i) {
        if (i < 0) return n;

        int p = Math.random() <= glitches[i] ? 1 : 0;
        System.out.print(p);

        return send(n ^ p, i - 1);
    }

    public static void main(String... args) {
        BrokenTelegram telegram = new BrokenTelegram(new double[]{0.1, 0.8, 0.7});
        for(int i = 1; i <= 20; i++) telegram.send(i % 2);
    }
}

Beispielausgabe:

Eingangsnachricht --> Liste Toggle Ereignisse --> Empfangene Nachricht
1-->101-->1
0-->110-->0
1-->010-->0
0-->110-->0
1-->100-->0
0-->010-->1
1-->110-->1
0-->000-->0
1-->110-->1
0-->110-->0
1-->000-->1
0-->110-->0
1-->010-->0
0-->110-->0
1-->011-->1
0-->110-->0
1-->110-->1
0-->011-->0
1-->010-->0
0-->010-->1

 

[httpdigest]

Es ist in sofern wichtig, als dass es nur zwei mögliche Werte gibt, sonst wäre die Berechnung komplizierter, bzw. jeder Knoten im Baum hätte genau so viele Kinder wie es mögliche Werte als Nachricht gibt.
Aber ja, es ist egal, ob es nun 1 und 0, oder Fu und Fara als Nachricht sind.

 

[Default]

Also ich habe das ganze mal so gelöst:

 return (i == n) ? ((m1 == m2) ? p[i] : 1.0 - p[i]) : (p[i] * recursion(p, i + 1, n, m1, (m2 == 0) ? 1 : 0) + (1 - p[i]) * recursion(p, i + 1, n, m1, m2));

 

[httpdigest]

Das kannst du noch weiter vereinfachen. Du brauchst z.B. die Variable `i` gar nicht (du kannst `n` immer dekrementieren). Da die Operatoren `*` sowie `+` kommutativ sind, kannst du also genausogut auch "von hinten" mit der letzten Person anfangen (die Reihenfolge der Personen bzw. Fehlerwahrscheinlichkeiten spielt keine Rolle).
Ausserdem brauchst du m1 und m2 nicht, bzw. nicht als zwei Variablen. Du brauchst nur einen boolean, der sagt, ob du jetzt im Fall bist, dass ein Fehler gemacht wird, oder im Fall, dass alles korrekt übertragen wird. Siehe auch meine erste Antwort.