Una de las distribuciones más utilizadas en datos discretos, por ejemplo en conteos poblacionales es la distribución geómetica simétrica, ya que permite agregar ruido entero con probabilidad decreciente conforme el ruido se aleja del cero. Esta propiedad asegura que los resultados se mantengan cercanos al valor original con alta probabilidad.

En este ejercicio simulamos ruido geometrico bajo un nivel de privacidad (epsilón) y veremos las probabilidades asociadas a cada posible valor de ruido. Por medio de la interpretación gráfica de razones de probabilidades probamos que un mecanismo geometrico es un mecanismo privado, es decir la salida del mecanismo no cambia drásticamente cuando se modifica un solo individuo en la base de datos.

Deducción de la distribución geométrica simétrica

En el contexto de privacidad diferencial, es necesario utilizar mecanismos de perturbación que generen ruido discreto, centrado en cero y con decaimiento exponencial. Una distribución que cumple con estas propiedades es la distribución geométrica simétrica, la cual puede derivarse directamente a partir de la distribución geométrica clásica.

Distribución geométrica clásica

Sea \(G \sim \text{Geom}(p)\), con \(0 < p < 1\), la distribución geométrica modela el número de fracasos antes del primer éxito en ensayos de Bernoulli:

\[ \Pr[G = k] = (1 - p)^k \cdot p, \quad \text{para } k = 0, 1, 2, \dots \]

Esta distribución es no negativa y sesgada a la derecha.

Necesidad de simetría

Para proteger datos sensibles bajo privacidad diferencial, necesitamos una distribución de ruido que:

  • Tenga soporte en los enteros \(\mathbb{Z}\)
  • Sea simétrica respecto al 0
  • Decaiga exponencialmente con la magnitud del valor

Construcción de la distribución geométrica simétrica

Para construir una distribución con esas propiedades, se sigue el siguiente procedimiento:

  1. Se genera \(G \sim \text{Geom}(p)\)
  2. Se elige un signo al azar: \(S \in \{-1, +1\}\), con \(\Pr(S = \pm 1) = 0.5\)
  3. Se define \(Z = S \cdot G\)

Entonces, la distribución de \(Z \in \mathbb{Z}\) es:

\[ \Pr[Z = z] = \frac{1 - p}{1 + p} \cdot p^{|z|}, \quad \text{para } z \in \mathbb{Z} \]

Esta es la distribución geométrica simétrica.

Relación con privacidad diferencial

Si se desea que el ruido cumpla con \(\varepsilon\)-privacidad diferencial, se define:

\[ p = e^{-\varepsilon} \]

Lo que da como resultado:

\[ \Pr[Z = z] = \frac{1 - e^{-\varepsilon}}{1 + e^{-\varepsilon}} \cdot e^{-\varepsilon |z|} \]

Esta distribución garantiza que un cambio en una unidad (sensibilidad 1) en la base de datos no cambia significativamente la probabilidad de cada salida, cumpliendo así con la definición formal de privacidad diferencial.

Implementación distribución geomética simétrica

ruido_geom <- function(x,epsilon,n=1) {
  p <- 1 - exp(-epsilon)
  sign <- sample(c(-1, 1), n, replace = TRUE)
  value <- rgeom(n, p)
  return(x+sign * value)
}

Simulación

Por definición, un mecanismo \(\mathcal{A}\) es diferencialmente privado si exiten dos conjuntos D y D’ adyacentes (que difieren de a lo más un elemento) y un conjunto S tal que

\(\frac{\Pr[\mathcal{A}(D) \in S]}{\Pr[\mathcal{A}(D') \in S]} \leq e^{\varepsilon}\).

y la definición de un mecanismo Geometrico para la función f es

\(\mathcal{A}(D, f, \varepsilon) = f(D) + (N_1, \ldots, N_M)\)

donde \(N_i\) son variables aletorias independientes que se obtienen a partir de la distribución geométrica simétrica con parámetro epsilon \(\varepsilon\)

Haremos una simulación

# Simular ruido introducido a dos valores;  x = 10 y x' = 11
epsilon <- 1  # nivel de privacidad
n <- 100000   # numero de simulaciones
x <- 5        # es el resultado de F(D)
x_prime <- 6  # es el resultado de F(D')

y1 <- replicate(n, ruido_geom(x, epsilon))
y2 <- replicate(n, ruido_geom(x, epsilon))
# Comparar distribuciones con tabla de frecuencias para cada ruido introducido 
# 
tbl1 <- table(y1) / n
tbl2 <- table(y2) / n
tbl1
## y1
##      -7      -6      -5      -4      -3      -2      -1       0       1       2 
## 0.00001 0.00002 0.00001 0.00004 0.00016 0.00035 0.00083 0.00192 0.00534 0.01577 
##       3       4       5       6       7       8       9      10      11      12 
## 0.04304 0.11607 0.63356 0.11554 0.04254 0.01570 0.00574 0.00227 0.00074 0.00020 
##      13      14      15 
## 0.00012 0.00002 0.00001
tbl2
## y2
##      -6      -5      -4      -3      -2      -1       0       1       2       3 
## 0.00001 0.00002 0.00004 0.00021 0.00027 0.00073 0.00226 0.00565 0.01618 0.04284 
##       4       5       6       7       8       9      10      11      12      13 
## 0.11643 0.63058 0.11733 0.04307 0.01569 0.00541 0.00204 0.00078 0.00028 0.00012 
##      14      15 
## 0.00003 0.00003
# el subconjunto S donde coinciden ambas bases de datos 
S <- intersect(names(tbl1), names(tbl2)) 
S
##  [1] "-6" "-5" "-4" "-3" "-2" "-1" "0"  "1"  "2"  "3"  "4"  "5"  "6"  "7"  "8" 
## [16] "9"  "10" "11" "12" "13" "14" "15"

Probar que la razon de probabilidades es menor que exp(epsilon) cuando se añade ruido geométrico

ratios <- tbl1[S] / tbl2[S]
 # Debe ser <= exp(epsilon)
 max(ratios)< exp(epsilon)
## [1] TRUE
 cat("Pr[A(D) in S =", tbl1[S],"\n")
## Pr[A(D) in S = 2e-05 1e-05 4e-05 0.00016 0.00035 0.00083 0.00192 0.00534 0.01577 0.04304 0.11607 0.63356 0.11554 0.04254 0.0157 0.00574 0.00227 0.00074 2e-04 0.00012 2e-05 1e-05

Obtener distibuciones de probabilidad

# Parámetros
epsilon <- 1  # Nivel de privacidad
z <- 20       # Rango de ruido a graficar
# Distribución geométrica discreta centrada en 0
geom_mech <- function(eps, z) {
  c <- (1 + exp(eps)) / (1 - exp(-eps))  
  values <- -z:z
  probs <- (exp(-eps * abs(values))) / c
  return(data.frame(value = values, prob = probs))
}
# Graficar
library(ggplot2)
# Distribución para x = 0

df_x <- geom_mech(epsilon, z)
df_x$input <- "x"

# Distribución para x' = x + 1 (solo desplazada)
df_xp <- df_x
df_xp$value <- df_xp$value + 1
df_xp$input <- "x + 1"
# Unir datos
df_all <- rbind(df_x, df_xp)
# Gráfico
ggplot(df_all, aes(x = value, y = prob, fill = input)) +
  geom_bar(stat = "identity", position = "dodge", alpha = 0.8) +
  scale_fill_manual(values = c("x" = "steelblue", "x + 1" = "tomato")) +
  labs(
    title = expression(paste("Distribución de salida con ruido geométrico (", epsilon, "=1)")),
    x = "Salida y", y = "Probabilidad", fill = "Entrada"
  ) +
  theme_minimal()