Informace k prednasce "Kombinatoricka a vypocetni geometrie II" 
(Jiri Matousek, Pavel Valtr, KAM)

Anotace

Probrano:

1. prednaska 26.2. (J.M.)

• Pravdepodobnost, ze konvexni obal n nahodnych nezavislych bodu na jednotkove kruznici obsahuje stred te kruznice, je rovna 1-2n/2^n. Trik: nejdriv se zvoli nahodne n dvojic protilehlych bodu, potom se z kazde dvojice nahodne vybere bod.
• Zobecneni do vyssi dimenze: n nahodnych nezavislych bodu na S^{d-1}. Stejny trik, vede na pocitani bunek v arrangementu n "rovniku" na S^{d-1}, to se da delat pomoci rekurence (f_d(n)=f_d(n-1)+f_{d-1}(n-1)).
• p_1,...,p_n nahodne nezavisle body ve ctverci, jaka je pravdepodobnost, ze jsou v konvexni poloze? (Pro n=4 Sylvesterova otazka). Prekvapive jednoducha formule [Valtr]: ((2n-2 nad n-1)/n!)^2.
• My udelame jednodussi vysledek: Pravdepodobnost, ze ty body tvori spolu s levym dolnim a pravym hornim rohem ctverce konvexni retezec, je 1/(n!(n+1)!).
• Prvni krok: jev M = body tvori monotoni posloupnost, pravdep. je 1/n!. Dukaz: pravdepodobnost, ze y-ove souradnice jsou usporadany podle permutace pi je pro kaznou permutaci pi stejna. To staci ukazat pro permutace, ktere se lisi jen vymenou sousednich prvku. Prislusna bijekce zamenuje y_{i-1} a y_i (a nechava vsechny ostatni souradnice na miste).
• Druhy krok: definujeme a_i jako smernici usecky p_{i-1} p_i, i=1,2,...,n+1 (kde body jsou cislovany odleva doprava). Tvrzeni: pokud nastane M, pak pravdepodobnost, ze ty a_i jsou usporadany podle permutace pi, je stejna pro vsechny pi. Zase jen pro permutace lisici se transpozici sousednich. Prislusna bijekce nahrazuje x_i cislem x_{i-1}+(x_{i+1}-x_i) a y_i cislem y_{i-1}+(y_{i+1}-y_i), a jinak vse nechava.
• Dusledek dukazu: efektivni algoritmus na generovani nahodneho konvexniho retezce (vygeneruj nahodne body, setrid x-ove a y-ove souradnice, uvaz usecky definovane vyslednou monotoni posloupnosti bodu, a naklad je odleva doprava podle rostouci smernice).
• Poznamka (bez dukazu): nahodne konvexni retezce konverguji k "limitnimu tvaru", danemu jistou parabolou L. Formulace: pokud x je nejaky bod ctverce pod L, potom pravdepodobnost, ze bude pod nahodnym n-bodovym konvexnim retezcem, konverguje k 1 pro n jdouci do nekonecna, a podobne pro x nad L.

2. prednaska 5/III/2003 (J.M.)

• Azumova nerovnost: Necht d_1,d_2,...,d_n jsou realne nahodne promenne. Predpokladejme, ze d_i nabyva hodnot jen v intervalu [-c_i,c_i] ("d_i je mala"), a dale ze plati E[d_{i_1}d_{i_2}...d_{i_k}]=0 pro kazdou volbu indexu i_1,i_2,...,i_k, 1 <= i_1 < i_2 < ... < i_k (neco jako nezavislost, ale slabsi). Necht Z=d_1+d_2+...+d_n. Potom Z je koncentrovana kolem sve stredni hodnoty (rovne 0): P[|Z|>t]< 2 e^{-t^2/2C}, kde C=c_1^2+c_2^2+...+c_n^2.
• Specialni pripad (a inspirace) je Cernovova nerovnost, kde d_1,d_2,...,d_n jsou nezavisle, nabyvaji hodnot +1 a -1, kazdou s pravdepodobnosti 1/2 (tedy c_i=1 pro vsechna i).
• Dukaz Azumovy nerovnosti: pouzije se Markovova nerovnost pro promennou exp(aZ), kde a>0 je vhodny realny parametr (optimalizuje se nakonec); k tomu je treba odhadnout shora E[exp(aZ)]. Kazdy faktor exp(ad_i) se pro d_i\in [-c_i,c_i] shora odhadne linearni funkci cosh(ac_i)+(d_i/c_i)sinh(ac_i) (konvexita!), po roznasobeni vsech techto linearnich funkci zmizi (dle predpokladu E[d_{i_1}...d_{i_k}]=0) vse az na soucin tech cosh(ac_i), tady se jeste odhadne cosh(ac_i)<= exp(a^2c_i^2/2).
• Kde vzit takova d_i, jako v Azumove nerovnosti? Typicky z martingalu, to obecne delat nebudeme, rekneme si specialni pripad. Necht X_1,...,X_n jsou nejake nezavisle realne promenne, a necht f(X_1,...,X_n) je nejaka jejich funkce. Priklady: X_i je indikator pritomnosti i-te hrany v nahodnem grafu, f je barevnost; nebo: X_i je i-ty nahodny bod v jednotkovem ctverci, f je delka euklidovske minimalni kostry mnoziny X_1,...,X_n, a pod. Klicova definice: definujeme Z_i=Z_i(omega_1,...,omega_i) jako stredni hodnotu f(omega_1,...,omega_i,X_{i+1},...,X_n), kde stredni hodnota je pres nahodne X_{i+1},...,X_n, zatimco omega_1,...,omega_i jsou fixovany. Tedy Z_0 je proste E[f] (vse nahodne), a Z_n=f (zadna nahodnost, vse jsou parametry).
• Tvrzeni: Polozime-li d_i=Z_i-Z_{i-1}, potom d_1,...,d_n splnuji predpoklad Azumovy nerovnosti, a pro f-E[f]=d_1+d_2+...+d_n dostaneme koncentraci jako v Azumovi. Dukaz: Abychom ukazali E[d_{i_1}...d_{i_k}]=0, podivame se na stradni hodnotu pres omega_{i_k}, na te zavisi pouze d_{i_k}, a je snadno videt, ze E_{omega_i}[d_i]=0.
• Abychom to mohli pouzit, musime umet odhadnout c_i, maximalni moznou absolutni hodnotu d_i. Jednoduchy pristup: c_i je nejvys "efekt" i-te promenne na f, tj. o kolik se muze f(x_1,...,x_n) zmenit kdyz (libovolne) zmenime x_i a vsechny ostatni x_j nechame stejne (ale ta x_j volime libovolne - snazime se efekt maximalizovat). Nekdy potrebujeme slozitejsi odhad c_i, vyuzivajici nahodnosti tech X_{i+1},...,X_n. Tedy c_i je stredni hodnota pres X_i,...,X_n vyrazu |f(omega_1,...,omega_i,X_{i+1},...X_n)-f(omega_1,...,omega_{i-1},X_i,...,X_n)|, nejhorsi pripad pres volbu tech omega_j (tedy maximalni efekt nahrazeni libovolneho omega_i nahodnym X_i).
• Ted budeme zkoumat problem obchodniho cestujiciho pro nahodne body. Pro mnozinu S v jednotkovem ctverci definujeme L(S) jako euklidovskou delku nejkratsi okruzni cesty skrz vsechny body S. Dale pisme L_n=L_n(X_1,...,X_n)=L({X_1,...,X_n}) pro X_1,...,X_n nahodne rovnomerne rozdelene nezavisle.
• Chceme na L_n pouzit Azumovu nerovnost, potrebujeme odhad tech c_i. Pro libovolnou volbu omega_1,...,omega_i, X_i,...,X_n mame
  L_{n-1}(omega_1,...,omega_{i-1},X_{i+1},...,X_n) <=
  L_n(omega_1,...,omega_i,X_{i+1},...,X_n) <=
  L_{n-1}(omega_1,...,omega_{i-1},X_{i+1},...,X_n) + 2 min {||omega_i-X_j||,i < j <= n}
  (prvni nerovnost: cesta skrz mensi mnozinu neni delsi nez cesta skrz vetsi mnozinu, druha nerovnost: cesta skrz mnozinu s bodem omega_i navic je nejvys tak dlouha jako cesta skrz puvodni mnozinu plus delka napojeni omega_i k nekteremu X_j). Podobne pro pridani X_i, a odtud c_i je nejvys
  2.max_x E[min{||x-X_j||: i < j <= n}],
  kde E[.] je vzhledem k nahodnym X_j.

3. prednaska 12/III/2003 (J.M.)

• Lemma: Jsou-li X_1,...,X_m nahodne body v jednotkovem ctverci jako obvykle, a x je libovolne, pak E[min_j ||X_j-x||]=O(m^{-1/2}). Dukaz: nejdriv odhadnout pravdepodobnost
  P[min > lambda ] < (1-(pi/4)lambda^2)^m < exp(-(pi/4)m lambda^2),
  pak odhadovat stredni hodnotu vhodnym rozbitim na intervaly podle lambda.
• Dosazanim do Azumovy nerovnosti:
  P[|L_n-E[L_n]|>t] < exp(-ct^2/log n),
  tedy typicke fluktuace L_n jsou nejvys kolem (log n)^{1/2}
• Poznamka: Podobne pro dimenzi d vyjde koncentrace s n^{1-2/d} misto log n.
• Ted chceme odhadnout E[L_n]. Shora: pro libovolnych n bodu v jednothovem ctverci existuje cesta delky O(n^{1/2}). Zdola: ukaze se E[min_{i ruzne od j} ||X_i-X_j||] = Omega(n^{-1/2}) (dom. cviceni), a odtud E[L_n]=Omega(n^{1/2}).
• Dalsi plan: ukazeme, ze lim_{n\to\infty} (E[L_n]/n^{1/2}) existuje, tj. L_n se nemeni prilis divoce v zavislosti na n.
• Nastroj: Poissonovo rozdeleni. Nahodna promenna X ma Poissonovo rozdeleni s parametrem lambda, nabyva-li hodnot 0,1,2,..., a hodnotu k nabyva s pravdepodobnosti exp(-lambda)lambda^k/k!. Plati E[X]=Var[X]=lambda.
• Poissonuv proces v rovine (s jednotkovou intenzitou): v omezene meritelne mnozine A v rovine vygenerujeme podle nej body ve dvou krocich:
  • Vygeneruj cislo N z Poiss. rozdelenim s parametrem lambda="plocha(A)" (kde plocha je ve skutecnosti Lebesgueova mira),
  • Vygeneruj N nezavislych nahodnych rovnomerne rozdelenych bodu v A.
  Predstava: rovina je pokryta velejemnou mrizkou z atomu, kazdy se v prvni minute rozpadne se stejnou velmi malou pravdepodobnosti (takovou, ze na jednotku plochy pripadne v prumeru jeden rozpadly atom) nezavisle na ostatnich, realizace Poissonova procesu jsou ty atomy rozpadle behem prvni minuty.
• Vlastnosti: Je-li B podmnozina A, pak zuzeni Poissonova procesu z A na B je zase Poiss. proces (spocte se). Dale (nebudeme potrebovat): Jsou-li B_1 a B_2 disjunktni podmnoziny A, pak zuzeni Poissonova procesu z A na B_1 a na B_2 jsou nezavisla.

4. prednaska 19/III/2003 (J.M.)

• Smerujeme k dukazu existence limity E[L_n]/n^{1/2}. Definujeme nahodnou promennou Z(t) jako delku optimalni obchodni cesty pro nahodne body generovane Poissonovym procesem (s jednotkovou intenzitou) ve ctverci [0,t)^2, a z(t)=E[Z(t)].
• Tvrzeni: f(t) := z(t)/t^2 ma limitu pro t jdouci do nekonecna.
• Dukaz: Nejdrive pozorovani: Pro kazde prirozene m a realne t>0 plati z(mt)+m^2 z(t)+Ctm^2 (rozdeleni ctverce o strane mt na sit m krat m, propojeni cest v malych ctvereccich; podstatne se vyuziva toho, ze zuzeni Poissonova procesu na maly ctverecek je zase Poissonuv proces). Tedy f(mt) <= f(t) +C/t. Vezmeme beta = lim inf f(t), pro epsilon>0 se vezme t_0 tak, aby f(t_0)< beta+epsilon, a pritom t_0> C/epsilon. Ze spojitosti f v t_0 plati f(t) < beta+2epsilon na [t_0,t_0+delta), a potom taky f(mt) < beta+3epsilon pro takova t, a vsechna dost velika cisla jsou tvaru mt pro t z intervalu (t_0,t_0+delta).
• Ted jak z(t) souvisi s puvodnim problemem? Oznacme a_n=E[L_n(X_1,..,X_n)], to je to co nas zajima. Plati z(t) = sum_{n=0}^\infty t.a_n e^{-t^2}t^{2n}/n!= t.E[a_N], kde N ma Poissonovo rozdeleni s parametrem n.
• Staci ukazat ze |a_n- E[a_N]| je radove mensi nez n^{1/2}, pak dostaneme ze a_n/n^{1/2} ma limitu, protoze z(n^{1/2})/n ma limitu.
• Pocitame |a_n-E[a_N]| <= sum_k |a_n-a_k| e^{-n} n^k/k!, odhadneme |a_n-a_k| <= C|n-k|^{1/2 (z propojeni dvou okruznich cest, a z toho, ze cesta skrz q modu ma delku O(q^{1/2})). Vysledna suma je l_1 norma jiste nahodne promenne X, tj. ||X||_1, kde X nabyva hodnoty |n-k|^{1/2} s pravdep. e^{-n} n^k/k!. Pak ||X||_1 <= ||X||_4 (nerovnost mezi l_p normami), a ||X||_4 je Var[Y]^{1/4}, kde Y ma Poissonovo rozdeleni s parametrem n. Zaverecny odhad je tedy O(n^{{1/4}).
• Celkem jsme dokazali Beardwoodovu-Haltonovu-Hammersleyho vetu: Existuje konstanta beta=beta_{TSP}(2) takova, ze L_n(X_1,...,X_n)/n^{1/2} pro n jdouci do nekonecna konverguje k beta s pravdepodobnosti 1.
• Podobne tvrzeni pro kazdou dimenzi d, a tez pro dalsi problemy (TSP v l_p metrikach, miminalni Steineruv strom - stejnou metodou; minimalni kostra, minimalni parovani - musi se delat trochu jinak, protoze nejsou "monotoni").
• Hodnoty beta nejsou znamy. Napriklad je dokazano 0.62 < beta_{TSP}(2) < 0.921, a pocitacove experimenty naznacuji 0.70 < beta_{TSP}(2) < 0.73.

5. prednaska 26/III/2003 (J.M.)

• Problem prirazeni (nebo tez problem parovani minimalni vahy): Jsou dana cisla c_{ij}, i,j=1,2,...,n, chceme najit permutaci pi ze S_n minimalizujici soucet c_{i,pi(i)}, i=1,2,...,n.
• Oznacme minimalni hodnotu toho souctu pro dane c=(c_{ij}) symbolem A_n(c). Budeme zkoumat stredni hodnotu A_n(c) pro c_{ij} nahodne nezavisle rovnomerne rozdelene v intervalu [0,1].
• Veta [Karp]: ta stredni hodnota je nejvys 2. (Prekvapive.)
• Formulace pomoci linearniho programovani: Zavedme konvexni mnohosten P v R^{n^2}, P={x >= 0, sum_i x_{ij}=1 pro kazde j, sum_{j} x_{ij}=1 pro kazde i} (Birkhoffuv mnohosten). Plati: vsechny vrcholy P maji vsechny souradnice celociselne (tj. 0 nebo 1). [Nedokazovali jsme, ale je to prerikani vety, ze kazda bistochasticka ctvercova matice (nezaporna radkove i sloupcove soucty 1) je konvexni kombinaci permutacnich matic; ta se dokazuje indukci podle poctu nenulovych policek matice.] Proto minimum cx pro x\in P se nabyva v 0/1 vektoru, a takovy vektor definuje prirazeni (permutaci pi).
• Poznamka: mnohosteny s celociselnymi vrcholy jsou dulezite v kombinatoricke optimalizaci, a souvisi tesne s tzv. totalne unimodularnimi maticemi (determinant kazde ctvercove podmatice je 0, +1, nebo -1).
• Zminenou Karpovu vetu dokazeme z obecnejsi vety [Dyer - Frieze - McDiarmid]: Necht c_1,...,c_n jsou nezavisle nahodne promenne, kazda rovnomerne rozdelena v intervalu [0,1]. Necht A je (pevna) matice m x n a necht b je (pevny) m-slozkovy vektor. Bud P={x\in R^n: x >= 0, Ax=b}, a bud w libovolny bod z P. Oznacme z^* := min {cx: x\in P} (to je nahodna promenna, zavisi na c). Potom E[z^*] <= soucet m nejvetsich slozek w.
• Odvozeni Karpovy vety z DFMcD: w_{ij} = 1/n pro vsechna i,j.
• Pro dukaz DFMcD vety muzeme predpokladat, ze A ma plnou hodnost m. Potom Ax=b definuje afinni podprostor dimenze n-m, ktery protina "kladny ortant" v mnohostenu P. V dukazu budeme predpokladat, ze kazdy vrchol P je definovan presne n nadrovinami: m z nich jsou ze soustavy Ax=b, a n-m jsou tvaru x_i=0. To se da dosahnout libovolne malou perturbaci matice A a vektoru b (predstava: kazdou souradnicovou nadrovinu malinko posuneme "do minusu").
• Dale, pro skoro vsechna c se min {cx: x\in P} nabyva v jedinem vrcholu.
• Ted budeme potrebovat neco ze simplexove metody, coz je velmi dulezity algoritmus na reseni ulohy linearniho programovani. Ulohu uvazujeme ve standardnim tvaru min{cx: x >= 0, Ax=b}, jako v DFMcD vete.
• Necht I je m-prvkova mnozina indexu z {1,2,...,n}; zapis A_I pro sloupce matice A indexovane I (bazicke sloupce), a A_N zbyle sloupce (nebazicke); podobne pro vektory c a x. Predpokladejme, ze A_I je regularni. Bazicke reseni prislusne I ma x_N=0 a x_I = A_I^{-1}b; pripustnost zde znamena x_I >= 0.
• Tvrzeni (kriterium optimality pro simplexovy algoritmus:
  • Je-li bazicke reseni prislusne I pripustne, a plati-li podminka
    c_N >= c_I A_I^{-1} A_N
    (rikejme ji podminka (*)), potom bazicke reseni prislusne I je optimalni, tj. minimalizuje cx pres {x >=0, Ax=b}.
  • Je-li P jednoduchy mnohosten, c je takove ze min cx se nabyva v jedinem vrcholu, a tento vrchol je bazicke reseni prislusne k nejakemu (jednoznacne urcenemu) I, potom plati podminka (*). Tj. kriterium v prechozim bodu je "prave kdyz" za dodatecnych predpokladu obecne polohy.
  Prvni cast tvrzeni je snadno videt z rozepsani cx na bazickou a nebazickou cast, druha cast da trochu vic prace - podstata je, ze kdyz by (*) neplatila, reseni by slo vylepsit jednim krokem simplexoveho algoritmu ("pivotovanim").

6. prednaska 2/IV/2003 (J.M.)

• Dukaz Dyerovy-Friezovy-McDiarmidovy vety. Predpokladame, ze matice A ma plnou hodnost m, a ze podprostour definovany Ax=b je v obecne poloze (jako v druhe casti tvrzeni z konce minule prednasky).
• Pravdepodobnostni prostor vsech c, tj. [0,1]^n, rozdelime na oblasti E_I, kde I je m-prvkova indexova podmnozina [n]: E_I sestava z tech c, pro nez bazicke reseni prislusne I je jednoznacne optimalni reseni uvazovaneho problemu min {cx: Ax=b, x >= 0}. E_I jsou disjunktni a pokryvaji vse az na mnozinu miry 0 (nejednoznacne reseni znamena, ze minimum nastane ve dvou vrcholech u a v, a cx=cu definuje nadrovinu).
• Fixujme I a volme c nahodne jen z E_I. Navic ted fixujeme nejakou hodnotu c_I (tj. bazickych slozek c), a nahodne volime pouze c_N. Klicove pozorovani: Tato nahodna volba c_N je totez, jako kdyz kazdou slozku c_j z c_N zvolime nahodne z rovnomerneho rozdeleni na intervalu [h_j,1] nezavisle na ostatnich, kde h_j je j-ta slozka c_I A_I^{-1} A_N. To plyne z tvrzeni (kriteria optimality baz. reseni) z minule prednasky.
• Dusledek: Pro nebazicky index j plati E[c_j | E_I, c_I pevne] = (1+h_j)/2.
• Trik: ted pocitame E[cw | E_I, c_I pevne], kde w je pripustne reseni z DFMcD vety. V pocitani se nejprve pouzije predchozi dusledek, pak rovnost Aw=b (zbavime se nebazickych sloupcu A), a potom se tam objevi z^* jakozto hodnota optimalniho reseni ve tvaru c_I A_I^{-1} b. Vyjde
  E[cw | E_I, c_I pevne] >= (1/2) sum_{j\in N} w_j + (1/2) z^*.
• Ted uvazujeme nahodne c_I (I je stale fixovane), a mame E[cw | E_I] >= (1/2) \sum_{j\in N} w_j + (1/2) E[z^* | E_I].
• Konecne oznacime p_I pravdepodobnost jevu E_I, a mame
  E[cw] = sum_I p_I E[cw | E_I] >= (1/2) E[z^*] + (1/2)sum_I p_I . sum_{j\not\in I} w_j.
  Na druhe strane ovsem E[cw] = (1/2) sum_{j=1}^n w_j. Porovnanim vyjde tvrzeni vety, tj. ze E[z^*] je nejvys soucet m nejvetsich slozek vektoru w.

7. prednaska 9/IV/2003 (P.V.)

8. prednaska 16/IV/2003 (P.V.)

9. prednaska 23/IV/2003 (P.V.)

10. prednaska 30/IV/2003 (P.V.)

11. prednaska 7/V/2003 (P.V.)