5.2. Кодтау көзі №2 теоремасы
Енді біз ақпарат теориясын толықтырамыз тағы бір теоремамен. Блоктағы жағдай көздерін және оның ұзындығын біріктірсек L ді және блокті кодтаймыз, орташа кодтық сөздің ұзындығы жағдайға энтропия көзін (x) егер L→∞ жақын болса. Жады көзі түгелдей саналады.
Теорема 5.2.1. Кодтау теоремасы дискретті стационарлы (X) көзі болып саналады.
Блок
ұзындығы үшін L ға D префикстік коды
бар, о да орташа кодтық сөздің ұзындығы
бір жағдайда
теңсіздігін қанағаттандырады.
(5.14)Теорема ерекше дәлелдеуді қажет етпейді. Егер біз L ұзындығының блогін қарастырсақ жаңа энтропиясына тәуелсіз, L* (X) және кодтық көздермен № 1 қолданады.Енді біз
Барлық теңсіздіктің L мүшесіне бөлсек ,біз кодтық сөздің ұзындығының жартысые мына жағдайда аламыз
Егер L→∞, (x) → (x)=H(x) сонда біз аламыз
Енді біз
Осыған орай,кел келген саз үшін кіші S ыңғайлы кодтау тәсілі блогінің, мазмұны L>1/S жағдайына сәйкес,кодтық сөздің теңсіздігі орташа ұзындықпен орындалады. Кодтау теоремасының көзі 2 көрсеткендей, L блок ұзындығын ұзартамыз, біз қалайда жақын энтропияны ыңғайландырамыз H(x)= (x).Бірақ тәжірбиеде кейбір шектеулер бар. Ол үшін L блогінің жағдайы декодтталған болуы мүмкін, ол толықтай қабылдануы керек, рұқсат етілмейтін кездер задержкада декоттау және буфер жадысының көлеміне рұқсат етілмейді.
5.3 Марковтың соңғы шынжыры
Осы және алдыңғы параграфтарда көрсетілгендей ерекше форма ондық көздер үшін қарастырылады, ол марковтік көздер.Оның баяндалуы марков шынжырымен байланысты, олар әр түрлі салаларда қолданылады.Марков шынжырының негізі дыбысты анықтауда, телефонның коммутатор каналдарында қолданады.Марков шынжыры желі қатынас зерттеу орталықтарында,және транспорттық потоктарда кеңінен қоладнылады. Марков шынжырының мағынасы тек математикалық мәнісімен анықталмайды,математикалық модел арқылы көптеген процесстерде ,тәжірбиелерде көмегін тигізеді.
5.3.1. Марков шынжырының дискретті уақыты
Бұл бөлімде соңғы Марковтың шынжыр түсінігі баяндалады.”Кездейсоқ қателер” қарапайым мысалда түсіндіреміз.
Мысалы: Студенттің кездейсоқ қателері
Бізді мына сұрақ қызықтырады , сыраханадан жатақханаға дейін алқаш студент бара ала ма. Басқаша сұрақты қарасытырайық кездейсок қателік 7 қадаммен студенті кеңістік жағдайына S1 ? немесе
P(кездейсоқ қателік S1 жағдайына n=7 уақыт мезетінде жетеді)
Ситуация, 5.2 суретте маңызды Марков шынжырының куәлігі бар.Марковтық шынжыр дискретті уақыты және марков процессінің жағдайына байланысты S(n).
Негізіг пункті сипаттау үшін марков шынжыры көптеген жағдайда болады.
N натуралді және стохастикалық векторы арқылы жіктеледі, n уақытында болу ықтималдығы бар.
Түгелдей Марков шынжырын анықтау үшін бізге ықтималдықпен есептеу әдісі рn(i) кез келген мезет уақытына n. Ықтималдықты анықтау үшін бізде мыналар бар
Маңызды саналатын нәрсе бастапқы кезеңдегі ықтималдықты анықтайтын шарттың болуы.
Жағдайдың ауысыуы өту ықтималдығында көрсетіледі.
Бұл өту ықтималдықтар келесідей қасиеттері бар:
Жағдайлардың бірінде n әрқашан кез келген
моментінде
бола алады.
Шекаралап жіктеу j жағдайында
момент ұзындығында бола алады.
Рекурсивті формула өту ықтималдығы үшін.(Жеке Колмогорова-Чэнмена жағдайы үшін)
Колмограф дискретті теңсіздігі-Цепочка ережесі бойынша Чэпмен ақпарат транформациясы ықтималдығы арқылы анықталады.
Теңдіктің екі жағында көбейтеміз 1/p(x1), сонда біз мынаны аламыз
X2 қосындысын алып , Колмограф-Чэпмен теңдік формасына өтемізовппвпав
(5.26 )ны (5.30) суреттегідей келтірген соң, мынау болжанады
Соңғы теңдік марков процессін көрсетеді.
Анықтама 5.3.1. Марков процессі –бұрынғы жағдай болашаққа әсер етпейді, егер қазіргі шақ белгілі болса деп анықталады.
Ескерту.Көрсетілген
мысалда бұрынғы шақ схотастикалық
айнымалы
ретінде белгілі, анықталып тұрған
қазіргі шақ -
ретінде белгілі.
Марков шынжырын қолданғанда қатты қысқартамыз,сонда олар гомоногенді, стационарлы, және жиілікті болып келеді. Осы үш түсінікті қарасытрайық.
Анықтама 5.3.2. Марковскийдің гомоногенді шынжыры – есептеу уақыты мен өту айнымалының жағдайына тәуелді емес.
Осылай, біз l айнымалының ықтималдығы тек есептеу уақытына тәуелді екенін білеміз.
Бұл жағдайда l=n2-n1 және m=n3-n2 Колмограф Чэпмен теңдігі (5.26) мына түрде жазуға болады.
Бұл теңдік векторлы жол мен векторлы баған ретінде компонент бойынша қосындысы ретінде көрсетіледі.Ықтималдық матрицасын жазып алып, біз (5.33) теңдікті матрицаның формасы ретінде көреміз
Бұл процессті бірінші қадамнан өтпелі ықтималдық матрицаның көмегімен бастауға болады
Байқасаңыз II стохастикалық матрицасының қосындысы 1 ықтималдық жолына тең.
Көптеген,
матрицалық түрлендірулерді шығындыға
жатқызсақ,
жағдайына өзгереді, біз бұдан
ықтималдығын ала аламыз, кез келген
уақытта n
Теорема 5.3.1. Гомоногенді Марковскийдің шынжыры түгелдей өтпелі матрица ықтималдығын баяндайды, және шығын жағдайын бөледі.
Жоғарыда
көрсетілген
түсініктерді(
5.3 сурет)
граф
жағдайымен
толықтыруға
болады.
Мұнда
бізде
әрбір
ілмек
жағдайға
байланысты,
ал
жолдар
жағдай
арасына
сәйкес
орналасқан.
Әрбір
бағдардардың
салмағы
болады,ол
өту
ықтималдығына
тең.
Осылай
біз
граф
жағдайыннан
толық
өту
ықтималдығына
байланысты
матрицалық
ақпартты
ала
алмыз.
Мысалы:Кездейсоқ адасатын студент(жалғасы).
Кездесоқ адасатынстуденттің ықтималдығы граф түрінде 5.4 суретте көрсетілген.
Граф жағдайы матирицаның өту ықтималдығына сәйкес келеді.
5.2 суретте шығын болып бөлінген жағдайы анықталып тұр.
Студенттік
адасуы 7 уақытша қадамының нәтижиесінде
жатақхананың есігінің алдында болуы,
бірінші вомпоненті вектрдың жағдайына
байланысты болу ықтималыдығы бар
.
Компьютер бойынша есептеулер
Бұдан
Ықтималдығы тең мынаған
Маңызды саналатын бөлігі марковскскийдің шындыры болып табылады, егер бақылау уақыты бөлу жағдайына байланысты болмаса.
Анықтама 5.3.3 Гомогенді Марков шынжыры стационарлы, егер бөлу жағдайы уақытпен болса.Бұл жағдайда бастапқы бөлу жеке векторлы матрица өтпелі ықтималдығына тең болады.
Ескерту. Егер вектор жағдайының бөлінуі стохастикалық вектор суммасымен тең 1ге болса, онда сумма компоненті жеке векторы да тең 1.
Марковскийдің шынжыры стационарлы болуы үшін (5.43) ол орындалып отыруы керек.Мейлі ро=(p1,P2,Рз,Р4), болсын онда
(5.43) пен (5.45) шарттардың қолана отырып, біз стационарлы бөлу жағдайын табамыз
Рекурстивті қатынастан (5.36) келесі маңызды сұрақтар пацда болады.Ұзақ уақыт өткенен кейін не болады? n→∞ Стационарлы бөліну жағдайы қалай орнығады? Стационарлы бөлінуде басқа құбылыс пайда болмай ма мысалы, мықты екі бөліну жағдайы?
Шектік матрицасы
Және
де N жолында шектік матрица шектік
бөлінуді
көрсетеді
;
Шектік бөліну -жалғыз стационарлы бөліну ықтималдығы Марков шынжырының кез келген жағдайына жиілікті.
Марковскийдің
шынжыры әрқашан жиілікті, егер кейбір
натурал
пайда болса, сонымен қатар кейбір
компоненттер баған матрицасына
нөлден бөлек болу керек
Соңғы түсініктер 5.3.4. анықтамасына сәйкес ,келесі Марковскийдің шынжыры жиілікті болып келеді, егер кейбір қадамдарда n болса кем дегенде бір жағдай орын алады, ол кез келген тіпті бастапқы жағдайға ұмтылады.
Мысалы: Кездейсоқ адасу (жалғасы)
Кездейсоқ студенттің адасуын анықтайық, Марковкскицдің шынжыры боцынша есеп шешімін таба ма екен
Өтпелі ықтималдық матрицасы (5.37) екі соңғы жағдайға байланысты, содан олар уақытша n тақ және жұп сандары белгілі
Сондықтан, бұл жағдайда Марков шынжыры жиілікті емес.
Басқа жағынан қарасақ, 5.3.4 анықтамадан соңғы шарттар орындалмайды, өйткені кел келген уақытта әрбір қадамда жұпқа немес таққа айналады.
Ескерту.
Егер
біз бастапқы бөлуді таңдасақ, мысалы
(5.46) тен онда кез келген уақыт қадамында
жағдай жетістікке жетеді немесе нәтижие
береді.
Мысалы: Марковскийдің шынжырын үш жағдайда қарастырайық
5.5. суретте үш жағдай көрсетілген
1.Өтпелі ықтималдық матрицасын салыңыз
2. Марковскийдің шынжыры стационарлы екенін көрсетіңіз.Бастапқы бөлінген жағдайын ескеріңіз.
3.Марковскийдің шынжыры жиілікті екенін көрсетіңіз
4.Өтпелі шегерімді матрицаны салыңыз
Шешімі.
1.Өтпелі ықтималдық матрицасы
2.Стационарлық.
Бастапқы бөліну жағдайы тең болса
Бірақ 5.4 шарт орындалады
3.Марковскийдің шынжыры жиі өйткені
үшін
соңғы шарт анықтама бойынша анықталады
5.3.4;
4.Шегерімді өтпелі матрица
Марковскийдің
шынжыры жиі болғандықтан 5.3.4, анықтаманы
қолданамыз ,
5.51 суретте бар