Keskustelu: Yleinen keskustelu: Odotusarvotehtävä

Tässä tulee matematiikan taitajille tehtävä, jota olen turhaan yrittänyt ratkaista.

Muodostetaan lukujono arpomalla n kertaa luku väliltä [-1, 1] (tasajakauma). Lukujonosta voidaan löytää suurin perättäisten lukujen summa. Mikä on tämän summan odotusarvo eri n:n arvoilla?

Esimerkiksi jos n = 4 ja arvotaan luvut (0,8, -0,2, 0,3, -0,7), suurin perättäisten lukujen summa on 0,9, jonka tuottavat kolme ensimmäistä lukua.

Jos n = 1, odotusarvo on selvästi 0. Integroimalla voi laskea, että odotusarvot tapauksille n = 2 ja n = 3 ovat 5/12 ja 11/16. Tästä eteenpäin integrointi tuntuu kuitenkin muuttuvan vaikeaksi.

Miten odotusarvon voisi laskea suuremmilla n:n arvoilla?

Ihan tarkennuksen vuoksi: Miten määritellään suurin perättäisten lukujen summa yleisesti, jos luvut ovat x_1, x_2,...x_n?

onko se

max (x_i+...+x_{i+k}), missä 0 <= k <= n-i ja 1 <= i <= n?

Jaska kirjoitti:

max (x_i+...+x_{i+k}), missä 0 <= k <= n-i ja 1 <= i <= n

Tämä määritelmä on oikea.

Olenkohan nyt ymmärtänyt satunnaislukujen odotusarvon luonteen väärin vai onko koodissani bugi tai satunnaislukuni huonoja... Olen ollut siinä käsityksessä, että jos suoritetaan riittävän monta testiä, niin tulosten keskiarvon pitäisi lähestyä odotusarvoa.

Kuitenkaan tässä tapauksessa kun ajan puoli miljoonaa kertaa, niin ainoa mistä saan noiden Antin odotusarvojen kaltaisen vastauksen on 1 numero. Pidemmillä sarjoilla vastauksista tulee joka ajokerralla eri.

Minäkin olen yrittänyt arvioida odotusarvoja kuvaamallasi tavalla, mutta minun ohjelmani tulokset ovat hyvin lähellä laskemiani tarkkoja odotusarvoja.

Siis joko sekä ohjelmani toimii väärin että olen laskenut väärin tai sitten ohjelmasi toimii väärin.

Ok. Pitäisi etsiä varmaan jostain läjä laadukkaiksi tunnettuja satunnaislukuja, tai sitten olen vaan puusilmä enkä näe mikä koodissa olisi vikana.

Ymmärsinhän nyt oikein, että jos on vaikka 4 luvun joukko satunnaislukuja, sanotaanko { a b c d } niin haettu suurin peräkkäisten lukujen summa on suurin seuraavista: a+b+c+d, a+b+c, b+c+d, a+b, b+c, c+d, a, b, c ja d? Vai jätetäänkö 1 numeron pituiset pois? (jossa tapauksessa tosin tuo 1 elementin systeemi ei olisi laskettavissa)

Kyllä olet ymmärtänyt oikein, myös yhden numeron "summat" ovat mukana.

Tuossa on oma ohjelmani odotusarvojen arviointiin:

Function Testi(maara As Integer) As Double
    ReDim taulu(maara) As Double
    Dim i As Integer
    For i = 1 To maara
        taulu(i) = Rnd * 2 - 1
    Next
    Dim summa As Double
    Dim suurin As Double
    summa = taulu(1)
    suurin = taulu(1)
    For i = 2 To maara
        If summa > 0 Then
            summa = summa + taulu(i)
        Else
            summa = taulu(i)
        End If
        If summa > suurin Then
            suurin = summa
        End If
    Next
    Testi = suurin
End Function

Private Sub Form_Load()
    Randomize Timer
    Dim maara As Integer
    Dim testit As Long
    maara = 3
    testit = 100000
    Dim summa As Double
    Dim i As Long
    For i = 1 To testit
        summa = summa + Testi(maara)
    Next
    MsgBox summa / testit
End Sub

Tässä vastaavasti omani. Näköjään sama kieli ja samat satunnaisluvut. Nyt vaan tutkin sitten sinun koodisi ja katson miksi tulee eri tulos :D

Nähtävästi teen asian vaikeammin, mutta se ei toki itsestään selitä miksi tulos on eri.

Option Explicit
Private Const Loops = 500000
Private Sub Form_Load()
    Randomize Timer
    Dim i As Long, j As Long, k As Long, l As Long, m As Double, am As Double, test As Double, r(10) As Double
    For i = 1 To 4
        am = 0
        For j = 1 To Loops
            For k = 1 To i
                r(i) = Rnd(1) * 2 - 1
            Next
            m = -100
            For k = 1 To i
                test = 0
                For l = k To i
                    test = test + r(l)
                    If test > m Then m = test
                Next
            Next
            am = am + m
        Next
        List1.AddItem i & vbTab & (am / Loops)
    Next
End Sub

EDIT: Hehe, ei voi olla näin sokea

For k = 1 To i
r(i) = ...

:D

Kyllähän se nyt antaa oikeita vastauksia, kun korvasin i -> k

Tässä on tiettävästi toimiva testiohjelma Pythonilla:

import random

def testaa(n, testeja):
    odotusarvo = 0
    for k in xrange(0, testeja):
        summa, paras = 0, -1
        for i in xrange(0, n):
            x = random.random() * 2 - 1
            summa = max(x, summa + x)
            paras = max(summa, paras)
        odotusarvo = odotusarvo + paras / testeja
    return odotusarvo

print testaa(3, 100000) # * 16 / 11 # jos halutaan prosentteina oikeasta

Yritin lähestyä tehtävää monelta eri kannalta, mutta jostakin syystä sain vääriä vastauksia jo tapauksesta n = 2. Täytynee yrittää vielä, mielenkiintoinen tehtävä.

Sain nyt mietittyä ohjelmani. Minua hämäsi aluksi se, saako tyhjä jono olla mukana. Tarkempi yo. viestien lukeminen olisi paljastanut, että sitä ei sallita. Tein sitten ohjelmasta sellaisen version, jossa Boolean-argumentilla voi päättää, onko tyhjän valinta mukana laskuissa vai ei.

Minun ja Metabolixin ohjelman periaate selviää lukemalla tämä juttu (in English), jos se ei ole tuttu:

http://wordaligned.org/articles/the-maximum-subsequence-problem

Tässä nyt se koodi. Oikeastaan se on vain muunnos Metabolixin ohjelmasta.

# -*- coding: latin-1 -*-

import random

def testaa(n, testejä, salli_tyhjä = False):
    odotusarvo = 0
    for k in xrange(0, testejä):
        paras_tähän, paras_kaikista = [(0,-1),(0,0)][salli_tyhjä]
        for i in xrange(0, n):
            x = random.uniform(-1, 1)
            paras_tähän = max([x,0][salli_tyhjä], paras_tähän + x)
            paras_kaikista = max(paras_tähän, paras_kaikista)
        odotusarvo += paras_kaikista
    return odotusarvo / testejä

print "yksi, ei", testaa(1, 100000)
print "kaksi, ei", testaa(2, 100000)
print "kolme, ei", testaa(3, 100000)
print "neljä, ei", testaa(4, 100000)

print

print "yksi, joo", testaa(1, 100000, True)
print "kaksi, joo", testaa(2, 100000, True)
print "kolme, joo", testaa(3, 100000, True)
print "neljä, joo", testaa(4, 100000, True)

Tuo Boolean-argumetin käyttö valitsimessa on eräiden koodareiden paha tapa (kuten minun). Se toimii, koska tosi muuttuu ykköseksi ja epätosi nollaksi, joten sillä vain valitaan sopivat arvot. Rumaahan se, mutta niin minäkin :) :)

Minkälaisella kaavalla tällaista satunnaislukujen oletusarvoa yleisesti ottaen pystyy laskemaan.

Ihan yksinkertaisimmillaan jos miettii että on kaksi lukua väliltä 0 ja 1, niin mikä on suuremman luvun odotusarvo. Vastaushan on 2/3, mutta en oikein keksi millä kaavalla tuohon tulokseen voisi päätyä.

Jos teen luvuista epäjatkuvia, eli tyyliin noppia ja kasvatan silmien määrää äärettömiin, niin voin toki laskea vastauksen. Silloin saan lukujonon joka lähestyy 2/3, mutta en keksi mitään kaavaa lukujonon osoittajaan. Nimittäjäksi saan kyllä n^2*(n-1).. Siis lukujono on (sieventämättömänä) 3/4, 13/18, 34/48, 70/100, 125/180, 203/294, 308/448 jne.

Tai no, itseasiassahan tuo osoittajan kaava on ihan yksinkertainen.
Sum(k = 1->n ) (2k^2 - 3k + 1)

Kai tuosta sitten olisi ihan perusmatematiikkaa laskea arvo kun n lähestyy ääretöntä. Pitäisi varmaan palata koulun penkille :D

Äkkiseltään tulee myös mieleen, että näinkin yksinkertaiseen hommaan voisi olla jokin helpompikin lähestymistapa..

Yksi konsti on laskea odotusarvo integroimalla kahden "silmukan" avulla. Toisessa tapauksessa x < y ja toisessa y < x.

Tapaus x < y:
∫₀¹∫_x¹ y dy dx = 1/3

Tapaus y < x:
∫₀¹∫_y¹ x dx dy = 1/3

Yhteensä: 1/3 + 1/3 = 2/3

Tapaus x < y ohjelmoijan tulkintana:

' e on mielivaltaisen pieni
For x = 0 To 1 Step e
    For y = x To 1 Step e
        o = o + y * (e ^ 2)
    Next
Next