\magnification=\magstep1
\input amstex
\hsize=16truecm
\parskip=2.5pt plus 1pt
\TagsOnRight

\define\A{{\bold A}}
\define\BB{{\bold B}}
\define\DD{{\bold D}}
\define\T{{\bold T}}
\define\U{{\bold U}}
\define\({\left(}
\define\){\right)}
\define\[{\left[}
\define\]{\right]}
\define\e{\varepsilon}
\define\oo{\omega}
\define\const{\text{\rm const.}\,}
\define\Var{\text{\rm Var}\,}
\define\Cov{\text{\rm Cov}\,}
\define\supp {\sup\limits}
\define\inff{\inf\limits}
\define\summ{\sum\limits}
\define\prodd{\prod\limits}
\define\limm{\lim\limits}
\define\limsupp{\limsup\limits}
\define\liminff{\liminf\limits}
\define\bigcapp{\bigcap\limits}
\define\bigcupp{\bigcup\limits}
\def\Re{\text{\rm Re}\,}
\font\script=cmcsc10

\centerline{\bf Az inform\'aci\'osz\'am\'{\i}t\'as n\'eh\'any fontos
fogalma \'es eredm\'enye.}

\beginsection 1. Az entr\'opia \'es felt\'eteles entr\'opia fogalma
\'es tulajdons\'agai.

Annak \'erdek\'eben, hogy meg\'erts\"uk az entr\'opia fogalm\'at
\'es azt, hogy milyen probl\'em\'ak vezettek annak megalkot\'as\'ahoz
tekints\"uk a k\"ovetkez\H{o} k\'erd\'est. Tudunk-e nyerni a tot\'on,
ha j\'ol ismerj\"uk a tot\'oban szerepl\H{o} csapatok erej\'et, \'es
ez\'ert nagy val\'osz\'{\i}n\H{u}s\'eggel meg tudjuk tippelni a
m\'erk\H{o}z\'esek eredm\'eny\'et? Mivel igaz\'an nagy nyerem\'enyt
csak telital\'alatos szelv\'ennyel lehet nyerni, foglalkozunk
azzal a k\'erd\'essel, hogy h\'any szelv\'enyt kell
kit\"olteni a telital\'alat el\'er\'ese \'erdek\'eben annak,
aki \'ert \'es annak aki nem \'ert a futballhoz. Azt v\'arjuk,
hogy egy futballhoz \'ert\H{o}nek sokkal jobbak a nyer\'esi es\'elyei.
Ez \'{\i}gy is van. De ahhoz, hogy ezt jobban meg\'erts\"uk \'es a
probl\'em\'at alaposabban vizsg\'alhassuk el\H{o}sz\"or meg kell
fogalmazni a k\'erd\'est pontosabban.

Ha biztos telital\'alatot szeretn\'enk el\'erni, akkor hi\'aba
tudjuk az eredm\'enyeket nagy, de nem 100 sz\'azal\'ekos
biztons\'aggal eltal\'alni,  c\'elunkat csak \'ugy \'erhetj\"uk el,
ha minden lehets\'eges kimenetre fogadunk. Ebben az esetben
teh\'at nem tudunk m\'ast tenni, mint egy olyan fogad\'o, aki
semmit sem tud az egyes m\'erk\H{o}z\'esek val\'osz\'{\i}n\H{u}
eredm\'eny\'er\H{o}l.
M\'as azonban a helyzet, ha megel\'egsz\"unk azzal, hogy nagy,
mondjuk $0.95$ val\'osz\'{\i}n\H{u}s\'eggel nyerj\"unk. Ekkor a
futballhoz \'ert\H{o} hat\'arozott el\H{o}nyben van a futballhoz
nem \'ert\H{o}vel szemben. Neki sokkal kevesebb szelv\'enyt kell
kit\"olteni e c\'el el\'er\'ese \'erdek\'eben, mint a m\'asiknak.
M\'asr\'eszt elk\'epzelhet\H{o}, hogy \'erdemes tot\'ozni, ha 10000
szelv\'eny kit\"olt\'es\'evel tudjuk biztos\'{\i}tani a majdnem
biztos nyer\'est, de nem \'erdemes akkor, ha ehhez 100000
szelv\'enyt kell kit\"olten\"unk.

A fenti k\'erd\'es term\'eszetesen elvezet a k\"ovetkez\H{o}
probl\'em\'ahoz. Tegy\"uk fel, hogy $n$ m\'erk\H{o}z\'es van, ezek
eredm\'enye egym\'ast\'ol f\"uggetlen, \'es meg tudjuk it\'elni,
hogy a p\'alyav\'alaszt\'o $p_1$,
a vend\'egcsapat $p_2$ val\'osz\'{\i}n\H{u}s\'eggel nyer,
\'es $p_3$ val\'osz\'{\i}n\H{u}s\'eggel lesz az eredm\'eny
d\"ontetlen. Tegy\"uk fel, hogy ezek a $p_1$, $p_2$ \'es $p_3$
val\'osz\'{\i}n\H{u}s\'egek mindegyik tal\'alkoz\'on ugyanazok
a sz\'amok, \'es az egyes m\'erk\H{o}z\'esek eredm\'enyei
egym\'ast\'ol f\"uggetlenek. Jel\"olj\"uk a p\'alyav\'alaszt\'o
nyer\'es\'enek bek\"ovetkezt\'et 1-gyel, a
ven\-d\'eg\-csa\-pa\-t\'et 2-vel, a d\"ontetlen eredm\'enyt
pedig $x$-szel,  \'ugy ahogy az a tot\'oban szok\'as. Arra
vagyunk kiv\'ancsiak, hogy h\'any tippet, h\'any $n$
hossz\'us\'ag\'u 1, 2, $x$ sorozatot kell megadnunk ahhoz, hogy
$p$ val\'osz\'{\i}n\H{u}s\'eggel ezen tippek valamelyike
tartalmazza az \"osszes m\'erk\H{o}z\'es helyes
v\'egeredm\'eny\'et. A $p$ sz\'am egy az 1 sz\'amn\'al kicsit
kisebb r\"ogz\'{\i}tett (azaz a m\'erk\H{o}z\'esek $n$
sz\'am\'at\'ol nem f\"ugg\H{o}) sz\'am,
\'es minket az \'erdekel, hogy k\"or\"ulbel\"ul h\'any tippet
kell megadnunk c\'elunk el\'er\'ese \'erdek\'eben akkor, ha $n$,
azaz a m\'erk\H{o}z\'esek sz\'ama nagyon nagy. Vil\'agos, hogy ez
a sz\'am f\"ugg a $p_1$, $p_2$ \'es $p_3$ sz\'amokt\'ol, azaz
att\'ol, hogy milyen
biztons\'aggal tudjuk megtippelni az eredm\'enyeket. Az, hogy semmit
nem tudunk a lehets\'eges v\'egeredm\'enyr\H{o}l azt jelenti, hogy
$p_1=p_2=p_3=\frac13$.

El\H{o}sz\"or pongyol\'an fogalmazom meg az eredm\'enyeket,
\'es azokra egy heurisztikus indokl\'ast adok, majd megadom
az \'all\'{\i}t\'asok \'es felhaszn\'alt fogalmak pontos
megfogalmaz\'as\'at az \'altal\'anos esetben, \'es ismertetem
a prec\'{\i}z bizony\'{\i}t\'asokat.

Meg tudjuk mondani, hogyan kell kit\"olteni a szelv\'enyeket,
ha pontosan $k$ tippet tehet\"unk, \'es az a c\'elunk, hogy a
lehet\H{o} legnagyobb val\'osz\'{\i}n\H{u}s\'eggel legyen
telital\'alatunk. Ha $k=1$, akkor a m\'erk\H{o}z\'essorozat
legval\'osz\'{\i}n\H{u}bb eredm\'eny\'ere \'erdemes tippelni.
Ha $k=2$, akkor a k\'et legval\'osz\'{\i}n\H{u}bb eredm\'enyre
tippelj\"unk, \'es \'altal\'anos $k$ eset\'en a legjobb
strat\'egia a $k$ legval\'osz\'{\i}n\H{u}bb eredm\'enyre
fogadni. Ezut\'an ha meghat\'arozzuk, hogy melyik az a
legkisebb $k=k(n)$ sz\'am, amelyre  a $k$
legval\'osz\'{\i}n\H{u}bb eredm\'eny valamelyike legal\'abb $p$
val\'osz\'{\i}n\H{u}s\'eggel bek\"ovetkezik, akkor
megoldjuk a feladatot. Ennek a $k=k(n)$ sz\'amnak a pontos
meghat\'aroz\'asa azonban neh\'ez. Enn\'el sokkal
egyszer\H{u}bb az al\'abbi \'ervel\'es, amely a nagy
sz\'amok (gyenge) t\"orv\'enye seg\'{\i}ts\'eg\'evel
j\'o k\"ozel\'{\i}t\H{o} \'ert\'eket ad a keresett $k=k(n)$
sz\'amra.

Be fogjuk l\'atni, hogy akkor \'erhet\H{o} el, hogy majdnem
1~val\'osz\'{\i}n\H{u}s\'eggel lesz te\-li\-ta\-l\'a\-la\-tunk $n$
m\'erk\H{o}z\'es tippel\'ese sor\'an, ha k\"or\"ulbel\"ul $2^{Hn}$
szelv\'enyt t\"olt\"unk ki al\-kal\-mas m\'odon, ahol $H$ egy
a $p_1$, $p_2$ \'es $p_3$ val\'osz\'{\i}n\H{u}s\'egekt\H{o}l
f\"ugg\H{o} sz\'am. Azaz, exponenci\'alisan sok szelv\'enyt kell
kit\"olteni, de az hogy milyen $H$ eg\"utthat\'o szerepel a
kitev\H{o}ben att\'ol f\"ugg, hogy milyen biztons\'aggal tudjuk
eltal\'alni a m\'erk\H{o}z\'esek eredm\'eny\'et. Ennek a $H$
sz\'amnak a kisz\'am\'{\i}t\'asa vezet el az entr\'opia
fogalm\'anak be\-ve\-ze\-t\'e\-s\'e\-hez.

A m\'erk\H{o}z\'essorozat eredm\'enye egy $n$ hossz\'us\'ag\'u
v\'eletlen 1, 2 \'es $x$ jelekb\H{o}l \'all\'o sorozat, ahol
mindegyik jel a t\"obbiekt\H{o}l f\"uggetlen\"ul $p_1$
val\'osz\'{\i}n\H{u}s\'eggel vesz fel 1 $p_2$
val\'osz\'{\i}n\H{u}s\'eggel 2 \'es $p_3$
val\'osz\'{\i}n\H{u}s\'eggel $x$ \'ert\'eket. C\'elunk
viszonylag kev\'es sorozat kiv\'alaszt\'asa \'ugy, hogy annak
val\'osz\'{\i}n\H{u}s\'ege, hogy a megjelen\H{o} v\'eletlen
sorozat ezen sorozatok valamelyike legyen majdnem 1. Vegy\"uk
\'eszre, hogy a nagy sz\'amok (gyenge) t\"orv\'enye szerint
majdnem minden sorozat olyan, hogy k\"or\"ulbel\"ul $np_1$
darab 1 \'ert\'eket, $np_2$ darab 2 \'ert\'eket \'es
$np_3$ darab $x$ \'ert\'eket tartalmaz. Nevezz\"unk egy
ezzel a tulajdons\'aggal rendelkez\H{o} sorozatot tipikusnak.
Nagy $n$ sz\'amra el\'eg a tipikus sorozatokra tippelni, mert
annak a val\'osz\'{\i}n\H{u}s\'ege, hogy valamelyik nem tipikus
sorozat jelenik meg majdnem nulla. Ez\'ert azt kell
meghat\'aroznunk, hogy h\'any tipikus sorozat van.

A tipikus sorozatok sz\'am\'at a k\"ovetkez\H{o} heurisztikus
\'ervel\'es seg\'{\i}ts\'eg\'evel ha\-t\'a\-roz\-hat\-juk meg.
Egy r\"ogz\'{\i}tett tipikus sorozat megjelen\'es\'enek a
val\'osz\'{\i}n\H{u}s\'ege k\"or\"ulbel\"ul
$p_1^{np_1}p_2^{np_2}p_3^{np_3}$, a tipikus
sorozatok \"osszval\'osz\'{\i}n\H{u}s\'ege majdnem 1, ez\'ert
a tipikus sorozatok sz\'ama k\"or\"ulbel\"ul
$\frac1{p_1^{np_1}p_2^{np_2}p_3^{np_3}}=2^{nH}$,
ahol $H=-p_1\log p_1-p_2\log p_2-p_3\log p_3$. Itt \'es
a tov\'abbiakban is a $\log$ jel 2-es alap\'u logaritmust fog
jelenteni. A term\'eszetes logaritmust az $\ln$ kifejez\'es
fogja jel\"olni.

Megfogalmazom \'es bebizony\'{\i}tom a fenti heurisztikus
\'ervel\'es seg\'{\i}ts\'eg\'evel kapott eredm\'eny egy
ter\-m\'e\-sze\-tes \'altal\'anos\'{\i}t\'as\'at.
El\H{o}tte ismertetem az eredm\'enyben megjelen\H{o} entr\'opia
fogalm\'at.

\medskip\noindent
{\bf Entr\'opia definici\'oja.}\/ {\it Legyen $\xi$ egy
\'ert\'ekeit egy v\'eges vagy megsz\'aml\'alhat\'oan v\'egtelen
$X=\{x_1,x_2,\dots\}$ halmazon felvev\H{o} val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o, amelyre $P(\xi=x_j)=p_j$, $j=1,2,\dots$, ahol
$\summ_j p_j=1$. A $\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
entr\'opi\'aja a
$$
H(\xi)=-\sum_j p_j\log p_j
$$
esetleg v\'egtelen \'ert\'eket felvev\H{o} mennyis\'eg, ahol
$\log$ a 2-es alap\'u logaritmust jel\"oli.}

\medskip\noindent
{\bf 1.~Megjegyz\'es.} {\it K\'enyelmi okokb\'ol megengedj\"uk, hogy
az entr\'opia fenti definici\'oj\'aban $P(\xi=x_j)=0$ legyen bizonyos
$x_j$ \'ert\'ekekre. Annak \'erdek\'eben, hogy a definici\'o ebben
az esetben is \'ertelmes legyen bevezetj\"uk a $0\log 0=0$
konvenci\'ot.}

\medskip\noindent
{\bf 2.~Megjegyz\'es.} {\it Ha t\"obb $\xi_1,\dots,\xi_k$ v\'eges
vagy megsz\'aml\'alhat\'o sok \'ert\'eket felvev\H{o}
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'onk van, akkor ezek
egy\"uttes $H(\xi_1,\dots,\xi_k)$ entr\'opi\'aj\'at \'ugy
de\-fi\-ni\-\'al\-juk, hogy a $\xi_1,\dots,\xi_k$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o sorozatot term\'eszetes
m\'odon azonos\'{\i}tjuk a $(\xi_1,\dots,\xi_k)$ v\'eletlen
vektorral, \'es annak entr\'opi\'aj\'at defini\'aljuk, mint
a $H(\xi_1,\dots,\xi_k)$ entr\'opi\'at. Ter\-m\'e\-sze\-te\-sen
a tekintett v\'eletlen vektor eloszl\'as\'at a
$$
P((\xi_1,\dots,\xi_k)=(x^{(1)}_{i_1},\dots,x^{(k)}_{i_k}))
=P(\xi_1=x^{(1)}_{i_1},\dots,\xi_k=x^{(k)}_{i_k})
$$
k\'eplet defini\'alja minden
$x^{(1)}_{i_1},\dots,x^{(k)}_{i_k}$ sorozatra.}

\medskip
Vegy\"uk \'eszre, hogy egy $\xi$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o entr\'opi\'aja nem f\"ugg att\'ol, hogy $\xi$ milyen
\'ert\'ekeket vesz fel. Az csak att\'ol f\"ugg, hogy a
val\'osz\'{\i}n\H{u}s\'egi mez\H{o} azon partici\'oja, amelynek
elemei a val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o azon
n\'{\i}v\'ohalmazai, ahol az valamilyen r\"ogz\'{\i}tett
\'ert\'eket vesz fel milyen val\'osz\'{\i}n\H{u}s\'eg\H{u}
halmazokb\'ol \'all.

A k\"ovetkez\H{o} eredm\'enyt fogjuk bizony\'{\i}tani.

\medskip\noindent
{\bf T\'etel f\"uggetlen val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'okb\'ol \'all\'o tipikus sorozatok sz\'am\'ar\'ol.}
{\it Legyen $\xi$ egy \'ert\'ekeit valamely v\'eges
$X=\{x_1,x_2,\dots,x_r\}$ halmazon f\"olvev\H{o}
val\-\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'o,
$\xi_1,\dots,\xi_n$ pedig f\"uggetlen, a $\xi$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'oval azonos eloszl\'as\'u
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'ok sorozata. Ekkor
minden $\e>0$ \'es $\delta>0$ sz\'amhoz l\'etezik olyan
$n_0=n_0(\e,\delta)$ k\"usz\"obindex, hogy $n\ge n_0$ eset\'en minden
olyan $A=\{(x^{(k)}_{j_1},\dots,x^{(k)}_{j_n}),\;1\le k\le L\}$
$X$ halmazbeli $n$-hossz\'us\'ag\'u sorozatokb\'ol
\'all\'o halmaz $L$ elemsz\'ama teljes\'{\i}ti az
$L=|A|\ge 2^{(1-\e)nH(\xi)}$ egyenl\H{o}tlens\'eget, amelyre
$P((\xi_1,\dots,\xi_n)\in A)\ge\delta$. Megford\'{\i}tva,
l\'etezik olyan
$\bar A=\{(x^{(k)}_{j_1},\dots,x^{(k)}_{j_n}),\;1\le k\le \bar L\}$
$\bar L$ darab $X$ halmazbeli $n$-hossz\'us\'ag\'u sorozatb\'ol
\'all\'o halmaz, amelyre $P((\xi_1,\dots,\xi_n)\in A)\ge1-\delta$,
\'es az $\bar A$ halmaz $\bar L$ elemsz\'ama teljes\'{\i}ti az
$\bar L=|\bar A|\le 2^{(1+\e)nH(\xi)}$ egyenl\H{o}tlens\'eget.
A fenti egyenl\H{o}tlens\'egekben $H(\xi)$ a $\xi$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o entr\'opi\'aj\'at jel\"oli.}

\medskip\noindent
{\it Megjegyz\'es.} A fenti t\'etel akkor is \'erv\'enyes, ha a
$\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o nem csak
v\'eges sok, hanem megsz\'aml\'alhat\'oan v\'egtelen sok \'ert\'eket
is felvehet. Ebben az esetben azonban a bizony\'{\i}t\'as finomabb
\'ervel\'est k\'{\i}v\'an. Ez\'ert a t\'etel ilyen ir\'any\'u
\'eles\'{\i}t\'es\'et egy kieg\'esz\'{\i}t\'esben ismertetem.

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ Jel\"olje $B$ az \"osszes olyan
$X$-beli elemekb\H{o}l \'all\'o $n$ hossz\'us\'ag\'u
$x_{j_1},\dots,x_{j_n}$ sorozatok halmaz\'at, amely
sorozatok legal\'abb $np_k(1-\e/2)$ multiplicit\'assal
tartalmazz\'ak az $x_k$ jelet minden $1\le k\le r$ indexre, ahol
$p_k=P(\xi=x_k)$. A nagy sz\'amok gyenge t\"orv\'enye sze\-rint
$P((\xi_1,\dots,\xi_n)\in B)\ge1-\frac\delta2$, ha
$n\ge n_0(\e,\delta)$ alkalmas $n_0(\e,\delta)$ k\"usz\"obindexszel.
Ez\'ert
$P((\xi_1,\dots,\xi_n)\in A\cap B)\ge\frac\delta2$, ha
$P((\xi_1,\dots,\xi_n)\in A)\ge\delta$. El\'eg bel\'atni, hogy
az $A\cap B$ halmaz sz\'amoss\'aga nagyobb, mint $2^{n(1-\e)H(\xi)}$.
Ennek \'erdek\'eben defini\'aljuk a k\"ovetkez\H{o} mennyis\'egeket.
Legyen $s_k(x)$ az $x=(x_{j_1},\dots,x_{j_n})$ sorozatban lev\H{o}
$x_k$ jelek sz\'ama minden $1\le k\le r$ indexre. Ekkor minden
$x=(x_{j_1},\dots,x_{j_n})\in A\cap B$, illetve
\'altal\'anosabban minden $x=(x_{j_1},\dots,x_{j_n})\in B$ sorozatra
$$
\align
P((\xi_1,\dots,\xi_n)=(x_{j_1},\dots,x_{j_n}))&=\prod_{k=1}^r p_k^{s_k(x)}
\le p_1^{n(1-\e/2)p_1}\cdots p_r^{n(1-\e/2)p_r}\\
&=2^{-n(1-\e/2)H(\xi)},
\endalign
$$
\'es mivel $P((\xi_1,\dots,\xi_n)\in A\cap B)\ge\frac\delta2$, az
$A\cap B$ halmaz sz\'amoss\'aga nagyobb, mint
$\frac\delta2 2^{n(1-\e/2)H(\xi)}\ge 2^{n(1-\e)H(\xi)}$, ha az
$n_0(\e,\delta)$ k\"usz\"obindexet el\'eg nagyra v\'alasztjuk.

Olyan $\bar A$ halmazt, amelyre
$P((\xi_1,\dots,\xi_n)\in\bar A)>1-\delta$, \'es elemsz\'ama
teljes\'{\i}ti a k\'{\i}v\'ant fels\H{o} becsl\'est  v\'alaszthatuk
\'ugy, mint az \"osszes olyan $n$ hossz\'us\'ag\'u $X$-beli
elemeket tartalmaz\'o $x_{j_1},\dots,x_{j_n}$ sorozatb\'ol
\'all\'o halmazt, amely sorozatok legfeljebb $np_k(1+\e)$
multiplicit\'assal tartalmazz\'ak az $x_k$ jelet minden
$1\le k\le r$ indexre. Ism\'et a nagy sz\'amok gyenge
t\"orv\'eny\'ere hivatkozva kapjuk, hogy
$P((\xi_1,\dots,\xi_n)\in A)\ge1-\delta$, ha
$n\ge n_0(\e,\delta)$ alkalmas $n_0(\e,\delta)$ k\"usz\"obindexszel.
M\'asr\'eszt minden $x=(x_{j_1},\dots,x_{j_n})\in \bar A$ sorozatra
$$
P((\xi_1,\dots,\xi_n)=(x_{j_1},\dots,x_{j_n}))
=\prod_{k=1}^r p_k^{s_k(x)}
\ge p_1^{n(1+\e)p_1}\cdots p_r^{n(1+\e)p_r}=2^{-n(1+\e)H(\xi)},
$$
\'es mivel az ilyen sorozatok \"osszval\'osz\'{\i}n\H{u}s\'ege
kisebb vagy egyenl\H{o} mint 1 innen k\"o\-vet\-ke\-zik, hogy az
$\bar A$ halmaz sz\'amoss\'aga kisebb, mint $2^{n(1+\e)H(\xi)}$.

\medskip
A fent bizony\'{\i}tott eredm\'enyt a k\"ovetkez\H{o} m\'odon is
interpret\'alhatjuk. Tekints\"uk egy $\xi$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'oval azonos eloszl\'as\'u,
f\"uggetlen  val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
$n$-hossz\'us\'ag\'u sorozatait, \'es v\'alasszuk ki e
v\'eletlen sorozatok $p$-ed r\'esz\'et alkalmas m\'odon, \'ugy
hogy csak viszonylag kev\'es sorozatot kelljen kiv\'alasztanunk. A
$p$-ed r\'esz kifejez\'es itt azt jelenti, hogy a kiv\'alasztott
sorozatok \"osszval\'osz\'{\i}n\H{u}s\'ege legal\'abb $p$. Az
ebben a feladatban szerepl\H{o} $p$ sz\'am teljes\'{\i}ti a
$0<p<1$ egyenl\H{o}tlens\'eget, egy\'ebk\'ent tetsz\H{o}legesen
v\'alaszthatjuk. Azt l\'attuk be, hogy c\'elunkat el\'erhetj\"uk
$2^{nH(\xi)+o(n)}$ a\-lkal\-ma\-san v\'alasztott sorozat
megad\'as\'aval, de kevesebbel m\'ar nem. Ennek az eredm\'enynek
megfogalmazhatjuk az al\'abbi k\"ovetkezm\'eny\'et. Ha a
tekintett v\'eletlen sorozatok nagy r\'esz\'et meg
akarjuk jel\"olni k\"ul\"onb\"oz\H{o}, de azonos hossz\'us\'ag\'u
v\'eletlen 0--1 sorozatokkal, ahol a `nagy r\'esz\'et'
kifejez\'es azt jelenti, hogy a sorozatok kis (alkalmasan
v\'alasztott) $\e$ val\'osz\'{\i}n\H{u}s\'egi r\'esz\'et
figyelmen k\'{\i}v\"ul hagyhatjuk, akkor az egyes sorozatokat
k\"or\"ulbel\"ul $nH(\xi)$ hossz\'us\'ag\'u 0--1 sorozatokkal
kell megjel\"oln\"unk. Ezt szok\'as \'ugy interpret\'alni, hogy
a tekintett v\'eletlen sorozat egyes tagjainak
a megnevez\'es\'ehez $H(\xi)$ bit sz\"uks\'eges, azaz ennyi
inform\'aci\'o kell annak megismer\'es\'ehez.

Olyan probl\'em\'at tekintett\"unk, amelynek vizsg\'alat\'aban
term\'eszetes m\'odon megjelent az entr\'opia fogalma.
Tekints\"uk ennek a probl\'em\'anak egy olyan v\'altozat\'at,
ahol az el\H{o}bb t\'argyalt feladathoz hasonl\'oan egy v\'eletlen
sorozatot akarunk nagy val\'osz\'{\i}n\H{u}s\'eggel eltalal\'alni,
de rendelkez\"unk bizonyos plusz inform\'aci\'oval. Nevezetesen
ismerj\"uk egy m\'asik, a minket \'erdekl\H{o} v\'eletlen
sorozattal kapcsolatban lev\H{o} v\'eletlen sorozat \'ert\'ekeit,
\'es ezt a plusz inform\'aci\'ot is fel k\'{\i}v\'anjuk haszn\'alni.
A probl\'ema jobb meg\'ert\'ese \'er\-de\-k\'e\-ben tekints\"uk
a kor\'aban vizsg\'alt tot\'oz\'asr\'ol sz\'ol\'o feladat egy olyan
v\'altozat\'at, amelyben ilyen k\'erd\'es mer\"ul fel.

A k\"ovetkez\H{o} feladatot vizsg\'aljuk. Megint egy
m\'erk\"oz\'essorozat eredm\'enyeire aka\-runk j\'ol tippelni a
tot\'on. Viszont a m\'erk\H{o}z\'esek el\H{o}tti napon az egyes
ta\-l\'al\-ko\-z\'o\-kon r\'esztvev\H{o} egy\"uttesek ifj\'us\'agi
csapatai is j\'atszanak egym\'as ellen, \'es annak eredm\'eny\'et
megismerhetj\"uk a tot\'oszelv\'eny kit\"olt\'ese el\H{o}tt. Az,
hogy az ifj\'us\'agi csapatok milyen eredm\'enyt \'ernek el, hogy
vannak felk\'esz\"ulve, inform\'aci\'ot ad a nagy csapatok
fel\-k\'e\-sz\"ult\-s\'e\-g\'e\-r\H{o}l is, \'es ez
megv\'altoztatja megit\'el\'es\"unket a lehets\'eges
v\'egeredm\'enyek va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-g\'e\-r\H{o}l.
A tot\'oszelv\'enyek kit\"olt\'es\'en\'el \'erdemes ezt az
inform\'aci\'ot is figyelembe venni. A k\'erd\'es az, hogy hogyan
vegy\"uk ezt figyelembe, \'es ezen plusz inform\'aci\'ok
felhaszn\'al\'asa eset\'en h\'any szelv\'enyt kell kit\"olten\"unk
annak \'erdek\'eben, hogy nagy val\'osz\'{\i}n\H{u}s\'eggel
telital\'alatot \'erj\"unk el.

Fogalmazzuk meg a feladatot pontosabban. Tekints\"uk $n$
m\'erk\H{o}z\'esp\'ar eredm\'enyeit, amelyeket jel\"olj\"unk a
$(\xi_l,\eta_l)$, $1\le l\le n$, jelp\'arokkal. (Az $l$-ik
m\'erk\H{o}z\'esp\'ar eredm\'enye a tot\'o $l$-ik
fordul\'oj\'aban szerepl\H{o} feln\H{o}tt \'es a nekik
megfelel\H{o} ifj\'us\'agi csapatok
m\'er\-k\H{o}\-z\'e\-s\'e\-nek az eredm\'enye, amelyeket
$\xi_l$-lel illetve $\eta_l$-lel jel\"ol\"unk.) Tegy\"uk fel,
hogy ezek a $(\xi_l,\eta_l)$ vektorok egym\'ast\'ol
f\"uggetlenek, \'es azonos eloszl\'as\'uak, tov\'abb\'a ezt
az eloszl\'ast ismerj\"uk. Vezess\"uk be az
$r(i,j)=P(\xi_l=i,\eta_l=j)$
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-ge\-ket, ahol az $i$
\'es $j$ v\'altoz\'ok az 1, 2 \'es $x$
\'ert\'ekeket veheti fel. A k\'erd\'es az, hogy ismerve az
$\eta_1,\dots,\eta_n$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
\'ert\'ekeit, h\'any $n$ hossz\'us\'ag\'u 1, 2, $x$ sorozatot
kell (alkalmasan) a tot\'oszelv\'anyen megadni, ha azt akarjuk
el\'erni, hogy ezen tippsorozatok valamelyike majdnem
1 val\'osz\'{\i}n\H{u}s\'eggel megegyezzen a v\'eletlen
$\xi_1,\dots,\xi_n$ sorozattal. Most is feltessz\"uk, hogy a
m\'erk\H{o}z\'esek $n$ sz\'ama nagy.

El\H{o}sz\"or a feladat heurisztikus megold\'as\'at ismertetem,
majd megfogalmazok egy \'altal\'anosabb eredm\'enyt, \'es megadom
annak a bizony\'{\i}t\'as\'at.

Jel\"olje $p(i)=r(i,1)+r(i,2)+r(i,3)$ a $\xi_l$
$q(j)=r(1,j)+r(2,j)+r(3,j)$ az $\eta_l$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'ok eloszl\'as\'at, ahol $i$ \'es $j$ az 1, 2 \'es $x$
\'ert\'ekeket veszi fel, \'es jel\"olje
$r(i|j)=\frac{r(i,j)}{q(j)}=P(\xi_l=i|\eta_l=j)$ a $\xi_l$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o felt\'eteles eloszl\'as\'at
felt\'eve az $\eta_l$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
\'ert\'ek\'et. Tekints\"uk az olyan $y_{v_1}$,\dots, $y_{v_l}$
sorozatokat, amelyek k\"or\"ulbel\"ul $nq(j)$ darab $j$ jelet
tartalmaznak, ahol $j=1$, 2 vagy $x$. Ha az $\eta_1$,\dots,
$\eta_n$ sorozat, azaz az ifj\'us\'agi m\'erk\"oz\'esek
eredm\'enyeinek a sorozata ilyen ar\'anyban veszi fel ezeket
az \'ert\'ekeket, akkor
tippelj\"unk \'ugy, hogy az \"osszes olyan tippet megadjuk,
amelyekben azon k\"or\"ulbel\"ul $nq(j)$ m\'erk\H{o}z\'es
k\"oz\"ul, amelyeknek ifj\'us\'agi m\'erk\H{o}z\'es
megfelel\H{o}j\'eben az $\eta_l=j$ eredm\'eny sz\"uletett
k\"or\"ulbel\"ul $nq(j)r(i|j)=np(i,j)$ m\'erk\H{o}z\'es
eredm\'eny\'et  tippelj\"uk $i$-nek, $i=1,2$ vagy $x$. Ha az
$\eta_l$, $1\le l\le n$, m\'erk\H{o}z\'esek eredm\'enyei nem
teljes\'{\i}tik a k\'{\i}v\'ant felt\'etelt, akkor a
tot\'oszelv\'enyeket tetsz\H{o}legesen kit\"olthetj\"uk
csup\'an arra \"ugyelve, hogy ne t\"olts\"unk ki t\'ul sok
szelv\'enyt.

A nagy sz\'amok t\"orv\'eny\'eb\H{o}l k\"ovetkezik, hogy az
adott m\'odon kit\"oltve a szelv\'enyeket majdnem egy
val\'osz\'{\i}n\H{u}s\'eggel lesz telital\'alatunk. Azt kell m\'eg
megbecs\"ul\"unk, hogy h\'any szelv\'enyt t\"olt\"ott\"unk ki. Ezt
az el\H{o}z\H{o} feladatban alkalmazott heurisztikus
\'ervel\'eshez hasonl\'oan tehetj\"uk meg. El\'eg csak azokat
az eseteket n\'ezni, amelyekben az $\eta_1,\dots,\eta_l$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok \'altal felvett
$y_{v_1},\dots,y_{v_n}$ eredm\'enyek k\"or\"ulbel\"ul $nq(j)$ $j$
eredm\'enyt tartalmaznak, $j=1,2$ vagy $x$. Ebben az esetben egy
olyan $\xi_1=x_{u_1},\dots,\xi_n=x_{u_n}$ eredm\'enynek, amelyre
tippelt\"unk a felt\'eteles val\'osz\'{\i}n\H{u}s\'ege
a $P(\cdot|\eta_1=y_{v_1},\dots,\eta_n=y_{v_n})$ felt\'eteles
eloszl\'as szerint k\"or\"ulbel\"ul
$\prodd_{i\in\{1,2,x\}}\prodd_{j\in\{1,2,x\}}r(i|j)^{nr(i,j)}$,
\'es mivel annak felt\'eteles val\'osz\'{\i}n\H{u}s\'ege a
tekintett felt\'eteles val\'osz\'{\i}n\H{u}s\'eg szerint, hogy
lesz telital\'alatunk majdnem 1, ez\'ert a kit\"olt\"ott
szelv\'enyek sz\'ama k\"or\"ulbel\"ul
$$
\prodd_{i\in\{1,2,x\}}\prodd_{j\in\{1,2,x\}}r(i|j)^{-nr(i,j)}
=2^{n\bar H},
$$
ahol $\bar H=-\summ_{i\in\{1,2,x\}}\summ_{j\in\{1,2,x\}}
r(i,j)\log\frac{r(i,j)}{q(j)}$. Teh\'at k\"or\"ulbel\"ul
$2^{n\bar H}$ szelv\'eny ki\-t\"ol\-t\'e\-s\'e\-vel tudunk majdnem
biztosan telital\'alatot el\'erni.

\medskip
Annak \'erdek\'eben, hogy a fenti heurisztikus t\'argyal\'asban
kapott eredm\'enyt pontosabban megfogalmazhassuk vezess\"uk be
a k\"ovetkez\H{o} fogalmat.

\medskip\noindent
{\bf A felt\'eteles entr\'opia definici\'oja.} {\it Legyen adva
k\'et $\xi$ \'es $\eta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o,
amelyek \'ert\'ekeiket egy v\'eges vagy megsz\'aml\'alhat\'oan
v\'egtelen $X=\{x_1,x_2,\dots\}$ illetve $Y=\{y_1,y_2,\dots\}$
halmazon veszik fel, \'es egy\"uttes eloszl\'asuk valamely
$r(i,j)=P(\xi=x_i,\eta=y_j)$, $x_i\in X$, $y_j\in Y$, f\"uggv\'eny.
Vezess\"uk be a $q(j)=P(\eta=y_j)=\summ_{x_i\in X}r(i,j)$
val\'osz\'{\i}n\H{u}s\'egeket is minden $y_j\in Y$ \'ert\'ekre.
A $\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o felt\'eteles
entr\'opi\'aja az $\eta$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'ora vonatkoz\'olag a
$$
H(\xi|\eta)=-\sum_{x_i\in X}\sum_{y_j\in Y}
r(i,j)\log\frac{r(i,j)}{q(j)}
$$
esetleg v\'egtelen \'ert\'eket felvev\H{o} mennyis\'eg, ahol
$\log$ a 2-es alap\'u logaritmust jel\"oli. A fenti defini\'oban
megengedj\"uk az $r(i,j)=0$ lehet\H{o}s\'eget bizonyos $(x_i,y_j)$
p\'arokra. Annak \'erdek\'eben, hogy a fenti \"osszeget ekkor is
\'ertelmezhess\"uk bevezetj\"uk a $0\log 0=0\log\frac00=0$
konvenci\'ot.}

\medskip\noindent
{\bf Megjegyz\'es.} {\it Abban az esetben, ha $H(\eta)<\infty$
\'erv\'enyes a
$$
H(\xi|\eta)=-\sum_{x_i\in X}\sum_{y_j\in Y} r(i,j)\log r(i,j)
+\sum_{y_j\in Y} q(j)\log q(j)=H(\xi,\eta)-H(\eta)
$$
azonoss\'ag.}

\medskip
A k\"ovetkez\H{o} t\'etel megfogalmaz\'as\'anak \'erdek\'eben
vezess\"unk be n\'eh\'any jel\"ol\'est. Adva egy $X$ halmaz,
jel\"olje az $X$ halmaz $x_k\in X$, $1\le k\le n$ elemeib\H{o}l
\'all\'o $n$ hossz\'us\'ag\'u $(x_1,\dots,x_n)$
sorozatok halmaz\'at $X^n$, hasonl\'oan egy $Y$ halmazbeli
elemekb\H{o}l \'all\'o $n$ hossz\'us\'ag\'u
$(y_1,\dots,y_n)$ sorozatok halmaz\'at $Y^n$ \'es az
$((x_1,\dots,x_n),(y_1,\dots,y_n))$ sorozatok halmaz\'at
$X^n\times Y^n$. Adva egy $A\subset X^n\times Y^n$
halmaz \'es egy $(y_1,\dots,y_n)\in Y^n$ sorozat legyen
$A(y_1,\dots,y_n)$ az $A$ halmaz metszete az
$X^n\times\{(y_1,\dots,y_n)\}$ halmazzal, azaz
$$
A(y_1,\dots,y_n)=\{(x_1,\dots,x_n)\colon\;
((x_1,\dots,x_n),(y_1,\dots,y_n))\in A\}.
$$
Jel\"olje $|A|$ egy (v\'eges) $A$ halmaz elemsz\'am\'at.

\medskip\noindent
{\bf T\'etel f\"uggetlen val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'okb\'ol \'all\'o \'es egy m\'asik f\"uggetlen
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-\-gi v\'altoz\'okb\'ol
\'all\'o v\'eletlen sorozat szerint tipikus sorozatok
sz\'am\'ar\'ol.} {\it Legyen adva egy $(\xi,\eta)$
v\'eletlen vektor, amelynek koordin\'at\'ai k\"oz\"ul $\xi$
\'ert\'ekeit egy $X=\{x_1,\dots,x_r\}$ $\eta$ pedig
egy $Y=\{y_1,\dots,y_s\}$ v\'eges halmazon
veszi fel. Legyen adva f\"ug\-get\-len \'es a $(\xi,\eta)$
p\'arral azonos eloszl\'as\'u
$((\xi_1,\eta_1),\dots,(\xi_n,\eta_n))$ v\'eletlen vektorok
egy so\-ro\-za\-ta. Ekkor minden $0<\e,\delta<1$
sz\'amp\'arhoz l\'etezik olyan $n_0=n_0(\e,\delta)$
k\"usz\"obindex, hogy minden $n\ge n_0$ sz\'amra igaz a
k\"ovetkez\H{o} \'all\'{\i}t\'as. Ha $B\in Y^n$ \'es
$A\in X^n\times Y^n$ olyan halmazok, amelyekre
$P(((\xi_1,\dots,\xi_n),(\eta_1,\dots,\eta_n))\in A|
\eta_1=y_{j_1},\dots,\eta_n=y_{j_n})\ge\delta$
minden $(y_{j_1},\dots,y_{j_n})\in B$ sorozatra, akkor
l\'etezik olyan $B_1\subset B$ halmaz,
amely\-re $P((\eta_1,\dots,\eta_n)\in B_1)
\ge P((\eta_1,\dots,\eta_n)\in B)-\delta$, \'es
az $A(y_{j_1},\dots,y_{j_n})$ halmaz sz\'amoss\'aga
teljes\'{\i}ti az
$|A(y_{j_1},\dots,y_{j_n})|>2^{n(1-\e)H(\xi|\eta)}$
egyenl\H{o}tlens\'eget minden
$(y_{j_1},\dots,y_{j_n})\in B_1$ sorozatra.

A m\'asik ir\'any\'u egyenl\H{o}tlens\'eg
megfogalmaz\'as\'aban csak azt az ese\-tet tekintj\"uk,
amikor $B=Y^n$, ez\'ert $P((\eta_1,\dots,\eta_n)\in B)=1$.
L\'eteznek olyan $A\in X^n\times Y^n$ \'es
$B_1\subset Y^n$ halmazok, amelyekre
$P((\eta_1,\dots,\eta_n)\in B_1)\ge1-\delta$,
$P(((\xi_1,\dots,\xi_n),(\eta_1,\dots,\eta_n))\in A|
\eta_1=y_{j_1},\dots,\eta_n=y_{j_n})\ge1-\delta$
minden $(y_{j_1},\dots,y_{j_n})\in B_1$ sorozatra,
tov\'abb\'a az $A(y_{j_1},\dots,y_{j_n})$ halmaz
sz\'amoss\'aga teljes\'{\i}ti az
$|A(y_{j_1},\dots,y_{j_n})|\le2^{n(1+\e)H(\xi|\eta)}$
egyen\-l\H{o}t\-len\-s\'e\-get minden
$(y_{j_1},\dots,y_{j_n})\in B_1$ sorozatra.
A fenti egyenl\H{o}tlens\'egekben $H(\xi|\eta)$ a $\xi$
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'o
felt\'eteles ent\-r\'o\-pi\'a\-j\'at jel\"oli az $\eta$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ora
vo\-nat\-ko\-z\'o\-lag.}

\medskip\noindent
{\bf Feladat:} {\it Bizony\'{\i}tsuk be a fenti t\'etel olyan
\'elesebb form\'aj\'at, amelyben megengedj\"uk azt is, hogy
az $X$ \'es $Y$ halmazok megsz\'aml\'alhat\'oan v\'egtelen
sz\'amoss\'ag\'uak legyenek.}

\medskip\noindent
{\it A t\'etel bizony\'{\i}t\'asa.}\/ Vezess\"uk be az
$r(i,j)=P(\xi=x_i,\eta=y_j)$, $q(j)=P(\eta=y_j)=\summ_{i=1}^r r(i,j)$
\'es $r(i|j)=P(\xi=x_i|\eta=y_j)=\frac{r(i,j)}{q(j)}$, $1\le i\le r$,
$1\le j\le s$, mennyis\'egeket. Adva egy
$y=(y_{j_1},\dots,y_{j_n})\in Y^n$ vektor, jel\"olje $s(y,j)$ az $y$
sorozatban szerepl\H{o} $y_j$ elemek sz\'am\'at, $1\le j\le s$, \'es
defini\'aljuk a k\"ovetkez\H{o} $B_0\in Y^n$ halmazt:
$$
B_0=\left\{y=(y_{j_1},\dots,y_{j_n})\colon\; y\in Y^n,\;
s(y,j)\ge(1-\tfrac\e4)nq(j) \text{ minden } 1\le j\le s
\text{ indexre}.\right\}.
$$
Ekkor a nagy sz\'amok t\"orv\'enye szerint
$P((\eta_1,\dots,\eta_n)\in B_0)\ge1-\delta$, ha $n\ge n_0$ egy
el\'eg nagy $n_0=n_0(\e,\delta)$ k\"usz\"obindexszel, ez\'ert
a $B_1=B\cap B_0$ halmazra $B_1\subset B$, \'es
$P((\eta_1,\dots,\eta_n)\in B_1)\ge
P((\eta_1,\dots,\eta_n)\in B_0)-\delta$. Defini\'aljuk minden
$(x,y)=((x_{i_1},\dots,x_{i_n}),(y_{j_1},\dots,y_{j_n}))
\in X^{n}\times Y^{n}$ sorozatra az $\ell(x,y,i,j)$ mennyis\'eget
minden $1\le i\le r$ \'es $1\le j\le s$ indexre \'ugy, mint az
$(x,y)$ vektorban szerepl\H{o} olyan
$(x_{i_k},y_{j_k})$, $1\le k\le n$, p\'arok sz\'am\'at,
amelyek egyenl\H{o}ek az $(x_i,y_j)$ p\'arral. Adva egy
$y=(y_{j_1},\dots,y_{j_n})\in B_0$ vektor defini\'aljuk a
k\"ovetkez\H{o} $C(y)\in X^n$ halmazt.
$$
\align
C(y)=\{x&=(x_{i_1},\dots,x_{i_n})\colon\;(x,y)\in X^n\times Y^n,\;
\ell(x,y,i,j)\ge (1-\tfrac\e2)nr(i,j) \\
&\qquad \text{minden }1\le i\le r,\; 1\le j\le s \text{ p\'arra.} \}
\endalign
$$
A nagy sz\'amok t\"orv\'eny\'eb\H{o}l k\"ovetkezik, hogy
$P((\xi_1,\dots,\xi_n)\in C(y)|\eta_1=y_{j_1},\dots,\eta_n=y_{j_n})
\ge1-\frac\delta2$, ha $y=(y_{j_1},\dots,y_{j_n})\in B_0$. Ugyanis,
ha $y\in B_0$, akkor e felt\'eteles val\'osz\'{\i}n\H{u}s\'eg
felt\'etel\'eben $s(y,j)\ge nq(j)(1-\frac\e4)$ olyan $k$
index van, amelyre $\eta_k=y_j$. Az $\xi_k$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok egy\"uttes eloszl\'asa ezen
$k$ indexekre a tekintett felt\'eteles eloszl\'as szerint
megegyezik $s(y,j)\ge (1-\frac\e4)nq(j)$ f\"uggetlen, $r(\cdot|j)$
eloszl\'as\'u val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
egy\"uttes eloszl\'as\'aval. Ez\'ert ez a sorozat a nagy sz\'amok
t\"orv\'enye szerint t\"obb, mint
$(1-\frac\delta2)^{1/rs}$ val\'osz\'{\i}n\H{u}s\'eggel tartalmaz
legal\'abb $n(1-\frac\e4)^2q(j)r(i|j)\ge n(1-\frac\e2)r(i,j)$
$x_i$ elemet minden $1\le i\le r$ indexre. Innen \'es a t\'etel
felt\'eteleib\H{o}l az is k\"ovetkezik, hogy tetsz\H{o}leges
$y=(y_{j_1},\dots,y_{j_n})\in B_1$ vektorra
$$
P(((\xi_1,\dots,\xi_n),(\eta_1,\dots,\eta_n))\in A,
(\xi_1,\dots,\xi_n)\in C(y)|
\eta_1=y_{j_1},\dots,\eta_n=y_{j_n})\ge\frac\delta2,
$$
ami \'ugy is \'{\i}rhat\'o, hogy
$$
P((\xi_1,\dots,\xi_n)\in C(y)\cap A(y)|
\eta_1=y_{j_1},\dots,\eta_n=y_{j_n})\ge\frac\delta2,
$$
ahol $A(y)=A(y_{j_1},\dots,y_{j_n})$.
Felhaszn\'alva ezt az egyenl\H{o}tlens\'eget \'es a $C(y)$ halmaz
elemeinek a tulajdons\'agait bel\'atjuk, hogy
$|A(y)\cap C(y)|\ge2^{n(1-\e)H(\xi|\eta)}$.
Ennek \'erdek\'eben vegy\"uk \'eszre, hogy tetsz\H{o}letes
$y=(y_{j_1},\dots,y_{j_n})\in B_1$ \'es
$(x_{i_1},\dots,x_{i_n})\in C(y)$ vektorokra
$$
\align
&P(\xi_1=x_{i_1},\dots,\xi_n=x_{i_n}|
\eta_1=y_{j_1},\dots,\eta_n=y_{j_n})=\prod_{i=1}^r\prod_{j=1}^s
r(i|j)^{\ell(x,y,i,j)}\\
&\qquad \le\prod_{i=1}^r\prod_{j=1}^s
r(i|j)^{(1-\e/2)nr(i|j)}=2^{-n(1-\e/2)H(\xi|\eta)}.
\endalign
$$
Az utols\'o k\'et egyenl\H{o}tlens\'egb\H{o}l k\"ovetkezik,
hogy
$$
|A(y_{j_1},\dots,y_{j_n})\cap C(y)|\ge \frac\delta2
2^{n(1-\e/2)H(\xi|\eta)}\ge 2^{(1-\e)nH(\xi|\eta)},
$$
ha $(y_{j_1},\dots,y_{j_n})\in B_1$.

A m\'asik ir\'any\'u becsl\'est az alkalmas $B\in Y^n$ \'es
$A\in X^n\times Y^n$ halmazok alkalmas definici\'oj\'aval
hasonl\'oan bizony\'{\i}thatjuk. Legyen
$$
B_1=\left\{y=(y_{j_1},\dots,y_{j_n})\colon\; y\in Y^n,\;
s(y,j)\le(1+\tfrac\e2)nq(j) \text{ minden } 1\le j\le s
\text{ indexre}.\right\},
$$
\'es
$$
\align
A=\{(x,y)&=((x_{i_1},\dots,x_{i_n}),(y_{j_1},\dots,y_{j_n}))\colon\;
(x,y)\in X^n\times Y^n,\; y\in B_1,\\
&\qquad\ell(x,y,i,j)\le (1+\e)nr(i,j)
\text{ minden }1\le i\le r,\; 1\le j\le s \text{ p\'arra.} \}
\endalign
$$
Az el\H{o}z\H{o} eset \'ervel\'es\'ehez hasonl\'oan
bizony\'{\i}thatjuk a nagy sz\'amok t\"orv\'enye
seg\'{\i}ts\'eg\'evel, hogy
$P((\eta_1,\dots,\eta_n)\in B_1)\ge1-\delta$, ha $n\ge n_0$, \'es
$$
\align
&P(((\xi_1,\dots,\xi_n),(\eta_1,\dots,\eta_n))\in A|
\eta_1=y_{j_1},\dots,\eta_n=y_{j_n})\\
&\qquad=P((\xi_1,\dots,\xi_n),\in A(y_{j_1},\dots,y_{j_n})|
\eta_1=y_{j_1},\dots,\eta_n=y_{j_n})\ge1-\delta
\endalign
$$
minden $(y_{j_1},\dots,y_{j_n})\in B_1$ sorozatra. Tov\'abb\'a
$$
\align
&P(\xi_1=x_{i_1},\dots,\xi_n=x_{i_n}|
\eta_1=y_{j_1},\dots,\eta_n=y_{j_n})=\prod_{i=1}^r\prod_{j=1}^s
r(i|j)^{\ell(x,y,i,j)}\\
&\qquad \ge\prod_{i=1}^r\prod_{j=1}^s
r(i|j)^{(1+\e)nr(i|j)}=2^{-n(1+\e)H(\xi|\eta)},
\endalign
$$
ha $(y_{j_1},\dots,y_{j_n})\in B_1$ \'es
$(x_{i_1},\dots,x_{i_n})\in A(y_{j_1},\dots,y_{j_n})$.
Felhaszn\'alva a (trivi\'alis)
$P((\xi_1,\dots,\xi_n)\in A(y_{j_1},\dots,y_{j_n})|
\eta_1=y_{j_1},\dots,\eta_n=y_{j_n})\le1$ egyenl\H{o}tlens\'eget
innen kapjuk, hogy
$|A(y_{j_1},\dots,y_{j_n})|\le2^{n(1+\e)H(\xi|\eta)}$
minden $(y_{j_1},\dots,y_{j_n})\in B_1$ sorozatra.

\medskip
A most bizony\'{\i}tott eredm\'enyt az el\H{o}z\H{o} eredm\'enyhez
hasonl\'oan a k\"ovetkez\H{o}k\'epp is interpret\'alhatjuk.
Legyen adva egy v\'eges sok \'ert\'eket felvev\H{o} $(\xi,\eta)$
v\'eletlen vektor (val\'oj\'aban az al\'abb megfogalmazott
\'all\'{\i}t\'as akkor is igaz, ha ez a v\'eletlen vektor
v\'egtelen sok \'ert\'eket is felvehet, de ezt nem
bizony\'{\i}tottuk be), \'es f\"uggetlen  v\'eletlen vektoroknak
egy ezzel a v\'eletlen vektorral azonos eloszl\'as\'u,
$n$-hossz\'us\'ag\'u $(\xi_1,\eta_1)$,\dots, $(\xi_n,\eta_n)$
sorozata. Ismerve az $\eta_1,\dots,\eta_n$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok \'ert\'ekeit ki akarunk
v\'alasztani viszonylag kev\'es sorozatot \'ugy, hogy ezek egyike
majdnem biztos meg\-egyez\-z\'ek a $\xi_1,\dots,\xi_n$ v\'eletlen
sorozat \'ert\'ek\'evel. A majdnem biztos kiv\'alaszt\'as itt
azt jelenti, hogy r\"ogz\'{\i}t\"unk egy kis $\e>0$ sz\'amot,
megadjuk az $(\eta_1,\dots,\eta_n)$ sorozatok lehets\'eges
\'ert\'ekeinek egy legal\'abb $1-\e$ m\'ert\'ek\H{u} halmaz\'at,
\'es amennyiben az $(\eta_1,\dots,\eta_n)$ sorozat ezek
valamelyik\'evel egyenl\H{o}, akkor kijel\"olj\"uk $n$
hossz\'us\'ag\'u sorozatok egy vi\-szony\-lag kev\'es elemb\H{o}l
\'all\'o halmaz\'at \'ugy, hogy annak a val\'osz\'{\i}n\H{u}s\'ege,
hogy a $(\xi_1,\dots,\xi_n)$ v\'eletlen sorozat megegyezik
ezek valamelyik\'evel legal\'abb $1-\e$. A kiv\'alasztott
sorozatok halmaza f\"ugghet az $(\eta_1,\dots,\eta_n)$ vektor
\'ert\'ek\'et\H{o}l. Azt l\'attuk be, hogy ezt megtehetj\"uk
$2^{nH(\xi|\eta)+o(n)}$ a\-lkal\-ma\-san v\'alasztott sorozat
seg\'{\i}ts\'eg\'evel, de kevesebbel m\'ar nem. Ennek az
eredm\'enynek megfogalmazhatjuk az al\'abbi k\"ovetkezm\'eny\'et.

Meg akarjuk nevezni a $(\xi_1,\dots,\xi_n)$ sorozatokat
az $\eta_1,\dots,\eta_n$ sorozat ismeret\'eben $m=m(n)$
hossz\'us\'ag\'u az $\eta_1,\dots,\eta_n$ sorozatt\'ol
f\"ugg\H{o} v\'alaszt\'assal 0--1 sorozatokkal \'ugy, hogy
$1-\e$ val\'osz\'{\i}n\H{u}s\'eggel egy $(\xi_1,\dots,\xi_n)$
sorozatot megnevez\"unk, \'es r\"ogz\'{\i}tett
$\eta_1,\dots,\eta_n$ sorozat megjelen\'ese eset\'en k\'et
k\"ul\"onb\"oz\H{o} $\xi_1,\dots,\xi_n$ sorozat elnevez\'ese
k\"ul\"onb\"oz\H{o}. Ez lehets\'eges $m=nH(\xi|\eta)+o(n)$
hossz\'us\'ag\'u 0--1 sorozatokkal, de r\"ovidebb sorozatokkal nem.
Ezt szok\'as \'ugy interpret\'alni, hogy az $\eta_1,\dots,\eta_n$
sorozat ismeret\'eben a $\xi_1,\dots,\xi_n$ sorozat
egyes tagjainak a megnevez\'es\'ehez $H(\xi|\eta)$ bit
sz\"uks\'eges, azaz az $\eta_k$ v\'altoz\'ok \'ert\'ek\'enek az
ismeret\'eben ennyi inform\'aci\'o kell az egyes $\xi_k$
v\'eletlen v\'altoz\'ok megismer\'es\'ehez.

\medskip
Megfogalmazom \'es bebizony\'{\i}tom az entr\'opi\'aval
\'es felt\'eteles entr\'opi\'aval kapcsolatos legfontosabb
egyenl\H{o}tlens\'egeket. Ezek mindegyike heurisztikus szinten
`ny\'{\i}lv\'anval\'o' k\"ovetkezm\'enye az entr\'opia \'es
felt\'eteles entr\'opia szeml\'eletes tartalm\'anak.

\medskip\noindent
{\bf T\'etel az entr\'opi\'aval \'es felt\'eteles entr\'opi\'aval
kapcsolatos fontos egyen\-l\H{o}t\-len\-s\'e\-gek\-r\H{o}l.}
{\it Legyenek $\xi$, $\eta$ \'es $\zeta$ v\'eges vagy
megsz\'aml\'alhat\'o sok \'er\-t\'e\-ket f\"olvev\H{o}
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok. Ezek teljes\'{\i}tik
a k\"ovetkez\H{o} egyenl\H{o}tlens\'egeket:

\medskip
\item{a1.)} $H(\xi)\ge0$, \'es egyenl\H{o}s\'eg akkor \'es csak
akkor \'erv\'enyes, ha a $\xi$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o egy val\'osz\'{\i}n\H{u}s\'eggel egy konstanssal
egyenl\H{o}.
\item{a2.)} Ha a $\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o $n$
\'ert\'eket vesz fel, akkor $H(\xi)\le\log n$. Egyenl\H{o}s\'eg
akkor \'es csak akkor \'erv\'enyes, ha a $\xi$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o \'altal felvett
$x_1,\dots,x_n$ \'ert\'ekekre $P(\xi=x_k)=\frac1n$ minden
$1\le k\le n$ indexre.

\medskip
\item{b.)} $H(\xi,\eta)\le H(\xi)+H(\eta)$, illetve kiss\'e
\'altal\'anosabban $H(\xi|\eta)\le H(\xi)$. Egyenl\H{o}s\'eg
akkor \'es csak akkor teljes\"ul, ha $\xi$ \'es $\eta$
f\"uggetlenek.

\medskip
\item{c.)} $H(\eta)\le H(\xi,\eta)$, illetve kiss\'e
\'altal\'anosabban $H(\xi|\eta)\ge0$. Egyenl\H{o}s\'eg akkor
\'es csak akkor teljes\"ul, ha $\xi=f(\eta)$ valamely
$f(\cdot)$ f\"uggv\'ennyel, azaz $\xi$ az $\eta$ f\"uggv\'enye.

\medskip
\item{d.)} $H(\xi|\eta,\zeta)\le H(\xi|\eta)$. Abban az esetben,
ha l\'etezik olyan a $(\xi,\eta)$ v\'eletlen vektort\'ol
f\"uggetlen $Z$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o, amelyre
$\zeta=h(\eta,Z)$ valamely alkalmas $h$ f\"uggv\'ennyel, akkor
egyenl\H{o}s\'eg \'all fenn.

}\medskip\noindent
{\it Megjegyz\'es.}\/ A felt\'eteles entr\'opi\'ar\'ol sz\'ol\'o
b) \'es c) pontban megfogalmazott egyen\-l\H{o}t\-len\-s\'e\-gek
akkor is \'erv\'enyesek, ha $H(\eta)=\infty$. Ebben az esetben
ezek az \'all\'{\i}t\'asok t\"obbet mondanak, mint a nekik
megfelel\H{o} az entr\'opi\'ar\'ol megfogalmazott
egyenl\H{o}tlens\'egek.

\medskip\noindent
{\bf K\"ovetkezm\'eny.}  {\it
\item{a.)} $H(f(\xi))\le H(\xi)$ tetsz\H{o}leges $f(\cdot)$
f\"uggv\'enyre.  Ha $\xi$ \'ert\'ekeit egy v\'egtelen
$X=\{x_1,x_2,\dots\}$ halmazban veszi fel, $H(\xi)<\infty$ \'es
minden $K\ge 1$ sz\'amra defini\'alunk egy olyan $\xi^{(K)}$,
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot, amelyre
$\xi^{(K)}_j=x_j$, ha $j\le K$, \'es $\xi^{(K)}_j=x^*$ valamely
$x^*\neq x_j$, $j=1,2,\dots$ \'ert\'ekkel, akkor
$H(\xi^{(K)})\le H(\xi)$, \'es minden $\e>0$ sz\'amhoz l\'etezik
olyan $K_0=K_0(\e)$ index, hogy $H(\xi^{(K)})\ge H(\xi)-\e$,
ha $K\ge K_0$.

\item{b.)} $H(\xi,\eta|\zeta)\ge H(\xi|\zeta)$, \'es egyenl\H{o}s\'eg
akkor \'es csak akkor \'all fenn, ha vagy $\eta=f(\zeta)$ alkalmas
$f$ f\"uggv\'ennyel vagy $H(\xi|\eta,\zeta)=\infty$. Tov\'abb\'a
$H(\xi,\eta|\zeta)\le H(\xi|\zeta)+H(\eta|\zeta)$.

}\medskip\noindent
{\it A k\"ovetkezm\'eny bizony\'{\i}t\'asa.}\/ Az a) r\'esz
bizony\'{\i}t\'asa: $H(\xi)=H(\xi,f(\xi))\ge H(f(\xi))$ a
t\'etel c) pontja szerint. Innen k\"ovetkezik a
$H(\xi^{(K)})\le H(\xi)$ egyenl\H{o}tlens\'eg, az $X$ t\'eren
defini\'alt $f(x_j)=x_j$, ha $j\le K$, \'es $f(x_j)=x^*$, ha $j\ge K$
v\'alaszt\'assal. Legyen $p_j=P(\xi=x_j)$, $j=1,2,\dots$. A
$H(\xi)=-\summ_{j=1}^\infty p_j\log p_j<\infty$ felt\'etelb\H{o}l
k\"ovetkezik, hogy l\'etezik olyan $K_0=K_0(\e)$ index, hogy
$-\summ_{j=1}^{K_0} p_j\log p_j<H(\xi)-\e$. Ilyen $K_0=K_0(\e)$
v\'alaszt\'assal igaz az a) r\'esz utols\'o \'all\'{\i}t\'asa is.

A k\"ovetkezm\'eny b) r\'esz\'enek az \'all\'{\i}t\'asa k\"ovetkezik a
$H(\xi,\eta|\zeta)=H(\xi|\eta,\zeta)+H(\eta|\zeta)$ azonoss\'agb\'ol
\'es a t\'etel c) illetve d) r\'esz\'enek az \'all\'{\i}t\'as\'ab\'ol.

\medskip
\'Erts\"uk meg, hogy az el\H{o}bb megfogalmazott t\'etel
egyenl\H{o}tlens\'egei az entr\'opia \'es felt\'eteles entr\'opia
szeml\'eletes tartalm\'anak megfelel\H{o} tulajdon\'agokat fejeznek
ki. Az a1) tulajdons\'ag azt mondja, hogy a $\xi$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o \'altal felvett
\'ert\'ek meg\-is\-me\-r\'e\-s\'e\-hez pozit\'{\i}v inform\'aci\'o
sz\"uks\'eges, kiv\'eve azt az elfajul\'o esetet, amikor $\xi$
\'ert\'eke (ismert) konstans, \'es ez\'ert nulla inform\'aci\'o is
elegend\H{o}. Az a2) \'all\'{\i}t\'as szerint egy $n$ \'ert\'eket
felvev\H{o} val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o \'ert\'ek\'enek
a megismer\'es\'ehez akkor kell a legt\"obb inform\'aci\'o, ha minden
\'ert\'eket egyforma val\'osz\'{\i}n\H{u}s\'eggel vesz fel, amit
\'ugy is interpret\'alhatunk, hogy azonk\'{\i}v\"ul, hogy tudjuk,
hogy $\xi$ $n$ \'ert\'eket vesz fel, semmilyen plusz inform\'aci\'onk
nincs annak viselked\'es\'er\H{o}l.

A b) tulajdons\'ag azt fejezi ki, hogy egy $\eta$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o \'ert\'ek\'enek az ismerete
cs\"okkentheti egy
$\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o \'ert\'ek\'enek
megismer\'es\'ehhez sz\"uks\'eges inform\'aci\'ot. Akkor nincs
cs\"okken\'es, ha $\xi$ \'es $\eta$ f\"uggetlenek, \'es ez\'ert
$\eta$ ismerete semmilyen \'ert\'ekes inform\'aci\'ot nem ad
$\xi$ viselked\'es\'er\H{o}l. A c) tulajdons\'ag szerint egy $\xi$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o \'ert\'ek\'enek a
megismer\'es\'ehez pozit\'{\i}v inform\'aci\'o sz\"uks\'eges egy
$\eta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o \'ert\'ek\'enek az
ismeret\'eben is. Akkor el\'eg nulla inform\'aci\'o, ha $\xi$ az
$\eta$ ismert f\"uggv\'enye.

A d) tulajdons\'ag jelent\'ese az, hogy egy $\xi$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o \'ert\'ek\'enek a
megismer\'es\'ehez kevesebb inform\'aci\'o sz\"uks\'eges, ha egy
$\eta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o \'ert\'ek\'en
k\'{\i}v\"ul egy m\'asik
$\zeta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o \'ert\'ek\'et is
ismerj\"uk. Semmilyen nyeres\'eget nem jelent viszont $\zeta$
ismerete, ha az a m\'ar ismert $\eta$ \'es egy mind a $\xi$ mind
az $\eta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot\'ol f\"uggetlen
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o f\"uggv\'enye.

\medskip
A t\'etel bizony\'{\i}t\'as\'aban fontos szerepet j\'atszik
egy egyszer\H{u} \'all\'{\i}t\'as, amelyet a bizony\'{\i}t\'as
jobb \'attekinthet\H{o}s\'ege \'erdek\'eben k\"ul\"on lemm\'aban
fogalmazok meg.

\medskip\noindent
{\bf Lemma az $x\log x$ f\"uggv\'eny viselked\'es\'er\H{o}l.}
{\it A $g(x)=x\log x$, ha $x>0$, $g(0)=0$ f\"uggv\'eny egy a
$[0,\infty)$ f\'elegyenesen folytonos, szigor\'uan konvex
f\"uggv\'eny, amelyre $g(0)=g(1)=0$.}

\medskip\noindent
{\it A lemma bizony\'{\i}t\'asa.}\/ K\"onnyen l\'athat\'o, hogy
$g(x)$ folytonos f\"uggv\'eny a $[0,\infty)$ f\'el\-egye\-ne\-sen,
\'es $g(0)=g(1)=0$. Ezenk\'{\i}v\"ul $g''(x)=\frac{\log e}x>0$ minden
$x>0$ sz\'amra, ahon\-nan k\"ovetkezik, hogy $g(x)$ szigor\'uan
konvex f\"uggv\'eny.

\medskip\noindent
{\it A t\'etel bizony\'{\i}t\'asa.} Jel\"olje $X=\{x_1,x_2,\dots\}$
a $\xi$, $Y=\{y_1,y_2,\dots\}$ az $\eta$ \'es $Z=\{z_1,z_2,\dots\}$
a $\zeta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o \'ert\'ekeit. Az
a) b) \'es c) r\'eszben haszn\'aljuk a $p(i)=P(\xi=x_i)$,
$q(j)=P(\eta=y_j)$ \'es $r(i,j)=P(\xi=x_i,\eta=y_j)$ jel\"ol\'est.
Az a1) \'all\'{\i}t\'as nyilv\'anval\'o, mert $-p(i)\log p(i)>0$, ha
$0<p(i)<1$, \'es $0\log 0=1\log 1=0$. Az a2) \'all\'{\i}t\'as k\"ovetkezik
a
$$
-H(\xi)=n\sum_{i=1}^n\frac1n g(p(i))\ge ng\(\frac 1n\sum_{i=1}^np(i)\)=
ng\(\frac1n\)=-\log n
$$
egyenl\H{o}tlens\'egb\H{o}l, ahol $g(x)$ a lemm\'aban szerepl\H{o}
konvex f\"ugg\-v\'eny. Mivel a $g(\cdot)$ f\"ugg\-v\'eny szigor\'uan
konvex egyenl\H{o}s\'eg csak a $p(i)=\frac1n$, $1\le i\le n$ esetben
lehets\'eges.

A b) \'all\'{\i}t\'as bizony\'{\i}t\'asa \'erdek\'eben \'{\i}rjuk fel
a
$$ \allowdisplaybreaks
\align
H(\xi|\eta)&=-\sum_{i,j} q(j)\frac{r(i,j)}{q(j)}\log \frac{r(i,j)}{q(j)}
=-\sum_i\(\sum_j q(j) g\(\frac{r(i,j)}{q(j)}\)\)\\
&\le -\sum_i\(g\(\sum_j q(j)\frac{r(i,j)}{q(j)}\)\)
=-\sum_i g(p(i))=H(\xi)
\endalign
$$
egyenl\H{o}tlens\'eget. E sz\'amol\'asban felhaszn\'altuk a
$g(x)=x\log x$ f\"uggv\'eny konvexit\'as\'at a $q(j)$, $q(j)>0$,
$\summ_j q(j)=1$ s\'ulyokkal azaz azt, hogy
$\summ_j q(j)g(u_j)\le g\(\summ_j q(j)u_j)\)$ minden $u_1\ge0$,
$u_2\ge0$,\dots sz\'amsorozatra, \'es a $\summ_j r(i,j)=p(i)$
azonoss\'agot. Felhaszn\'alva a $g(\cdot)$ f\"uggv\'eny
szigor\'u konvexit\'as\'at kapjuk, hogy egyenl\H{o}s\'eg akkor
\'es csak akkor lehets\'eges, ha b\'armely r\"ogz\'{\i}tett
$i$ indexre $\frac{r(i,j)}{q(j)}=\alpha_i$ valamely $\alpha_i$
sz\'ammal minden $j$ indexre. Ez azt jelenti. hogy
$r(i,j)=\alpha_iq(j)$, \'es ezt az azonoss\'agot \"osszegezve a
$j$ v\'altoz\'ora azt kapjuk, hogy
$p(i)=\alpha_i\summ_j r(i,j)=\alpha_i$,
azaz $r(i,j)=p(i)q(j)$ minden $i$ \'es $j$ indexre, teh\'at a
$\xi$ \'es $\eta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
f\"uggetlenek.

A c) \'all\'{\i}t\'as bizony\'{\i}t\'asa \'erdek\'eben \'{\i}rjuk fel
a
$$
-H(\xi|\eta)=\sum_j q(j)
\(\sum_i\frac{r(i,j)}{q(j)}\log \frac{r(i,j)}{q(j)}\)
$$
azonoss\'agot \'es vegy\"uk \'eszre, hogy e kifejez\'esben
szerepl\H{o} a bels\H{o} \"osszeg minden $j$-re teljes\'{\i}ti
a $\summ_i\frac{r(i,j)}{q(j)}\log \frac{r(i,j)}{q(j)}\le0$
azonoss\'agot. Innen k\"ovetkezik, hogy $H(\xi|\eta)\ge0$.
Egyenl\H{o}s\'eg csak akkor lehets\'eges, ha mindegyik
$\frac{r(i,j)}{q(j)}$ tag vagy null\'aval vagy eggyel egyenl\H{o}.
Ez azt jelenti, hogy l\'etezik egy olyan $i(j)$ index, hogy
$\frac{r(i(j),j)}{q(j)}=1$, azaz $P(\xi=x_{i(j)}|\eta=y_j)=1$.
Ez\'ert egyenl\H{o}s\'eg akkor \'es csak akkor teljes\"ul, ha
$\xi=f(\eta)$ valamely alkalmas $f$ f\"uggv\'ennyel.

A d) r\'esz \'all\'{\i}t\'as\'anak vizsg\'alat\'aban vezess\"uk be
a $p(i)=P(\xi=x_i)$ \'es $q(j)=P(\eta=y_j)$ mennyis\'egek mellett
az $u(i,j)=P(\xi=x_i,\eta=y_j)$, $v(j,k)=P(\eta=y_j,\zeta=z_k)$
valamint a $t(i,j,k)=P(\xi=x_i,\eta=y_j,\zeta=z_k)$ mennyis\'egeket
is. Ezekkel a jel\"ol\'esekkel fel\"{\i}rhatjuk, hogy
$$
\align
H(\xi|\eta,\zeta)&=-\sum_{i,j,k}t(i,j,k)\log\frac{t(i,j,k)}{v(j,k)}
=-\sum_{i,j} \(\sum_k q(j)
\frac{v(j,k)}{q(j)}\frac{t(i,j,k)}{v(j,k)}\log\frac{t(i,j,k)}{v(j,k)}\)\\
&=-\sum_{i,j} q(j)\(\sum_k\frac{v(j,k)}{q(j)}
g\(\frac{t(i,j,k)}{v(j,k)}\)\) \le -\sum_{i,j} q(j)
g\(\sum_k\frac{v(j,k)}{q(j)}\frac{t(i,j,k)}{v(j,k)}\)\\
&= -\sum_{i,j} q(j) g\(\sum_k\frac{t(i,j,k)}{q(j)}\)
= -\sum_{i,j} q(j) g\(\frac{u(i,j)}{q(j)}\)\\
&=-\sum_{i,j}P(\xi=x_i,\eta=y_j)
\log\frac{P(\xi=x_i,\eta=y_j)}{P(\eta=y_j)}=H(\xi|\eta).
\endalign
$$
E sz\'amol\'asokban felhaszn\'altuk, hogy $g(\cdot)$ konvex
f\"uggv\'eny, $\summ_k\frac{v(j,k)}{q(j)}=1$, \'es
$\summ_k\frac{t(i,j,k)}{q(j)}=\frac{u(i,j)}{q(j)}$.
A kapott egyenl\H{o}tlens\'agben azonoss\'agot \'{\i}rhatunk
abban a speci\'alis esetben, ha $\frac{t(i,j,k)}{v(j,k)}=\alpha(i,j)$,
azaz, ha ez a t\"ort csak az csak az $i$ \'es $j$
v\'altoz\'ot\'ol f\"ugg. Speci\'alisan egyenl\H{o}s\'eg
\'erv\'enyes, ha $\frac{t(i,j,k)}{v(j,k)}={u(i,j)}{q(j)}$
vagy ekvivalens m\'odon megfogalmazva akkor, ha
$P(\zeta=z_k|\xi=x_i,\eta=y_j)=P(\zeta=z_k|\eta=y_j)$
minden $i$, $j$ \'es $k$ indexre. (N\'emi sz\'amol\'as
megmutatja, mi\'ert \'erdemes az $\alpha(i,j)$ f\"uggv\'enyt
\'{\i}gy v\'alasztani.) A t\'etel bizony\'{\i}t\'as\'at
befejezz\"uk, ha megmutatjuk, hogy ez az azonoss\'ag teljes\"ul
akkor, ha $\zeta=h(\eta,Z)$ egy a $(\xi,\eta)$ v\'eletlen
vektort\'ol f\"uggetlen $Z$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'oval. Ez az azonoss\'ag viszont igaz, mert az
adott esetben $P(\zeta=z_k|\xi=x_i,\eta=y_j)=
P(h(y_j,Z)=z_k|\xi=x_i,\eta=y_j)=P(h(y_j,Z)=z_k)$, \'es
hasonl\'oan $P(\zeta=z_k|\eta=y_j)=
P(h(y_j,Z)=z_k|\eta=y_j)=P(h(y_j,Z)=z_k)$.

\medskip\noindent
{\bf Kieg\'esz\'{\i}t\'es:} {\it F\"uggetlen, \'ert\'ekeiket
esetleg v\'egtelen halmazban felvev\H{o}
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'al\-to\-z\'ok\-b\'ol
\'all\'o tipikus sorozatok sz\'am\'anak a becsl\'ese.}

\medskip\noindent
A {\it f\"uggetlen val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'okb\'ol \'all\'o tipikus sorozatok sz\'am\'ar\'ol}
sz\'ol\'o t\'etelben becs\-l\'est adtunk arra, hogy h\'any
tipikus sorozatot tartalmaz egy $\xi$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'oval azonos eloszl\'as\'u f\"uggetlen
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok $\xi_1,\dots,\xi_n$
sorozata. Pontosabban fogalmazva azt becs\"ult\"uk meg, hogy
r\"ogz\'{\i}tve egy kis $\e>0$ sz\'amot k\"or\"ulbel\"ul h\'any
sorozatot tartalmaz a $(\xi_1,\dots,\xi_n)$ v\'eletlen sorozatok
egy $1-\e$ m\'ert\'ek\H{u} alkalmasan v\'alasztott r\'eszhalmaza.
A v\'alasz a $\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o $H(\xi)$
entr\'opi\'aj\'at\'ol f\"ugg.

Ezt az eredm\'enyt csak abban az esetben l\'attuk be, ha a $\xi$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o csak v\'eges sok
\'ert\'eket vehet fel. Ugyanakkor term\'eszetes azt v\'arni, hogy
a t\'etel \'all\'{\i}t\'asa \'erv\'enyes megsz\'aml\'alhat\'oan
v\'egtelen sok \'ert\'eket felvev\H{o} $\xi$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o eset\'en. Bel\'atjuk, hogy
ez t\'enyleg \'{\i}gy van. Az egyszer\H{u} fogalmaz\'as
\'erdek\'eben feltessz\"uk, hogy $H(\xi)<\infty$, hiszen
val\'oj\'aban minket csak ez az eset \'erdekel.

A t\'etelben a tipikus sorozatok sz\'am\'ara adott als\'o
becsl\'es k\"onnyen visszavezethet\H{o} egy v\'eges sok \'ert\'eket
felvev\H{o} $\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o eset\'ere.
Val\'oban, ha $\xi$ \'ert\'ekeit egy $X=\{x_1,x_2,\dots\}$
v\'egtelen halmazon veszi fel, akkor minden $\e>0$ sz\'amhoz meg
lehet adni egy olyan $K=K(\e)$ sz\'amot \'ugy, hogy arra a $\xi^*$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ora, amelyet a $\xi^*=x_k$,
ha $\xi=x_k$ \'es $k\le K(\e)$, valamint $\xi^*=x^*$ valamilyen 
\'uj $x^*$ \'ert\'ekkel, ha $\xi=x_k$, \'es $k\ge K(\e)$ k\'epletek
defini\'alnak \'erv\'enyes a $H(\xi)-\e<H(\xi^*)\le H(\xi)$ 
egyenl\H{o}tlens\'eg. Al\-kal\-maz\-hat\-juk a {\it f\"uggetlen
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'okb\'ol \'all\'o tipikus
sorozatok sz\'am\'ar\'ol} sz\'ol\'o t\'etel als\'o
becs\-l\'e\-s\'et egy a $\xi^*$ (v\'eges sok \'ert\'eket
felvev\H{o}) val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'oval azonos
eloszl\'as\'u f\"uggetlen val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
sorozat\'ara, \'es ebb\H{o}l k\"onnyen levezethet\H{o} a t\'etelben
szerepl\H{o} als\'o becsl\'es az \'altal\'anos esetben.
De a fels\H{o} becsl\'es bizony\'{\i}t\'asa nehezebb, ez \'uj
gondolatokat ig\'enyel. Ezzel a k\'erd\'essel fogok foglalkozni az
al\'abbiakban. A k\"ovetkez\H{o} eredm\'enyt fogom bizony\'{\i}tani.

\medskip\noindent
{\bf T\'etel f\"uggetlen, v\'eges vagy megsz\'aml\'alhat\'oan
v\'egtelen sok \'ert\'eket felvev\H{o} val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'okb\'ol \'all\'o tipikus sorozatok sz\'am\'ar\'ol.}
{\it Legyen $\xi$ egy \'ert\'ekeit valamely v\'eges vagy
megsz\'aml\'alhat\'oan v\'egtelen sz\'amoss\'ag\'u
$X=\{x_1,x_2,\dots,x_r\}$ halmazon f\"olvev\H{o}
val\-\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'o, amelyre 
$H(\xi)<\infty$, $\xi_1,\dots,\xi_n$ pedig f\"uggetlen, a $\xi$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'oval azonos eloszl\'as\'u
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'ok sorozata. Ekkor
minden $\e>0$ \'es $\delta>0$ sz\'amhoz l\'etezik olyan
$n_0=n_0(\e,\delta)$ k\"usz\"obindex, hogy $n\ge n_0$ eset\'en
l\'etezik olyan
$$
A=A(n)=\{(x^{(k)}_{j_1},\dots,x^{(k)}_{j_n}),\;1\le k\le L\}
$$
$\L$ darab $X$ halmazbeli $n$-hossz\'us\'ag\'u sorozatb\'ol
\'all\'o halmaz, amelyre $P((\xi_1,\dots,\xi_n)\in A)\ge1-\delta$,
\'es az $\A$ halmaz $L$ elemsz\'ama teljes\'{\i}ti az
$L=|A|\le 2^{(1+\e)nH(\xi)}$ egyen\-l\H{o}t\-len\-s\'e\-get.}

\medskip\noindent
{\it A t\'etel bizony\'{\i}t\'asa.}\/ Vezess\"uk be a
$p(k)=P(\xi=x_k)$ jel\"ol\'est, \'es adva f\"uggetlen
a $\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'oval azonos
eloszl\'as\'u, f\"uggetlen val\'osz\'{\i}n\H{u}s\'egi 
v\'altoz\'oknak egy $\xi_1,\dots,\xi_n$ sorozata, jel\"olje 
$\eta_k(n)$ a $\xi_1,\dots,\xi_n$ sorozatban szerepl\H{o} 
$x_k$ elemek sz\'am\'at. Be fogom l\'atni, hogy
$$
-\frac1n\sum_k\log p(k) \cdot |\eta_k(n)-np(k)|\Rightarrow 0,
\quad\text{ha }n\to\infty, \tag A1
$$
ahol $\Rightarrow$ sztochasztikus konvergenci\'at jel\"ol.

El\H{o}sz\"or azt mutatom meg, hogy a (A1) rel\'aci\'ob\'ol
k\"ovetkezik a t\'etel \'all\'{\i}t\'asa.

V\'alasszunk olyan $\e_n\to0$ \'es $\delta_n\to0$ sorozatokat,
amelyekre
$$
P\(-\sum_k\log p(k)\cdot|\eta_k(n)-np(k)|>n\e_n\)\le\delta_n.
\tag A2
$$
Ha az $(A1)$ rel\'aci\'o teljes\"ul, akkor ez megtehet\H{o}. Adva
egy $x=(x_{j_1},\dots,x_{j_n})\in X^n$ sorozat, jel\"olje $s(k,x)$
azon $r$, $1\le r\le n$, indexek sz\'am\'at, amelyekre $x_{j_r}=x_k$.
Defini\'aljuk minden $n=1,2,\dots$ indexre az
$$
A(n)=\left\{x=(x_{j_1},\dots,x_{j_n})\colon\; x\in X^n,\;
-\sum_{k=1}^\infty \log p(k) \cdot |s(k,x)-np(k)|\le n\e_n\right\}
$$
halmazt, ahol $\e_n$ megegyezik az (A2) formul\'aban szerepl\H{o} 
$\e_n$ sz\'ammal. Vegy\"uk \'eszre, hogy az (A2) formula alapj\'an
$P((\xi_1,\dots,\xi_n)\in A(n))\ge1-\delta_n\le 1-\delta$,
ha $n\ge n_0(\delta,\e)$ alkalmas $n_0$ k\"usz\"obindexszel.
Sz\"uks\'eg\"unk van m\'eg egy j\'o fels\H{o} becsl\'esre az 
$A(n)$ halmaz elemsz\'am\'ar\'ol. Ennek \'erdek\'eben 
\'{\i}rjuk fel az  al\'abbi egyenl\H{o}tlens\'eget:
$$
\align
&P((\xi_1,\dots,\xi_n)=(x_{j_1},\dots,x_{j_n}))
=\prod_{k=1}^\infty p_k^{s(k,x)} \\
&\qquad\ge \exp\left\{\frac1{\log 2}
\sum_{k=1}^\infty n p(k)\log p(k)
+\frac1{\log 2}\sum_{k=1}^\infty 
\log p(k)\cdot|s(k,x)-np(k)|\right\}\\
&\qquad\ge 2^{-nH(\xi)}\cdot 2^{-n\e_n}\ge2^{-n(1+\e)H(\xi)},
\endalign
$$
ha $x=(x_{j_1},\dots,x_{j_n})\in A(n)$, \'es $n\ge n_0(\e,\delta)$
alkalmas $n_0$ k\"usz\"obindexszel. Mivel
$P((\xi_1,\dots,\xi_n)\in A(n))\le1$, innen kapjuk, hogy az
$A(n)$ halmaz elemsz\'ama kisebb, mint $2^{n(1+\e)H(\xi)}$. 
Ezzel bel\'attuk, hogy a t\'etel
\'all\'{\i}t\'asa k\"ovetkezik az (A1) rel\'aci\'ob\'ol.

Az (A1) rel\'aci\'o bizony\'{\i}t\'asa \'erdek\'eben minden
r\"ogz\'{\i}tett $\e>0$ \'es $\delta>0$ sz\'amhoz v\'alasszunk
olyan $K=K(\e,\delta)$ sz\'amot, amelyre
$-\summ_{k=K}^\infty p(k)\log p(k)\le \frac{\e\delta}2$.
Ez megtehet\H{o} a $H(\xi)<\infty$ felt\'etel miatt. Vegy\"uk
\'eszre, hogy $E\eta_k(n)=np(k)$, ez\'ert
$$
-\summ_{k=K}^\infty\log p(k) E |\eta_k(n)-np(k)|
\le\summ_{k=K}^\infty 2np(k)\log p(k)\le n\e\delta.
$$ 
Innen a Markov egyenl\H{o}tlens\'eg alapj\'an
$$
P\(-\frac1n\summ_{k=K}^\infty\log p(k)\cdot
|\eta_k(n)-np(k)|\ge\delta\)\le\e.
$$
M\'asr\'eszt tetsz\H{o}leges $k$ indexre $E\eta_k(n)=np(k)$,
$\Var\eta_k(n)=np(k)(1-p(k))$, ahonnan
$E(\frac1n)^2\log^2 p(k) |\eta_k(n)-np(k)|^2
=\frac{p(k)(1-p(k))\log^2 p(k)}n$, \'es ez\'ert
$-\frac1n\log p(k)|\eta_k(n)-np(k)|\Rightarrow0$, ha 
$n\to\infty$. A fenti becsl\'esekb\H{o}l k\"ovetkezik, hogy
$$
\limsup_{n\to\infty}P\(-\frac1n\summ_{k=1}^\infty\log p(k)\cdot
|\eta_k(n)-np(k)|\ge2\delta\)\le\e.
$$
Mivel ez az egyenl\H{o}tlens\'eg minden $\e>0$ \'es $\delta>0$
sz\'amra \'erv\'enyes ez azt jelenti, hogy igaz az (A1) 
rel\'aci\'o is.


\bye



