simfork.lua

-- Monte Carlo Simulation of state machine in paper

-- Make one attempt to reach state 1000, fail at zero
function attempt (p)
    local state = 2    
    local ups = 1
    
    while state > 0 do
        if state > 1000 then
            -- attempt succeeded
            return 0
        end
        
        if math.random() < p then
            state = state +1
            ups = ups + 1
        else
            state = state -1
        end
    end

    -- attempt failed, return number of orphans
    return ups
end

-- Make an attempt to succeed and keep retrying until successful, counting orphans
function persist(p)
    local orphans = 0
    repeat
        local t = attempt (p)
        orphans = orphans + t
    until t == 0
       
    return orphans
end

-- Make lots of runs to success to estimate expected number of orphans
function orphancalc (p)
    local limit = 100000
    local totalorphans = 0
    for i = 0, limit -2 do
        totalorphans = totalorphans + persist(p)
    end
    print(p, totalorphans / limit)
end

-- Make lots of attempts to estimate success probability
function attemptcalc (p)
    local limit = 100000
    local successes = 0
    for i = 0, limit -2 do
       if attempt (p) == 0 then
           successes = successes + 1
       end
    end
    
    print(p, successes / limit)
end

math.randomseed (os.time())
local p = tonumber(arg[1])
attemptcalc (p)
orphancalc (p)