We are interested in estimating the transition matrix of a discrete time, finite Markov chain in the presence of covariates. The data points are obtained from independent sample paths of the chain which are observed at random times. This study was motivated by the circulation of banknotes where a sample path corresponds to a banknote. Based on suitable independence assumptions, we build simple conditional transition matrix estimates, given the covariate vector value, using empirical estimators of transition probabilities and $\ell-$th roots of the transition matrices. The effect of continuous covariates is accounted for by kernel smoothing and the one of discrete covariates via stratification. The conditional transition matrix estimator can be easily applied to large streaming data and requires low computer resources. The performance of our approach is illustrated using simulated data.