Revisions to What is a two-sided geometric distribution?

Added language identifier to highlight code

Source Link

edit approved Apr 20, 2023 at 14:20

Carlos Pinzón

103
4

Addressed comments on my initial answer

Source Link

edited Nov 7, 2019 at 20:42

Andrew Reed

41
3

The differences betweenTo understand the two-sided geometric (TSG) distribution, I think it helps to contrast it with the "standard" geometric distribution. For the geometric distribution, I will assume the following convention from Wikipedia:

The probability distribution of the number X of Bernoulli trials needed to get one success, supported on the set { 1, 2, 3, ... }

e.g. In the case of flipping a fair coin, 50% of the time we would expect success ("heads") after 1 trial (coin flip). For a fair coin, where Pr[heads] = Pr[tails] = 0.5, the expected number of trials to flip heads decreases by a factor of 0.5. This constant factor results in a geometric progression.

Note that - for what I am referring to as a "standard" geometric progression - the probability of success after 1 trial is, by definition, the probability that a single trial yields success (50% in the coin-flipping example). Also, note that there is no notion of "success after 0 trials" in the convention that I am referencing.

Now, let's contrast the "standard" geometric distribution with the TSG, as described in Universally Utility-Maximizing Privacy Mechanisms (UUMPM). In UUMPM, the authors introduce the TSG as a method to introduce "discrete noise" to discrete values, as opposed to introducing "continuous noise" via the Laplace distribution. Thus, the TSG is supported on the set of all integers, as opposed to the "standard" geometric distribution, which is only supported on positive integers. In other words, as a noise-generation mechanism, the TSG can randomly introduce 0 noise, negative discrete noise, or positive discrete noise.

In UUMPM, the authors give the probability mass function (PMF) of the TSG as: $$Pr[ Z = z] = \frac{1-\alpha}{1+\alpha}\alpha^{\left | z \right |}$$

Semantically, this gives the probability of introducing $|z|$ amount of "discrete noise." Note that the TSG decays in the same way that a "standard" geometric distribution decays: for each increment of $z$, either positive or negative, the probability decreases by a factor of $\alpha$.

This leads us to what I would consider the main difference between a TSG and the "standard" geometric distribution are: the probability that the TSG introduces 0 noise.

The samples/results can include 0 and negative numbers, and

the "probability of staying at 0" is calculated differently than the other integers.

Note that, when $z = 0$, the PMF for the TSG becomes: $$Pr[ Z = z] = \frac{1-\alpha}{1+\alpha}$$

The Python codeAs a concrete example, let's assume we have a TSG that "decays like" the coin-flipping example above (belowi.e $\alpha = 0.5$). This yields: $$Pr[ Z = 0 | \alpha = 0.5] = \frac{1-0.5}{1+0.5}0.5^{\left | 0 \right |} = \frac{0.5}{1.5} = 33.\overline{3}\%$$

Thus, for a TSG that decays with $\alpha = 0.5$, we have a $33.\overline{3}\%$ chance of introducing 0 noise. From this "starting base" of $33.\overline{3}\%$, the probability of introducing a certain amount of discrete noise decreases by a factor of 0.5, in both the positive and negative directions. e.g. $Pr[Z = -1] = Pr[Z = 1] = 16.\overline{6}\%$, etc.

Again, contrast this result for the TSG with the example of coin-flipping with a "standard" geometric distribution. Although both of the distributions I described decay with a ratio of 0.5, the TSG "started at" 0 with $33.\overline{3}\%$ probability, whereas the "standard" geometric distribution "started at 1" with $50\%$ probability.

For anyone interested in sampling from the two-sided geometric distribution, here is some Python code I wrote that implements Example 2.1 from the OP's linkUUMPM. Specifically, given the probability mass functionPMF for a two-sided geometric distribution: $$Pr[ Z = z] = \frac{1-\alpha}{1+\alpha}\alpha^{\left | z \right |}$$

The differences between the two-sided geometric distribution and the "standard" geometric distribution are:

The samples/results can include 0 and negative numbers, and

the "probability of staying at 0" is calculated differently than the other integers.

The Python code (below) implements Example 2.1 from the OP's link. Specifically, given the probability mass function for a two-sided geometric distribution: $$Pr[ Z = z] = \frac{1-\alpha}{1+\alpha}\alpha^{\left | z \right |}$$

To understand the two-sided geometric (TSG) distribution, I think it helps to contrast it with the "standard" geometric distribution. For the geometric distribution, I will assume the following convention from Wikipedia:

The probability distribution of the number X of Bernoulli trials needed to get one success, supported on the set { 1, 2, 3, ... }

e.g. In the case of flipping a fair coin, 50% of the time we would expect success ("heads") after 1 trial (coin flip). For a fair coin, where Pr[heads] = Pr[tails] = 0.5, the expected number of trials to flip heads decreases by a factor of 0.5. This constant factor results in a geometric progression.

Note that - for what I am referring to as a "standard" geometric progression - the probability of success after 1 trial is, by definition, the probability that a single trial yields success (50% in the coin-flipping example). Also, note that there is no notion of "success after 0 trials" in the convention that I am referencing.

Now, let's contrast the "standard" geometric distribution with the TSG, as described in Universally Utility-Maximizing Privacy Mechanisms (UUMPM). In UUMPM, the authors introduce the TSG as a method to introduce "discrete noise" to discrete values, as opposed to introducing "continuous noise" via the Laplace distribution. Thus, the TSG is supported on the set of all integers, as opposed to the "standard" geometric distribution, which is only supported on positive integers. In other words, as a noise-generation mechanism, the TSG can randomly introduce 0 noise, negative discrete noise, or positive discrete noise.

In UUMPM, the authors give the probability mass function (PMF) of the TSG as: $$Pr[ Z = z] = \frac{1-\alpha}{1+\alpha}\alpha^{\left | z \right |}$$

Semantically, this gives the probability of introducing $|z|$ amount of "discrete noise." Note that the TSG decays in the same way that a "standard" geometric distribution decays: for each increment of $z$, either positive or negative, the probability decreases by a factor of $\alpha$.

This leads us to what I would consider the main difference between a TSG and the "standard" geometric distribution: the probability that the TSG introduces 0 noise.

Note that, when $z = 0$, the PMF for the TSG becomes: $$Pr[ Z = z] = \frac{1-\alpha}{1+\alpha}$$

As a concrete example, let's assume we have a TSG that "decays like" the coin-flipping example above (i.e $\alpha = 0.5$). This yields: $$Pr[ Z = 0 | \alpha = 0.5] = \frac{1-0.5}{1+0.5}0.5^{\left | 0 \right |} = \frac{0.5}{1.5} = 33.\overline{3}\%$$

Thus, for a TSG that decays with $\alpha = 0.5$, we have a $33.\overline{3}\%$ chance of introducing 0 noise. From this "starting base" of $33.\overline{3}\%$, the probability of introducing a certain amount of discrete noise decreases by a factor of 0.5, in both the positive and negative directions. e.g. $Pr[Z = -1] = Pr[Z = 1] = 16.\overline{6}\%$, etc.

Again, contrast this result for the TSG with the example of coin-flipping with a "standard" geometric distribution. Although both of the distributions I described decay with a ratio of 0.5, the TSG "started at" 0 with $33.\overline{3}\%$ probability, whereas the "standard" geometric distribution "started at 1" with $50\%$ probability.

For anyone interested in sampling from the two-sided geometric distribution, here is some Python code I wrote that implements Example 2.1 from UUMPM. Specifically, given the PMF for a two-sided geometric distribution: $$Pr[ Z = z] = \frac{1-\alpha}{1+\alpha}\alpha^{\left | z \right |}$$

Source Link

created Nov 7, 2019 at 18:42

Andrew Reed

41
3

The differences between the two-sided geometric distribution and the "standard" geometric distribution are:

The samples/results can include 0 and negative numbers, and
the "probability of staying at 0" is calculated differently than the other integers.

The Python code (below) implements Example 2.1 from the OP's link. Specifically, given the probability mass function for a two-sided geometric distribution: $$Pr[ Z = z] = \frac{1-\alpha}{1+\alpha}\alpha^{\left | z \right |}$$

zeroProb() implements $\frac{1-\alpha}{1+\alpha}$
np.random.geometric(1-p) implements $\alpha^{\left | z \right |}$
signProb() accounts for the absolute value in $\alpha^{\left | z \right |}$

    #!/usr/bin/env python
    
    import random
    import numpy as np
    
    # The "chance of staying put at 0" is the main difference from the
    # standard implementation of a geometric distribution.
    
    # zeroProb() will return 1 if you "leave 0," which effectively
    # "turns ON" the standard implementation in twoSidedGeoDist().
    def zeroProb(p):
      #                    this is the chance of "staying put at 0"
      if random.random() < (1.0 - p)/(1.0 + p):
        return 0
      else:
        return 1
    
    # Coin flip to determine if the result is negative or positive.
    # This only applies when we "leave 0."
    def signProb():
      if random.random() < 0.5:
        return -1
      else:
        return 1
    
    def twoSidedGeoDist(p):
      #      (1) Did we "leave 0"? [Y=1|N=0]          (3) +/-
      return zeroProb(p) * np.random.geometric(1-p) * signProb()
    #                      (2) "Leave 0" i.e. Standard implementation
    
    alpha = 1.0/3.0
    counts = {}
    trials = 1000000
    
    for i in range(trials):
      result = twoSidedGeoDist(alpha)
      if result in counts:
        counts[result] = counts[result] + 1
      else:
        counts[result] = 1
    
    for x in sorted(counts.keys()):
      print(str(x) + "\t" + str(counts[x]) + "\t" + str(counts[x]*1.0 / trials))

Stack Exchange Network

Return to Answer