9. Vytvořující funkce a jejich aplikace při analýze homogenních markovských řetězců

   

   9.1. Motivace

   

   9.2. Definice: Definice vytvořující funkce posloupnosti reálných čísel.

   

   9.3. Příklad: Najděte vytvořující funkce k posloupnostem:

   a) a[n] = 1, n = 0, 1, ...

   b) a[n] = n, n = 0, 1, ...

   c) a[n] = x^n, n = 0, 1, ...

   d) a[n] = nx^n, n = 0, 1, ...

   

   Řešení:

   ad a)

   ad b)

   ad c)

   ad d)

   Výsledky uspořádáme do přehledné tabulky:

   +------------------------------------+
   |a[n           |G[a](z)              |
   |--------------+---------------------|
   |]1            |1/(1-z)              |
   |--------------+---------------------|
   |n             |z/(1-z)^2            |
   |--------------+---------------------|
   |x^n           |1/(1-xz)             |
   |--------------+---------------------|
   |nx^n          |xz/(1-xz)^2          |
   +------------------------------------+

   

   9.4. Věta: Výpočet členů posloupnosti pomocí vytvořující funkce

   

   9.5. Příklad: Je dána vytvořující funkce G[a](z) = e^z. Najděte odpovídající posloupnost .

   Řešení: a[0] = 1, .

   

   9.6. Definice: Definice konvoluce a konvoluční mocniny.

   

   9.7. Věta: Výpočet vytvořující funkce konvoluce a konvoluční mocniny.

   

   9.8. Definice: Definice vytvořující funkce posloupnosti vektorů resp. matic.

   

   9.9. Věta: Výpočet vytvořující funkce posloupnosti matic přechodu HMŘ po n krocích.

   

   9.10. Věta: Výpočet vytvořující funkce posloupnosti vektorů absolutních pravděpodobností HMŘ
   po n krocích.

   

   9.11. Poznámka: Poznámka o úspoře numerických výpočtů při použití vytvořujících funkcí.

   

   9.12. Příklad: Nechť homogenní markovský řetězec  s množinou stavů
   J = {1,2}  popisuje chování výrobní linky, která se v n-tém období nachází buď v provozu (stav
   1) nebo v opravě (stav 2). Dlouhodobým sledováním byla zjištěna matice přechodu: . Pomocí
   vytvořujících funkcí najděte matici přechodu po n krocích P^n a vektor absolutních
   pravděpodobností po n krocích p(n).

   

   Řešení: Z věty 9.9. plyne, že .

   det(I-zP) =

   .

   (Upozornění: Prvky matice  byly získány rozkladem na parciální zlomky. Např. prvek a[11] = .
   Podobně získáme další prvky.)

    je vytvořující funkce posloupnosti a[n] = 1, n = 0, 1, 2, ...

    je vytvořující funkce posloupnosti a[n] = , n = 0, 1, 2, ...

   Matici P^n lze tedy psát ve tvaru: P^n = .

   Interpretace: První matice je konstantní a nezávisí na počtu kroků. Lze snadno ověřit, že je
   to limitní matice přechodu A. Druhá matice násobená koeficientem , představuje přechodnou
   složku daného homogenního markovského řetězce.

   

   Pro vektor absolutních pravděpodobností platí:

   p(n) = p(0).P^n = p(0). Druhý sčítanec v závorce pro
   n → ∞ konverguje k 0, tedy lze psát . Pomocí vytvořujících funkcí jsme tedy
   dostali vektor limitních pravděpodobností .