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?

  • $\begingroup$ It sounds to me as though you want to use stochastic ordering / monotone couplings. A reference book for this is "Lectures on the Coupling Method" by T. Lindvall. Google should find lots of hits also. $\endgroup$ – Anthony Quas Feb 25 '16 at 19:08
  • $\begingroup$ Thank you for your response! I have used coupling in the past, but for a special case so I never viewed it as related. I have googled and read a little, but it seems that what I have in mind is not really fleshed out anywhere. Admittedly, it is a special case, but it seems so natural to me. $\endgroup$ – dog Feb 25 '16 at 21:54
  • $\begingroup$ The stochastic ordering of two negative binomial laws, but in the version where you only count the failures and not all necessary trials, is characterized in projecteuclid.org/…, with the condition in the abstract being correct and in display (1.11) in the paper erroneous. $\endgroup$ – Lutz Mattner Feb 25 '16 at 23:45
  • $\begingroup$ The method of the above paper might also work for your shifted negative binomials. $\endgroup$ – Lutz Mattner Feb 25 '16 at 23:52
  • $\begingroup$ That is exactly what I was looking for Lutz! Thank you for this hammer :-) I need a few more tools so I will read your paper carefully and see what I can get. $\endgroup$ – dog Feb 26 '16 at 1:55

Your Answer

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

Browse other questions tagged or ask your own question.