Iteroidut erotukset

Enkä analysoi!

Hypoteesini:

Jakauma on symmetrinen nollan ympäri ja ulottuu 2**(k-1):een asti.
Perustelu: Jos ykköset ja nollat vaihdetaan, niin jokainen luku muuttuu vastaluvukseen joka iteraatiossa. Joka tasolla voi suurin esiintyvä luku olla itseisarvoltaan maksimissaan 2 kertaa edellisen suurin (kun otetaan edellisen maksimi - edellisen minimi, niin saadaan tämä kaksinkertainen (kun induktiivisesti oletetaan että ne olivat nuo mainitut -2**(k-1):t)). Nämä saavutetaan alternoivilla jonoilla.

On väliköitä, jotka eivät esiinny ollenkaan. Nämä tulevat tietyissä pötköissä ja "hyville luvuille" (kuten 5 ja 7 olisiko että alkuluvulle(??)) myös pötköjen välit ovat säännölliset (kun taas esim 8:lle hypyt näyttäisivät menevän 4,6,4,6,...). Ne alkavat näin (merkitsen vain positiivisen puolen symmetrisyyden takia):

2: []
3: []
4: [5]
5: [2, 3, 7, 8, 12, 13] (kahden pituinen pötkö, hyppy 4)
6: [7, 8, 13, 14, 21, 22, 23, 27, 28, 29] (pötkö: 2, hypyt: 5, 7, ei mutta sitten onkin kolmen pituinen, hylätään tämä pötkö hypoteesi nyt ainakin yhdistetyille luvuille).
7: [2, 3, 4, 5, 9, 10, 11, 12, 16, 17, 18, 19, 23, 24, 25, 26, 30, 31, 32, 33, 37, 38, 39, 40, 44, 45, 46, 47, 51, 52, 53, 54, 58, 59, 60, 61] (pötkö: 4, hyppy: 4)

Noh, nämä käyvät jo pitkiksi niin en enää laita mutta kasilla on tuo 3:sta lähtevä 3 pituinen pötkö ja hypyt sitten menee miten menevätkään.

Lisäksi ainakin hyvillä luvuilla on aina siten, että missä todennäköisyyttää onkaan niin siinä on keskellä piikki ja sen sivuilla symmetrisesti, niinkuin jossain fraktaalirakenteessa.

Menisikö kone niin, että se on edellisen linjagraafi? Siirtymistä tulee solmuja ja siirtymät jos eka menee tilaan josta toinen lähtee. Ja tn tulee vissiin aina olemaan puoli kaikissa siirtymissä.
Kokeilin simuloinnilla laskea koneen siirtymiä siten, että tiloina vain mahdolliset esiintyvät lukuarvot:

https://pastebin.pl/view/1695c233

Kyllähän se näyttä oikean tuloksen antavan, mutta matriisin muodosta en kyllä nää mitään kaavamaisuuksia.

Lähtökonehan on tietysti 1/2 * [[1,1], [1,1]]
Ja seuraava on helppo keksiä ottamalla neljä tilaa: joko ollaan miinusykkösen puolella tai plus ykkösen ja kummallakin puolella on oma nollansa. Kone on 1/2[[1,0,1,0], [1,0,1,0], [0,1,0,1], [0,1,0,1]]. Steadystate on vakiovektori 1/4(1,1,1,1). Mutta nollalla oli kaksi tilaa, joten se on kaksi kertaa todennäköisempi kuin muut eli puolet tulee pitkässä juoksussa olemaan nollia ja yksneljäsosat plus ja miinus ykkösiä.
Tuo jälkimmäinenhän tulisi linjagraafina ( https://en.wikipedia.org/wiki/Line_graph#Line_digraphs )
Hmm... pitääpä katsoa miten seuraava (k=2) linjagraafi muodostuisi.

Sehän on De Brujinin verkko: https://en.wikipedia.org/wiki/De_Bruijn_graph

Samahan se tosiaan on vaikka pidettäisiin muistissa koko k-pituinen binäärijono ja tutkitaan kaikkia mahdollisia tällaisia. Mutta sitten ne romahdutetaan erotuksiin.

Tässä yksinkertaisempi tapa tuottaa todennäköisyydet:

https://pastebin.pl/view/38ad62d0

Eli luvun j todennäköisyys on suhteessa sen alkukuvan kokoon funktiossa

p: {0,1}^(k 1) -> Z,
p(x) = sum((-1)**(k j 1)*binomial(k, j)*x_j)

Sain tehtyä Desmokseen funktion arvojen histogrammin piirtäjän:

https://www.desmos.com/calculator/odcy0nxgvu

Parametriä k voi muutella liukusäätimestä ja koordinaatistoa zoomata ja siirrellä. Katsokaapa miten säännöllinen alkuluvuille tulee! Ei kannata kuitenkaan k:ta liian suureksi laittaa ettei jumita (jätin nyt ylärajaksi 10, mutta sitäkin voi toki itse muuttaa).

Tein lisäksi tuollaisen yleisen Python koodin, joka laskee hyperkuution {0,1}^k kuvan (multijoukkona) lineaarisessa polynomissa c1*x1 ... ck*xk.

https://pastebin.pl/view/7e7889bd

Se on melko nopea, kunhan eri kuvapisteitä ei tule paljoa. Mutta tässähän (kun kertoimet ovat itseisarvoltaan niin suuria), niin kuvapisteitä tulee mahdollisesti paljon. Pitäisikin katsoa kuinka kuvan koko kasvaa.

Hypoteesini on että alkuluvuille tulee aina kolmi-piikkejä joissa keskimmäinen on kaksi kertaa niin suuri kuin sen vieressä olevat (jotka ovat yhtäsuuret keskenään). Suuremmilla arvoilla (kuten k=11) taitaa tulla pitempiäkin tyhjiä jaksoja, joten piikeillä ei aina tasavälit ole (mutta onkohan siten, että siellä välissä on piikki, mutta se on vain arvoltaan 0,0,0 ??).

Selvennetään nyt tehtävää alkuperäisestä sen verran, että n=k 1 ja iteroidaan niin pitkään kunnes jää vain yksi luku (eli k kertaa) ja sitten kysytään millä todennäköisyydellä tämä luku saa minkäkin arvon. Sillä sehän on sama asia kuin jos n olisi suuri ja tarkasteltaisiin pitkää jonoa lukuja, joka k-iteraation jälkeen saatiin.
Se lineaarimuoto, jossa on alternoivat binomikertoimet on juuri k 1:stä luvusta x0,x1,.., xk saatava iteroitu erotus ja sen arvojahan tässä juuri kysytään, kun muuttujat x0, x1, .., xk saavat arvoja joukosta {0, 1}.