Теңгерімді орнатыңыз - Set balancing

Бұл мақала үшін қосымша дәйексөздер қажет тексеру. Өтінемін көмектесіңіз осы мақаланы жақсарту арқылы дәйексөздерді сенімді дерек көздеріне қосу. Ресурссыз материалға шағым жасалуы және алынып тасталуы мүмкін. Дереккөздерді табу: «Теңгерімді орнату»  – жаңалықтар  · газеттер  · кітаптар  · ғалым  · JSTOR (Желтоқсан 2015) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз)

The теңдестіруді орнатыңыз математикадағы есеп - бұл жиынтықты шамамен бірдей сипаттамаларға ие екі жиынға бөлу мәселесі. Бұл табиғи түрде пайда болады эксперименттерді жобалау.^[1]:71–72

Пәндер тобы бар. Әр пәннің екілік болып саналатын бірнеше ерекшеліктері бар. Мысалы: әр пән жас та, кәрі де болуы мүмкін; не қара, не ақ; не ұзын, не қысқа; Мақсаты - зерттелушілерді екі топқа бөлу: емдеу тобы (Т) және бақылау тобы (C), әр функция үшін Т-да осы қасиетке ие субъектілердің саны шамамен CEg-де осы ерекшелікке ие субъектілер санына тең болса, екі топта да шамамен бірдей жастар саны, бірдей сан болуы керек қара адамдардың, бірдей ұзын бойлылардың және т.б.

Матрицаны ұсыну

Формальды түрде теңдестірілген жиынтық мәселесін келесідей сипаттауға болады.

${ displaystyle m}$ - бұл жалпы халықтың субъектілерінің саны.

${ displaystyle n}$ бұл потенциалды ерекшеліктердің саны.

Тақырыптар сипатталады ${ displaystyle A}$, an ${ displaystyle n рет m}$ матрица енгізілген ${ displaystyle {0,1}}$. Әр баған тақырыпты, ал әрбір жол ерекшелікті білдіреді. ${ displaystyle a_ {i, j} = 1}$ егер тақырып ${ displaystyle j}$ ерекшелігі бар ${ displaystyle i}$, және ${ displaystyle a_ {i, j} = 0}$ егер тақырып ${ displaystyle j}$ ерекшелігі жоқ ${ displaystyle i}$.

Топтарға бөлу арқылы сипатталады ${ displaystyle b}$, an ${ displaystyle m times 1}$ жазбасы бар вектор ${ displaystyle {-1,1}}$. ${ displaystyle b_ {j} = 1}$ егер тақырып ${ displaystyle j}$ емдеу тобында Т және ${ displaystyle b_ {j} = - 1}$ тақырып болып табылады ${ displaystyle j}$ С тобында.

Функциялардың тепе-теңдігі сипатталады ${ displaystyle c = A cdot b}$. Бұл ${ displaystyle n рет 1}$ вектор. Сандық мәні ${ displaystyle c_ {i}}$ теңгерімсіздік болып табылады ${ displaystyle i}$: егер ${ displaystyle c_ {i}> 0}$ онда пәндер көбірек ${ displaystyle i}$ Т және егер ${ displaystyle c_ {i} <0}$ онда пәндер көбірек ${ displaystyle i}$ C.

The теңгерімсіздік берілген бөлімнің анықтамасы:

${ displaystyle I (b) = || A cdot b || _ { infty} = max _ {i in 1 dots, n} | c_ {i} |}$

Жинақталған теңдестіру проблемасы - векторды табу ${ displaystyle b}$ бұл тепе-теңдікті азайтады ${ displaystyle I (b)}$.

Кездейсоқ алгоритм

Шамалы шешімді келесідей өте қарапайым түрде табуға болады рандомизацияланған алгоритм:

Әр тақырыпты емдеу тобына 1/2 ықтималдықпен жіберіңіз.

Матрицалық тұжырымдауда:

Элементтерін таңдаңыз ${ displaystyle b}$ {1, -1} ішіндегі әрбір мәнге 1/2 ықтималдықпен кездейсоқ.

Таңқаларлықтай, дегенмен бұл алгоритм матрицаны толығымен елемейді ${ displaystyle A}$, ол кішкене теңгерімсіздікке жетеді жоғары ықтималдықпен көптеген мүмкіндіктер болған кезде. Формальды түрде кездейсоқ вектор үшін ${ displaystyle b}$:

${ displaystyle Prob left [I (b) geq { sqrt {4m ln n}} right] leq { frac {2} {n}}}$

ДӘЛЕЛ:

Келіңіздер ${ displaystyle k_ {i}}$ ерекшеліктері бар пәндердің жалпы саны ${ displaystyle i}$ (эквивалентті, ішіндегілердің саны ${ displaystyle i}$- матрица ${ displaystyle A}$). Келесі екі жағдайды қарастырыңыз:

Оңай жағдай: ${ displaystyle k_ {i} leq { sqrt {4m ln n}}}$. Содан кейін, 1 ықтималдығымен, ерекшелік теңгерімсіздігі ${ displaystyle i}$ (біз белгілеген ${ displaystyle c_ {i}}$) ең көп дегенде ${ displaystyle { sqrt {4m ln n}}}$.

Қатты жағдай: ${ displaystyle k_ {i}> { sqrt {4m ln n}}}$. Әрқайсысы үшін ${ displaystyle j}$, рұқсат етіңіз ${ displaystyle X_ {j} = a_ {i, j} b_ {j}}$. Әрқайсысы осындай ${ displaystyle X_ {j}}$ - бұл кездейсоқ шама, ол 1 немесе -1 болуы мүмкін, 1/2 ықтималдығы бар. Ерекшеліктердегі теңгерімсіздік ${ displaystyle i}$ бұл: ${ displaystyle c_ {i} = sum _ {j = 1} ^ {m} {X_ {j}}}$. Бастап ${ displaystyle X_ {j}}$ тәуелді емес кездейсоқ шамалар болып табылады Шернофф байланған, әрқайсысы үшін ${ displaystyle a> 0}$:

${ displaystyle Prob left [| c_ {i} | geq a right] leq 2 exp (-a ^ {2} / 2m)}$

Таңдау: ${ displaystyle a = { sqrt {4m ln n}}}$ ал:

${ displaystyle Prob left [| c_ {i} | geq { sqrt {4m ln n}} right] leq { frac {2} {n ^ {2}}}}$

Бойынша одақ байланысты,

${ displaystyle Prob left [ бар i: | c_ {i} | geq { sqrt {4m ln n}} right] leq { frac {2} {n}}}$.

Әдебиеттер тізімі