Frequent episode mining is a popular method for discovering temporal dependencies in symbolic time series data. In frequent pattern mining, it is important to assess statistical significance of discovered patterns so as to be able to discard unimportant patterns. In the literature, statistical significance is assessed through a hypothesis testing framework where the null hypothesis models data with no important patterns. Most currently available methods for frequent episode mining can handle only an iid null hypothesis. Since the data is a time series, it is desirable to deal with a null hypothesis that also allows for simple temporal dependencies. In this paper we present a method to characterize the distribution of non-overlapped occurrences of an episode and hence to assess its significance under a Markovian null hypothesis. This is the first such result. We illustrate the effectiveness of the method through simulations.