Uma cadeia de Markov é uma sequência X₁, X₂, X₃, ... de variáveis aleatórias. O escopo destas variáveis, isto é, o conjunto de valores que elas podem assumir, é chamado de espaço de estados, onde X_n denota o estado do processo no tempo n. Se a distribuição de probabilidade condicional de X_n+1 nos estados passados é uma função apenas de X_n, então:

Uma maneira simples de visualizar um tipo específico de cadeia de Markov é através de uma máquina de estados finitos. Se você está no estado y no tempo n, então a probabilidade de que você se mova para o estado x no tempo n + 1 não depende de n, e somente depende do estado atual y em que você está. Assim em qualquer tempo n, uma cadeia de Markov finita pode ser caracterizada por uma matriz de probabilidades cujo elemento (x, y) é dado por e é independente do tempo n. Estes tipos de cadeia de Markov finitas e discretas podem também ser descritas por meio de um grafo dirigido (orientado), onde cada aresta é rotulada com as probabilidades de transição de um estado a outro sendo estes estados representados como os nós conectados pelas arestas.