Hallo miteinander,
Sie müssen wieder einmal für die Übungen zu Theoretischer Informatik III eine viel zu schwierige Aufgabe bearbeiten. Es handelt sich um eine Beweisaufgabe und Sie haben auch schon einen Beweis gefunden. Allerdings sind Sie sich nicht sicher, dass Ihr Beweis auch wirklich korrekt ist!2 Sie beschlieÿen daher, Ihre Kommilitonen zu fragen. Leider sind sich diese auch nicht sicher, sie antworten aber stets nach endlicher Zeit mit Beweis ist wahrscheinlich korrekt oder mit Beweis ist wahrscheinlich falsch. Aus Erfahrung wissen Sie, dass bei Ihren Kommilitonen folgende Wahrscheinlichkeitsverteilung vorliegt:
• Ist der Beweis tatsächlich korrekt, antworten Ihre Kommilitonen mit einer Wahrscheinlichkeit von 90% mit Beweis ist wahrscheinlich korrekt.
• Ist der Beweis falsch, so antworten sie mit einer Wahrscheinlichkeit von 40% trotzdem mit Beweis ist wahrscheinlich korrekt.
Sie benötigen die Punkte unbedingt und wollen vermeiden, dass Sie eine falsche Lösung abgeben. Genauer möchten Sie bei einem falschen Beweis mit einer Wahrscheinlichkeit von mindestens 99,9% auch herausnden, dass der Beweis falsch ist. Wie gehen Sie vor? Begründen Sie Ihre Antwort.
Problem:
Muss ich nur den zweiten Punkt beachten?
Ich habe allgemein Probleme mir Wahrscheinlichkeiten und die fallen mir allgemein nicht einfach solche Aufgaben
Meine Idee ist, das man was mit der Markov-Ungleichung rechnen muss. Aber wie genau da scheitere ich dann dran.
Danke schon mal für eure Hilfe
