tree branch problem/simulator

[vh]

First there is one branch on a tree (the trunk)
after one step, the branch flips two coins. for each heads that appears, a new branch will grow off that branch.
after another step, the newly created branches will also each flip two coins, and for each heads that appears a new branch.

on average, how long will the tree take to stop growing?

[tuto99]

Wouldn't the tree growth fluctuate? Because let's say I have a coin, and if I get heads, another person comes in with a coin, and if he gets heads but I get tails, only one person joins. You know?

[vh]

yes, it will fluctuate, and on average it will stay the same.

[vh]

this code here simulates the problem described above

Code: [Select]

from numpy.random import binomial

def step(flip):
    result = binomial((2*flip),0.5)
    return result

while 1:
    derp = 4
    steps = 0
    while derp > 0:
        derp = step(derp)
        steps = steps + 1
    print steps

[vh]

this code will print out the result when it is over 1 million steps. which happens every 10 seconds or so.

the largest value i've seen so far is 3806368

edit: holyshit it just outputted a 14320876

Code: [Select]

from numpy.random import binomial

def step(flip):
    result = binomial((2*flip),0.5)
    return result

while 1:
    derp = 4
    steps = 0
    while derp > 0:
        derp = step(derp)
        steps = steps + 1
    if steps > 999999:
        print steps

[vh]

this code output the total amount of branches every grown. for a 2.7 millions step tree, this amount is around 400 billion

from numpy.random import binomial

def step(flip):
    result = binomial((2*flip),0.5)
    return result

while 1:
    derp = 4
    steps = 0
    size = 0
    while derp > 0:
        perp = step(derp)
        derp = perp
        steps = steps + 1
        size = size + perp
    if steps > 999999:
        print steps, size

[vh]

*change derp to 1 to match the original problem

[vh]

final code, will print commas in numbers for easy reading

Code: [Select]

from numpy.random import binomial
def intWithCommas(x):
    if type(x) not in [type(0), type(0L)]:
        raise TypeError("Parameter must be an integer.")
    if x < 0:
        return '-' + intWithCommas(-x)
    result = ''
    while x >= 1000:
        x, r = divmod(x, 1000)
        result = ",%03d%s" % (r, result)
    return "%d%s" % (x, result)
def step(flip):
    result = binomial((2*flip),0.5)
    return result
trial = 0
while 1:
    derp = 1
    steps = 0
    size = 0
    while derp > 0:
        perp = step(derp)
        derp = perp
        steps = steps + 1
        size = size + perp
        trial = trial + 1
    if steps > 99999:
        print intWithCommas(trial), intWithCommas(steps), intWithCommas(size)

[vh]

this version has a filter

Code: [Select]

from numpy.random import binomial
def intWithCommas(x):
    if type(x) not in [type(0), type(0L)]:
        raise TypeError("Parameter must be an integer.")
    if x < 0:
        return '-' + intWithCommas(-x)
    result = ''
    while x >= 1000:
        x, r = divmod(x, 1000)
        result = ",%03d%s" % (r, result)
    return "%d%s" % (x, result)
def step(flip):
    result = binomial((2*flip),0.5)
    return result
trial = 0
filter = input('filter    ')
while 1:
    derp = 1
    steps = 0
    size = 0
    while derp > 0:
        perp = step(derp)
        derp = perp
        steps = steps + 1
        size = size + perp
        trial = trial + 1
    if steps > filter-1:
        print intWithCommas(trial), intWithCommas(steps), intWithCommas(size)

[vh]

this version will only print the largest step, which for me, is about 80 million, with 1,347 trillion branches

from numpy.random import binomial
import os
def intWithCommas(x):
    if type(x) not in [type(0), type(0L)]:
        raise TypeError("Parameter must be an integer.")
    if x < 0:
        return '-' + intWithCommas(-x)
    result = ''
    while x >= 1000:
        x, r = divmod(x, 1000)
        result = ",%03d%s" % (r, result)
    return "%d%s" % (x, result)
def step(flip):
    result = binomial((2*flip),0.5)
    return result
trial = 0
filter = 0
while 1:
    derp = 1
    steps = 0
    size = 0
    while derp > 0:
        perp = step(derp)
        derp = perp
        steps = steps + 1
        size = size + perp
        trial = trial + 1
    if steps > filter:
        filter = steps
        os.system('cls')
        print intWithCommas(trial), intWithCommas(steps), intWithCommas(size)

[atomic7732]

1432 guess