Markov Chains: How much steps to conclude a Transition Matrix
I expect you have, or can make, a matrix of transition counts. Consider the data in each row to be draws from a multinomial distribution. Then you should be able to use sample size calculations for the multinomial to get off the ground. 

It is also possible that your data is not well described by a simple Markov chain. There are some available techniques for this, e.g. multistate modelling, but which may or may not fit your particular problem.