10. Vytvořující funkce a jejich aplikace při analýze homogenních markovských řetězců
10.1. Motivace:
Při analýze homogenních markovských řetězců se často pracuje s mocninami přechodu, což je výpočetně náročné. Tomu se
lze vyhnout, pokud použijeme vytvořující funkce. Postupujeme tak, že najdeme transformaci daného originálu, učiníme
příslušnou operaci a provedeme zpětnou transformaci. Lze dokázat, že mezi originálem a jeho transformací existuje
vzájemně jednoznačný vztah. Vytvořující funkce se též nazývají z-transformace a jsou diskrétní obdobou Laplaceovy
transformace, která se často používá především v technických aplikacích.
10.2. Definice: Definice vytvořující funkce reálné posloupnosti
Nechť { }∞
=0nna je posloupnost reálných čísel. Jestliže řada ∑
∞
=
=
0n
n
na za)z(G konverguje v nějakém okolí 0, nazveme ji
vytvořující funkcí posloupnosti { }∞
=0nna . (Obecněji lze vytvořující funkci zavést i pro posloupnost komplexních čísel, ale
tímto případem se zabývat nebudeme.)
10.3. Příklad:
Najděte vytvořující funkce k posloupnostem:
a) an = 1, n = 0, 1, ...
b) an = n, n = 0, 1, ...
c) an = xn
, n = 0, 1, ...
d) an = nxn
, n = 0, 1, ...
Řešení:
ad a) 1z,
z1
1
zza)z(G
0n
n
0n
n
na <
−
=== ∑∑
∞
=
∞
=
ad b)
( )
1z,
z1
z
z1
1
dz
d
zz
dz
d
znzznzza)z(G 2
0n
n
1n
1n
0n
n
0n
n
na <
−
=
−
===== ∑∑∑∑
∞
=
∞
=
−
∞
=
∞
=
ad c)
x
1
z,
xz1
1
)xz(zxza)z(G
0n
n
0n
nn
0n
n
na <
−
==== ∑∑∑
∞
=
∞
=
∞
=
ad d)
( ) ( ) x
1
z,
xz1
xz
t1
t
t1
1
dt
d
t
t
dt
d
tnttxztsubstituce)xz(nznxza)z(G
22
0n
n
1n
1n
0n
n
0n
nn
0n
n
na
<
−
=
−
=
−
=
======== ∑∑∑∑∑
∞
=
∞
=
−
∞
=
∞
=
∞
=
Výsledky uspořádáme do přehledné tabulky:
an Ga(z)
1 1/(1-z)
n z/(1-z)2
xn
1/(1-xz)
nxn
xz/(1-xz)2
10.4. Věta:
Nechť Ga(z) je vytvořující funkce posloupnosti { }∞
=0nna . Pak pro n = 0, 1, 2, ... platí:
0z
)n(
a
n
!n
)z(G
a
=
= .
Důkaz:
Řadu ∑
∞
=
=
0n
n
na za)z(G budeme derivovat člen po členu a vyjádříme hodnotu této derivace v bodě z = 0. Přitom užijeme
konvenci 00
= 1.
n = 0: Ga(0) = a0
n = 1: 1a
1n
1n
n
0n
n
na a)0(G
dz
d
,nzaza
dz
d
)z(G
dz
d
=== ∑∑
∞
=
−
∞
=
n = 2:
( )
!2
0G
a12a)0(G
dz
d
,z)1n(naza
dz
d
)z(G
dz
d
)2(
a
22a2
2
2n
2n
n
0n
n
n2
2
a2
2
=⇒⋅⋅=−== ∑∑
∞
=
−
∞
=
n = 3:
( )
!3
0G
a123a)0(G
dz
d
,z)2n)(1n(naza
dz
d
)z(G
dz
d
)3(
a
33a3
3
3n
3n
n
0n
n
n3
3
a3
3
=⇒⋅⋅⋅=−−== ∑∑
∞
=
−
∞
=
atd.
10.5. Příklad:
Je dána vytvořující funkce Ga(z) = ez
. Najděte odpovídající posloupnost { }∞
=1nna .
Řešení:
a0 = 1, { }
∞
=
∞
=






====
0n
0nn321
n!
1
atedy,,
!3
1
a,
2
1
a,
1
1
a K .
10.6. Definice: Definice konvoluce a konvoluční mocniny
Nechť { }∞
=0nna , { }∞
=0nnb jsou reálné posloupnosti. Jejich konvolucí rozumíme posloupnost { }∞
=0nnc , kde
cn = a0bn + a1bn-1 + ... + anb0.
Zkráceně píšeme {c} = {a}*{b}.
Konvoluci {a}*{a} nazýváme druhou konvoluční mocninou posloupnosti { }∞
=1nna a značíme ji {a}2*
.
Obecně k-tá konvoluční mocnina posloupnosti { }∞
=0nna je {a}k*
= {a}* ... *{a}.
10.7. Věta: Věta o vytvořující funkci konvoluce
Jestliže posloupnost { }∞
=0nna má vytvořující funkci Ga(z) a posloupnost { }∞
=0nnb má vytvořující funkci Gb(z), pak posloupnost
{ }∞
=0nnc , která je konvolucí daných dvou posloupností, má vytvořující funkci Gc(z) = Ga(z).Gb(z). k-tá konvoluční mocnina
{a}k*
posloupnosti { }∞
=0nna má vytvořující funkci Ga(z)k
.
Důkaz:
Součin Ga(z).Gb(z) dostaneme vynásobením mocninných řad.
Koeficient u zn
je v tomto součinu roven a0bn + a1bn-1 + ... + anb0.
10.8. Definice: Definice vytvořující funkce posloupnosti vektorů či posloupnosti matic
a) Nechť I je nejvýše spočetná indexová množina. Uvažme posloupnost vektorů a0 = ( ) Iii0a ∈
, a1 = ( ) Iii1a ∈
, ....
Vytvořující funkce posloupnosti vektorů { }∞
=1nna je definována vztahem: Ga(z) = ( ) Iiai )z(G ∈
, kde Gai(z) = ∑
∞
=0n
n
ni za .
Zkráceně píšeme: Ga(z) = ∑
∞
=0n
n
n za .
b) Nechť I, J jsou nejvýše spočetná indexové množiny. Uvažme posloupnost maticA0 = ( ) Jj,Iiij0a ∈∈
, A1 = ( ) Jj,Iiij1a ∈∈
, ....
Vytvořující funkce posloupnosti matic { }∞
=0nnA je definována vztahem: GA(z) = ( ) Jj,Iiaij )z(G ∈∈
, kde Gaij(z) = ∑
∞
=0n
n
nijza .
Zkráceně píšeme:
GA(z) = ∑
∞
=0n
n
n zA .
(Vytvořující funkce posloupnosti vektorů či posloupnosti matic vznikne tak, že získáme vytvořující funkce posloupnosti
odpovídajících složek a vzniklé vytvořující funkce uspořádáme do vektoru či do matice.)