Tämä on vuorovaikutteinen tehtävä.
Laiska Sam ja ahkera Sarah ovat saaneet tehtäväkseen keksiä kaksi mielenkiintoista todennäköisyysjakaumaa aakkoston $\{H, T\}$ pituutta $n$ olevien merkkijonojen joukolle. Laiska Sam yksinkertaisesti heittää kolikkoa $n$ kertaa (kumpikin puoli esiintyy todennäköisyydellä $\frac{1}{2}$; kaikki kolikonheitot ovat riippumattomia) ja kirjoittaa ”H” jokaisesta kruunasta ja ”T” jokaisesta klaavasta. Haluat auttaa ahkeraa Sarahia antamaan laiskalle Samille opetuksen. Sinulle annetaan kokonaisluku $t$. Auta Sarahia keksimään jakauma, joka on $t$-lähellä tasajakaumaa, samalla kun todistat vuorovaikutteisesti, että pystyt erottamaan laiskan Samin ja ahkeran Sarahin jakaumat toisistaan pituuden $t$ oraakkelipääsyllä.
Muodollisesti, jollekin kokonaisluvulle $n$, tarkastellaan kokoa $2^n$ olevaa joukkoa $S = \{H, T\}^n$, joka koostuu kaikista mahdollisista pituuden $n$ merkkijonoista kahden merkin ”H” ja ”T” aakkostolla. Jakauma joukolla $S$ määritellään joukon $S$ alkioilla indeksoiduksi pituuden $2^n$ ei-negatiivisten reaalilukujen taulukoksi $\{a_s\}_{s \in S}$, jolle lukujen summa on $1$. Yksi yksinkertaisimmista jakaumista on tasajakauma, jossa kaikki $a_s$ ovat yhtä suuria kuin $2^{-n}$.
Lukuparille $\varepsilon \in [0; +\infty)$ ja $k \in \{0, 1, \dots, n\}$ sanomme, että $\{a_s\}_{s \in S}$ on $(\varepsilon, k)$-riippumaton jakauma, jos mille tahansa $k$:n indeksin valinnalle $1 \le i_1 < i_2 < \dots < i_k \le n$ ja mille tahansa aakkoston $\{H, T\}$ pituuden $k$ merkkijonojen osajoukolle $T \subseteq \{H, T\}^k$ pätee seuraava: lukujen $a_s$ summa niiden $2^{n-k}|T|$ merkkijonon $s$ yli, joiden osajono $s[i_1]s[i_2]\dots s[i_k]$ kuuluu joukkoon $T$, poikkeaa arvosta $\frac{|T|}{2^k}$ enintään $\varepsilon$. Todennäköisyyslaskennan termein tämä voidaan ilmaista muodossa:
$$\forall 1 \le i_1 < i_2 < \dots < i_k \le n \quad \forall T \subseteq \{H, T\}^k \quad \frac{|T|}{2^k} - \varepsilon \le \mathbb{P}_{s \leftarrow \{a_s\}_{s \in S}} \{s[i_1]s[i_2]\dots s[i_k] \in T\} \le \frac{|T|}{2^k} + \varepsilon.$$
Intuitiivisesti tämä tarkoittaa, että erottaaksesi jakauman tasajakaumasta sinun täytyy joko erottaa todennäköisyydet, joiden erotus on enintään $\varepsilon$, tai tarkastella useampaa kuin $k$:ta bittiä jakauman tuottamissa merkkijonoissa.
Jakaumaa $\{a_s\}_{s \in S}$ kutsutaan $t$-läheiseksi tasajakauman kanssa, jos se on $(2^{-t}t, t)$-riippumaton.
$(\varepsilon, k)$-riippumattomuuden määritelmässä oletettiin epäsuorasti, että sinun on ensin valittava $k$ indeksiä ja vasta sitten tutkittava todennäköisyysjakaumaa näillä $k$:lla indeksillä. Pituuden $k$ oraakkelipääsymallissa kaikki on toisin. Luodaan satunnainen pituuden $n$ merkkijono, ja sen jälkeen suoritetaan $k$ kierrosta seuraavassa muodossa: ilmoitat kokonaisluvun $i \in \{1, 2, \dots, n\}$, ja vastauksena sinulle kerrotaan $s[i]$. Voit päättää, mitä indeksiä kysyt seuraavaksi, ottaen huomioon kaikki aiemmin esitetyt kysymykset ja niiden vastaukset.
Todistaaksesi, että pystyt erottamaan laiskan Samin ja ahkeran Sarahin jakaumat, sinun tulee – kun käytössäsi on pituuden $t$ oraakkelipääsy heidän jakaumistaan poimittuun $m$:ään pituuden $n$ merkkijonoon (joista jokainen on luotu riippumattomasti ja tasajakautuneesti joko laiskan Samin tai ahkeran Sarahin jakaumasta) – päätellä jokaisesta niistä, kumman jakaumasta se on otettu, ja arvata oikein vähintään $0.75m - 2\sqrt{m}$ kertaa.
Vuorovaikutusprotokolla
Ensimmäinen rivi sisältää kokonaisluvun $t$, joka ilmaisee vaaditun läheisyyden tasajakaumaan sekä oraakkelipääsyn pituuden ($1 \le t \le 5$).
Tulosta vastauksena rivi, jolla on yksi kokonaisluku $n$, joka ilmaisee niiden merkkijonojen pituuden, joille olet valmis antamaan jakauman ja vuorovaikutteisen todistuksen erotettavuudesta ($t \le n \le 20$).
Tulosta seuraavalle riville $2^n$ kokonaislukua $b_s$, jotka määrittelevät jakaumasi ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). Näiden tietojen perusteella tuomaristo valitsee jakauman $\{a_s\}_{s \in S}$ säännön $a_s = b_s / \sum_{s \in S} b_s$ mukaisesti. Lukujen $b_s$ arvot on lueteltava merkkijonojen $s$ aakkosjärjestyksessä: esimerkiksi kun $n = 3$, luvut tulee tulostaa seuraavassa järjestyksessä: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.
Lue seuraavaksi kokonaisluku $m$, joka ilmaisee vuorovaikutteisten tarkistusten lukumäärän ($1 \le m \le 10^4$). Tämän jälkeen esitetään $m$ tarkistusta, jotka on suoritettava yksi kerrallaan.
Jokaisen tarkistuksen alussa tuomaristo valitsee ensin jakauman $\{a_s\}_{s \in S}$ joko laiskalta Samilta tai ahkeralta Sarahilta todennäköisyydellä $\frac{1}{2}$. Sen jälkeen tuomaristo poimii satunnaisen merkkijonon $s \sim \{a_s\}_{s \in S}$: mikä tahansa merkkijono $s$ voidaan saada todennäköisyydellä $a_s$. Tuomaristo antaa sinulle sitten mahdollisuuden esittää enintään $t$ kysymystä merkkijonon $s$ merkeistä. Esittääksesi kysymyksen tulosta rivi, jolla on kokonaisluku $q \in \{1, 2, \dots, n\}$, joka ilmaisee haluamasi merkin indeksin. Lue sen jälkeen merkki ”H” tai ”T”, joka on vastaus kyselyyn. Esitettyäsi $0$ – $t$ kysymystä tulosta rivi, jolla on nimi ”Sam”, jos uskot merkkijonon $s$ olevan peräisin laiskan Samin jakaumasta, tai ”Sarah”, jos uskot merkkijonon $s$ olevan peräisin ahkeran Sarahin jakaumasta. Siirry tämän jälkeen välittömästi seuraavaan tarkistukseen, kunnes olet suorittanut kaikki $m$.
Merkkijonot voidaan tulostaa isoilla tai pienillä kirjaimilla.
Muista tyhjentää tulostepuskuri (flush) jokaisen tulostetun rivin jälkeen.
Esimerkki
Syöte 1
2 3 T T T T T
Tuloste 1
3 7 4 8 9 7 6 7 1 1 2 SAM 1 2 Sarah 3 sARaH