tree-depth-proba.js

// success(depth: number, numTries: number, q: number)
//
// Compute the probability to generate at least one tree with depth superior to `depth`
// Given we tried `numTries` times with a probality of having a node of q
//
// with:
//   type Tree<T> = Node<T> | Leaf<T>
//   type Node<T> = { left: Tree<T>, right: Tree<T> }
//   type Leaf<T> = T
//
// Limitations: `depth` cannot be too high given it will overflow (around 10 for the max)

const factorialCache = {};
const factorial = n => {
	if (n === 0n) return 1n;
	if (factorialCache[n]) return factorialCache[n];
	const v = n * factorial(n - 1n);
	factorialCache[n] = v;
	return v;
};

const binom = (n, k) => factorial(n) / (factorial(k) * factorial(n - k));

const pCache = {};
const p = (n, m, q) => {
	if (n === 0) return 1;
	const key = `${n},${m},${q}`;
	if (pCache[key]) return pCache[key];

	let v = 0;
	for (let i = 1 ; i <= m ; ++i) {
		v += Number(binom(BigInt(m), BigInt(i))) * (q**i) * ((1- q)**(m-i)) * p(n - 1, i * 2, q);
	}
	pCache[key] = v;
	return v;
}

const success = (depth, numTries, q) => {
	const pOne = p(depth, 1, q);
	return 1 - (1 - pOne) ** numTries;
}

// Example:
// success(5, 100, 1/3)