What is a two-sided geometric distribution?

Question

I found in some articles (such as this) references to two-sided geometric distribution. But I went through texts of probability and did not find anything called "two-sided geometric distribution". What does this mean? And where can I find standard formulas for this model?

Answer 1

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 |}$$

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

Answer 2

This is quite old but I thought I would add an answer to help anyone else who might run across this same question. I stumbled upon this reading the same paper as the OP. A google search lead me here. I found a better explanation per this paper also pertaining to diff privacy:

https://privacytools.seas.harvard.edu/files/privacytools/files/diff_priv.pdf

To put it simply it is a discrete analog to the Laplace distribution. I hope that helps.