Кіріспе
Ақпарат теориясында типтік жиын – бұл олардың бастапқы таралуының энтропиясының теріс дәрежесіне көтерілген екіге жуық ықтималдығы бар тізбектер жиыны. Осы жиынның жалпы ықтималдығы бірге жуық, бұл үлкен сандар заңының бір түрі болып табылатын асимптотикалық тең бөлу қасиетінің (AEP) салдары. Типикалық ұғым тізбектің ықтималдығымен ғана айналысады, ал нақты тізбектің өзімен емес. Бұл сығымдалу теориясында маңызды рөл атқарады, себебі ол деректерді сығымдаудың теориялық мүмкіндігін ұсынады, арқасында кез келген Xn тізбесін орташа есеппен nH(X) биттермен бейнелеуге болады, соның нәтижесінде энтропияны дереккөзден алынған ақпаратты өлшеу құралы ретінде қолдануға негіз болады. AEP стационарлық эргодикалық процестердің кең класы үшін де дәлелденуі мүмкін, бұл типтік жиынды жалпы жағдайларда анықтауға мүмкіндік береді.
Мысал
Интуитивті түрде, ең ықтимал тізбек әдеттегі жиынның мүшесі емес. Мысалы, X – i.i.d. Бернулли кездейсоқ айнымалысы, мұнда p(0) = 0,1 және p(1) = 0,9 деп есептейік. n тәуелсіз сынақта, p(1) > p(0) болғандықтан, нәтижелердің ең ықтимал тізбегі барлық 1-дерден тұрады, яғни (1, 1, ..., 1). Мұнда X-тің энтропиясы H(X) = 0,469-қа тең, ал бұл тізбек типтік жиынға кірмейді, себебі оның орташа логарифмдік ықтималдығы n-нің мәніне қарамастан, кездейсоқ айнымалы X-тің энтропиясына жетіңкіреп жақындамайды. Бернулли кездейсоқ айнымалылары үшін типтік жиын n тәуелсіз сынақтағы 0-дер мен 1-дердің орташа саны бар тізбектерден тұрады. Мұны оңай көрсетуге болады: егер p(1) = p және p(0) = 1 – p болса, онда m 1-дік n сынақ үшін, Бернулли сынақтарының тізбегіндегі 1-дердің орташа саны m = np тең. Осылайша, бізде бар. Бұл мысалда, егер n = 10 болса, онда типтік жиынға барлық тізбектер кіреді, олардың барлығында бір ғана 0 бар. Егер p(0) = p(1) = 0,5 болса, онда барлық мүмкін бинарлық тізбектер типтік жиынға жатады.
So this sequence is not in the typical set because its average logarithmic probability cannot come arbitrarily close to the entropy of the random variable X no matter how large we take the value of n.
For Bernoulli random variables, the typical set consists of sequences with average numbers of 0s and 1s in n independent trials. This is easily demonstrated: If p(1) = p and p(0) = 1 p, then for n trials with m 1's, we have
The average number of 1's in a sequence of Bernoulli trials is m = np. Thus, we have
For this example, if n=10, then the typical set consist of all sequences that have a single 0 in the entire sequence. In case p(0)=p(1)=0.5, then every possible binary sequences belong to the typical set.
Өте типтік реті (өте типтік, әріптік типтік)
Егер x1, ..., xn тізбегі шекті немесе шексіз әліпбиде анықталған белгілі бір бірлескен үлестіруден алынса, онда күшті типтік жиын, Aε,strong(n) – тізбектегі белгілі бір символдың кездесу саны бойынша қанағаттандырылатын тізбектер жиынтығы ретінде анықталады. Күшті типтік тізбектердің әлсіз типтік екендігі (әртүрлі ε тұрақтысымен) көрсетіледі, сондықтан осылай аталады. Алайда, бұл екі форма эквивалентті емес. Жадысы жоқ каналдар үшін теоремаларды дәлелдеуде күшті типтікпен жұмыс істеу ыңғайлырақ. Дегенмен, анықтамадан көрініп тұрғанындай, типтікліктің бұл түрі тек шекті қолдауы бар кездейсоқ шамалар үшін ғана анықталады.
where is the number of occurrences of a specific symbol in the sequence. It can be shown that strongly typical sequences are also weakly typical (with a different constant ε), and hence the name. The two forms, however, are not equivalent. Strong typicality is often easier to work with in proving theorems for memoryless channels. However, as is apparent from the definition, this form of typicality is only defined for random variables having finite support.
Бірлескен типтік реті
Екі тізбек және бірлесіп ε типті болып есептеледі, егер жұп бірлескен үлестірімге қатысты ε типті болса, сондай-ақ екеуі де және олардың шекті үлестірімдеріне қатысты ε типті болса. Мұндай жұптардың жиыны бірлесіп ε типті n-тік тізбектермен белгіленеді. және екі тәуелсіз кездейсоқ шама тізбегі бірдей шекті үлестірімдермен болсын. Онда кез келген ε>0 үшін, n жеткілікті үлкен болғанда, бірлесіп типтік тізбектер келесі қасиеттерге ие болады:
Үлгілік жиынтық кодтамасы
Ақпарат теориясында типтік жиынтық декодтау, жіберілген хабарды бақылаумен бірлесіп ε-типтік болатын кодты сөзді қамтитын хабар ретінде бағалау үшін кездейсоқ кодтаумен бірге қолданылады. Яғни,
мұнда – хабардың бағасы, – хабардың кодты сөзі және – бақылау болып табылады. ε-типтілік, арна статистикасын сипаттайтын ауысу ықтималдығы және кездейсоқ код кітапшасындағы код сөздерін жасау үшін қолданылатын кіріс үлестірімі ескере отырып анықталады.