Skip to main content
2 of 3
+top level tag (pr)
Myshkin
  • 17.6k
  • 5
  • 71
  • 137

Stochastic orders

Please forgive me if this is not precise enough to post here. Simply ask me to remove it if it is not suitable. I am new here.

I am bounding the running time of an algorithm as a random variable $X$ and want to preserve as much information about the distribution of $X$ as possible. For various reasons the basic distributions that show up are geometric, negative binomial, or slight tweaks of these. There is some leg room to change the algorithm to give a simpler analysis.

The idea is now to not do things the usual computer science way, i.e., ad-hoc analysis of expected values and possibly bounds on variance etc recursively, but to operate on the distributions themselves. Apart from potentially being clean it has other advantages that would take us too far to explain here.

A natural thing is then for example to "bound" a negative binomial distribution $NB(p,r)$ (counting steps until we have $r$ successes) by another negative binomial distribution with smaller $r'$ that is more efficient to sample, expected value related by $r/r'$, but is not as concentrated.

More complicated examples are things expressed as $G_Y\circ G_X$ for probability (or moment) generating functions of $X$ and $Y$, both with negative binomial-ish distributions, or $\min(X,Y)$, etc.

Is there a unified theory for operating and "bounding" distributions of these "well-behaved" forms that Google refuses to point out to me and none of my colleagues know about?

"Bounding" here means a stochastic order of course, but is there a "right" choice in this setting?

dog
  • 11
  • 2