Let A be the W*-algebra, L1(E(0),), where E(0) is a fnite set and is a probability measure with full support. Let P:A->A be a completely positive unital map. In the present context, P is given by a stochastic matrix. We study the properties of P that are refected in the dilation theory developed by Muhly and Solel in Int. J. Math. 13, 2002. Let H be the Hilbert space L2(E(0),) and let pi : A -> B(H) the representation of A given by multiplication. Form the Stinespring space H1. Then X is a W*-correspondence over P is expressed through a completely contractive representation T of X on H. This representation can be dilated to an isometric representation V of X on a Hilbert space that contains H. We show that X is naturally isomorphic to the correspondence associated to the directed graph E whose vertex space is E(0) and whose edge space is the support of the matrix representing P - a subset of E(0)E(0). Further, V is shown to be essentially a Cuntz-Krieger representation of E. We also study the simplicity and the ideal structure of the graph C*-algebra associated to the stochastic matrix P.