Fishing For Better Constants: The Prophet Secretary Via Poissonization

We introduce a new technique (i.e. \emph{sharding}) of breaking up random variables into many independent random variables that behaves together as the original single random variable. This in turn enables us to model the random variables using a Poisson distribution (i.e. \emph{Poissonization}). These two ideas, leads to an improved analysis of the Prophet Secretary problem and its variants. Beyond the (small but significant) improvement in the constants, the new analysis is significantly simpler and more intuitive than previous (quite involved) analysis. We also get several simpler proofs of existing known results. The new approach might be of independent interest to the order-selection variant of the prophet inequality.