2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Probably this is the distribution with density $ce^{-k|x|}$. $\endgroup$ – Alexandre Eremenko Aug 7 '15 at 13:45
  • $\begingroup$ @Alexandre Eremenko: On the integers, that is. As a density (on the reals) it is called the double exponential distribution. $\endgroup$ – kjetil b halvorsen Aug 7 '15 at 13:56
  • $\begingroup$ @AlexandreEremenko How is this related to the standard geometric distribution? Could you refer me to some text on this subject? A simple internet search did not reveal much. Thanks a lot. $\endgroup$ – Arani Aug 7 '15 at 15:30
  • $\begingroup$ @AlexandreEremenko Also, the text says that its density is $\frac{\alpha - 1}{\alpha + 1} \alpha^{-|k|}$. I am not sure how this follows from the above function. $\endgroup$ – Arani Aug 7 '15 at 15:36
2
$\begingroup$

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))
$\endgroup$
  • $\begingroup$ Hi Andrew, welcome to OP. (a) Can you provide a reference to your answer? (b) Is the inset equation the definition of the two-sided geometric distribution? (c) Is it defined only for integers? $\endgroup$ – Amir Sagiv Nov 7 at 18:50
  • $\begingroup$ There are two problems with this answer: 1) "the 'probability of staying at $0$' is calculated differently than the other integers" - how, exactly? 2) Python code is unlikely to be much appreciated on a mathematics-oriented site. I don't know who upvoted this, but I consider it to be quite a poor answer. In particular, I don't see how it answers the OP's question. $\endgroup$ – Alex M. Nov 7 at 19:07
  • $\begingroup$ I edited my answer to (hopefully) address these deficiencies. $\endgroup$ – Andrew Reed Nov 7 at 21:57
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi and welcome to MO. How does the paper you link to answers the OP? Can you add a few sentences? $\endgroup$ – Amir Sagiv Oct 15 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.