Tangled Trees.ipynb

Kernel: Python 3 (system-wide)

tangled trees

Suppose you draw rows of $n$ evenly spaced dots each, and you take out your favorite set of $m$ $n$-sided dice. For each dot $d$ in the first row, you roll all $m$ dice. For each number $a$ rolled, you draw a line from $d$ to the dot in the row below that is in the column $a$. Continue this process, row by row, until there is some dot in the first row that is connected to every dot in some row---say---row $t$.

What is the expected value of $t ?$

import random as rand

The expected value of how many distinct numbers will be rolled when throwing $m$ $n$-sided dice:

def f_experimental(m,n,s):
    numDict = {}
    for _ in range(s):
        num = len(set([rand.randint(1,n) for i in range(m)]))
        if num not in numDict:
            numDict[num] = 1
        else:
            numDict[num] += 1
    return sum([key * numDict[key] for key in numDict]) / s

f_experimental(5,10,10000)

4.096

Proved: $$f(m,n)=n-\left(\frac{n-1}{n}\right)^{m}$$

def f(m,n):
    return n - n * ((n-1)/(n))**m

f(5,10)

4.0950999999999995

The expected value of the minimum number of rows $t$ so that one of the first dots covers all of the dots on row $t$

def g_helper_experimental(m,n):
    row = [{i} for i in range(1, n + 1)]
    t = 0
#     print(t, row)
    while set(range(1,1+n)).intersection(*row) == set():
        next_row = [set() for _ in range(n)]
        t += 1
        for dot in range(n):
            for _ in range(m):
                new_dot = rand.randint(0,n-1)
                next_row[new_dot] = next_row[new_dot].union(row[dot])
        row = next_row
#         print(t, row)
    return t


def g_experimental(m,n,s):
    t_dict = {}

    for _ in range(s):
        t = g_helper_experimental(m,n)
        if t not in t_dict:
            t_dict[t] = 1
        else:
            t_dict[t] += 1

    return sum([t * t_dict[t] for t in t_dict]) / s

g_experimental(2,6,10000)

7.1819

from IPython.display import display, Markdown

table = "|$n,m$ |" + " | ".join(f"${m}$" for m in range(2,20)) + " | \n"
table += "".join("|:--:" for _ in range(22)) + "|\n"
for n in range(1,20):
    table += f"| **${n}$** "
    for m in range(2,20):
        table += f" | ${g_experimental(m,n,1000)}$"
    table += " |\n"

display(Markdown(table))

|$n,m$ |$2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | $15$ | $16$ | $17$ | $18$ | $19$ | |:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐:--😐 | $1$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | | $2$ | $1.44$ | $1.08$ | $1.02$ | $1.005$ | $1.003$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | | $3$ | $3.023$ | $1.555$ | $1.178$ | $1.061$ | $1.02$ | $1.003$ | $1.0$ | $1.0$ | $1.001$ | $1.001$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | | $4$ | $4.159$ | $2.233$ | $1.736$ | $1.353$ | $1.154$ | $1.059$ | $1.018$ | $1.004$ | $1.003$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | | $5$ | $5.755$ | $2.459$ | $2.073$ | $1.833$ | $1.55$ | $1.301$ | $1.144$ | $1.051$ | $1.027$ | $1.009$ | $1.001$ | $1.001$ | $1.001$ | $1.0$ | $1.001$ | $1.0$ | $1.0$ | $1.0$ | | $6$ | $6.889$ | $2.82$ | $2.129$ | $2.032$ | $1.937$ | $1.694$ | $1.476$ | $1.298$ | $1.151$ | $1.069$ | $1.036$ | $1.014$ | $1.002$ | $1.002$ | $1.0$ | $1.0$ | $1.0$ | $1.001$ | | $7$ | $8.897$ | $3.28$ | $2.238$ | $2.045$ | $2.019$ | $1.968$ | $1.835$ | $1.69$ | $1.477$ | $1.28$ | $1.162$ | $1.083$ | $1.036$ | $1.027$ | $1.006$ | $1.0$ | $1.001$ | $1.0$ | | $8$ | $10.697$ | $3.601$ | $2.386$ | $2.076$ | $2.02$ | $2.004$ | $1.982$ | $1.92$ | $1.792$ | $1.647$ | $1.454$ | $1.272$ | $1.177$ | $1.105$ | $1.049$ | $1.024$ | $1.011$ | $1.006$ | | $9$ | $13.083$ | $3.871$ | $2.572$ | $2.103$ | $2.02$ | $2.01$ | $2.006$ | $1.996$ | $1.964$ | $1.891$ | $1.773$ | $1.641$ | $1.466$ | $1.337$ | $1.204$ | $1.107$ | $1.087$ | $1.033$ | | $10$ | $17.072$ | $4.046$ | $2.853$ | $2.132$ | $2.027$ | $2.009$ | $2.001$ | $2.0$ | $1.997$ | $1.977$ | $1.943$ | $1.856$ | $1.773$ | $1.643$ | $1.476$ | $1.341$ | $1.228$ | $1.155$ | | $11$ | $20.438$ | $4.328$ | $3.08$ | $2.276$ | $2.031$ | $2.005$ | $2.003$ | $2.003$ | $2.0$ | $1.999$ | $1.993$ | $1.978$ | $1.925$ | $1.853$ | $1.735$ | $1.618$ | $1.514$ | $1.389$ | | $12$ | $26.476$ | $4.612$ | $3.205$ | $2.41$ | $2.048$ | $2.008$ | $2.006$ | $2.0$ | $2.0$ | $2.001$ | $1.998$ | $1.994$ | $1.984$ | $1.973$ | $1.92$ | $1.868$ | $1.765$ | $1.644$ | | $13$ | $31.427$ | $4.776$ | $3.29$ | $2.576$ | $2.08$ | $2.015$ | $2.0$ | $2.001$ | $2.0$ | $2.0$ | $2.0$ | $1.998$ | $1.999$ | $1.994$ | $1.977$ | $1.956$ | $1.903$ | $1.839$ | | $14$ | $40.203$ | $5.221$ | $3.347$ | $2.793$ | $2.143$ | $2.015$ | $2.004$ | $2.003$ | $2.0$ | $2.0$ | $2.0$ | $2.001$ | $2.0$ | $1.998$ | $1.997$ | $1.99$ | $1.975$ | $1.952$ | | $15$ | $52.85$ | $5.56$ | $3.379$ | $2.956$ | $2.241$ | $2.015$ | $2.002$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $1.999$ | $2.0$ | $1.996$ | $1.993$ | | $16$ | $65.825$ | $5.788$ | $3.416$ | $3.055$ | $2.374$ | $2.036$ | $2.009$ | $2.002$ | $2.002$ | $2.001$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $1.997$ | | $17$ | $91.185$ | $6.073$ | $3.459$ | $3.087$ | $2.539$ | $2.069$ | $2.012$ | $2.004$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | | $18$ | $115.233$ | $6.29$ | $3.556$ | $3.087$ | $2.699$ | $2.11$ | $2.016$ | $2.004$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | | $19$ | $145.382$ | $6.466$ | $3.637$ | $3.129$ | $2.83$ | $2.178$ | $2.015$ | $2.001$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ | $2.0$ |

Link to plot: https://www.desmos.com/calculator/qnhlthsdip