Кіріспе
Кездейсоқ айнымалыларға қолданылатын теңсіздік. Ақпарат теориясында Фано теңсіздігі (Фаноның кері теоремасы және Фано леммасы деп те аталады) шулы каналдағы жоғалған орташа ақпаратты жіктеу қатесінің ықтималдығымен байланыстырады. Оны Роберт Фано 1950 жылдардың басында МТИ-де ақпарат теориясы бойынша докторлық семинар өткізіп жатқанда шығарған, ал кейіннен 1961 жылғы оқулығында жазды. Ол кез келген декодердің қателік ықтималдығының төменгі шегін, сондай-ақ тығыздық бағалаудағы минимакстік тәуекелдердің төменгі шегін табу үшін қолданылады. Кездейсоқ айнымалылар кіріс және шығыс хабарламаларын біртұтас ықтималдықпен белгілейді. Егер қате орын алса, онда , мұндағы – нұсқасы болып табылады. Бұл жерде – шартты энтропия, – байланыс қатесінің ықтималдығы, ал – тиісті екілік энтропияны білдіреді.
In information theory, Fano's inequality (also known as the Fano converse and the Fano lemma) relates the average information lost in a noisy channel to the probability of the categorization error. It was derived by Robert Fano in the early 1950s while teaching a Ph. D. seminar in information theory at MIT, and later recorded in his 1961 textbook. It is used to find a lower bound on the error probability of any decoder as well as the lower bounds for minimax risks in density estimation. Let the random variables and represent input and output messages with a joint probability Let represent an occurrence of error; i. e., that , with being an approximate version of Fano's inequality is
where denotes the support of ,
is the conditional entropy,
is the probability of the communication error, and
is the corresponding binary entropy.
Интуиция
Фано теңсіздігін кез келген болжамды пайдалана отырып, шартты үлестірудің белгісіздігін екі сұраққа бөлу жолы ретінде қарастыруға болады. Бірінші сұрақ, терминіне сәйкес келетін, болжаушының белгісіздігіне қатысты. Егер болжам дұрыс болса, қалған белгісіздік болмайды. Егер болжам қате болса, кез келген дискретті үлестірудің белгісіздігі, қате болжамнан басқа барлық мүмкіндіктер бойынша біркелкі үлестірудің энтропиясымен шектеледі. Бұл энтропияға тең. Екстремалды жағдайларды қарастыратын болсақ, егер болжаушы әрқашан дұрыс болса, теңсіздіктің бірінші және екінші мүшелері 0-ге тең болады, ал толыққанды болжаушының болуы оны толығымен анықтайды, яғни . Егер болжаушы әрқашан қате болса, онда бірінші мүше 0-ге тең болады, ал белгісіздік тек қалған мүмкіндіктер бойынша біркелкі үлестірумен шектеледі.