Title: Stochastic Input Models in Online Computing,
Abstract: In this paper, we study twelve stochastic input models for online problems
and reveal the relationships among the competitive ratios for the models. The
competitive ratio is defined as the worst ratio between the expected optimal
value and the expected profit of the solution obtained by the online algorithm
where the input distribution is restricted according to the model. To handle a
broad class of online problems, we use a framework called request-answer games
that is introduced by Ben-David et al. The stochastic input models consist of
two types: known distribution and unknown distribution. For each type, we
consider six classes of distributions: dependent distributions, deterministic
input, independent distributions, identical independent distribution, random
order of a deterministic input, and random order of independent distributions.
As an application of the models, we consider two basic online problems, which
are variants of the secretary problem and the prophet inequality problem, under
the twelve stochastic input models. We see the difference of the competitive
ratios through these problems.