"Opettavainen esimerkki"

[vastaus aiempaan viestiin]

Palaan vielä tähän Hessun esittämään tehtävään erityisesti
"opettavaisena esimerkkinä".

Ratkaisun olennainen osa on laskea pienimmän pisteluvun odotusarvo.
Olipa jäänyt huomaamatta, että sen yleinen lauseke on esitettävissä
n-nopalla ja yleisesti m rippumattoman heiton tapauksessa varsin
sievässä summamuodossa

              n
(1) E(m,n) = SUM (k/n)^m
             k=1

eli Survon kielellä

E(m,n):=for(k=1)to(n)sum((k/n)^m)

Siis esim. alkuperäisessä tilanteessa m=3, n=6
E(3,6)=2.0416666666667
ja aukikirjoitettuna aikaisempaa yksinkertaisemmin

(1^3+2^3+3^3+4^3+5^3+6^3)/6^3=2.0416666666667

Tämä johtuu siitä, että vaikka todennäköisyyksiä

P(m,n,k):=((n-k+1)/n)^m-((n-k)/n)^m  (k=1,2,...,n)

ei saa nätimmiksi, niiden muuttujan arvoilla painotettu summa

E1(m,n):=for(k=1)to(n)sum(k*P(m,n,k))

(eli määritelmän mukainen odotusarvo) on helppo supistaa muotoon (1)
peräkkäisten termien kumotessa osittain toisiansa.

            * * *

En huomannut tätä olennaista yksinkertaistusta ilman osittaista
"arvailulaskentaa", missä päättelin seuraavasti:

Näytin jo ensimmäisessä viestissä, että

(Pol3) E(3,n) = (n+1)^2/(4*n)                   "Polynomi"

mikä on tietenkin yksinkertaisempi esitys kuin kaavan (1) mukainen

(Pot3) E(3,n) = (1^3+2^3+3^3+4^3+...+n^3)/n^3   "Potenssisumma"

Vastaavanlaiset rinnakkaisesitykset tapauksessa m=4 ovat

(Pol4) E(4,n) = 1/30*(6*n^5+15*n^4+10*n^3-n)/n^4
ja
(Pot4) E(4,n) = (1^4+2^4+3^4+4^4+...+n^4)/n^4

Näistä tuloksen (Pol4) määräsin, siis vielä tuntematta Pot-esityksiä,
Survon avulla kokeellisesti arvoilla n=2,3,...8 käyttäen esim.
arvolla n=8 laskentakaaviota

COMB L TO NOPAT.TXT  / L=LATTICE,4 MIN=1,1,1,1 MAX=8,8,8,8
FILE SAVE NOPAT.TXT TO NEW NOPAT
VARSTAT NOPAT,*,SORT
.......................
STAT NOPAT,CUR+1 / VARS=X1 SUMS=1 RESULTS=0
Basic statistics: NOPAT N=4096
Variable: X1       X1 (##)
min=1         in obs.#1
max=8         in obs.#4096
mean=2.1416016 stddev=1.2872884 skewness=1.1458813 kurtosis=0.8478106
sum1=8772
autocorrelation=0.76781
lower_Q=1         median=2         upper_Q=3


josta saadaan E(4,8)=8772/8^4=8772/4096=2.1416015625.
Kun tarkastellaan näiden lukujen osoittajia arvoilla n=1,2,...,8,
(nimittäjinä luvut n^4), sain lukujonon alkupään
1,17,98,354,979,2275,4676,8772
ja kutsuin apuun verkosta kokonaislukujonojen "tietosanakirjan" (OEIS)
http://oeis.org/ 
jonka hakukenttään syötin nuo luvut ja OEIS tarjosi tulokseksi

A000538: Sum of fourth powers 0^4+1^4+...n^4

ja samalla (Pol4)-kaavaa vastaavan lausekkeen.

Vasta kun näin tämän, "arvasin" yleisen tuloksen (1) ja ihmettelin
jonkin aikaa, kunnes tajusin, miten siihen päästään suoraan.
Tämänhän kerroin tämän viestini alussa.
Ilman tällaista hapuilua (1) saattaisi olla vieläkin minulta
tietymättömissä.

            * * *

Pol Pot -vertailua:
(Huom. ei mitään tekemistä Kamputsean entisen diktaattorin kanssa:)

OEIS kertoi myös, että esityksen (Pol4) summaosan, mutta varmaankin aika
erilaisilla merkinnöillä, on esittänyt (persialainen) matemaatikko
al-Kachi jo 1400-luvun alussa.
Saksalainen Johann Faulhaber kykeni löytämään oikeat polynomilausekkeet
tapaukseen (Pol23) asti 1600-luvun alussa.
Niinpä summien 1^m+2^m+...+n^m "Pol"-esitykset tunnetaan nykyisin
Faulhaberin kaavoina ja niistä kerrotaan mm. Wikipedia-artikkelissa
http://en.wikipedia.org/wiki/Faulhaber's_formula 

Vasta vuonna 1834 Carl Jacobi todisti nuo kaavat yleisesti.
"Pol"-kaavat näyttävät hyviltä sikäli "Pot"-kaavoihin verrattuna, että
silloin kun ollaan kiinnostuneita tapauksista, joissa m on pieni lukuun
n verrattuna, "Pol"-kaavoilla yhteenlaskettavia on vain noin m kpl,
mutta "Pot"-kaavoilla niitä on n kpl.

Pienillä arvoilla "Pol"-kaavat m=1,2,3,4 ovat todellisia klassikoita.
Yleisillä m-arvoilla "Pol"-kaavat ovat sikäli konstikkaampia, että ne
sisältävät termiensä kertoimina sekä hieman hankalia Bernoulli-lukuja
että binomikertoimia.

Nykyisin numeerinen laskenta koneilla on kuitenkin niin nopeaa, että
tyytyisin käyttämään "Pot"-kaavaa käytännössä.
Esim. jos miljoonasta ensimmäisestä kokonaisluvusta valitaan 10 kpl
toisistaan riippumatta umpimähkään, niin niistä pienimmän odotusarvo
saadaan nykyisellä koneellani Survolla "Pot"-kaavaa käyttäen
seuraavasti:

E(m,n):=for(k=1)to(n)sum((k/n)^m)

TIME COUNT START              (jatkuva aktivointi F2 ESC sarakkeelta 12)
E(10,10^6)=90909.590909925
TIME COUNT END   0.765

Tulos syntyy alle sekunnissa. On huomattava vielä, että editoriaalinen
laskenta Survossa (koska kaikki tapahtuu resursseja kuluttavalla
tulkkiperiaatteeella) vie aikaa ainakin kymmenen kertaa enemmän kuin
ajamalla esim. suoralla, erikseen laaditulla, C-kielisellä ohjelmalla.
"Pot"-kaava (1) lienee täysin riittävä kaikkiin numeerisiin tarpeisiin.

"Pol"-kaavojen merkitys rajoittunee näin lähinnä teoreettisiin
tarkasteluihin.

Oma mielenkiintonsa on sillä, että odotusarvo 90909.59...on tässä
tapauksessa lähellä lukua         10^6/(10+1)=90909.090909091
ja on ilmeinen houkutus päätellä, että asymtoottisesti luvun n kasvaessa
E(m,n) on noin n/(m+1).
Tämä näkyy myös edellä olevista "Pol"-kaavoista Pol3 ja Pol4, mutta ei
ainakaan suoraan niiden yleisestä esityksestä, joka on myös esim.
sivulla
http://mathworld.wolfram.com/FaulhabersFormula.html 
(mutta tässähän saatan erehtyä).

On jälleen arvattavissa, että k:nneksi pienimmän luvun odotusarvo on
asymptoottisesti (alle ykkösen tarkkuudella) k*n/(m+1), k=1,2,...,m eli
nuo odotusarvot jakautuvat käytännössä "tasaisesti" välille (1,n).
Tämä vaikuttaa intuitiivisestikin hyvin uskottavalta.

            * * *

Olisin voinut lopettaa tämän viestin ensimmäiseen *** -riviin.
Kirjoitukseni varsinaisena pontimena on ollut kuitenkin osoittaa
tämän vähäpätöisen todennäköisyysongelman ratkaisun yhteydessä, miten
tärkeätä olisi se, että matemaattisluontointen juttujen ja jopa
julkaisujen yhteydessä jollain tapaa rehdisti kerrottaisiin, miten
todellisuudessa päädyttiin saavutettuihin tuloksiin.
Tyylinä on aina ollut, että artikkelit laaditaan niin viimeistellyiksi,
että kaikki roskat on lakaistu pois ja tekijät näyttäytyvät fiksumpina,
mitä todellisuudessa ovat olleet ongelmia ratkoessaan.
Ennen nykyistä tietoteknologiaa oli ymmärrettävää, että jo
panatuskustannukset huomioon ottaen esityksen tiivistäminen oli kaiken
a&o ja eleganssi ehdoton vaatimus.
Matemaattispitoisissa (painetuissa) julkaisuissa ehkä edelleenkin nämä
perinteiset hyveet vallitkoot, mutta mielestäni monissa tapauksissa
olisi upeaa, jos tekijät laatisivat verkkoon sen todellisen tarinan
kompendiumina, joka avaisi lukijoille mahdollisuudet tarkastella ja
paremmin ymmärtää erilaisia yksityiskohtia sekä toistaa numeeriset ja
symboliset laskennat (ja jopa jatkaa omilla, uusilla tarkasteluilla).

Tällainen käytäntö olisi myös alaa opetteleville varsin hyödyllistä.

Korostan näitä näkökohtia tietenkin myös (rehellisesti) sen vuoksi, että
esim. Survo-tyylillä näiden kompendiumien laatiminen olisi usein
sangen luonnollista, koska tehty työ luonnostaan raportoi tällöin
itsensä.
Siis tämänkin viestin voi siirtää leikepöydän kautta Survon tai Musteen
toimituskenttään ja tarkistella yksityiskohtia.

Seppo Mustonen

Luettelo keskustelunaiheista

Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!