We study subproduct systems in the sense of Shalit and Solel arising from stochastic matrices on countable state spaces, and their associated operator algebras. We focus on the non-self-adjoint tensor algebra, and Viselters generalization of the Cuntz-Pimsner C*-algebra to the context of subproduct systems. Suppose that $X$ and $Y$ are Arveson-Stinespring subproduct systems associated to two stochastic matrices over a countable set $Omega$, and let $mathcal{T}_+(X)$ and $mathcal{T}_+(Y)$ be their tensor algebras. We show that every algebraic isomorphism from $mathcal{T}_+(X)$ onto $mathcal{T}_+(Y)$ is automatically bounded. Furthermore, $mathcal{T}_+(X)$ and $mathcal{T}_+(Y)$ are isometrically isomorphic if and only if $X$ and $Y$ are unitarily isomorphic up to a *-automorphism of $ell^infty(Omega)$. When $Omega$ is finite, we prove that $mathcal{T}_+(X)$ and $mathcal{T}_+(Y)$ are algebraically isomorphic if and only if there exists a similarity between $X$ and $Y$ up to a *-automorphism of $ell^infty(Omega)$. Moreover, we provide an explicit description of the Cuntz-Pimsner algebra $mathcal{O}(X)$ in the case where $Omega$ is finite and the stochastic matrix is essential.