A Study on Poset Probability
Abstract: Let be a finite poset (partially ordered set) with cardinality
. A linear extension of
is an order-preserving bijection
:
, that is, if
in
then
. We define the poset probability
as the proportion of linear extensions where
. We are primarily interested in
for incomparable elements
. The probability has significance in areas such as information theory. Let
denote the total number of linear extensions of
. We prove that the poset probability can be evaluated as
where
is the set of order ideals of
without
or
, where we can add
to get a new order ideal of
. The practicality of the preceding formula is explored and we show that
The formula is particularly useful for certain classes of posets such as partition posets which are examined in further detail. We apply the formula to prove that, for all partition posets of shape
, the probability obeys
where
is the nth Catalan number and
. We also explore how Monte Carlo methods can be used to estimate
.
AT THIS PAGE YOU CAN DOWNLOAD THE WHOLE ESSAY. (follow the link to the next page)
