Frage: Zeigen Sie, dass die obige Kreisel-Methode differentially private ist...
Text erkannt:
Aufgabe 3. In der Vorlesung wurde eine Version von "Randomized Response" vorgestellt: Teilnehmern einer Umfrage wird ein Kreisel gegeben, der mit Wahrscheinlichkeit \( p \) "Ja" und mit Wahrscheinlichkeit \( 1-p \) "Nein" angibt. Wenn die eigene (wahre) Antwort auf die Umfrage der Antwort des Kreisels entspricht, gibt man "True" zurück, ansonsten "False".
Text erkannt:
(c) Zeigen Sie, dass die obige Kreisel-Methode differentially private ist, und nennen Sie eine Abschätzung für \( \epsilon \) in Abhängigkeit von p.
Zur Erinnerung: Ein Algorithmus \( A \) wird \( \epsilon \)-differentially private genannt, wenn
\( \operatorname{Pr}[A(x) \in S] \leq e^{\epsilon} \cdot \operatorname{Pr}[A(y) \in S] \)
für alle \( S \subseteq \) output \( (A) \), wobei \( x \) und \( y \) zwei Datenbanken sind, die sich in einem Eintrag unterschei\( \operatorname{den}\left(\|x-y\|_{1}=1\right) \)
Hinweis: es ist hinreichend, den Fall zu betrachten, dass \( x \) und \( y \) jeweils eine "Befragung" sind, mit unterschiedlicher wahrer Antwort. output \( (A)=[0,1] \) sind die möglichen Resultate nach der Randomisierung \( (0= \) False, \( 1= \) True). Überlegen Sie sich, für welche S Sie die Ungleichung ausrechnen müssen, und wie sich aus den Ergebnissen die untere Schranke von \( \epsilon \) ergibt.
Code:
