In a couple of papers I am working on (in random graph theory) I have encountered the following property of certain probability distributions, which I will describe shortly, and I am wondering if this property has been studied or named previously.
Some quick background:
The exponential distribution is min-stable: Whenever, for some $t \in (0,1)$, $X\sim Exp(t)$ and $Y\sim Exp(1-t)$, then $\min(X,Y)\sim Exp(1)$. (Another way of expressing this is that if $X\sim Exp(1)$ and $Y\sim Exp(1)$, then $\min(\frac{X}{t},\frac{Y}{1-t})\sim Exp(1)$.) Similarly, generalized extreme value (GEV) distributions are max-stable: the maximum over several (rescaled) GEV random variables is itself a GEV random variable.
The usage of the word 'stable' stems from the stability property of the Gaussian, Cauchy & Lévy distributions, where a similar property holds but with a sum instead of min or max.
My question
The property that I am interested is the following: Let $X,Y$ be independent non-negative random variables following some distribution $F$. Assume there exist $a,b>0$ such that $X,Y$ can be coupled to a $Z$ following the same distribution and satisfying $$ \mathrm{Property: \,\,}Z \leq \min(aX,bY)$$
More specifically, I am interested in the case when for some $q>0$ and any $t\in (0,1)$ this is true with $a:=t^{-q},b:=(1-t)^{-q}$. As noted above, this holds with equality with $q=1$ when $F$ is the exponential distribution, and as a consequence it holds for the Weibull distribution with shape parameter $q^{-1}$. It also holds with $q=1$ for the continuous uniform $U(0,1)$ distribution, which is used in a 1979 paper on the minimum matching problem by Walkup. In general, it often holds when the cdf $F$ scales like $F(t)=t^{1/q}$ near $0$ and is otherwise nicely behaved.
In contrast to min-stability, this property can hold for both continuous and discrete probability distributions. I think it holds for the discrete uniform distribution $\mathrm{Unif}(1,k)$, but I have not checked this carefully.
- Are you aware of this property being studied elsewhere?
- If not, what would be a good name for it? Min-stable distributions have been defined in extrem value theory, but sub-min-stable does not feel quite right: The distribution is not stable under taking minimums, it is more like a monotonicity condition. One could also consider this property as a 'one-sided' version of min-stability, but the terms semi-stable and one-sided stability are already used for other things.
- Could something akin to the Fisher–Tippett–Gnedenko theorem hold for this variant of min-stability? That theorem is a complete classification of max-stable distributions: the only possible cases are the Fréchet, Gumbel or Weibull distributions. Since the property above is looser (only an inequality), a complete classification is probably too much to ask for, but something weaker could be attainable.
Any help or links to papers would be appreciated. This isn't quite my area of expertise, and I have searched using the terms that I could find -- but I could easily be missing some crucial piece of terminology.
Motivation
Let's say that you have the complete graph $K_n$ with random $Exp(1)$ edge weights, and want to find some specific structure in it -- an $n$-cycle, or a spanning tree, say -- whose total weight is low. (The total weight of a subgraph is the sum of the edge weights of the edges used in the subgraph.) A useful trick is to split each edge into two: a green edge with an $Exp(1-t)$ weight, and a red edge with an independent $Exp(t)$ weight, for some small $t>0$. The minimum of such a pair of edge weights then follows an $Exp(1)$ distribution.
One can then use the marginally heavier green edges to build an almost complete structure (for instance, any path on $n-k$ vertices for some $k$), and use the much heavier red edges to finish it. The hope is that if only a small number of red edges is used, their large weights won't dominate the total weight. The total weight of the structure obtained in this way is an upper bound on the optimal structure. However, the green and red edge weights are independent and this makes the problem easier to analyse. (The incomplete green structure is independent from the red edge weights.)
(In Walkup's paper, this trick was used to show that the minimum weight of a perfect matching on the complete bipartite graph with $n+n$ vertices and with random $U(0,1)$ edge weights is at most 3. It was later shown that the minimum weight converges to $\zeta(2)=\pi^2/6$ in probability as $n\to \infty$.) A variant of this trick was also used in the proof of a similar convergence for the Traveling Salesman problem (i.e. finding a spanning cycle).
