¿Qué significa "el espacio de probabilidad está sobre las tiradas de moneda del algoritmo M"?

2

En el libro The Algorithmic Foundations of Differential Privacy por Cynthia Dwork, Aaron Roth en página 16 (en realidad página 20 en el visor de pdf), se encuentra en la parte inferior de la página:

  

Definición 2.2 (algoritmo aleatorio) . Un algoritmo aleatorio ℳ   con el dominio A y el rango discreto B se asocia con un mapeo    M : A → ∆ ( B ). En la entrada a A , el algoritmo ℳ genera ℳ ( a ) = b con probabilidad ( M ( a )) b para cada b B . El espacio de probabilidad se encuentra sobre las tiradas de moneda del algoritmo ℳ.

¿Qué significa la oración final?

Alguien dijo que los autores podrían querer decir que una vez que haya realizado la receta descrita en ese párrafo, realice el truco de doble moneda con posibilidad de negación plausible descrito en 2.3 en la página 15. ¿Eso es lo que significa?

    
pregunta cheater 27.06.2016 - 17:07
fuente

1 respuesta

1

Me puse en contacto con los autores y fueron muy útiles. La cita original lo dice todo:

  

El libro trata sobre algoritmos aleatorios que actúan sobre conjuntos de datos. Siempre puedes verlos como algoritmos deterministas, que toman dos entradas: el conjunto de datos y también una cadena de bits aleatorios.

     

La definición de privacidad diferencial tiene un operador de probabilidad, y lo que esa observación significa es que la probabilidad se toma sobre la aleatoriedad de la cadena de bits aleatoria (es decir, la aleatoriedad interna del algoritmo), manteniendo el conjunto de datos fijo.

La clave para esto es que la definición dice: "el algoritmo ℳ produce ... con probabilidad ...". Esta es una elección aleatoria, y la fuente de aleatoriedad está definida por la oración "El espacio de probabilidad está sobre las tiradas de moneda del algoritmo ℳ".

    
respondido por el cheater 27.06.2016 - 18:16
fuente

Lea otras preguntas en las etiquetas