  This paper studies the maximum cardinality matching problem in stochastically
evolving graphs. We formally define the arrival-departure model with stochastic
departures. There, a graph is sampled from a specific probability distribution
and it is revealed as a series of snapshots. Our goal is to study algorithms
that create a large matching in the sampled graphs. We define the price of
stochasticity for this problem which intuitively captures the loss of any
algorithm in the worst case in the size of the matching due to the uncertainty
of the model. Furthermore, we prove the existence of a deterministic optimal
algorithm for the problem. In our second set of results we show that we can
efficiently approximate the expected size of a maximum cardinality matching by
deriving a fully randomized approximation scheme (FPRAS) for it. The FPRAS is
the backbone of a probabilistic algorithm that is optimal when the model is
defined over two timesteps. Our last result is an upper bound of $\frac{2}{3}$
on the price of stochasticity. This means that there is no algorithm that can
match more than $\frac{2}{3}$ of the edges of an optimal matching in hindsight.
