Determining transition probabilities in probabilistic algotithms

The main problem of the paper is related to the algebraic method for determining transition probabilities in probabilistic algorithms interpreted in finite structures. The correctness of this method is based on a lemma stating that the determinant of a matrix (being of a special form) is different from zero. The paper contains two proofs of this lemma, formulated without a proof in [3].

---

Poniższa praca zawiera dwa dowody lematu opublikowanego w pracy [3] bez dowodu. Algebraiczny fakt rozważany w lemacie jest punktem wyjściowym dla metody wyznaczania prawdopodobieństw przejść w iteracyjnych algorytmach probabilistycznych interpretowanych w skończonych dziedzinach. Dotyczy on niezerowości wyznacznika macierzy o pewnej specyficznej postaci.