P6 - Vytvořující funkce 1.16 Pojem vytvořující funkce Významným analytickým prostředkem pro řešení úloh spojených s Markovovými řetězci jsou vytvořující funkce [moment generating functions].[1] Vytvořující funkce jsou jakousi diskrétní analogií Laplaceovy transformace, dosti často užívané hlavně v technických aplikacích. Při rozboru Markovových řetězců často pracujeme s mocninami matice pravděpodobností přechodu, což je práce při větším rozměru matice dosti těžkopádná. Lze se tomu vyhnout právě zavedením vytvořujících funkcí. Aplikace vytvořujících funkcí spočívá v určení příslušné transformace (obrazu) k danému originálu (vzoru), ve vykonání příslušných operací v oboru transformované funkce a ve zpětné transformaci za účelem získání řešení v původním oboru. Lze dokázat, že mezi původní funkcí a jejím obrazem existuje jednoznačná korespondence. V praktických aplikacích usnadňují využití vytvořujících funkcí slovníky transformací (tabulky typických funkcí a jejich transformací). Definice 17 Máme funkci , kde takto. Vytvoříme k ní mocninnou řadu : (1.51) , kde . O funkci mluvíme jako o původní funkci, je k ní příslušná vytvořující funkce (jako obraz funkce původní). Uveďme několik základních poznatků o vztahu původních funkcí a k nim příslušných vytvořujících funkcí. (A) Je-li , pak , což je vidět přímo z definice (1.51)[2]. (B) Je-li , pak , což je vidět z následujícího. (1.52) (C) Je-li , pak , Některé typické případy vytvořujících funkcí uvedeme v tabulce f(n) F(z) 1 1/(1-z) n z/(1-z)^2 a^n z/(1-az) na^n az/(1-az)^2 ^__________________________________________________________________________________________________ ____________ Pro analýzu Markovových řetězců má důležitý význam transformace vektorů a matic. Použijeme-li uvedené transformace na každý prvek vektoru resp. matice, provádíme tím transformaci celého vektoru či matice. Hovoříme pak o vytvořující funkci vektoru nebo matice. Vytvořující funkci vektoru můžeme psát ve tvaru (1.53) , kde . Vytvořující funkci matice můžeme psát ve tvaru (1.54) , . Pro maticovou funkci , kde A je čtvercová matice, platí tento rozvoj Inverzní matice je vyjádřená jako součet nekonečné geometrické řady (jde o analogii se skalární funkcí ). Pokud je matice regulární (tj. je-li čtvercová s lineárně nezávislými řádky/sloupci), pak inverzní matice k matici existuje a je jednoznačně určena. Pro platí transformace Během řešení úloh spojených s Markovovými řetězci pomocí vytvořujících funkcí se často setkáváme se zlomky dvou typů: (1.55A,B) a Zlomek (1.55A) je možné rozložit pomocí metody neurčitých činitelů na součet dvou parciálních zlomků se jmenovateli a . Potom se určí veličiny A,B, které vyhovují rovnici (1.56) . Tuto rovnici je možné řešit porovnáním koeficientů u absolutních členů a u členů obsahujících proměnnou z. Po odstranění zlomků v (1.56) máme , z čehož obdržíme (1.57) a Řešením této soustavy rovnic pro neznámé A,B dostaneme (1.58) , Obdobně, jako řešení zlomku (1.55B) na základě obdobných úvah dostaneme (1.59) , . Použijeme-li zmíněné transformace na každý prvek vektoru resp. matice. Provádíme tím transformaci celého vektoru resp. matice. Při rozboru chování vektoru absolutních pravděpodobností vyjdeme z vytvořující funkce tohoto vektoru ve tvaru (1.60) . Pro vektor absolutních pravděpodobností platí , kde je matice pravděpodobností přechodu po 1 kroku. Vytvořující funkci tedy můžeme vyjádřit ve tvaru (1.61) . Levou stranu (1.61) můžeme také vyjádřit ve tvaru (1.62) . Výraz je rovněž vytvořující funkcí . Platí tedy vztah (1.63) Odtud dostaneme pro : (1.64) , kde * je jednotková matice , je inverzní k matici . Ze vztahu (1.64) je zřejmé, že použitím vytvořující funkce se vyhneme umocňování matice , což obvykle znamená úsporu numerických výkonů. Na druhé straně zůstává určitým problémem hledání inverzní matice . Při hledání inverzní matice je možné vyjít z definice (1.65) kde je algebraický doplněk k prvku , pro který platí , kde je subdeterminant, který vznikne z determinantu A po vynechání i-tého řádku a j-tého sloupce. 1.17 - Ilustrace pomocí Příkladu 7 – výrobní linka Abychom mohli provést výpočet dle vztahu (1.64), je třeba spočíst inverzi matice . Nejdříve vypočteme matici (1.66) K provedení inverze vypočteme dle vztahu (1.65) determinant matice . Dostaneme . Dále máme . Tedy (1.67) Jednotlivé prvky matice rozložíme pomocí metody neurčitých činitelů na součet dvou parciálních zlomků. Prvek inverzní matice typu (1.55A) lze rozložit na . Po odstranění zlomků dostaneme . Porovnáním koeficientů u absolutních členů a u členů s proměnnou z, dostaneme soustavu rovnic , která má řešení . Prvek inverzní matice je typu (1.55B). Po provedeném rozkladu na dva zlomky pomocí metody neurčitých činitelů nebo přímo dosazením do (1.58) dostaneme pro čitatele zlomků hodnoty a . Když rozložíme na dva zlomky i zbývající dva prvky , inverzní matice , dostaneme Jde vlastně o součet dvou matic, takže můžeme rozepsat (1.68) . Z tabulky z-transformací najdeme zpětnou transformaci funkce původní funkci. Odpovídá ji funkce . Funkci odpovídá funkce . Znamená to, že pro platí (1.69) . Matice se skládá ze dvou matic, které mají odlišné vlastnosti. První matice je konstantní a nezávislá na počtu kroků n. Tato matice se nazývá stacionární matice. Druhá matice násobená koeficientem představuje přechodnou (transientní) složku procesu. Protože obrazem funkce byla vytvořující funkce , můžeme psát (1.70) . Druhý výraz v závorce konverguje pro k nule. Můžeme tedy psát . Nezávisle na tom, zda je vektor počátečních pravděpodobností nebo jsme takto dostali pomocí vytvořující funkce vektor limitních pravděpodobností . Poznámka I pro řadu dalších situací platí, že systém popsaný pomocí vytvořující funkce má složku rovnovážnou (stacionární) a složku přechodnou (transientní). 1.18 Vytvořující funkce posloupností , Definice 18: Vytvořující funkce posloupnosti je definována vztahem (1.71) pro [3] Podobným způsobem definujeme vytvořující funkci posloupnosti (1.72) pro Připomeňme, že pro mocninné řady , resp. platí konvolutorní vztah (1.73A) opět pro , kde (1.73B) neboli (1.73C) . Jestliže ztotožníme koeficienty s a podobně koeficienty ztotožníme s , pak porovnáním dříve uvedeného vztahu (1.13) (1.74)=(1.13) pro s (1.73B) dostaneme (1.75A) pro , neboli (1.75B) pro Odečtení konstanty 1 je nutné, protože vztah (1.74) neplatí pro . Způsobem analogickým k tomu, který vedl k (1.74) dostaneme: (1.76) , a . kde je pravděpodobnost,toho, že první přechod ze stavu do stavu se vyskytne právě v k-tém přechodu. Opět dodefinujeme pro všechna a všechna . Z (1.76) plyne, že (1.77) pro . Na základě (1.75B) může být také postavena základní klasifikace stavů: A) Stav je trvalý právě tehdy, když platí (Definice 6) Sdělení říká, že stav je trvalý právě tehdy, jestliže (vycházeje právě ze stavu ) pravděpodobnost návratu do stavu po nějaké určitém počtu kroků je jedna. V porovnání k tomuto jsme definovali B) Stav je přechodný právě tehdy, když platí (Definice 8) To říká, že stav je přechodný právě tehdy, jestliže (vycházeje ze stavu ) existuje „reziduální“ pravděpodobnost , že se systém do stavu po jakkoliv velkém konečném počtu kroků již nevrátí. Tuto klasifikaci stavů lze dále přenést i na chování pravděpodobností přechodu po krocích , což jsme ukázali ve Větě 3A konstatující, že Stav je trvalý právě tehdy, jestliže platí a Větě 3B sdělující, že Stav je přechodný právě tehdy, když . ________________________________ [1] Variantním názvem jsou též z-transformace [2] Jde zřejmě o součet členů nekonečné geometrické posloupnosti s kvocientem z. [3] Poloměr konvergence je nutno takto omezit, aby mocninná řada konvergovala.