Оценки скорости сходимости в предельных теоремах для совместных распределений части характеристик случайных двоичных отображений | ПДМ. 2012. № 4(18).

Оценки скорости сходимости в предельных теоремах для совместных распределений части характеристик случайных двоичных отображений

Исследуется предельное распределение векторов, состоящих из части спектральных и автокорреляционных коэффициентов и весов подфункций линейных комбинаций координатных функций случайной двоичной вектор-функции. Получены теоремы об асимптотической нормальности этих векторов с оценкой скорости сходимости. Получены сравнения, которым должны удовлетворять координаты этих векторов.

Speeds of convergence in limit theorems for joint distributions of some random binary mappings characteristics.pdf Введение Согласно [1], в устойчивости современных блочных и поточных шифрсистем к различным методам анализа значительную роль играют свойства используемых в них двоичных вектор-функций или S-Ьох'ов. В работе [2] доказано, что многие важные свойства двоичного отображения f, такие, как максимальная нелинейность, корреляционная иммунность, устойчивость, сводятся к обладанию этими свойствами всеми ненулевыми линейными комбинациями координатных функций f, называемых в [3] компонентными функциями или компонентами. Свойства же компонент могут быть выражены в терминах их коэффициентов Фурье — Уолша — Адамара (спектральных коэффициентов), весов подфункций и автокорреляций. Для произвольных подмножества I = |i1,... , i|/1} множества {1,..., n} и непустого подмножества J = {j^,..., j|j|} множества {1,... , m} через wJ (f) обозначим вес (f^i''"'* подфункции fJ)1'"''1i компоненты fJ = j ф ... ф j| отображения f = (f1,... , fm) G Bm, получаемой, если у аргумента функции fJ значения координат с номерами i1,... , i | i | положить равными единице. Под |I | понимается мощность множества I. В таких же условиях для компоненты fJ можно определить спектральный коэффициент Фурье — Уолша — Адамара F J (f ) = 1 ^ (-1)^J (x)®Xi1 ® ' ' ' ®Xi|j| 2 и автокорреляционный коэффициент (автокорреляционную функцию, автокорреляцию) rJ (f )= (-1)f J(х)ф/J) где в/ Е Vn — двоичный вектор веса |11, в котором единицы стоят на i1,... , i|/ местах, 1 = 0. Многие свойства двоичных отображений зависят от того, чему равен вектор, состоящий из части определённых выше характеристик всех компонент или их части. В частности, двоичное отображение является корреляционно-иммунным порядка k, если вектор (w/ (f) — 2n-|/1-1 : J С {1,... , m}, J = 0,1 С {1,... , n}, 1 ^ |11 ^ k) или вектор (F/ (f) : J С {1,..., m}, J = 0,1 С {1,... , n}, 1 ^ |11 ^ k) состоят из одних нулей [4]. Кроме того, отображение подчиняется строгому лавинному критерию или критерию распространения степени 1, если состоит из нулей вектор (rjj (f): j Е {1,... , m}, i е{1,...,п}) [1]. Изучению подобных векторов в случае одной компоненты или булевой функции посвящены работы [4-6]. Подробный обзор публикаций, в том числе и по этой тематике, содержится в [1]. Пусть функция f выбирается случайно и равновероятно из множества Bm всех m-мерных двоичных функций от n переменных. Это эквивалентно независимому равновероятному выбору её значений f (а) из множества Vm двоичных векторов размерности m для всех а из множества V^. Можно рассматривать значение функции f как вектор длины m, состоящий из значений её координатных двоичных функций от n переменных: f (а) = (f1 (а), f2 (а),...,fm (а)) : Vn ^ Vm, где fi (а) : Vn ^ {0,1} для всех i Е {1,... ,m}. Тогда значения fi (а) выбираются независимо и равновероятно из множества {0,1} для всех а из множества Vn и для всех i Е {1,... , m}. В случае случайного выбора f векторы, состоящие из части характеристик компонент отображения, также являются случайными, и возникает вопрос об их распределении, в том числе и предельном. В п. 1 данной работы доказаны отношения сравнимости, которым должны удовлетворять координаты векторов части характеристик. В п. 2 получены результаты о характере и скорости сходимости к нулю нормы вектора части спектральных коэффициентов компонент случайного двоичного отображения, а также показана асимптотическая нормальность этого вектора с оценкой скорости сходимости. В п. 3 и 4 при введении дополнительных условий аналогичные результаты получены для векторов части весов подфункций компонент и автокорреляционных коэффициентов. Везде далее E£ обозначает математическое ожидание случайной величины £. 1. Сравнения для характеристик компонент двоичного отображения Для произвольного или случайного отображения f будем записывать далее F/ (f ) = F/, w/ (f )= w/, r/ (f ) = r/. Формулы связи между спектральными и автокорреляционными коэффициентами широко известны (к примеру, теорема 65 в [7]). В работе [4] доказаны формулы связи весов подфункций и спектральных коэффициентов для любых булевых функций: lci j w FJ = E(-1)W (2"-1 - 2|L| wL), J - 2П-111-1 = 2-!1 | £ (-1)|L|+1 FLJ. LCI IJ LCI, L=I Последнее равенство, опубликованное О. В. Денисовым в начале 2000 г., является аналогом равенства Саркара для коэффициентов Уолша WJ = 2FJ, названного так в [8]. Из него легко выводится отношение сравнимости для спектральных коэффициентов, также представленное в [4]: FJ ^ £ (-1)|I\L|+1FJ (mod 2111). Но это отношение верно для части спектральных коэффициентов, относящихся только к одной компоненте fJ функции f. Докажем следующее Утверждение 1. Для любого непустого подмножества J = {j'1,... , j|j|} множества {1,... , m} и произвольного подмножества I = |i1,... , i|i|} множества {1,... , n} имеет место \ 1'''.'1 fji ' ... ' fji ji • • • jjui ' 4 '''.'i|I| I| £ (-1)|f|+1wf = 2|J|-1 0=SCJ Доказательство. Очевидно, что wJ = £ в (a) fJ (a), где в (a) = ailai2...a* aeVn (при I = 0 считаем, что ^i (a) = 1). Получим £ (-1)|f|+1 wf = £ (-1)|S|+1 £ ei (a) fS (a) = 0=SCJ 0=SCJ a£V„ = £ ei (a) £ (-1)|f|+1 f ф ... ф fe|S|\. Известно, что j ф ... ф fj = £ (-2)|K|-1 ... ffc|K|, следовательно, 0=KCJ £ (-l)| f|+1 (fsi ф...фfe|S|\ = £ (-1) f|+1 £ (-2)K | -1 fki ...fk -A Qr~ 7 V / ГЛ-/-ЯГ- T гл-f-lf^Q v|K|-1 's|S| / = Zj ( 1) ( 2) fki ...fk|K| 0=SCJ v 7 0=SC J 0=KCS = £ ( - 2)|K|-1 fki ...fk|K| £ ( - 1)|f|+1 = 0=KCJ S:KCSC J = £ 2 | K | -1fki ...fk|K|I {K = J} = 2 | J | -fi ...f,J|, 0=KCJ где I {K = J} —индикатор того, что множество K равно множеству J. В итоге получаем £ (-1)|f|+1 wf = £ ei (a) £ (-1)|f|+1 (fsi ф ... ф fs|S|\ 0=SCJ aev„ 0=SCJ v 7 2|J|-1 £ ei (a) fji ...fj j . | " (a) f Л ... f j J| • a€V„ Утверждение доказано. ■ Из последнего равенства легко выводится сравнение для весов подфункций. Следствие 1. В условиях утверждения 1 выполняется сравнение ^ (—1)|S|wf = 0 (mod 2|/|-1). 0=SC/ К отношению же из [4] добавляется новое сравнение для спектральных коэффициентов. Следствие 2. В условиях утверждения 1 выполняются сравнения Е (—1)|L|F/ = 0 (mod 2|Т|), LC/ £ (—1)|l|+|s|fL = 0 (mod 2|/|+|/1-1). 0=SC J, LCi Доказательство. Первое сравнение очевидно. Рассмотрим £ (—1)|S|+1 (wS — 2n-|/|-1) = Е (—1)|S|+42-|/1 ■ E (—1)|L|+1Ff) , 0=SC/ 0=SC/ V LC/ J Y (—1)|S|+1 (wS — 2n-|/1-1) = E (—1)|S|+1wf — 2n-|/|-1 0=SC/ \0=SC/ 1,...,1 1,...,1 i1,...,iiii 2|/1 2n-|/|-|/|. fj1 ' ... ' fj|j|) E (—1)|S|+^2-|/1 ■ E (—1)|L|+1Ff) = 2-|/1 £ Y (—1)|L|+|S|FL 0=SC/ V LC/ J 0=SC/LC/ Следовательно, 2- | 1 | - | /+1 E E (—1)lL |+| S|Ff = Лл ■ ... ■ Ли)1^ 0 = .Sr" T Т гТ V / ii ,... _ 2n-|/1-1 i1,...,i|I| 0=SC/LC/ Теперь докажем два свойства, общих для автокорреляционных коэффициентов всех двоичных отображений. Утверждение 2. Пусть n Е N, n ^ 2, f (x) Е Bm — произвольная функция, 1 С {1,... , n} и J С {1,... , m}, где 1, J = 0. Тогда r/ (f) = 0 (mod 4). Доказательство. Пусть без ограничения общности J = {1}, 1 = {n — |11 + 1, ... , n}. Обозначим 1n Е Vn двоичный вектор веса |11, состоящий из единиц. Получим Г/ (f)= Е (—1)/J(х)ф/J(x®ei) = Y Е f( — 1)/1(а,в)®/1(а,в®Т|1|Л = xev„ «evn_|i| eevji| ^ ' = Y 2 Y f(—^/^о,7)®/^®^7®^^)4 = 2 E E (1 — 2 (1 {f1 (а, 0,7) 0 f1 (а, 1,7 0 em-1) = 1})) = 4|2n-2 — E | E 1{f1 (а, 0, y) 0 f (а, 1,7 0 ё|/М) = 1} V «evn_m y7eV|i|_1 Утверждение доказано. ■ Утверждение 3. Пусть I1,I2 С {1,...,n} и J С {1,...,m}, где I1,I2, J = 0. Тогда rJi - rJ2 = 0 (mod 8). Доказательство. Если I1 = I2, то утверждение очевидно. Без ограничения общности считаем, что J = {1}, I1 = I2. Обозначим eii = a, ei2 = в, a = в. Тогда rJ — rJ = ( — 1)/i(x) |^(—1)/i(x®a) — (—1)/i(x©eA i 2 x€Vr ^ 7 Будем говорить, что y G Vn эквивалентен x G Vn, если y = x ф ^1a ф ^2в для некоторых ^1,^2 G {0,1}. Очевидно, что отношение эквивалентности введено корректно. Разобьём Vn на классы эквивалентности V/= по этому отношению и преобразуем разность rJi (f) - rJ (f): " — ^/i(x®a)e/i(x^/_ -|-,/i(x®a®e)e/i(x®a) — 2(— 1)/i(x®e)®/i(x) — 2(—1)/i(x®a®e)®/i(x®e) (-1) — /i(x®e)\ ((_ n/i(x) x£Vn/ rJi (f) - rJ (f) = £ (2(-1)/i(x®a)®/i(x) + 2(—1)J 2 £ —1)/i(x®a) — (— 1)/i(x®e^ 1)/i(x) + ( —1)/i(x®a®e^ Осталось заметить, что в сумме каждый из двух сомножителей делится на 2. ■ Полученные сравнения позволяют уточнить вопрос о возможных значениях, которые могут принимать координаты векторов, состоящие из части характеристик компонент случайного двоичного отображения. 2. Предельные теоремы для вектора, состоящего из части спектральных коэффициентов компонент случайного двоичного отображения Пусть f — случайная функция из Bm. Рассмотрим вектор S (f )= (fJ (f) : Is С {1,... , n}, 0 = Js С {1,... , m}, s G{1,...,r}) , состоящий из r коэффициентов Фурье — Уолша — Адамара, где r — некоторое натуральное число, не превышающее 2n+m — 2n, и наборы множеств (J1,I1) ,..., (Jr, Ir) попарно различны. Из определения спектральных коэффициентов легко видеть, что этот вектор равен сумме 2n векторов S (f ) = 1 £ X (a) = 1 £ ((-1)/Js(a)®aii®'.'®aiis|: s G {1,... , r}\. 2 aev„ 2 a£V„ v 7 Рассмотрим набор из 2n независимых и одинаково распределённых случайных векторов x (a) = (x1 (a) ,..., xr (a)), a G Vn, координаты которых имеют математическое ожидание Exs (a) = E(—1)/Js(a)®aii®'.'®aiis| =0 для всех s G {1, . . . , r}. Очевидно, что для любых k, s G {1,... , r} ковариация координат равна , , s , ss (a)®aii ®.'.®ai ®/J (a)®aii ®.'.®а; cov(xs (a) ,Xk (a)) = E(-1) i |Is| i |Ik| = I {k = s} . Следовательно, х (а), а Е Vn, —независимые одинаково распределённые в Rr случайные векторы с единичной ковариационной матрицей и нулевым средним. Сумма векторов Е X (а) лежит в множестве Rr, которое является евклидовым «eVn r пространством со скалярным произведением ("X, ") = Е xiyi, где "xX = (x1... xr) Е Rr, i=1 Х" = (у1... yr) Е Rr, и нормой I""|| = л/(", "X). Как легко видеть, ||х (а)|| = //r, следовательно, верно, что E ^||х (а)||в^ = re/2 < то при всех вещественных в Е (0, 2). Таким образом, мы попадаем в условия основной теоремы [9], из которой следует, что верно Утверждение 4. Пусть n Х то, m — произвольное натуральное число, в Е Е (0, 2) — вещественное число. Тогда для любых попарно различных наборов множеств (J1,11), ..., (Jr, 1r), где С {1,... , n}, 0 = Js С {1,... , m} для всех s Е {1,... , r}, r Е N, верно, что норма вектора 2-n/eS (f) сходится к нулю с вероятностью 1. Данное утверждение при в = 1 является формулировкой усиленного закона больших чисел для случайных векторов х (а), а Е Vn. Очевидно, что выполняется и обычный закон больших чисел для случайных векторов, и возникает вопрос о скорости сходимости нормы вектора 2-n/eS (f) к нулю. Для случайных векторов с нулевыми математическими ожиданиями выполняется теорема 1 [10, с. 47], из которой следует Утверждение 5. Пусть n, m — произвольные натуральные числа, в Е (0, 2) — вещественное число. Тогда для любых попарно различных (J1,/1), ..., (Jr, 1r), где С {1,..., n}, 0 = Js С {1,..., m} для всех s Е {1,..., r}, r Е N, для любого е > 0 верно неравенство P {||2-n/eS(f)|| ^ е} ^ 422(e-2)n/e. Докажем теперь теорему о скорости сходимости распределения Pn вектора 21-n/2S (f) к распределению Ф стандартного r-мерного нормального закона. Теорема 1. Пусть n, m — произвольные натуральные числа. Тогда для любых попарно различных (J1,11) ,... , (Jr, 1r), где С {1,..., n}, 0 = Js С {1,... , m} для всех s Е {1,... , r}, r Е N, и для любого выпуклого борелевского множества B справедливо неравенство |Pn (B) — Ф (B)| ^ 400r7/42-n/2. Доказательство. Согласно основному результату [11], если £(1),£(2),... — независимые одинаково распределённые в Rr случайные величины с единичной ковариационной матрицей и нулевым средним, ^ — случайная величина со стан- N дартным r-мерным нормальным распределением, Sn = N-1/2 Е £(j), то = j=1 = sup |P (Sn Е A) — P (^ Е A)| ^ 400r1/4E||£(1)||3N-1/2, где L — класс выпуклых бо- AeL релевских подмножеств Rr. Для векторов х (а), а Е Vn, попадаем в условия этого результата при Е||х (а)||3 = = r3/2 и N = 2n. ■ Данная теорема предлагает равномерные по r оценки расстояния между распределением вектора 21-n/2S (f) и многомерным стандартным нормальным распределением в обобщённой метрике полной вариации по классу выпуклых борелевских множеств и, следовательно, в равномерной метрике в терминах [12]. При n "то из этой теоремы следует асимптотическая нормальность вектора и, следовательно, интегральная предельная теорема. 3. Предельные теоремы для вектора, состоящего из части весов подфункций компонент случайного двоичного отображения Теперь рассмотрим вектор W (f) = (21+(|/*|/2) (w/s (f) — 2n-|/s|-1) : С {1,... ,n}, 0 = Js С {1,... , m}, s Е {1,... , r}) , состоящий из r весов подфункций, где r — некоторое натуральное число, не превышающее 2n+m — 2n, а пары множеств (J1,11) ,..., (Jr, 1r) —любые попарно различные. Из определения w/ (f) легко видеть, что этот вектор равен сумме векторов W (f )= E (2^в/s (а) (—1)/JS(а)Ф1 : s Е {1,..., r}) = E т (а), «eVn v 7 «eVn где в/ (а) = а^аi2 ... а^^ (при 1 = 0 считаем, что в/ (а) = 1). Рассмотрим набор из 2n независимых случайных векторов т (а), для всех координат которого Ts (а) верно равенство Ет5 (а) = 2 ¥ в/s (а) Е(—1)/J (а)ф1 = 0. Следовательно, т (а), а Е Vn — независимые не одинаково распределенные в Rr случайные величины с нулевым средним. Сумма векторов Е т (а) лежит в Rr. Введём aeVn Условия 1. Пусть выполняется следующее: 1) Зафиксировано некоторое натуральное r Е {1,..., 2m — 1}. 2) Зафиксирован набор непустых попарно различных подмножеств J1,... , Jr множества { 1 , . . . , m} . 3) Для любого s Е {1,... , r} зафиксировано произвольное подмножество множества { 1 , . . . , n} . r Обозначим 5 = Е 2|/s|. s=1 Пусть выполняются условия 1. Тогда при фиксированном m выполняется неравенство Е||т (а)||2 ^ 5 < +то. Следовательно, попадаем в условия теоремы 4.2.1 [13], согласно которой верно следующее Утверждение 6. Пусть n Х то, m — произвольное натуральное число. Тогда для любых попарно различных (J1,11) ,... , (Jr, 1r), удовлетворяющих условиям 1, норма вектора 2-nW (f) сходится к нулю с вероятностью 1. Данное утверждение является формулировкой усиленного закона больших чисел для случайных векторов т (а), а Е V^. Рассмотрим вопрос о скорости сходимости нормы вектора 2-nW (f) к нулю. Аналогично утверждению 5 можно легко доказать, что верно Утверждение 7. Пусть n,m — произвольные натуральные числа. Тогда для любых попарно различных (J1,11) ,..., (Jr, 1r) и для любого е > 0 верно неравенство P {||2-nW (f)У ^ е} ^ e-22-nE 2|/s|. s=1 Определение 1 [14]. Пусть £(1),... , £(N) есть N независимых не обязательно одинаково распределённых случайных векторов в Rr с ковариационными матрицами cov (£(j)), j Е {1,...,N}. Тогда средней ковариационной матрицей случайных век- 1 N торов £(1),..., £(N) называется матрица V = — Z cov (£(j)). N j=i Теперь оценим скорость сходимости характеристической функции специальным образом преобразованного вектора, составленного из весов подфункций, к характеристической функции стандартного многомерного нормального закона соответствующей размерности. Утверждение 8. Пусть n, m — произвольные натуральные числа. Дано случайное отображение f = (f1, f2,... , fm) Е B^ и выполняются условия 1. Тогда для всех t Е Rr, таких, что ||t|| ^ 2n/4-1 $-1/2, для характеристической функции (t) случайного вектора wr = (2^+1-1 (wJs (f) - 2n-|Is|-1) : Is С {1,... , n}, 0 = Js С {1,... , m}, s Е {1,... , r}) верно неравенство —2.U..W 7e-1 "til4 + Alltll2( A2-n^|t|2 + ^ 38^+"2 ¥>»r (t) - e-2^ 2-n-2||t||4^-e-2II*" + *||t||2 ^^2-n^|t|2 + -j e-10001 Доказательство. Пусть f — случайная функция из B^. Рассмотрим вектор wr = (2^+1-n (wJ (f) - EwJs (f)) : s Е {1,... ,r}) , где EwJs (f) = 2n-|Is|-1. Очевидно, что wr = 2-n/2 E т (a). s a€Vr Рассмотрим набор из 2n независимых случайных векторов т (a), для всех координат которого Ts (a) выполняется свойство Ets (a) = 0. Для любых k, s Е {1,..., r} верно равенство cov (Ts (a) ,Tk (a)) = 2^+¥ft. (a) ^ (a) E(-1)f J(а)ф/Jk(a) = 2|Is|,5is (a) I {k = s} . Следовательно, средняя ковариационная матрица V, за исключением главной диагонали, заполнена нулями, а элементы главной диагонали равны Е 2|Is|eis (a) = 1. 2n a€Vn Получили, что т (a), a Е Vn — независимые неодинаково распределённые в Rr случайные векторы с единичной средней ковариационной матрицей и нулевым средним. Рассмотрим ляпуновскую дробь /s 2n, определённую по формуле Е E (|(t,T (a))|s) 7 a€V„ 's,2n = SUp ="а"' Е E ((t,T (a))2Г */2' a€Vn Во введённых обозначениях выполняется теорема 8.6 из [14], согласно которой, если каждый вектор т (a) имеет конечный четвертый абсолютный момент р4 (т (a)) = Е||т (а)||4 и ляпуновская дробь /4,2- не превосходит единицы, то для всех t Е Rr 1 -1/4 таких, что ||t|| ^ 1 /4 1/ , справедливо неравенство ¥>»r (t) — e-2(1 + i62-n/2^3 (t)) 7 , ,, . ,,4 _!|Ш14 / 9 ,0 ,, . ,,a 1 ■100 M2 ^/4,2-11114e 2+ I —/2 ||t||8 + -/2 2n ||t|6 I e 40 4 , 2n |H| e 2 + V 500/4,2n |H| +36/3 , 2 где (t) = 2-n E E ((t,т (а))3). Легко видеть, что a€Vn Р4 (т (а))= (Е (2^в/s (а))^2 = (Е 2^ (а)) 2 ^ 52. В обозначениях (8.11) в [14] р4 = 2-n Е Р4 (т (а)). Очевидно, что р4 ^ 52, Е ((t, т (а))3) =0 и (t) = 0. В силу неравенства (8.12) из [14] /4,2n ^ 2-n52, /3,2n ^ 2-n/253/2. Следовательно, для всех t Е Rr, таких, что ||t|| ^ 2n/4-15-1/2 ^ 2n/4-1(p4)-1/4 ^ 1 /-1/4, выполняется утверждение теоремы. ■ Теперь, используя утверждение 8, докажем теорему о скорости сходимости распределения wr к распределению Ф стандартного r-мерного нормального закона. Теорема 2. Пусть m, n — произвольные натуральные числа, L — множество бо-релевских выпуклых подмножеств Rr, выполняется набор условий 1 и дано случайное отображение f = (f1, f2,... , fm) Е B^. Пусть для n выполняется n > max {52 — 1, 12 + 2log2 (95(r + 2)2)} . Тогда для случайного вектора wr из формулировки утверждения 8 с распределением Qn верно следующее неравенство: sup |Qn (C) — Ф (C)| ^ 4 (b1 (r) 2-n/2 + b2 (r) 2-n/2n-1/2 + 63 (r) 2-nnr/2+ cec 3 ^ +64 (r) 2-3n/2n-3/2 + 65 (r) 2-2nnr/2 + 6б (r) e-28077 2-n/4nr/2+ 2-/2 2n/2 \ +67 (r) e-1677 2-n/4nr/2 + 68 (r) e- W7 2-3n/4nr/2J , где Ф — распределение случайной величины со стандартным r-мерным нормальным распределением, 25г4/353/2Г((г + 1) /2) 11r53/2 61 (r) =-3nW(r/2) 7) + — + (4 + e3/2) 53/2 (r — 1) 53/2 21/253/2 (r3/2 — 3r1/2 + 2) + 6e3/2/2n + 2r1/2ne1/2 + П3/2 , (Г (r/2))2 у 20 V 4 У 18 V 383 У V 2 2(r-1)/2r(r-2)/2(ln2)r/252 /7 r /r + 4\ _5_ /1000\ ^ /r + 6^ 3 (r)= (Г (r/2))2 V 20 4 V 23r5/2^3 ч 9 ■ 2( )/2r(r-2)/2(ln 2)r/2#4( ) ^Г () 64 (r) = -;— ,65 (r) = -----238^-\_2_J_ () n(log 2)3/2 ,5 () 125(Г (r/2))2 r ч 2r+3#1/2r(r-2)/2(ln 2)r/2 / 3 \(1+r)/2 62 (r) = -пт;, 6б (r) = -2- -= , (nln2)1/ (Г (r/2))2 \3 - 2^27 ' £1/22r+3r(r-2)/2(ln2)r/2 ч £2 2r+7/2r(r-2)/2(ln 2)r/2 67 (r) = -2-,68 (r) = -2-. (Г (r/2))2 w 3(Г (r/2))2 Здесь Г (x) —значение гамма-функции Эйлера в точке x. Доказательство. Верно следующее равенство: / Icd (Qn - ф) |P (wr Е C) - Ф(С)| где Ic — индикатор множества С. Рассмотрим случайный вектор K со значениями в Rr с плотностью о \ r r / . 3а \ тт / sin axs 2п ) , V ax s=1 PK (x1 ...xr)H2- П s где a = 2n-1/3r5/6. Сглаживающая вероятностная мера, порождённая этим вектором, активно используется в [14]. Рассмотрим случайный вектор eK с распределением K£. Согласно неравенству (13.12) из [14], P (eK Е Rr\B (0 : e)) ^ P (K Е Rr\B (0 : 1)) ^ 1, 8 где B (x : e) —открытый шар в Rr радиуса e с центром в x. Тогда 7 1 P (eK Е B (0: e)) ^ 8 > ^. Следовательно, попадаем в условия следствия 11.5 в [14]: 4 /1 / Icd (Qn - Ф) ^ 4 Qwi0 (Rr) ||(Qn - Ф) * K || + w;c (2e : Ф)) где * — внутренняя операция свёртки (композиции) двух конечных обобщённых мер; wIc (S) = sup |/C (x) - 1C (y)| —колебание функции 1C на множестве S; вариационная норма [14] на классе всех конечных обобщённых мер, равная полной вариации меры, обозначена как ||(Qn - Ф) * K£||, wjc (2e : Ф) = sup J1 wIc (B (x - y : 2e)) Ф (dx). y€Rr Rr Очевидно, что wIc (Rr) = 1, а, согласно неравенству (13.42) из [14], * , ^ 25/2Г ((r + 1) /2) Теперь рассмотрим поведение величины ||(Qn — Ф) * K£||. Из определения вариационной нормы следует, что ||(Qn — Ф) * Ke|| =2 sup |(Qn — Ф) * K (B)| , BeBr где Br — борелевская сигма-алгебра подмножеств из Rr. Для каждого борелевского множества B и k > 0 определим множества B1 = B П B (0: k) , B2 = B\B1. Оценим |(Qra — Ф) * K (Bi)|, i Е {1, 2}. Рассмотрим конечную обобщённую меру P1 (а) с плотностью (X1 . . . Xr) x 6 (х(3,0,...,0) (x3 — 3x1) + ... + X(0,0,...,3) (x? — 3Xr)) + + 1 (X(2,1,...,0) (x2X2 — x2) + X(0,...,1,2) (x;!xr-1 — xr-1)) + Pa (x1 ... xr) +х(1,1,1,0,...,0)x1x2x3 + . . . + х(0,...,1,1,1)xr-2xr-1xr где X(Yl,...,7fc) = XY — семиинварианты (кумулянты) вероятностной меры, порождённой случайным вектором т (а), порядка y; ^ (x1... xr) —плотность распределения случайного вектора со стандартным r-мерным нормальным распределением. Согласно равенству (7.22) из [14], / pa (x1... xr) dx=0. Пусть P1=2-n E Pa (x1...xr). Rr a£V„ Данная мера введена в равенстве (2.10) в [15]. Имеем |(Qra — Ф) * K (B1)| ^ |Я„ * K (B1)| + 2-n/2 |P1 * K£ (B1 )| , где Яга = Qra — Ф — 2-n/2 P1. Обозначим через Hn = J ei(t,x)Hn (dx) преобразование Фурье обобщённой меры Hn. Rr Согласно неравенству (13.22) из [14], получим |Hn * K (B1)| ^ (2n)-rAr (B1) / Hn (t) K£ (t) где Ar — мера Лебега на Rr. С учётом вычисленного в [14] преобразования Фурье для P1 получаем, что верно равенство Hn = . ei(t,x)Hn (dx) = . ei(t,x) (Qn — Ф — n-1/2P1) (dx) = Rr Rr = Q — e-2 ||t||2( 1 + i3n-1/2^3(t^ , где ^3 (t) = 2-n £ E ((^т (а))3). V 6 / aey„ aeVn 3) Легко показать, что E ((t, т (а)) ) =0. Возьмем в качестве е величину ar1/2p32-(n-3)/2, где р3 = 2-n £ Р3 (т (а)), aeVn р3 (т (а)) = Е||т (а)||3. Очевидно, что р3 ^ 53/2. Согласно соотношению (13.36) в [14], верно неравенство / H (t) K (t) Rr f H (t) , 4 1 , , 1 I

Ключевые слова

случайное двоичное отображение, локальная предельная теорема, закон больших чисел, автокорреляционные коэффициенты, спектральные коэффициенты, веса подфункций, random binary mapping, local limit theorem, law of large numbers, autocorrelation coefficients, spectral coefficients, weights of subfunction

Авторы

ФИООрганизацияДополнительноE-mail
Панков Константин НиколаевичМосковский государственный технический университет радиотехники, электроники и автоматикистарший преподаватель кафедры информационной безопасностиk.n.pankov@gmail.com
Всего: 1

Ссылки

Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004. 472 с.
Ященко В. В. Свойства булевых отображений, сводимые к свойствам их координатных функций // Вестник МГУ. Сер. Математика. 1997. Т. 33. №1. С. 11-13.
Carlet C. Vectorial Boolean functions for cryptography // Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Encyclopedia of Mathematics and its Applications. V. 134. New York: Cambridge University Press, 2010. P. 398-472.
Денисов О. В. Локальная предельная теорема для распределения части спектра случайной двоичной функции // Дискретная математика. 2000. Т. 12. №1. С. 82-95.
Панков К. Н. Верхняя граница для числа функций, удовлетворяющих строгому лавинному критерию // Дискретная математика. 2005. Т. 17. №2. С. 95-101.
Рязанов Б. В. О распределении спектральной сложности булевых функций // Дискретная математика. 1994. Т. 6. №2. С. 111-129.
Таранников Ю. В. Комбинаторные свойства дискретных структур и приложения к криптологии. М.: МЦНМО, 2011. 152 с.
Халявин А. В. Оценка нелинейности корреляционно-иммунных булевых функций // Прикладная дискретная математика. 2011. №1. С. 34-69.
Азларов Т. А., Володин Н. А. Законы больших чисел для одинаково распределенных банаховозначных случайных величин // Теория вероятностей и её применения. 1981. Т. 26. №3. С. 584-590.
Кахан Ж.-П. Случайные функциональные ряды. М.: Мир, 1973. 304 с.
Bentkus V. On the dependence of the Berry-Esseen bound on dimension // J. Stat. Plan. Infer. 2003. V. 113. No. 2. P. 385-402.
Золотарев В. М. О свойствах и связях некоторых типов метрик // Записки научных семинаров ЛОМИ. 1979. Т. 87. С. 18-35.
Padgett W. J. and Taylor R. L. Laws of Large Numbers for Normed Linear Spaces and Certain Frechet Spaces. New York: Springer, 1973. 117 p.
Бхаттачария Р. Н., Ранга Р. Аппроксимация нормальным распределением и асимптотические разложения. М.: Наука, 1982. 288 с.
Bhattacharya R. N. Rates of weak convergence for the multidimensional central limit theorem // Теория вероятностей и ее применения. 1970. Т. 15. №1. С. 69-85.
Прохоров Ю. В. Распространение неравенств С. Н. Бернштейна на многомерный случай // Теория вероятностей и её применения. 1968. Т. 13. №2. С. 266-274.
 Оценки скорости сходимости в предельных теоремах для совместных распределений части характеристик случайных двоичных отображений | ПДМ. 2012. № 4(18).

Оценки скорости сходимости в предельных теоремах для совместных распределений части характеристик случайных двоичных отображений | ПДМ. 2012. № 4(18).

Полнотекстовая версия