poseticDataAnalysis (version 1.0.0)

BubleyDyerEvaluation: Estimating function averages on linear extensions, by the Bubley-Dyer procedure.

Description

BubleyDyerEvaluation computes the averages of the input functions (defined on linear orders) over a subset of linear extensions of the input poset, randomly generated by the Bubley-Dyer procedure.

Usage

BubleyDyerEvaluation(
  generator,
  n = NULL,
  error = NULL,
  output_every_sec = NULL
)

Value

List of the estimated averages, along with the number of linear extensions used to compute them.

Arguments

generator

S4 object of class BubleyDyerEvaluationGenerator created by function BuildBubleyDyerEvaluationGenerator(), implicitly containing the poset and the list of functions, whose averages are to be estimated.

n

Number of linear extensions to be generated. See the Details, for further information on this parameter.

error

A real number in \((0,1)\), representing the "distance" from uniformity of the sampling distribution of the linear extensions. This parameter is used to determine the number of linear extensions to be sampled, in order to achieve the desired "distance". According to Bubley and Dyer (1999), if error\(=\epsilon\) and \(E\) is the number of elements in the poset, then the number \(n_\epsilon\) of sampled linear extensions is given by

\(n_\epsilon=E^4(\ln(E))^2+E^3\ln(E)\ln(\epsilon^{-1})\).

If both arguments n and error are specified by the user, the number of linear extensions actually generated is n.

output_every_sec

Integer specifying a time interval (in seconds).
By specifying this argument, during the execution of BubleyDyerEvaluation, the number of linear extensions progressively generated is printed on the R-Console, every output_every_secseconds.

Details

The function BubleyDyerEvaluation allows the user to update previously computed averages, so as to improve estimation accuracy. The generator internally stores the averages computed at each call of BubleyDyerEvaluation. At the subsequent call (with the same generator argument), the previously computed averages are updated, based on the newly sampled linear extensions. In this case, the number of additional linear extensions is determined either directly, by parameter n, or indirectly, by specifying parameter error, which sets the desired "distance" from uniformity of the sampling distribution of linear extensions, in the Bubley-Dyer procedure. In the latter case, the number of additional linear extensions is computed as \(n_\epsilon-n_a\), where \(n_\epsilon\) is the number of linear extensions necessary to achive the desired "distance" and \(n_a\) is the total number of linear extensions generated in the previous calls of BubleyDyerEvaluation. If \(n_\epsilon-n_a\leq 0\), no further linear extensions are generated and a warning message is displayed.

In case new function averages are desired, run BubleyDyerEvaluation with a generator argument newly generated by function BuildBubleyDyerEvaluationGenerator.

References

Bubley, R., Dyer, M. (1999). Faster random generation of linear extensions. Discrete Mathematics, 201, 81-88. https://doi.org/10.1016/S0012-365X(98)00333-1

Examples

# \donttest{
el1 <- c("a", "b", "c", "d")
el2 <- c("x", "y")
el3 <- c("h", "k")
dom <- matrix(c(
  "a", "b",
  "c", "b",
  "b", "d"
), ncol = 2, byrow = TRUE)

pos1 <- POSet(elements = el1, dom = dom)

pos2 <- LinearPOSet(elements = el2)

pos3 <- LinearPOSet(elements = el3)

pos <- ProductPOSet(pos1, pos2, pos3)

# median_distr computes the frequency distribution of median profile

elements <- POSetElements(pos)

median_distr <- function(le) {
  n <- length(elements)
  if (n %% 2 != 0) {
    res <- (elements == le[(n + 1) / 2])
  } else {
    res <- (elements == le[n / 2])
  }
  res <- as.matrix(res)
  rownames(res) <- elements
  colnames(res) <- "median_distr"
  return (as.matrix(res))
}

# computation with parameter n
BDgen <- BuildBubleyDyerEvaluationGenerator(poset = pos, seed = NULL, median_distr)
res <- BubleyDyerEvaluation(BDgen, n=40000, output_every_sec=1)
#refinement results with parameter n
res <- BubleyDyerEvaluation(BDgen, n=10000, output_every_sec=1)
#refinement results with parameter error
res <- BubleyDyerEvaluation(BDgen, error=0.2, output_every_sec=1)
#Attempt to further refine results with parameter `error=0.2` does not modify previous result
res <- BubleyDyerEvaluation(BDgen, error=0.2, output_every_sec=1)

# computation with parameter error
BDgen <- BuildBubleyDyerEvaluationGenerator(poset = pos, seed = NULL, median_distr)
res <- BubleyDyerEvaluation(BDgen, error=0.2, output_every_sec=1)
# }