IT1 (Полный комплект лекций Г.А. Дьячкова)

á.ç. äØÑÞËÏ×ôÅÏÒÉÑ ÉÎÆÏÒÍÁÃÉɧ1.÷×ÅÄÅÎÉÅóÏÄÅÒÖÁÎÉÅ1. ôÅÏÒÅÔÉËÏ-ÉÎÆÏÒÍÁÃÉÏÎÎÁÑ ÂÌÏË-ÓÈÅÍÁ, ÓÏÏÂÝÅÎÉÅ ÉÓÔÏÞÎÉËÁ É ËÏÄÏ×ÙÅ ÓÌÏ×Á, ÌÉÎÅÊÎÏÅ ËÏÄÉÒÏ×ÁÎÉÅ, ÓËÏÒÏÓÔØ ËÏÄÁ.2. ëÁÎÁÌ Ó×ÑÚÉ, ÐÒÑÍÁÑ É ÏÂÒÁÔÎÁÑ ÔÅÏÒÅÍÙ ûÅÎÎÏÎÁ, ÍÅÔÏÄ ÓÌÕÞÁÊÎÏÇÏ ËÏÄÉÒÏ×ÁÎÉÑ.3. íÁÔÅÍÁÔÉÞÅÓËÁÑ ÍÏÄÅÌØ ÚÁÄÁÞÉ ÐÏÉÓËÁ, ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ ÄÌÑ ÍÏÄÅÌÉ ÐÏÉÓËÁ á. òÅÎØÉ.1.1 ðÅÒÅÄÁÞÁ ÉÎÆÏÒÍÁÃÉÉ ÐÏ ËÁÎÁÌÕ Ó×ÑÚÉúÁÄÁÞÉ ÔÅÏÒÉÉ ÉÎÆÏÒÍÁÃÉÉ (ÍÁÔÅÍÁÔÉÞÅÓËÏÊ ÔÅÏÒÉÉ Ó×ÑÚÉ), ÉÚÕÞÁÅÍÙÅ × ÄÁÎÎÏÍ ËÕÒÓÅÌÅËÃÉÊ, ÍÏÖÎÏ ÐÏËÁÚÁÔØ ÎÁ ÐÒÉ×ÏÄÉÍÏÊ ÎÉÖÅ ÂÌÏË-ÓÈÅÍÅ, ËÏÔÏÒÁÑ ÏÐÉÓÙ×ÁÅÔ ÐÅÒÅÄÁÞÕËÏÎÅÞÎÏÊ Ä×ÏÉÞÎÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ (ÉÎÆÏÒÍÁÃÉÏÎÎÏÇÏ ÓÌÏ×Á) ÐÏ Ä×ÏÉÞÎÏÍÕ ËÁÎÁÌÕÓ×ÑÚÉ:Uk1éÓÔÏÞÎÉË =⇒ëÏÄÅÒX1N =E (U1k )=⇒YN1ëÁÎÁÌ =⇒äÅËÏÄÅÒU~1k =D(Y1N )=⇒áÄÒÅÓÁÔ ,Pr{U1k = u} = pk (u); Pr{Y1N = y|X1N = x} = PN (y|x); Pr{U~1k 6= U1k } ≤ ;u = (u1 ; u2 ; : : : ; uk ) ∈ {0; 1}k ; x = (x1 ; x2 ; : : : ; xN ) ∈ {0; 1}N ; y = (y1 ; y2 ; : : : ; yN ) ∈ {0; 1}N :üÔÁ ÂÌÏË-ÓÈÅÍÁ ÏÚÎÁÞÁÅÔ ÓÌÅÄÕÀÝÅÅ.•éÓÔÏÞÎÉË ÇÅÎÅÒÉÒÕÅÔ ÐÒÅÄÎÁÚÎÁÞÅÎÎÕÀ ÄÌÑ ÁÄÒÅÓÁÔÁ Ä×ÏÉÞÎÕÀ (ÉÚ 0 É 1) ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ U1k = (U1 ; U2 ; : : : ; Uk ) ÄÌÉÎÙ k ≥ 1, ËÏÔÏÒÁÑ ÎÁÚÙ×ÁÅÔÓÑ ÓÏÏÂÝÅÎÉÅÍÉÓÔÏÞÎÉËÁ.

îÁ ÑÚÙËÅ ÔÅÏÒÉÉ ×ÅÒÏÑÔÎÏÓÔÅÊ ÓÏÏÂÝÅÎÉÅ ÉÓÔÏÞÎÉËÁ ÉÎÔÅÐÒÅÔÉÒÕÅÔÓÑËÁË ÓÌÕÞÁÊÎÁÑ (Ó ÔÏÞËÉ ÚÒÅÎÉÑ ÁÄÒÅÓÁÔÁ) ×ÅÌÉÞÉÎÁ Ó ÉÚ×ÅÓÔÎÙÍ, ÉÌÉ ÎÅÉÚ×ÅÓÔÎÙÍ,ÒÁÓÐÒÅÄÅÌÅÎÉÅÍ ×ÅÒÏÑÔÎÏÓÔÅÊ pk = pk (u). úÎÁÞÅÎÉÑ u ∈ {0; 1}k , ÄÌÑ ËÏÔÏÒÙÈ ×ÅÒÏÑÔÎÏÓÔÉ pk (u) > 0, ÂÕÄÅÍ ÎÁÚÙ×ÁÔØ ÉÎÆÏÒÍÁÃÉÏÎÎÙÍÉ ÓÌÏ×ÁÍÉ. þÉÓÌÏ ÉÎÆÏÒÍÁÃÉÏÎÎÙÈ ÓÌÏ× ÏÂÏÚÎÁÞÉÍ ÞÅÒÅÚ M .

÷ ÞÁÓÔÎÏÓÔÉ, ÓÏÏÂÝÅÎÉÅ ÉÓÔÏÞÎÉËÁ ÍÏÖÅÔ ÐÒÉÎÉÍÁÔØÒÁ×ÎÏ×ÅÒÏÑÔÎÙÅ ÚÎÁÞÅÎÉÑ ÎÁ ÍÎÏÖÅÓÔ×Å {0; 1}k Ä×ÏÉÞÎÙÈ ÓÌÏ× ÄÌÉÎÙ k, Ô.Å. M = 2kÉ pk (u) = 2−k ÄÌÑ ÌÀÂÏÇÏ u ∈ {0; 1}k . úÁÆÉËÓÉÒÕÅÍ ÎÅËÏÔÏÒÕÀ ÎÕÍÅÒÁÃÉÀ ÉÎÆÏÒÍÁÃÉÏÎÎÙÈ ÓÌÏ× ÃÅÌÙÍÉ ÞÉÓÌÁÍÉ ÏÔ 1 ÄÏ M . ÷ ÄÁÌØÎÅÊÛÅÍ, ÎÅ ÎÁÒÕÛÁÑ ÏÂÝÎÏÓÔÉ, ÍÙÂÕÄÅÍ ÞÁÓÔÏ ÒÁÓÓÍÁÔÒÉ×ÁÔØ ÉÎÆÏÒÍÁÃÉÏÎÎÙÅ ÓÌÏ×Á ËÁË ÜÌÅÍÅÎÔÙ ÍÎÏÖÅÓÔ×Á ÃÅÌÙÈÞÉÓÅÌ ÏÔ 1 ÄÏ M .•äÌÑ ÐÅÒÅÄÁÞÉ ÐÏ ËÁÎÁÌÕ Ó×ÑÚÉ ÉÎÆÏÒÍÁÃÉÏÎÎÏÅ ÓÌÏ×Ï ÐÏÓÔÕÐÁÅÔ ÎÁ ×ÈÏÄ ËÏÄÅÒÁ, ËÏÔÏÒÙÊ ÏÔÏÂÒÁÖÁÅÔ (ËÏÄÉÒÕÅÔ) ÅÇÏ c ÐÏÍÏÝØÀ ÆÕÎËÃÉÉ ËÏÄÉÒÏ×ÁÎÉÑ E × ÐÅÒÅÄÁ×ÁÅÍÏÅÐÏ ËÁÎÁÌÕ Ó×ÑÚÉ Ä×ÏÉÞÎÏÅ ËÏÄÏ×ÏÅ ÓÌÏ×Ïx = E (u); u ∈ {0; 1}k ; x ∈ {0; 1}N ;1ÄÌÉÎÙ N ≥ k.

óÏ×ÏËÕÐÎÏÓÔØ ×ÓÅÈ M ÓÌÏ× ÏÂÒÁÚÕÅÔ ËÏÄ ÄÌÉÎÙ N É ÏÂßÅÍÁ M . ÷ÄÁÌØÎÅÊÛÅÍ ËÏÄX , kxn (m)k; n = 1; 2; : : : ; N; m = 1; 2; : : : ; M;ÂÕÄÅÍ ÚÁÐÉÓÙ×ÁÔØ ËÁË Ä×ÏÉÞÎÕÀ (N × M )-ÍÁÔÒÉÃÕ, ÓÔÏÌÂÅà ËÏÔÏÒÏÊx(m) , (x1 (m); x2 (m); : : : ; xN (m)) ∈ {0; 1}N ; m = 1; 2; : : : ; M;Ñ×ÌÑÅÔÓÑ ËÏÄÏ×ÙÍ ÓÌÏ×ÏÍ ÄÌÑ ÉÎÆÏÒÍÁÃÉÏÎÎÏÇÏ ÓÌÏ×Á Ó ÎÏÍÅÒÏÍ m. ÷ ÜÔÏÍ É ×Ï ×ÓÅÈÓÌÅÄÕÀÝÉÈ ÐÁÒÁÇÒÁÆÁÈ ÓÉÍ×ÏÌ , ÉÓÐÏÌØÚÕÅÔÓÑ ÄÌÑ ÏÂÏÚÎÁÞÅÎÉÑ ÒÁ×ÅÎÓÔ×Á ÐÏ ÏÐÒÅÄÅÌÅÎÉÀ.

ëÏÄÏ×ÙÅ ÓÌÏ×Á ÍÏÖÎÏ ÉÎÔÅÒÐÒÅÔÉÒÏ×ÁÔØ ËÁË ÚÎÁÞÅÎÉÑ ÓÌÕÞÁÊÎÏÊ ×ÅÌÉÞÉÎÙX1N , (X1 ; X2 ; : : : ; XN ) = E (U1k );ÎÁÚÙ×ÁÅÍÏÊ ×ÈÏÄÎÙÍ ÓÉÇÎÁÌÏÍ ÄÌÉÎÙ N ≥ k. þÉÓÌÏ N ÎÁÚÙ×ÁÅÔÓÑ ×ÒÅÍÅÎÅÍ ÒÁÂÏÔÙËÁÎÁÌÁ ÄÌÑ ÐÅÒÅÄÁÞÉ ÓÏÏÂÝÅÎÉÑ ÉÓÔÏÞÎÉËÁ, Á ÞÉÓÌÏ R , logN2 M ÎÁÚÙ×ÁÅÔÓÑ ÓËÏÒÏÓÔØÀËÏÄÉÒÏ×ÁÎÉÑ (ÐÅÒÅÄÁÞÉ) ÓÏÏÂÝÅÎÉÑ ÉÓÔÏÞÎÉËÁ (ÐÏ ËÁÎÁÌÕ Ó×ÑÚÉ). äÌÑ ÓÏÏÂÝÅÎÉÑ ÓÒÁ×ÎÏ×ÅÒÏÑÔÎÙÍÉ ÚÎÁÞÅÎÉÑÍÉ ÓËÏÒÏÓÔØ R , k=N ÏÐÒÅÄÅÌÑÅÔ ÞÉÓÌÏ Ä×ÏÉÞÎÙÈ ÉÎÆÏÒÍÁÃÉÏÎÎÙÈ ÓÉÍ×ÏÌÏ×, ÐÅÒÅÄÁ×ÁÅÍÙÈ ÚÁ ÅÄÉÎÉÃÕ ×ÒÅÍÅÎÉ ÒÁÂÏÔÙ ËÁÎÁÌÁ.

÷ÁÖÎÙÍÞÁÓÔÎÙÍ ÓÌÕÞÁÅÍ ËÏÄÅÒÁ Ñ×ÌÑÅÔÓÑ ÌÉÎÅÊÎÙÊ ËÏÄÅÒ, ÚÁÄÁ×ÁÅÍÙÊ Ä×ÏÉÞÎÏÊ (N × k)ÍÁÔÒÉÃÅÊ G, ÌÉÎÅÊÎÏ ÎÅÚÁ×ÉÓÉÍÙÅ ÓÔÏÌÂÃÙ ËÏÔÏÒÏÊ ÏÂÒÁÚÕÀÔ ÂÁÚÉÓ ÐÏÄÐÒÏÓÔÒÁÎÓÔ×ÁÒÁÚÍÅÒÎÏÓÔÉ ≤ k × ÌÉÎÅÊÎÏÍ ÐÒÏÓÔÒÁÎÓÔ×Å {0; 1}N ÎÁÄ ÐÏÌÅÍ Ä×ÏÉÞÎÙÈ ÞÉÓÅÌ. ðÒÉÜÔÏÍ ÆÕÎËÃÉÑ ËÏÄÉÒÏ×ÁÎÉÑ E ÏÐÒÅÄÅÌÑÅÔÓÑ ËÁË ÏÐÅÒÁÃÉÑ ÐÒÏÉÚ×ÅÄÅÎÉÑ × Ä×ÏÉÞÎÏÍÐÏÌÅ ÍÁÔÒÉÃÙ G ÎÁ ÓÔÏÌÂÅà (ÉÎÆÏÒÍÁÃÉÏÎÎÏÅ ÓÌÏ×Ï) u, Ô.Å.x = E (u)•⇐⇒x,Gu:ëÁÎÁÌ Ó×ÑÚÉ ÏÐÉÓÙ×ÁÅÔÓÑ ÕÓÌÏ×ÎÙÍ ÒÁÓÐÒÅÄÅÌÅÎÉÅÍ, Ô.Å. ÎÁÂÏÒÏÍ ÕÓÌÏ×ÎÙÈ ×ÅÒÏÑÔÎÏÓÔÅÊPN = kPN (y|x)k; x; y ∈ {0; 1}N ;ÇÄÅ PN (y|x) { ÕÓÌÏ×ÎÁÑ ×ÅÒÏÑÔÎÏÓÔØ ÐÏÌÕÞÅÎÉÑ ÎÁ ×ÙÈÏÄÅ ËÁÎÁÌÁ Ä×ÏÉÞÎÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ (×ÙÈÏÄÎÏÇÏ ÓÉÇÎÁÌÁ) Y1N = (Y1 ; Y2 ; : : : ; YN ) = y; ÅÓÌÉ ×ÈÏÄÎÏÊ ÓÉÇÎÁÌX1N = x.

÷ÁÖÎÙÍ ÐÒÉÍÅÒÏÍ ËÁÎÁÌÁ Ó×ÑÚÉ Ñ×ÌÑÅÔÓÑ Ä×ÏÉÞÎÙÊ ÓÉÍÍÅÔÒÉÞÎÙÊ ËÁÎÁÌÂÅÚ ÐÁÍÑÔÉ (äóë), × ËÏÔÏÒÏÍ ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ (ÉÓËÁÖÅÎÉÑ) ÐÒÉ ÐÅÒÅÄÁÞÅ ÏÄÎÏÇÏÄ×ÏÉÞÎÏÇÏ ÓÉÍ×ÏÌÁ (ÐÅÒÅÈÏÄÎÁÑ ×ÅÒÏÑÔÎÏÓÔØ) ÚÁÄÁÅÔÓÑ ÐÁÒÁÍÅÔÒÏÍ p; 0 < p < 1=2, ÉÏÛÉÂËÉ × ÒÁÚÎÙÅ ÍÏÍÅÎÔÙ ×ÒÅÍÅÎÉ ÐÅÒÅÄÁÞÉ ÐÒÏÉÓÈÏÄÑÔ ÎÅÚÁ×ÉÓÉÍÏ, Ô.Å.PN (y|x) ,NYi=1P1 (yi |xi ) = p(x;y) (1 − p)N −(x;y) ;ÇÄÅ P1 (0|1) = P1 (1|0) = p; P1 (0|0) = P1 (1|1) = 1 − p; Á (x; y) { ÞÉÓÌÏ ÎÅÓÏ×ÐÁÄÁÀÝÉÈÐÏÚÉÃÉÊ (ÒÁÓÓÔÏÑÎÉÅ èÜÍÍÉÎÇÁ) × ÓÌÏ×ÁÈ x É y. äÒÕÇÉÍ ÐÒÉÍÅÒÏÍ ËÁÎÁÌÁ Ó×ÑÚÉ, ËÏÔÏÒÙÊ ÍÙ ÂÕÄÅÍ ÉÚÕÞÁÔØ × §2, Ñ×ÌÑÅÔÓÑ ËÁÎÁÌ Ó ÒÁ×ÎÏ×ÅÓÎÙÍ ÛÕÍÏÍ (ëòû). õÓÌÏ×ÎÙÅ×ÅÒÏÑÔÎÏÓÔÉ ÜÔÏÇÏ ËÁÎÁÌÁ ÏÐÒÅÄÅÌÑÀÔÓÑ ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏÍPN (y|x) ,½ ¡ ¢−1Nt0;2; ÅÓÌÉ (x; y) = t,ÅÓÌÉ (x; y) 6= t,ÇÄÅ t; 1 ≤ t ≤ N=2, { ÆÉËÓÉÒÏ×ÁÎÎÙÊ ÃÅÌÏÞÉÓÌÅÎÎÙÊ ÐÁÒÁÍÅÔÒ.

ïÐÒÅÄÅÌÅÎÉÅ ëòûÏÚÎÁÞÁÅÔ, ÞÔÏ ÓÉÇÎÁÌ ÎÁ ×ÙÈÏÄÅ ëòû ÉÍÅÅÔ ÒÁ×ÎÏÍÅÒÎÏÅ ÒÁÓÐÒÅÄÅÌÅÎÉÅ ÎÁ ÓÆÅÒÅèÜÍÍÉÎÇÁ ÒÁÄÉÕÓÁ t, ÃÅÎÔÒ ËÏÔÏÒÏÊ Ñ×ÌÑÅÔÓÑ ×ÈÏÄÎÙÍ ÓÉÇÎÁÌÏÍ ëòû. ðÕÓÔØ dae ÏÂÏÚÎÁÞÁÅÔ ÎÁÉÍÅÎØÛÅÅ ÃÅÌÏÅ ÞÉÓÌÏ ≥ a. ÷ ÄÁÌØÎÅÊÛÅÍ ÂÕÄÅÍ ÚÁÄÁ×ÁÔØ ÐÁÒÁÍÅÔÒ ëòû× ×ÉÄÅ t = dpN e, ÇÄÅ ÐÏ ÁÎÁÌÏÇÉÉ Ó äóë ÆÉËÓÉÒÏ×ÁÎÎÏÅ ÚÎÁÞÅÎÉÅ p; 0 < p < 1=2 ÎÅÍÅÎÑÅÔÓÑ ÐÒÉ ÉÚÍÅÎÅÎÉÉ N . ÷ § 3 ÍÙ ÂÕÄÅÍ ÒÁÓÓÍÁÔÒÉ×ÁÔØ ËÏÍÂÉÎÁÔÏÒÎÕÀ ÍÏÄÅÌØÄ×ÏÉÞÎÏÇÏ ËÁÎÁÌÁ Ó×ÑÚÉ, ËÏÔÏÒÁÑ ÎÁÚÙ×ÁÅÔÓÑ ËÁÎÁÌÏÍ Ó t ÏÛÉÂËÁÍÉ É ÚÁÄÁÅÔÓÑ ÎÅÒÁ×ÅÎÓÔ×ÏÍ (x; y) ≤ t. äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÐÒÉ ÐÅÒÅÄÁÞÅ ÚÁ ×ÒÅÍÑ N ÍÏÖÅÔ ÐÒÏÉÚÏÊÔÉÎÅ ÂÏÌÅÅ t ÏÛÉÂÏË.•÷ÙÈÏÄÎÏÊ ÓÉÇÎÁÌ Y1N ËÁÎÁÌÁ Ó×ÑÚÉ ÐÏÓÔÕÐÁÅÔ ÎÁ ×ÈÏÄ ÄÅËÏÄÅÒÁ, ËÏÔÏÒÙÊ Ó ÐÏÍÏÝØÀÄÅËÏÄÉÒÕÀÝÅÊ ÆÕÎËÃÉÉ Du = D(y); u ∈ {0; 1}k ; y ∈ {0; 1}N ;ÐÒÅÏÂÒÁÚÕÅÔ ÅÇÏ × ÐÒÉÎÑÔÕÀ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ (ÓÏÏÂÝÅÎÉÅ ÁÄÒÅÓÁÔÁ)U~k = (U~1 ; U~2 ; : : : ; U~k ) = D(Y N ):11÷ ËÁÞÅÓÔ×Å ×ÁÖÎÏÇÏ ÐÒÉÍÅÒÁ ÄÅËÏÄÉÒÕÀÝÅÊ ÆÕÎËÃÉÉ ××ÅÄÅÍ ÒÁÓÓÍÁÔÒÉ×ÁÅÍÏÅ × § 2ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÐÏ ÍÁËÓÉÍÕÍÕ ÐÒÁ×ÄÏÐÏÄÏÂÉÑ (íð - ÄÅËÏÄÉÒÏ×ÁÎÉÅ), ËÏÔÏÒÏÅ ÂÕÄÅÍÏÂÏÚÎÁÞÁÔØ ÓÉÍ×ÏÌÏÍ Díð (y).

üÔÏ ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÚÁ×ÉÓÉÔ ÏÔ ÆÕÎËÃÉÉ ËÏÄÉÒÏ×ÁÎÉÑx = E (u) É ÏÐÒÅÄÅÌÑÅÔÓÑ ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏÍ: Díð (y) = u, ÇÄÅ ÉÎÆÏÒÍÁÃÉÏÎÎÏÅÓÌÏ×Ï u ÉÍÅÅÔ ÎÁÉÍÅÎØÛÉÊ ÎÏÍÅÒ ÓÒÅÄÉ ×ÓÅÈ ÉÎÆÏÒÍÁÃÉÏÎÎÙÈ ÓÌÏ× u0 , ÄÌÑ ËÏÔÏÒÙÈÄÏÓÔÉÇÁÅÔÓÑmax P (y|E (u )) = PN (y|E (u)) , PN (y|E (Díð (y))) :u0 =1;2;:::;M N0•ðÁÒÁ ËÏÄÉÒÏ×ÁÎÉÅ{ÄÅËÏÄÉÒÏ×ÁÎÉÅ (E; D) ÎÁÚÙ×ÁÅÔÓÑ ÍÅÔÏÄÏÍ ÐÅÒÅÄÁÞÉ ÓÏÏÂÝÅÎÉÑÉÓÔÏÞÎÉËÁ ÐÏ ËÁÎÁÌÕ PN . ÷ ËÁÞÅÓÔ×Å ËÒÉÔÅÒÉÑ ÍÅÔÏÄÁ ÐÅÒÅÄÁÞÉ (E; D) ÒÁÓÓÍÁÔÒÉ×ÁÅÔÓÑ ×ÅÒÏÑÔÎÏÓÔØ ÎÅÓÏ×ÐÁÄÅÎÉÑ ÓÏÏÂÝÅÎÉÑ ÉÓÔÏÞÎÉËÁ Ó ÓÏÏÂÝÅÎÉÅÍ ÁÄÒÅÓÁÔÁ, Ô.Å.ÞÉÓÌÏQ(pk ; PN ; E; D) , Pr{U~1k 6= U1k };ÎÁÚÙ×ÁÅÍÏÅ ×ÅÒÏÑÔÎÏÓÔØÀ ÏÛÉÂËÉ. ïÔÍÅÔÉÍ ÄÏËÁÚÙ×ÁÅÍÏÅ × §2 ×ÁÖÎÏÅ Ó×ÏÊÓÔ×ÏÏÐÔÉÍÁÌØÎÏÓÔÉ íð-ÄÅËÏÄÉÒÏ×ÁÎÉÑ, ËÏÔÏÒÏÅ ÓÏÓÔÏÉÔ × ÓÌÅÄÕÀÝÅÍ.

åÓÌÉ ÓÏÏÂÝÅÎÉÅÉÓÔÏÞÎÉËÁ ÉÍÅÅÔ ÒÁ×ÎÏÍÅÒÎÏÅ ÒÁÓÐÒÅÄÅÌÅÎÉÅ, ÔÏ ÄÌÑ ÌÀÂÏÊ ÆÕÎËÃÉÉ ËÏÄÉÒÏ×ÁÎÉÑ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ ÍÉÎÉÍÉÚÉÒÕÅÔÓÑ ÐÒÉ íð-ÄÅËÏÄÉÒÏ×ÁÎÉÉ. ðÒÏÂÌÅÍÁ ËÏÄÉÒÏ×ÁÎÉÑ ÄÌÑ ÐÅÒÅÄÁÞÉ ÉÎÆÏÒÍÁÃÉÉ ÐÏ ËÁÎÁÌÕ Ó×ÑÚÉ ÆÏÒÍÕÌÉÒÕÅÔÓÑ ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏÍ.ðÕÓÔØ ÚÁÄÁÎÙ ÒÁÓÐÒÅÄÅÌÅÎÉÅ ×ÅÒÏÑÔÎÏÓÔÅÊ ÓÏÏÂÝÅÎÉÑ ÉÓÔÏÞÎÉËÁ pk , ËÁÎÁÌ Ó×ÑÚÉPN É ÄÏÐÕÓÔÉÍÏÅ ÚÎÁÞÅÎÉÅ ×ÅÒÏÑÔÎÏÓÔÉ ÏÛÉÂËÉ > 0. ôÒÅÂÕÅÔÓÑ ÐÏÓÔÒÏÉÔØ ÍÅÔÏÄ ÐÅÒÅÄÁÞÉ (E; D), ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ ËÏÔÏÒÏÇÏ Q(pk ; PN ; E; D) ≤ .ðÕÓÔØ N → ∞, M , d2NR e Á ÓËÏÒÏÓÔØ ÐÅÒÅÄÁÞÉ R > 0 { ÆÉËÓÉÒÏ×ÁÎÁ. ðÒÉ×ÅÄÅÍ ÐÏÌÕÞÅÎÎÙÅ ë.ûÅÎÎÏÎÏÍ ÎÅÏÂÈÏÄÉÍÙÅ (ÏÂÒÁÔÎÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ) É ÄÏÓÔÁÔÏÞÎÙÅ (ÐÒÑÍÁÑÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ) ÁÓÉÍÐÔÏÔÉÞÅÓËÉÅ ÕÓÌÏ×ÉÑ ÓÕÝÅÓÔ×Ï×ÁÎÉÑ ÍÅÔÏÄÁ ÐÅÒÅÄÁÞÉ Ó ×ÅÒÏÑÔÎÏÓÔØÀ ÏÛÉÂËÉ, ÓÔÒÅÍÑÝÅÊÓÑ Ë ÎÕÌÀ. äÌÑ ÆÉËÓÉÒÏ×ÁÎÎÏÊ ÓËÏÒÏÓÔÉ ÐÅÒÅÄÁÞÉ R É ËÁÎÁÌÁÓ×ÑÚÉ PN ××ÅÄÅÍ ÏÐÔÉÍÁÌØÎÕÀ (ÍÉÎÉÍÁËÓÎÕÀ) ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ:E (PN ; R) ,min max Q(pk ; PN ; E; D):(E;D) pk3ôÅÏÒÅÍÁ ûÅÎÎÏÎÁ.

óÕÝÅÓÔ×ÕÅÔ ÏÐÒÅÄÅÌÑÅÍÏÅ ËÁÎÁÌÏÍ Ó×ÑÚÉ PN ÞÉÓÌÏ C , ÎÁÚÙ×Á-ÅÍÏÅ ÐÒÏÐÕÓËÎÏÊ ÓÐÏÓÏÂÎÏÓÔØÀ ËÁÎÁÌÁ, ÄÌÑ ËÏÔÏÒÏÇÏ ÓÐÒÁ×ÅÄÌÉ×Ù ÓÌÅÄÕÀÝÉÅ Ä×Á ÕÔ×ÅÒÖÄÅÎÉÑ:1. ïÂÒÁÔÎÁÑ ÔÅÏÒÅÍÁ. åÓÌÉ R > C , ÔÏClim E (PN ; R) ≥ 1 − ;RN →∞Ô.Å. ÐÒÉ R > C É N → ∞ ÎÅ ÓÕÝÅÓÔ×ÕÅÔ ÍÅÔÏÄÁ ÐÅÒÅÄÁÞÉ Ó ×ÅÒÏÑÔÎÏÓÔØÀ ÏÛÉÂËÉ,ÓÔÒÅÍÑÝÅÊÓÑ Ë ÎÕÌÀ.2. ðÒÑÍÁÑ ÔÅÏÒÅÍÁ. åÓÌÉ R < C , ÔÏlim E (PN ; R) = 0;N →∞Ô.Å.

ÐÒÉ R < C É NÓÔÒÅÍÑÝÅÊÓÑ Ë ÎÕÌÀ.→∞ÓÕÝÅÓÔ×ÕÅÔ ÍÅÔÏÄ ÐÅÒÅÄÁÞÉ Ó ×ÅÒÏÑÔÎÏÓÔØÀ ÏÛÉÂËÉ,ïÂÒÁÔÎÁÑ ÔÅÏÒÅÍÁ ÂÕÄÅÔ ÄÏËÁÚÁÎÁ × § 4. ÷ ÏÓÎÏ×Å ×Ù×ÏÄÁ ÜÔÏÊ ÔÅÏÒÅÍÙ ÌÅÖÉÔ ÐÒÅÄÌÏÖÅÎÎÏÅ ë.ûÅÎÎÏÎÏÍ ÆÕÎÄÁÍÅÎÔÁÌØÎÏÅ ÐÏÎÑÔÉÅ ÉÎÆÏÒÍÁÃÉÉ ÐÁÒÙ ÓÌÕÞÁÊÎÙÈ ×ÅÌÉÞÉÎ.÷ ÓÌÕÞÁÅ ËÁÎÁÌÁ Ó ÒÁ×ÎÏ×ÅÓÎÙÍ ÛÕÍÏÍ (ëòû) ÐÒÑÍÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ ÐÏÌÕÞÅÎÁ × § 2.äÌÑ ÄÉÓËÒÅÔÎÏÇÏ ËÁÎÁÌÁ ÂÅÚ ÐÁÍÑÔÉ (äëâð), Ñ×ÌÑÀÝÅÇÏÓÑ ÏÂÏÂÝÅÎÉÅÍ äóë ÎÁ ÐÒÏÉÚ×ÏÌØÎÙÅ ËÏÎÅÞÎÙÅ ÁÌÆÁ×ÉÔÙ, ÜÔÁ ÔÅÏÒÅÍÁ ÄÏËÁÚÙ×ÁÅÔÓÑ × § 6. ÷ ÍÅÔÏÄÅ ÄÏËÁÚÁÔÅÌØÓÔ×Á,ËÏÔÏÒÙÊ ÎÁÚÙ×ÁÅÔÓÑ ÍÅÔÏÄÏÍ ÓÌÕÞÁÊÎÏÇÏ ËÏÄÉÒÏ×ÁÎÉÑ, ××ÏÄÉÔÓÑ ÁÎÓÁÍÂÌØ ÆÕÎËÃÉÊ ËÏÄÉÒÏ×ÁÎÉÑ E (ÉÌÉ ËÏÄÏ× X ) Ó ÎÅËÏÔÏÒÙÍ ÚÁÄÁÎÎÙÍ ÎÁ ÎÅÍ ÒÁÓÐÒÅÄÅÌÅÎÉÅÍ ×ÅÒÏÑÔÎÏÓÔÅÊ.îÁÐÒÉÍÅÒ, ÁÎÓÁÍÂÌØ ÌÉÎÅÊÎÙÈ ÆÕÎËÃÉÊ ËÏÄÉÒÏ×ÁÎÉÑ ÐÒÅÄÓÔÁ×ÌÑÅÔ ÓÏÂÏÊ ÍÎÏÖÅÓÔ×Ï, ÓÏÓÔÏÑÝÅÅ ÉÚ 2Nk ÒÁ×ÎÏ×ÅÒÏÑÔÎÙÈ Ä×ÏÉÞÎÙÈ (N × k)-ÍÁÔÒÉà G.

üÔÏ ÏÚÎÁÞÁÅÔ, ÞÔÏ ×ÓÅ NkÜÌÅÍÅÎÔÏ× ÓÌÕÞÁÊÎÏÊ ÍÁÔÒÉÃÙ G Ñ×ÌÑÀÔÓÑ ÎÅÚÁ×ÉÓÉÍÙÍÉ ÏÄÉÎÁËÏ×Ï ÒÁÓÐÒÅÄÅÌÅÎÎÙÍÉ Ä×ÏÉÞÎÙÍÉ ÓÌÕÞÁÊÎÙÍÉ ×ÅÌÉÞÉÎÁÍÉ, ÐÒÉÎÉÍÁÀÝÉÍÉ ÚÎÁÞÅÎÉÑ 0 É 1 Ó ×ÅÒÏÑÔÎÏÓÔÑÍÉ 1=2.ðÕÓÔØ ÎÁ ×ÙÈÏÄÅ ËÁÎÁÌÁ ÉÓÐÏÌØÚÕÅÔÓÑ ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÐÏ ÍÁËÓÉÍÕÍÕ ÐÒÁ×ÄÏÐÏÄÏÂÉÑ. ôÏÇÄÁ ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ ËÏÄÁ, ËÁË ÆÕÎËÃÉÑ ÎÁ ÁÎÓÁÍÂÌÅ, Ñ×ÌÑÅÔÓÑ ÓÌÕÞÁÊÎÏÊ ×ÅÌÉÞÉÎÏÊ.òÁÓÓÍÁÔÒÉ×ÁÅÔÓÑ ÕÓÒÅÄÎÅÎÉÅ (ÍÁÔÅÍÁÔÉÞÅÓËÏÅ ÏÖÉÄÁÎÉÅ) ×ÅÒÏÑÔÎÏÓÔÉ ÏÛÉÂËÉ ÐÏ ÁÎÓÁÍÂÌÀ ËÏÄÏ×, ÄÌÑ ËÏÔÏÒÏÇÏ ÕÄÁÅÔÓÑ ÐÏÓÔÒÏÉÔØ ×ÅÒÈÎÀÀ ÏÃÅÎËÕ, ÓÔÒÅÍÑÝÕÀÓÑ Ë ÎÕÌÀ, ÅÓÌÉÓËÏÒÏÓÔØ ÐÅÒÅÄÁÞÉ R < C . ïÔÓÀÄÁ ÓÌÅÄÕÅÔ ÓÕÝÅÓÔ×Ï×ÁÎÉÅ ÆÕÎËÃÉÉ ËÏÄÉÒÏ×ÁÎÉÑ E (ÉÌÉËÏÄÁ X ), ÄÌÑ ËÏÔÏÒÏÊ ÐÒÉ íð-ÄÅËÏÄÉÒÏ×ÁÎÉÉ ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ ÓÔÒÅÍÉÔÓÑ Ë ÎÕÌÀ ÐÒÉR < C .

äÌÑ ÐÒÉÍÅÒÏ× äóë É ëòû, ÚÁÄÁ×ÁÅÍÙÈ ÐÁÒÁÍÅÔÒÏÍ p; 0 < p < 1=2, ÐÒÏÐÕÓËÎÁÑÓÐÏÓÏÂÎÏÓÔØ C ×ÙÞÉÓÌÑÅÔÓÑ (ÓÍ. §4) ÐÏ ÆÏÒÍÕÌÅC = 1 − h(p); h(p) , −p log2 p − (1 − p) log2 (1 − p):æÕÎËÃÉÑ h(p) ÎÁÚÙ×ÁÅÔÓÑ Ä×ÏÉÞÎÏÊ ÜÎÔÒÏÐÉÅÊ.1.2 íÁÔÅÍÁÔÉÞÅÓËÁÑ ÍÏÄÅÌØ ÚÁÄÁÞÉ ÐÏÉÓËÁòÁÓÓÍÏÔÒÉÍ ÓÌÅÄÕÀÝÕÀ ÍÁÔÅÍÁÔÉÞÅÓËÕÀ ÍÏÄÅÌØ ÌÏÇÉÞÅÓËÏÊ ÚÁÄÁÞÉ, ÎÁÚÙ×ÁÅÍÏÊ ÐÏÉÓËÏÍ . ðÕÓÔØ ÄÁÎÏ ËÏÎÅÞÎÏÅ ÍÎÏÖÅÓÔ×ÏA = {a1 ; a2 ; : : : ; aM };4ÓÏÓÔÏÑÝÅÅ ÉÚ M ÜÌÅÍÅÎÔÏ× (ÆÁËÔÏÒÏ× ), Ó ÎÅËÏÔÏÒÙÍ ÆÉËÓÉÒÏ×ÁÎÎÙÍ, ÎÏ ÎÅÉÚ×ÅÓÔÎÙÍÐÏÄÍÎÏÖÅÓÔ×ÏÍ S = {ai1 ; ai2 ; : : : ; aim }; 1 ≤ i1 < i2 < : : : < im ≤ M , ËÏÔÏÒÏÅ ÎÁÄÏ ÎÁÊÔÉ .üÌÅÍÅÎÔÙ ÐÏÄÍÎÏÖÅÓÔ×Á S ÎÁÚÙ×ÁÀÔÓÑ ÄÅÆÅËÔÎÙÍÉ ÜÌÅÍÅÎÔÁÍÉ (ÉÌÉ ÚÎÁÞÉÍÙÍÉ ÆÁËÔÏÒÁÍÉ). ïÂÙÞÎÏ ÐÒÅÄÐÏÌÁÇÁÅÔÓÑ, ÞÔÏ ÎÅÉÚ×ÅÓÔÎÏÅ ÐÏÄÍÎÏÖÅÓÔ×Ï ÚÎÁÞÉÍÙÈ ÆÁËÔÏÒÏ×ÐÒÉÎÁÄÌÅÖÉÔ ÎÅËÏÔÏÒÏÍÕ ÉÚ×ÅÓÔÎÏÍÕ ËÌÁÓÓÕ ÄÏÐÕÓÔÉÍÙÈ ÐÏÄÍÎÏÖÅÓÔ×.äÌÑ ÐÏÉÓËÁ S ⊆ A ÒÁÚÒÅÛÁÅÔÓÑ ÐÒÏ×ÅÓÔÉ ÓÅÒÉÀ ÉÚ N ÜËÓÐÅÒÉÍÅÎÔÏ× (ÇÒÕÐÐÏ×ÙÈ ÐÒÏ×ÅÒÏË ), × ËÁÖÄÏÍ ÉÚ ËÏÔÏÒÙÈ ÍÏÖÎÏ ×ÙÂÒÁÔØ ÎÅËÏÔÏÒÏÅ ÐÏÄÍÎÏÖÅÓÔ×Ï (ÇÒÕÐÐÕ) T ⊆ A É×ÙÑÓÎÉÔØ: ÓÏÄÅÒÖÉÔ ÉÌÉ ÎÅÔ ÔÅÓÔÉÒÕÅÍÁÑ ÇÒÕÐÐÁ T ÈÏÔÑ ÂÙ ÏÄÉÎ ÄÅÆÅËÔÎÙÊ ÜÌÅÍÅÎÔ.ïÂÏÚÎÁÞÁÑ ÓÉÍ×ÏÌÏÍ ∅ ÐÕÓÔÏÅ ÍÎÏÖÅÓÔ×Ï, ÍÏÖÎÏ ÎÁÐÉÓÁÔØ, ÞÔÏ Ä×ÏÉÞÎÙÊ ÒÅÚÕÌØÔÁÔ ÐÒÏ×ÅÒËÉ y ∈ {0; 1} ×ÙÞÉÓÌÑÅÔÓÑ ÐÏ ÓÌÅÄÕÀÝÅÍÕ ÐÒÁ×ÉÌÕ:½y=T1; ÅÓÌÉ S T T 6= ∅;0; ÅÓÌÉ S T = ∅:äÁÎÎÕÀ ÍÏÄÅÌØ ×ÙÞÉÓÌÅÎÉÑ ÒÅÚÕÌØÔÁÔÁ ÐÒÏ×ÅÒËÉ ÐÒÉ ÇÒÕÐÐÏ×ÏÍ ÔÅÓÔÉÒÏ×ÁÎÉÉ ÅÓÔÅÓÔ×ÅÎÎÏ ÎÁÚ×ÁÔØ ÂÕÌÅ×ÏÊ ÍÏÄÅÌØÀ.

îÁ ×ÙÂÏÒ ÐÏÄÍÎÏÖÅÓÔ×Á Tn ; n = 1; N; ËÏÔÏÒÏÅ ÐÒÏ×ÅÒÑÅÔÓÑ × n-ÏÍ ÜËÓÐÅÒÉÍÅÎÔÅ, ×ÏÚÍÏÖÎÙ ÎÅËÏÔÏÒÙÅ ÏÇÒÁÎÉÞÅÎÉÑ. üÔÏÔ ×ÙÂÏÒ ÍÏÖÅÔ ÚÁ×ÉÓÅÔØ ÔÁËÖÅ ÏÔ ÒÅÚÕÌØÔÁÔÏ× y1 ; y2 ; : : : ; yn−1 ÐÒÅÄÙÄÕÝÉÈ ÇÒÕÐÐÏ×ÙÈ ÐÒÏ×ÅÒÏË. îÁ ÏÓÎÏ×ÁÎÉÉÉÔÏÇÁ ÐÒÏ×ÅÒÏË y = (y1 ; y2 ; : : : ; yN ); ÇÄŽyn ,T1; ÅÓÌÉ S T Tn 6= ∅;0; ÅÓÌÉ S Tn = ∅;ÜËÓÐÅÒÉÍÅÎÔÁÔÏÒ ÄÏÌÖÅÎ ÏÄÎÏÚÎÁÞÎÏ ×ÏÓÓÔÁÎÏ×ÉÔØ (ÎÁÊÔÉ) ÎÅÉÚ×ÅÓÔÎÏÅ ÐÏÄÍÎÏÖÅÓÔ×ÏÚÎÁÞÉÍÙÈ ÆÁËÔÏÒÏ× S .ðÒÉÍÅÒÁÍÉ ÒÅÁÌØÎÙÈ ÐÒÏÃÅÄÕÒ ÐÏÉÓËÁ, Ó×ÏÄÑÝÉÈÓÑ Ë ÏÐÉÓÁÎÎÏÊ ÍÏÄÅÌÉ, Ñ×ÌÑÅÔÓÑ ÐÏÉÓËÄÅÆÅËÔÎÙÈ ÐÒÉÂÏÒÏ×, ÐÏÉÓË ÜÆÆÅËÔÉ×ÎÙÈ ÌÅËÁÒÓÔ× (ÑÄÏ×), ÐÏÉÓË ÏÛÉÂÏË × ÐÒÏÇÒÁÍÍÅ ÄÌÑü÷í, ÐÏÉÓË ÎÕÖÎÙÈ ËÁÒÔÏÞÅË × ËÁÔÁÌÏÇÅ ÂÉÂÌÉÏÔÅËÉ, ÒÁÄÉÏÌÏËÁÃÉÏÎÎÙÊ ÐÏÉÓË É Ô.Ð.÷ÓÅ ÓÔÒÁÔÅÇÉÉ (ÐÌÁÎÙ ) ÐÏÉÓËÁ ÅÓÔÅÓÔ×ÅÎÎÏ ËÌÁÓÓÉÆÉÃÉÒÏ×ÁÔØ ÎÁ ÓÔÁÔÉÞÅÓËÉÅ, Ô.Å.ÔÁËÉÅ ÓÔÒÁÔÅÇÉÉ, ÄÌÑ ËÏÔÏÒÙÈ ×ÙÂÏÒ n-ÏÊ ÐÒÏ×ÅÒËÉ Tn ; n = 1; 2; : : : ; N; ÎÅ ÚÁ×ÉÓÉÔ ÏÔÒÅÚÕÌØÔÁÔÏ× y1 ; y2 ; : : : ; yn−1 ÐÒÅÄÙÄÕÝÉÈ n − 1 ÐÒÏ×ÅÒÏË, É ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÙÅ, ËÏÇÄÁ ÔÁËÁÑ ÚÁ×ÉÓÉÍÏÓÔØ ÄÏÐÕÓËÁÅÔÓÑ.