Erhalten Sie alle Antworten richtig, indem Sie die gleiche Prüfung einige Male ablegen

11

Regen lernt nie, deshalb ist sie mittelfristig völlig ahnungslos, obwohl es nur aus Ja / Nein-Fragen besteht. Glücklicherweise erlaubt Rain's Professor ihr, die gleiche Halbzeit so oft zu wiederholen, wie sie will, aber er meldet nur die Punktzahl, sodass Rain nicht weiß, welche Probleme sie falsch gemacht hat. Wie kann Rain alle Antworten richtig machen, indem er die Prüfung so oft wie möglich wiederholt?

Um es formeller auszudrücken, die Prüfung hat insgesamt n Ja / Nein-Fragen, deren richtige Antwort lautet X1,X2,,XniidBernoulli(0.5). Ich möchte eine Strategie finden, die die erwartete Häufigkeit minimiert, mit der Rain die Prüfung wiederholen muss.

Ich habe eine Weile darüber nachgedacht. Wenn Rain zum ersten Mal die Halbzeit spielt, hat ihre Punktzahl immer eine Verteilung vonBinom(n,0.5)Unabhängig von ihrer Antwort verringert jede Strategie die gleiche Entropie. Ich habe jedoch keine Ahnung, was dies bedeutet. Bedeutet das, dass eine zufällige Vermutung so gut ist wie die Beantwortung aller "Ja" oder aller "Nein"?

Obwohl dies keine Hausaufgabenfrage ist, plane ich, mein nächstes Forschungsprojekt darauf aufzubauen

  1. Bitte geben Sie einige Hinweise anstelle einer vollständigen Antwort.
  2. Wenn diese Frage bereits beantwortet wurde, geben Sie mir bitte einen Hinweis.
Nalzok
quelle
Die Verteilung ist nicht binomial n 0,5, es sei denn, es gibt andere Parameter, die Sie nicht erwähnen. Es hängt von ihrer anfänglichen Wettstrategie ab (seien wir ehrlich, dies ist ein Problem der Spieltheorie) und auch von der Verteilung der richtigen Antwort. Ein Ansatz könnte darin bestehen, bei jedem ersten Durchgang für jede Frage mit "Nein" zu antworten. Die tatsächlich richtige Antwort kann auf jede Frage "Nein" lauten.
AdamO
@bounty / Martijn / ein bisschen Meta: Ich verstehe nicht - warum ist das eine Frage mit zu wenig Aufmerksamkeit? Erstens ist es ein bekanntes Problem aus der "Spieltheorie" mit mehreren spezifischen Lösungen. Zweitens, warum ist die beste Antwort von derselben Person wie das Kopfgeld (es macht mir wirklich nichts aus, wenn ich auf viele Punkte hinweise). Trotzdem bin ich mir nicht sicher, ob die wirklichen Fragen des OT beantwortet werden. Es scheint immer noch offene Fragen zu den Bedingungen und Auswirkungen des Spiels zu geben.
Cherub
@cherub Ich versuche, meine Reputationsbewertung loszuwerden. Eigentlich wollte ich zehn Fragen stellen, aber ich blieb bei nur drei.
Sextus Empiricus

Antworten:

4

Dies ähnelt dem Spiel Mastermind .

Zu diesem Thema gibt es viel Literatur. Für diesen speziellen Fall (4 Fragen mit jeweils 6 Optionen) wurden verschiedene Strategien entwickelt, die die durchschnittliche Anzahl der Takes auf etwas über 4,3 reduzieren.

Sie können eine dieser Strategien auswählen oder eine neue erstellen und auf den Fall von anwenden n Fragen mit 2Optionen, die Ihre Situation ist. Die Frage ist zu weit gefasst, um hier eine detaillierte Antwort zu geben.

Sextus Empiricus
quelle
4

Dies ist ein Optimierungsproblem, bei dem Sie nach einem Unbekannten suchen n-stellige Binärzahl aus Vermutungen, wobei die Rückmeldung aus diesen Vermutungen lautet, dass Sie die Anzahl der korrekten Ziffern erhalten. Dies ist im Wesentlichen nur binäres Mastermind , das auch in einem Rechenproblem untersucht wird, das als "Black-Box-Optimierung" bezeichnet wird (siehe z. B. Doerr et al. 2001 ).

Ben - Monica wieder einsetzen
quelle
4

Wie andere gesagt haben, ist das Problem dem Spiel Mastermind sehr ähnlich. Angenommen, die richtigen Antworten sind binäre Variablenci zum i=1,,n und dieser Regen macht den Test k mal, mal j antworten xi,j zum i-te Frage (in,jk). Die total richtige Antwort auf diej-th mal ist Tj.

Was folgt, sind nur einige Beobachtungen und Anmerkungen, basierend auf der expliziten Aufforderung des OP, nur einige Hinweise auf das Problem zu geben.

  1. Beachten Sie, dass eine einfache "informationstheoretische" Untergrenze auf k für eine generische Konfiguration der richtigen Antworten ist kO(n/logn): Jeder Test gibt Rain eine Nummer 0Tjn, was beträgt logn Wissensbits, während das erforderliche Wissen, um alle Antworten zu kennen, ~ istn (wegen dem n binäre Fragen).

  2. Im allgemeinen Fall können Sie Variablen definieren ziY und ziN sein 0 oder 1 jeweils wenn die i-th richtige Antwort ist Ja oder Nein. Auf diese Weise besteht Ihr Problem darin, den Punkt der richtigen Antworten in einem "diskreten" linearen Dimensionsraum zu bestimmen 2n: um zu sehen, warum Sie berücksichtigen, dass Sie durch die obige Definition von Variablen die Einschränkungen haben

    ziY+ziN=1

    Darüber hinaus bei Ihrem j- Bei der Prüfung testen Sie eine lineare Kombination solcher Variablen und wissen, dass ihre Summe ist Tj::

    i=1nziY/N=Tj

    Dies unterstreicht, dass es trivial ist, ein solches Problem in zu lösen n Fragen, weil durch den Test k mal hast du n+k Gleichungen, die einen Punkt in a definieren 2n Dimensionsraum, so dass Sie nur nehmen können, wenn Sie klug genug sind, keine redundanten Abfragen zu stellen (ändern Sie einfach Ihre Antworten einzeln) n mal das Quiz.

  3. In bestimmten Fällen (z. B. wenn das Ja / Nein-Verhältnis besonders unausgeglichen ist) sollte es einfach sein, besonders geeignete Heuristiken zu finden: Nehmen wir an, Sie wissen anhand eines Beispiels, dass das gesamte Quiz nur eine Ja-Antwort enthält. Sie können es dann in nur findenlognAbfragen nach Standardhalbierung der Antwortsätze. Darüber hinaus können Sie überprüfen, ob Sie sich in einem solchen Fall befinden, indem Sie eine erste Abfrage "Ja" (in diesem Fall) ausgebenT1=1).

  4. Durch Verallgemeinern der Idee im vorherigen Aufzählungspunkt, wenn die Anzahl der Ja-Antworten ist C (annehmen Cn/2) (und dies kann durch eine einzelne Abfrage bekannt werden), suchen Sie im Grunde eine Menge von Größen C innerhalb einer Reihe von Größe n (also gibt es (nC)nCvon ihnen) und Ihre Anfrage besteht darin, die Kardinalität des Schnittpunkts eines Satzes Ihrer Wahl mit dem Satz von Ja-Fragen zu kennen, was meiner Meinung nach ein viel genauer untersuchtes Problem ist und auf dem Sie wahrscheinlich viele Referenzen finden können.S

    Rufen Sie den Satz Sie Tring zu finden (Ja Antworten) . Mit einer einzigen Abfrage können Sie die Kardinalität . Mit einer zufällig ausgewählten Menge die als Abfrage verwendet wird, können Sie nun die Kardinalität der beiden Teilmengen und , und Ihr ursprüngliches Problem wurde auf zwei Teilprobleme von ungefähr der Hälfte der Größe reduziert (auch die Anzahl der gesuchten Ja-Antworten halbiert sich normalerweise bei jeder Iteration). Ich werde keine expliziten Details schreiben, aber es geht nur um einfache Wahrscheinlichkeitsberechnungen.Y|Y|=mS|YS|=t|YSc|=mt

    Unter Ausnutzung der obigen Beobachtung sollten Sie einen probabilitischen Algorithmus entwickeln, der das Teilproblem löst , wodurch Sie eine Grenze von . Die Entwicklung eines deterministischen Algorithmus für ein solches Problem kann mit der Technik der maximierten Erwartungen erfolgen, aber ich kann nicht vorhersehen, ob es funktionieren würde oder nicht.P(m,n)≃≤1+2P(m/2,n/2)O(mlogn)

Dario Balboni
quelle
2

Möchten Sie die maximale Anzahl von Wiederholungen minimieren? oder die erwartete Anzahl von Wiederholungen minimieren?

Sie könnten sehr unterschiedliche Strategien entwickeln, je nachdem, welche Sie betrachten möchten.

Ein naiver Ansatz im ersten Schritt würde bis zu Mal dauern und darin bestehen, den Test zum ersten Mal durchzuführen. Beim zweiten Test wird nur die erste Antwort geändert. Wenn die Punktzahl steigt, behalten Sie die neue Antwort bei, wenn Es geht zurück zur ersten Antwort für alle zukünftigen Schritte. Ändern Sie beim 3. Mal (2. Wiederholung) nur die 2. Antwort usw.n+1

Jetzt können Sie andere Strategien mit dieser vergleichen. Wenn beim zweiten Testdurchgang 2 Antworten geändert werden, wenn sich die Punktzahl ändert, kennen wir die richtigen Antworten für 2 Fragen und haben einen Schritt gespeichert. Wenn wir jedoch eine geändert haben, um richtig und die andere falsch zu sein, ist die Punktzahl korrekt nicht ändern und wir wissen nicht, welche Änderung korrekt war, bis wir die Prüfung ein drittes Mal ablegen und nur eine von ihnen ändern (aber das sagt uns auch etwas über die andere), also wiederholen Sie entweder 1 oder 2, um 2 Antworten zu erhalten (50%) Chance von jedem), was die erwartete Anzahl von Wiederholungen verringert, aber wahrscheinlich das Maximum gleich hält.

Jetzt können Sie sich andere Strategien ansehen und sehen, wie sie miteinander verglichen werden (ändern Sie die ersten 3 Antworten, ändern Sie die ersten usw.).n2

Greg Snow
quelle
Danke für den Tipp! Mein Geld ist für das Ändern des erstenn2, weil dadurch die Korrelation zwischen der ersten und der zweiten Wiederholung minimiert wird. Ich werde allerdings etwas rechnen, um das zu überprüfen.
Nalzok