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

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 $X_1, X_2, \dots, X_n \stackrel{iid}{\sim} \text{Bernoulli}(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 von$\text{Binom}(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.

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 $2$Optionen, die Ihre Situation ist. Die Frage ist zu weit gefasst, um hier eine detaillierte Antwort zu geben.

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 ).

Wie andere gesagt haben, ist das Problem dem Spiel Mastermind sehr ähnlich. Angenommen, die richtigen Antworten sind binäre Variablen$c_i$ zum $i = 1, \ldots, n$ und dieser Regen macht den Test $k$ mal, mal $j$ antworten $x_{i, j}$ zum $i$-te Frage ($i \le n, j \le k$). Die total richtige Antwort auf die$j$-th mal ist $T_j$.

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 $k \ge O(n / \log n)$: Jeder Test gibt Rain eine Nummer $0 \le T_j \le n$, was beträgt $\le \log n$ Wissensbits, während das erforderliche Wissen, um alle Antworten zu kennen, ~ ist$n$ (wegen dem $n$ binäre Fragen).

2. Im allgemeinen Fall können Sie Variablen definieren $z^Y_i$ und $z^N_i$ 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

   $$z^Y_i + z^N_i = 1$$

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

   $$\sum_{i = 1}^n z^{Y/N}_i = T_j$$

   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 finden$\log n$Abfragen 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) ausgeben$T_1 = 1$).

4. Durch Verallgemeinern der Idee im vorherigen Aufzählungspunkt, wenn die Anzahl der Ja-Antworten ist $C$ (annehmen $C \le n/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 $\binom{n}{C} \simeq n^C$von 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| = m$$S$$|Y \cap S| = t$$|Y \cap S^c| = m - t$

   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) \simeq\le 1 + 2 * P(m/2, n/2)$$O(m \log n)$

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.).$\frac{n}{2}$