Search Results for “stochastic ordering”

Source: Stochastic ordering

In probability theory and statistics, a stochastic order quantifies the concept of one random variable being "bigger" than another. These are usually partial orders, so that one random variable

A

{\displaystyle A}

may be neither stochastically greater than, less than, nor equal to another random variable

B

{\displaystyle B}

. Many different orders exist, which have different applications.

Usual stochastic order

stochastic

= Characterizations

= Other properties

Stochastic dominance

Stochastic

stochastic

for at least one realization.
First-order stochastic dominance:

A

≺

(
1
)

B

{\displaystyle A\prec _{(1)}B}

if and only if

Pr
(
A
>
x
)
≤
Pr
(
B
>
x
)

{\displaystyle \Pr(A>x)\leq \Pr(B>x)}

for all

x

{\displaystyle x}

and there exists

x

{\displaystyle x}

such that

Pr
(
A
>
x
)
<
Pr
(
B
>
x
)

{\displaystyle \Pr(A>x)<\Pr(B>x)}

.
Second-order stochastic dominance:

A

≺

(
2
)

B

{\displaystyle A\prec _{(2)}B}

if and only if

∫

−
∞

x

[
Pr
(
B
>
t
)
−
Pr
(
A
>
t
)
]

d
t
≥
0

{\displaystyle \int _{-\infty }^{x}[\Pr(B>t)-\Pr(A>t)]\,dt\geq 0}

for all

x

{\displaystyle x}

, with strict inequality at some

x

{\displaystyle x}

.
There also exist higher-order notions of stochastic dominance. With the definitions above, we have

A

≺

(
i
)

B

⟹

A

≺

(
i
+
1
)

B

{\displaystyle A\prec _{(i)}B\implies A\prec _{(i+1)}B}

.

Multivariate stochastic order

An

R

d

{\displaystyle \mathbb {R} ^{d}}

-valued random variable

A

{\displaystyle A}

is less than an

R

d

{\displaystyle \mathbb {R} ^{d}}

-valued random variable

B

{\displaystyle B}

in the "usual stochastic order" if

E
⁡
[
f
(
A
)
]
≤
E
⁡
[
f
(
B
)
]

for all bounded, increasing functions

f
:

R

d

⟶

R

{\displaystyle \operatorname {E} [f(A)]\leq \operatorname {E} [f(B)]{\text{ for all bounded, increasing functions }}f\colon \mathbb {R} ^{d}\longrightarrow \mathbb {R} }

Other types of multivariate stochastic orders exist. For instance the upper and lower orthant order which are similar to the usual one-dimensional stochastic order.

A

{\displaystyle A}

is said to be smaller than

B

{\displaystyle B}

in upper orthant order if

Pr
(
A
>

x

)
≤
Pr
(
B
>

x

)

for all

x

∈

R

d

{\displaystyle \Pr(A>\mathbf {x} )\leq \Pr(B>\mathbf {x} ){\text{ for all }}\mathbf {x} \in \mathbb {R} ^{d}}

and

A

{\displaystyle A}

is smaller than

B

{\displaystyle B}

in lower orthant order if

Pr
(
A
≤

x

)
≤
Pr
(
B
≤

x

)

for all

x

∈

R

d

{\displaystyle \Pr(A\leq \mathbf {x} )\leq \Pr(B\leq \mathbf {x} ){\text{ for all }}\mathbf {x} \in \mathbb {R} ^{d}}

All three order types also have integral representations, that is for a particular order

A

{\displaystyle A}

is smaller than

B

{\displaystyle B}

if and only if

E
⁡
[
f
(
A
)
]
≤
E
⁡
[
f
(
B
)
]

{\displaystyle \operatorname {E} [f(A)]\leq \operatorname {E} [f(B)]}

for all

f
:

R

d

⟶

R

{\displaystyle f\colon \mathbb {R} ^{d}\longrightarrow \mathbb {R} }

in a class of functions

G

{\displaystyle {\mathcal {G}}}

.

G

{\displaystyle {\mathcal {G}}}

is then called generator of the respective order.

Other dominance orders

The following stochastic orders are useful in the theory of random social choice. They are used to compare the outcomes of random social choice functions, in order to check them for efficiency or other desirable criteria. The dominance orders below are ordered from the most conservative to the least conservative. They are exemplified on random variables over the finite support {30,20,10}.
Deterministic dominance, denoted

A

⪰

d
d

B

{\displaystyle A\succeq _{\mathrm {dd} }B}

, means that every possible outcome of

A

{\displaystyle A}

is at least as good as every possible outcome of

B

{\displaystyle B}

: for all x < y,

Pr
[
A
=
x
]
⋅
Pr
[
B
=
y
]
=
0

{\displaystyle \Pr[A=x]\cdot \Pr[B=y]=0}

. In other words:

Pr
[
A
≥
B
]
=
1

{\displaystyle \Pr[A\geq B]=1}

. For example,

0.6
×
30
+
0.4
×
20

⪰

d
d

0.5
×
20
+
0.5
×
10

{\displaystyle 0.6\times 30+0.4\times 20\succeq _{\mathrm {dd} }0.5\times 20+0.5\times 10}

.
Bilinear dominance, denoted

A

⪰

b
d

B

{\displaystyle A\succeq _{\mathrm {bd} }B}

, means that, for every possible outcome, the probability that

A

{\displaystyle A}

yields the better one and

B

{\displaystyle B}

yields the worse one is at least as large as the probability the other way around: for all x

Pr
[
A
=
x
]
⋅
Pr
[
B
=
y
]
≤
Pr
[
A
=
y
]
⋅
Pr
[
B
=
x
]

{\displaystyle \Pr[A=x]\cdot \Pr[B=y]\leq \Pr[A=y]\cdot \Pr[B=x]}

For example,

0.5
×
30
+
0.5
×
20

⪰

b
d

0.33
×
30
+
0.33
×
20
+
0.34
×
10

{\displaystyle 0.5\times 30+0.5\times 20\succeq _{\mathrm {bd} }0.33\times 30+0.33\times 20+0.34\times 10}

.
Stochastic dominance (already mentioned above), denoted

A

⪰

s
d

B

{\displaystyle A\succeq _{\mathrm {sd} }B}

, means that, for every possible outcome x, the probability that

A

{\displaystyle A}

yields at least x is at least as large as the probability that

B

{\displaystyle B}

yields at least x: for all x,

Pr
[
A
≥
x
]
≥
Pr
[
B
≥
x
]

{\displaystyle \Pr[A\geq x]\geq \Pr[B\geq x]}

. For example,

0.5
×
30
+
0.5
×
10

⪰

s
d

0.5
×
20
+
0.5
×
10

{\displaystyle 0.5\times 30+0.5\times 10\succeq _{\mathrm {sd} }0.5\times 20+0.5\times 10}

.
Pairwise-comparison dominance, denoted

A

⪰

p
c

B

{\displaystyle A\succeq _{\mathrm {pc} }B}

, means that the probability that that

A

{\displaystyle A}

yields a better outcome than

B

{\displaystyle B}

is larger than the other way around:

Pr
[
A
≥
B
]
≥
Pr
[
B
≥
A
]

{\displaystyle \Pr[A\geq B]\geq \Pr[B\geq A]}

. For example,

0.67
×
30
+
0.33
×
10

⪰

p
c

1.0
×
20

{\displaystyle 0.67\times 30+0.33\times 10\succeq _{\mathrm {pc} }1.0\times 20}

.
Downward-lexicographic dominance, denoted

A

⪰

d
l

B

{\displaystyle A\succeq _{\mathrm {dl} }B}

, means that

A

{\displaystyle A}

has a larger probability than

B

{\displaystyle B}

of returning the best outcome, or both

A

{\displaystyle A}

and

B

{\displaystyle B}

have the same probability to return the best outcome but

A

{\displaystyle A}

has a larger probability than

B

{\displaystyle B}

of returning the second-best best outcome, etc. Upward-lexicographic dominance is defined analogously based on the probability to return the worst outcomes. See lexicographic dominance.

Other stochastic orders

= Hazard rate order

=
The hazard rate of a non-negative random variable

X

{\displaystyle X}

with absolutely continuous distribution function

F

{\displaystyle F}

and density function

f

{\displaystyle f}

is defined as

r
(
t
)
=

d

d
t

(
−
log
⁡
(
1
−
F
(
t
)
)
)
=

f
(
t
)

1
−
F
(
t
)

.

{\displaystyle r(t)={\frac {d}{dt}}(-\log(1-F(t)))={\frac {f(t)}{1-F(t)}}.}

Given two non-negative variables

X

{\displaystyle X}

and

Y

{\displaystyle Y}

with absolutely continuous distribution

F

{\displaystyle F}

and

G

{\displaystyle G}

, and with hazard rate functions

r

{\displaystyle r}

and

q

{\displaystyle q}

, respectively,

X

{\displaystyle X}

is said to be smaller than

Y

{\displaystyle Y}

in the hazard rate order (denoted as

X

⪯

h
r

Y

{\displaystyle X\preceq _{\mathrm {hr} }Y}

) if

r
(
t
)
≥
q
(
t
)

{\displaystyle r(t)\geq q(t)}

for all

t
≥
0

{\displaystyle t\geq 0}

,
or equivalently if

1
−
F
(
t
)

1
−
G
(
t
)

{\displaystyle {\frac {1-F(t)}{1-G(t)}}}

is decreasing in

t

{\displaystyle t}

.

= Likelihood ratio order

=
Let

X

{\displaystyle X}

and

Y

{\displaystyle Y}

two continuous (or discrete) random variables with densities (or discrete densities)

f
(
t
)

{\displaystyle f(t)}

and

g
(
t
)

{\displaystyle g(t)}

, respectively, so that

g
(
t
)

f
(
t
)

{\displaystyle {\frac {g(t)}{f(t)}}}

increases in

t

{\displaystyle t}

over the union of the supports of

X

{\displaystyle X}

and

Y

{\displaystyle Y}

; in this case,

X

{\displaystyle X}

is smaller than

Y

{\displaystyle Y}

in the likelihood ratio order (

X

⪯

l
r

Y

{\displaystyle X\preceq _{\mathrm {lr} }Y}

).

= Variability orders

=
If two variables have the same mean, they can still be compared by how "spread out" their distributions are. This is captured to a limited extent by the variance, but more fully by a range of stochastic orders.

Convex order

Convex order is a special kind of variability order. Under the convex ordering,

A

{\displaystyle A}

is less than

B

{\displaystyle B}

if and only if for all convex

u

{\displaystyle u}

,

E
⁡
[
u
(
A
)
]
≤
E
⁡
[
u
(
B
)
]

{\displaystyle \operatorname {E} [u(A)]\leq \operatorname {E} [u(B)]}

.

= Laplace transform order

=
Laplace transform order compares both size and variability of two random variables. Similar to convex order, Laplace transform order is established by comparing the expectation of a function of the random variable where the function is from a special class:

u
(
x
)
=
−
exp
⁡
(
−
α
x
)

{\displaystyle u(x)=-\exp(-\alpha x)}

. This makes the Laplace transform order an integral stochastic order with the generator set given by the function set defined above with

α

{\displaystyle \alpha }

a positive real number.

= Realizable monotonicity

=
Considering a family of probability distributions

(

P

α

)

α
∈
F

{\displaystyle ({P}_{\alpha })_{\alpha \in F}}

on partially ordered space

(
E
,
⪯
)

{\displaystyle (E,\preceq )}

indexed with

α
∈
F

{\displaystyle \alpha \in F}

(where

(
F
,
⪯
)

{\displaystyle (F,\preceq )}

is another partially ordered space, the concept of complete or realizable monotonicity may be defined. It means, there exists a family of random variables

(

X

α

)

α

{\displaystyle (X_{\alpha })_{\alpha }}

on the same probability space, such that the distribution of

X

α

{\displaystyle X_{\alpha }}

is

P

α

{\displaystyle {P}_{\alpha }}

and

X

α

⪯

X

β

{\displaystyle X_{\alpha }\preceq X_{\beta }}

almost surely whenever

α
⪯
β

{\displaystyle \alpha \preceq \beta }

. It means the existence of a monotone coupling. See

References

Bibliography

M. Shaked and J. G. Shanthikumar, Stochastic Orders and their Applications, Associated Press, 1994.
E. L. Lehmann. Ordered families of distributions. The Annals of Mathematical Statistics, 26:399–419, 1955.