{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [] }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" } }, "cells": [ { "cell_type": "markdown", "source": [ ">>> THE THEOREMS OF THE MANY MONKEYS\n", ">>>>\n", ">>>> José Rodríguez\n", ">>>>\n", ">>>> jose@ejristos.com\n", ">>>>\n", ">>>> 21 november 2025.\n", ">>>>\n", ">>>> Bogotá, Colombia.\n", "\n", "> *Abstract.*\n", "\n", "\n", "In a previous work, we demonstrated that for randomness, the generation of a binary string identical to a target string is an arduous task, by imagining a system where a monkey attempts to type continuously. In this work, we expand our study to a large number of monkeys to observe the results.\n" ], "metadata": { "id": "rLltY8A8LCe3" } }, { "cell_type": "markdown", "source": [ "\n", "# BASIC PREDICTIONS\n", "\n", "We have studied in [our previous work](https://colab.research.google.com/drive/1sb63vEjlQ2WtEh3iC-6qINaZ2T84tXNB?usp=sharing), the capability of one monkey to match a binary string by tapping at random at a writer machine. We learned that this explains the origin of our DNA but with so small a probability that it is strongly recommended to look for other alternatives. Thus, our plan here is to consider many monkeys instead of one.\n", "\n", "The elementary prediction is that many monkeys do it better than one. So, we need to quantify the advantage. To that aim, our intention is to use, among other tools, the Geometric Distribution that was already used in the previous work. So, let us review it:\n", "\n", "\n", "> *Definition.* The Random Variable $X$ over numbers 0, 1, 2, 3,... with probability of $k$ given by\n", ">>\n", ">> $p(k) = (1-p)^kp$\n", ">>\n", ">> is called the ***Geometric Random Variable***. It is also referred as the ***Geometric Distribution,*** meaning that $X$ follows a distribution determined by $p(k)$. In simpler terms, when repetitions are made, the relative frequency of experiencing $k$ failures before the first success converges to the expected value $p(k).\n", "\n", "To apply this distribution to our scenario with multiple monkeys, we must consider the entire group of monkeys as a single entity and determine the probability of success for the entire ensemble.\n", "\n", "\n", "\n", "The ensemble of monkey succeeds if one monkeys does it. But this also happens if two monkeys succeed or if whatever number of monkey does it. The exact calculation is done by means of the [Binomial Distribution](https://colab.research.google.com/drive/1Opwqqx_CDqV93OzHIm3_MZtRxPdtFSo3?usp=sharing):\n", "\n", "> If the probability of success of one monkey is $a$, the probability of success of $r$ monkeys among $n$ monkey is\n", ">>\n", ">> $ p(r) = $ $n\\choose r$ $p^r (1-p)^{n-r}$\n", ">>\n", "> because $r$ monkeys must succeed and $n-r$ fail. In particular, the probability of global failure is\n", ">>\n", ">> $p(0) = $ $n\\choose 0$ $p^0 (1-p)^{n}$\n", ">>\n", ">> $p(0) = (1-p)^{n}$\n", "\n", "The whole unit of monkeys succeeds if $r >=1$ and, of course, if $r<=n$. Therefore, the probability of success of the ensemble $p(E)$ of $n$ monkeys is\n", "\n", "$ p(E) = p(r >= 1) $\n", ">\n", "> $ = \\sum^n_1 p(r) $\n", ">\n", "> $ = \\sum^n_1 $$n\\choose r$ $p^r (1-p)^{n-r}$\n", ">\n", "> $ = 1- p(0) $,\n", ">\n", "> $ = 1 - (1-p)^n$\n", "\n", "> *Test.* If we have one monkey in the ensemble, the probability of success of the ensemble must be equal to $p$. Is that true? Let us see:\n", ">>\n", ">> $ p(E) = 1 - (1-p)^1 = 1 - (1-p) = 1-1+p = p$\n", ">>\n", ">> as it must be. Our formula passed the test.\n", "\n", "> *Exercise.* We already know the probability of success of the ensemble, $p(E)$, as a unit. What is, then, the probability of $k$ failures before success of the whole ensemble?\n", ">\n", "> *Answer.* When the probability of success, in general, is $p$, the probability of $k$ failures before success $p(k)$ is\n", ">>>\n", ">>> $p(k) = (1-p)^kp$\n", ">>\n", ">> So, when $p = p(E)$, $p(k)$ becomes\n", ">>>\n", ">>> $p(k) = (1-p(E))^k p(E)$\n", ">>>\n", ">>> $ p(k) = (1-( 1 - (1-p)^n))^k ( 1 - (1-p)^n)$\n", ">>\n", ">> where $n$ is the number of monkeys and $k$ is the number of failures before success.\n", "\n", "> *Exercise.* Test the anterior formula: it must reduce to $(1-p)^kp$ if $n = 1$\n", ">\n", ">> *Answer.* If $n=1$,\n", ">>>\n", ">>> $p(k) = (1-( 1 - (1-p) ))^k ( 1 - (1-p))$\n", ">>>\n", ">>> $p(k) = (1- 1 + (1-p) )^k ( 1 - 1+p))$\n", ">>>\n", ">>> $p(k) = ( 1-p)^k p$\n", ">>>\n", ">> We passed the test.\n", "\n", "> *Exercise.* Prove that\n", ">>\n", ">> $\\sum^\\infty_{k = 0} p(k) = 1$\n", ">>\n", ">> If this is true, and since all $p(k)$ are positive, we have the right to say thet $p(k)$ represents a probability.\n", ">>\n", ">> *Answer.*\n", ">>\n", ">> $\\sum^\\infty_{k = 0} p(k) = $\n", ">>\n", ">>> $= \\sum^\\infty_{k = 0}(1-( 1 - (1-p)^n))^k ( 1 - (1-p)^n)$\n", ">>\n", ">> If we rename $1 - (1-p)^n$ as $p$, we get\n", ">>\n", ">>> $\\sum^\\infty_{k = 0} p(k) = \\sum^\\infty_{k = 0}(1-p)^k p $\n", ">>\n", ">> This is the ordinary geometric Distribution provided that\n", ">>\n", ">> $1 - (1-p)^n > 0$\n", ">>\n", ">> This is true because for $ 0 < p < 1$, we have\n", ">>\n", ">> $1 > 1-p > (1-p)^n$\n", ">>\n", ">> from which we get\n", ">>\n", ">> $1-(1-p)^n > 0$.\n", "\n", "> *Interpretation.* The equation\n", ">>\n", ">> $\\sum^\\infty_{k = 0} p(k) = 1$\n", ">>\n", "> is the **Many Monkeys Theorem for infinite time** saying that the ensemble of monkeys will someday succeed and will reproduce whatever text, no matter how complex it could be.\n", "\n", "> *Exercise.* resolve the following objection:\n", ">>\n", ">> *Objection.* The probability of success is in general tiny and that of failure is almost 1. So, nothing prevents that a process may consists of failure after failure even beyond eternity.\n", ">>\n", ">> *Answer.* All failures can be counted and are finite in number. So, you never can claim that you have arrived until infinite. To witness the power of the theorem, just keep experimenting.\n", "\n", "> *Exercise.* Develop the code for 200 repetitions of a simulation of the Geometric Distribution with $p = 0.1$ and a couple of monkeys in order to estimate its distribution, with mean, variance and graph. Do you consider that it pays to make part of a couple?\n", ">\n", "> *Answer.* The code for estimating the distribution of the Geometric Distribution that arises from a couple of monkeys is the following. It is a simple adaptation of the code developed by Gemini for a single monkey. This type of adaptations will be our usual behavior.\n" ], "metadata": { "id": "Bjkt7o7INncs" } }, { "cell_type": "code", "source": [ "# Geometric distribution for two monkeys\n", "import random\n", "import statistics\n", "import matplotlib.pyplot as plt\n", "\n", "def geometric_simulation_trials2(p):\n", " \"\"\"\n", " Simulates a geometric distribution and returns the number of trials until the first success.\n", "\n", " Args:\n", " p: The probability of success (a number between 0 and 1).\n", "\n", " Returns:\n", " The number of trials until the first success.\n", " \"\"\"\n", " trials = 0\n", " while True:\n", " trials += 1\n", " if random.random() < p:\n", " break\n", " else:\n", " if random.random() < p:\n", " break\n", " return trials\n", "\n", "# Parameters for the simulation\n", "p = 0.1\n", "num_repetitions = 200\n", "\n", "# Run the simulation multiple times and store the number of trials\n", "trial_counts = [geometric_simulation_trials2(p) for _ in range(num_repetitions)]\n", "\n", "# Calculate and print the mean and variance\n", "mean_trials = statistics.mean(trial_counts)\n", "variance_trials = statistics.variance(trial_counts)\n", "\n", "print(f\"Mean number of trials after {num_repetitions} repetitions with p={p}: {mean_trials:.2f}\")\n", "print(f\"Variance of the number of trials after {num_repetitions} repetitions with p={p}: {variance_trials:.2f}\")\n", "\n", "# Plot a histogram of the trial counts\n", "plt.figure(figsize=(10, 6))\n", "plt.hist(trial_counts, bins=range(min(trial_counts), max(trial_counts) + 2), density=True, alpha=0.75, edgecolor='black')\n", "plt.title('Estimated Geometric Distribution')\n", "plt.xlabel('Number of Trials Until First Success')\n", "plt.ylabel('Probability Density')\n", "plt.grid(axis='y', alpha=0.75)\n", "plt.show()" ], "metadata": { "id": "MDlmFX-CP1w-" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "We can now compare these results for two monkeys with those for one monkey.\n", "\n", "For two monkeys:\n", ">\n", "> Mean number of trials after 200 repetitions with p=0.1: 5.22\n", ">\n", "> Variance of the number of trials after 200 repetitions with p=0.1: 22.36\n", ">\n", "For one monkey (results of the corresponding program in the previous work):\n", "> Mean number of trials after 200 repetitions with p=0.1: 8.52\n", ">\n", "> Variance of the number of trials after 200 repetitions with p=0.1: 52.27\n", "\n", "We see that the a couple succeeds after a mean of 5.22 trials while one single monkeys need 8.52. Thus, a couple succeeds faster than a lonely cowboy. Also, the mean has more predictive power for two monkeys than for one because the variance for two monkeys is 22.36, while that for one is 52.27.\n", "\n", "Verdict: To form part of a couple pays very good as in average as in its predictive power. This helps to explain why must people prefer to get married -if only we back one another. This also guaranties that sex is a fundamental institution in biology because everything in Biology spins around complexity.\n", "\n", "> *Exercise*. Generalize the previous code from 2 to $n$ monekys.\n", ">\n", "> *Answer.* The generalization for $n$ monkeys is the following:\n", "\n", "\n", "\n" ], "metadata": { "id": "lHoulxyrbs20" } }, { "cell_type": "code", "source": [ "# Geometric distribution for many monkeys\n", "import random\n", "import statistics\n", "import matplotlib.pyplot as plt\n", "import time\n", "\n", "start_time = time.time() # Record the start time\n", "print(\"Program starts\")\n", "\n", "# Parameters for the simulation\n", "p = 0.1\n", "num_monkeys = 10\n", "num_repetitions = 200\n", "\n", "\n", "def geometric_simulation_trials_m(p, n):\n", " \"\"\"\n", " Simulates a geometric distribution and returns the number of trials until the first success.\n", "\n", " Args:\n", " p: The probability of success (a number between 0 and 1).\n", " n: The number of monkeys.\n", "\n", " Returns:\n", " The number of trials until the first success.\n", " \"\"\"\n", " trials = 0\n", " while True:\n", " trials = trials + 1\n", " for _ in range(n):\n", " t = random.random()\n", " # print(f\"t = {t}\")\n", " if t < p:\n", " # print(f\"Number of trials = {trials}\")\n", " return trials\n", "\n", "\n", "\n", "# Run the simulation multiple times and store the number of trials\n", "trial_counts = [geometric_simulation_trials_m(p, num_monkeys) for _ in range(num_repetitions)]\n", "\n", "# Calculate and print the mean and variance\n", "mean_trials = statistics.mean(trial_counts)\n", "variance_trials = statistics.variance(trial_counts)\n", "\n", "print(f\"Mean number of trials after {num_repetitions} repetitions with p={p}: {mean_trials:.2f}\")\n", "print(f\"Variance of the number of trials after {num_repetitions} repetitions with p={p}: {variance_trials:.2f}\")\n", "\n", "# Plot a histogram of the trial counts\n", "plt.figure(figsize=(10, 6))\n", "plt.hist(trial_counts, bins=range(min(trial_counts), max(trial_counts) + 2), density=True, alpha=0.75, edgecolor='black')\n", "plt.title(f'Estimated Geometric Distribution for {num_monkeys} monkeys, p(succes of 1 monkey) = {p}')\n", "plt.xlabel('Number of Trials Until First Success')\n", "plt.ylabel('Probability Density')\n", "plt.grid(axis='y', alpha=0.75)\n", "plt.show()\n", "\n", "end_time = time.time() # Record the end time\n", "elapsed_time = end_time - start_time\n", "\n", "print(f\"Script execution time: {elapsed_time:.4f} seconds\")" ], "metadata": { "id": "EEnKVJWhxDnz" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "> *Exercise.* Run the program and assess it.\n", ">\n", "> *Answer.* Many monkeys seem to be much better than one because success seems to come very soon if 10 monkeys work at the same time.\n", "\n", "> *General challenge.* Follow the plan executed in the previous work for one monkey and implement it for whatever number of monkeys.\n", ">\n", "> *Our directive.* We will pursue the most important points only. We transcribe complete developments to motivate comprehension to the full.\n", "\n", "\n", "\n" ], "metadata": { "id": "csWbA4ffga9V" } }, { "cell_type": "markdown", "source": [ "\n", "## Testing the basic prediction\n", "\n", "Let us compare the predictions of our formulae with the results of a simulation.\n", "\n", "> *Exercise.* Compare the distribution observed in the previous program with the predicted values of our formulae.\n", ">\n", "> *Answer.* The best mode to compare observed to predicted is through a graphic. This is done in the following program:\n" ], "metadata": { "id": "l6g5xo3JMGSr" } }, { "cell_type": "code", "source": [ "# Geometric distribution for many monkeys\n", "import random\n", "import statistics\n", "import matplotlib.pyplot as plt\n", "import time\n", "import numpy as np\n", "\n", "start_time = time.time() # Record the start time\n", "print(\"Program starts\")\n", "\n", "# Parameters for the simulation\n", "p = 0.01\n", "num_monkeys = 10\n", "n = num_monkeys\n", "num_repetitions = 200\n", "\n", "def geometric_simulation_trials_m2(p, n):\n", " \"\"\"\n", " Simulates a geometric distribution and returns the number of trials until the first success.\n", "\n", " Args:\n", " p: The probability of success (a number between 0 and 1).\n", " n: The number of monkeys.\n", "\n", " Returns:\n", " The number of trials until the first success.\n", " \"\"\"\n", " trials = -1\n", " while True:\n", " trials = trials + 1\n", " for _ in range(n):\n", " t = random.random()\n", " # print(f\"t = {t}\")\n", " if t < p:\n", " # print(f\"Number of trials = {trials}\")\n", " return trials\n", "\n", "# Run the simulation multiple times and store the number of trials\n", "trial_counts = [geometric_simulation_trials_m2(p, num_monkeys) for _ in range(num_repetitions)]\n", "\n", "# Calculate and print the mean and variance\n", "mean_trials = statistics.mean(trial_counts)\n", "variance_trials = statistics.variance(trial_counts)\n", "\n", "print(f\"Mean number of trials after {num_repetitions} repetitions with p={p}: {mean_trials:.2f}\")\n", "print(f\"Variance of the number of trials after {num_repetitions} repetitions with p={p}: {variance_trials:.2f}\")\n", "\n", "def predicted(p,n,k):\n", " \"\"\"Calculate the theoretical geometric distribution for an ensemble of n monkeys\"\"\"\n", " # $ p(k) = f = (1-( 1 - (1-p)^n))^k ( 1 - (1-p)^n)$\n", " # where $n$ is the number of monkeys and $k$ is the number of failures before success.\n", " g = (1-p)**n #Probability of global failure\n", " s = 1-g # Probability of success of the ensemble, at least one monkey succeeds\n", " f = ((1-s)**k)* s # Geometric distribution for the ensemble\n", " return f\n", "\n", "#Expected probabilities as a function of k with paramters p and n\n", "l = np.arange(0, max(trial_counts) + 1)\n", "theoretical_probabilities = [predicted(p,n,k) for k in l]\n", "\n", "\n", "# Plot a histogram of the trial counts\n", "plt.figure(figsize=(10, 6))\n", "plt.hist(trial_counts, bins=range(min(trial_counts), max(trial_counts) + 2), density=True, alpha=0.75, edgecolor='black')\n", "plt.title(f'Estimated Geometric Distribution for {num_monkeys} monkeys, p = {p}, {num_repetitions} repetitions')\n", "plt.xlabel('Number of Trials Until First Success')\n", "plt.ylabel('Probability Density')\n", "plt.grid(axis='y', alpha=0.75)\n", "plt.plot(l, theoretical_probabilities, 'r-', label='Theoretical Distribution')\n", "plt.legend( )\n", "plt.show()\n", "\n", "end_time = time.time() # Record the end time\n", "elapsed_time = end_time - start_time\n", "\n", "print(f\"Script execution time: {elapsed_time:.4f} seconds\")" ], "metadata": { "id": "gyYo3iKVpEFm" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "> *Exercise.* Run the program and assess it.\n", ">\n", "> *Answer.* The fitting of the predicted to the observed is fine in spite of the fact that only 200 repetitions were undertaken.\n", "\n", "We have seen general properties of the Geometric Distribution applied to an ensemble of monkeys. Let us specialize now to the case when success means to match a target string that could be binary or of DNA." ], "metadata": { "id": "-mCeUtmqOHRL" } }, { "cell_type": "markdown", "source": [ "\n", "# THE SHAKESPEARE CHALLENGE\n", "\n", "Our desire is to say something about the possibilities that randomnes has to explain our DNA. But, from the linguistic point of view, our DNA has nothing special. So, explaining the DNA is changed into explaining, for instance, a Shakespeare artwork. Or, as we do, explaining an arbitrary binary string.\n", "\n", "> *Definition.* The **Shakespeare challenge** is to match a target string of length $H$ reporting the procedure and cost of doing this.\n", "\n", "> *Exercise.* Calculate the predictions of the Geometric Distribution when success means to solve the Shakespeare Challenge using random binary strings of the same length. In the folklore, each random string represents the proposal of one monkey.\n", ">\n", "> *Answer.* We must calculate the probability of matching a target binary string of length $H$ using random binary strings. Let us proceed.\n", "\n", "There are 2 options for each site in the binary string and we have $H$ sites, then there are $2^H$ possible different strings with equal probability. Hence, the probability of matching the target string by one monkey is equivalent to the probability of picking the matching string that is equal to $1/2^H$.\n", "\n", "What happens with the probability of success if we have $n$ monkeys?\n", "\n", "The ensemble of monkeys succeeds if one monkeys does it. But this also happens if two monkeys succeed or if whatever number of monkey does it. The exact calcule is done by means of the Binomial Distribution:\n", "\n", "The probability of success of one monkey is $a = 1/2^H$, and the probability of success of $r$ monkeys among the $n$ monkey is\n", "\n", "$ p(r) = $ $n\\choose r$ $a^r (1-a)^{n-r}$\n", "\n", "because $r$ monkeys succeed and $n-r$ fail. In particular, the probability of global failure is\n", ">\n", "> $p(0) = $ $n\\choose 0$ $a^0 (1-a)^{n}$\n", ">\n", "> $p(0) = (1-a)^{n}$\n", "\n", "The whole unit of monkeys succeeds if $r >=1$ and, of course, if $r<=n$. Therefore, the probability of success of the ensemble $p(E)$ of $n$ monkeys is\n", "\n", "$ p(E) = p(r >= 1) $\n", ">\n", "> $ = \\sum^n_1 p(r) $\n", ">\n", "> $ = \\sum^n_1 $$n\\choose r$ $a^r (1-a)^{n-r}$\n", ">\n", "> $ = 1- p(0) $,\n", ">\n", "> $ = 1 - (1-a)^n$\n", "\n", "Recalling that $ a = 1/2^H$,\n", ">\n", "> $ p(E) = 1 - (1-\\frac{1}{2^H})^n$\n", ">\n", "where $n$ is the number of monkeys and $H$ is the length of each one of the binary strings.\n", "\n", "This is the probability of success of the ensemble as a unit.\n", "\n", "\n", "We can plug now $p(E)$ into the geometric distribution that gives the probability of success after $k$ failures or attempts:\n", ">\n", "> $p(k) = (1-p)^kp$\n", ">\n", "> $p(k) = (1-p(E))^kp(E)$\n", ">\n", "> $p(k) = (1-(1 - (1-\\frac{1}{2^H})^n))^k(1 - (1-\\frac{1}{2^H})^n)$\n", "\n", "How can we prove that the sum of these expression over $k$ is 1?\n", "\n", "The proof is already done in the previous work. It was done for the Geometric Distribution for whatever value of the probability of success, $p$. The only thing that we are doing here is to specify $p = p(E)$. In any case, it must be positive. Is that true? Let us see:\n", ">\n", "> $ p(E) = 1 - (1-\\frac{1}{2^H})^n > 0 ?$\n", ">\n", " Yes, this is true because\n", ">\n", "> $2^H \\ge 0$\n", ">\n", "> $\\frac{1}{2^H} \\ge 0$\n", ">\n", ">\n", "> $-\\frac{1}{2^H} \\le 0$\n", ">\n", "> Adding 1 to both sides\n", ">\n", "> $1-\\frac{1}{2^H} \\le 1 $\n", ">\n", "> Applying antigravity:\n", ">\n", "> $- (1-\\frac{1}{2^H}) \\ge -1 $\n", ">\n", "> Adding 1 to both sides\n", ">\n", "> $ 1 - (1-\\frac{1}{2^H})^n \\ge 0$\n", ">\n", "> as demanded.\n", "\n", "In conclusion, we have proved the following result:\n", "\n", "> *Theorem.* When success means to match a target binary string of length $H$ using $n$ random binary strings of the same length per repetition, the probability of success after $k$ failures is given by\n", "\n", ">\n", "> $p(k) = (1-(1 - (1-\\frac{1}{2^H})^n))^k(1 - (1-\\frac{1}{2^H})^n)$\n", ">\n", "Or, to facilitate reading, by\n", ">\n", "> $p(k) = (1-p(E))^kp(E)$\n", ">\n", "where $p(E)$, the probability of success of the ensemble of $n$ monkeys in one repetition, is given by\n", ">\n", "> $ p(E) = 1 - (1-\\frac{1}{2^H})^n$\n", ">\n" ], "metadata": { "id": "QqVPYIl6dGi7" } }, { "cell_type": "markdown", "source": [ "# A CASE STUDY\n", "\n", "The task is to explain the existence of a DNA string 100 bases long. We need to know how much the cost diminishes if we work with many monkeys instead of with one.\n", "\n", "> *Exercise.* Compare the probability of success in one round of one monkey to that of 1000 monkeys, when the task is to synthesize a DNA string 100 bases long.\n", ">\n", "> *Answer.* The associated number of options for a DNA string with 100 bases is\n", ">>\n", ">> $4^{100} = (10^{0.61})^{100} = 10^{61}$\n", ">>\n", "> that is a 10 followed by 60 zeroes. And the corresponding probability is\n", ">>\n", ">> $p = \\frac{1}{10^{61}} = 1 \\times 10^{-61}$\n", ">>\n", "> This $p$ is the probability of success of one monkey in one trial. The corresponding probability for $n$ monkeys is\n", ">>\n", ">> $ p(E) = 1 - (1-\\frac{1}{4^H})^n$\n", ">>\n", "> When the number of monkeys is $n= 1000$, and the length of the DNA string is $H = 100$, the probability of success of the ensemble in one repetition $ p(E) $ is:\n", ">>\n", ">> $ p(E) = 1 - (1-\\frac{1}{4^{100}})^{1000}$\n", ">>\n", ">\n", "> To evaluate the included binomial, let us use the binomial expansion:\n", ">>\n", ">>\n", ">> $(a+b)^n = a^n + na^{n-1}b + \\frac{n(n-1)}{2}a^{n-2}b^2 + \\frac{n(n-1)(n-2)}{2 \\times 3}a^{n-3}b^3 + \\frac{n(n-1)(n-2)(n-3)}{2 \\times 3 \\times 4}a^{n-4}b^4 +...+ \\frac{n(n-1)(n-2)(n-3)(n-4)...(n-k+1)}{k!}a^{n-k}b^k+ ...$ \n", ">>\n", "> Here $a = 1$, $b = -1/n$ and the exponent is $m$. The minus sign of $b$ says that the signs will alternate in the expansion.\n", ">>\n", ">> $ (1 - 1/n)^m = 1 - m (1/n) + \\frac{m(m-1)}{2} (1/n)^2 - \\frac{m(m-1)(m-2)}{3!} (1/n)^3 + ...$\n", ">>\n", "> Replacing, $n = 4^{100} = 10^{61}$ and $m = 1000 = 10^{3} $, we have:\n", ">>\n", ">> $ (1 - 1/10^{61})^{10^{3}} = 1 - (10^{3}) (1/10^{61}) + \\frac{(10^{3}) (10^{3}) }{2} (1/10^{61})^2 - \\frac{(10^{3})(10^{3})(10^{3}) }{3!} (1/10^{61})^3 + ...$\n", ">>>\n", ">>> $ = 1 - 1/10^{58} + \\frac{1}{2} \\frac{10^{6}}{10^{122}} - \\frac{1}{6} \\frac{10^{9}}{10^{183}} + ...$\n", ">>>\n", ">>> $ = 1 - \\frac{1}{10^{58}} + \\frac{1}{2} \\frac{1 }{10^{116}} - \\frac{1}{6} \\frac{1 }{10^{174}} + ...$\n", ">>\n", "> At last, we get:\n", ">>\n", ">> $ (1-\\frac{1}{4^{100}})^{1000} = (1 - \\frac{1}{10^{61}})^{10^{3}} = 1 - \\frac{1}{10^{58}}$\n", ">>\n", "> Therefore, the probability of success of the whole ensemble as a unit in one round is\n", ">>\n", ">>\n", ">> $ p(E) = 1 - (1-\\frac{1}{4^{100}})^{1000}$\n", ">>\n", ">> $ p(E) = 1 - (1 - \\frac{1}{10^{58}})$\n", ">>\n", ">> $ p(E) = \\frac{1}{10^{58}}$\n", "\n", "> Let us notice that instead of the whole expansion of the binomial, we could take just the first two terms:\n", "\n", ">> $(a+b)^n = a^n + na^{n-1}b$\n", ">>\n", "> we get\n", ">>\n", ">> $(1-\\frac{1}{4^{100}})^{1000} = 1+ 1000 \\times 1 \\times (-\\frac{1}{4^{100}})$\n", ">>>\n", ">>> $ = 1 - 1000 \\times 1 \\times (\\frac{1}{4^{100}})$\n", ">>>\n", ">>> $ = 1 - 10^3 \\times (10^{0.61})^{-100}$\n", ">>>\n", ">>> $ = 1 - 10^3 \\times 10^{-61} $\n", ">>>\n", ">>> $ = 1 - 10^{-58} $\n", ">>>\n", "> Therefore:\n", ">>\n", ">> $ p(E) = 1 - (1-\\frac{1}{4^{100}})^{1000}$\n", ">>\n", ">> $ p(E) = 1 - (1 - 10^{-58})$\n", ">>\n", ">> $ p(E) = 10^{-58}$\n", ">>\n", "According to our treatment, the effect of the number of monkeys is insignificant: 1000 monkeys augments the probability of success from $10^{-61}$ to $ 10^{-58}$. This is in one round. What could happen if we allow many, many repetitions?\n", "\n", "> *Exercise.* Estimate the number of repetitions allowed during the age of the Earth.\n", ">\n", ">* Answer.* Let us imagine that one repetition last 1 millisecond. The accepted age of the Earth is 5000 million years. The number of repetitions that can be run during that lapse of time is\n", ">\n", ">> $N = 1000 \\times 60 \\times 60 \\times 24 \\times 365 \\times 5000 \\times 1000000 $\n", ">>>\n", ">>> $= 6 \\times 6 \\times 24 \\times 365 \\times 5 \\times 100000 \\times 1000 \\times 1000000 $\n", ">>>\n", ">>> $= 1576800 \\times 100000 \\times 1000 \\times 1000000 $\n", ">>>\n", ">>> $= 15768 \\times 10^{16} $\n", ">>>\n", ">>> $= 20000 \\times 10^{16} $\n", ">>>\n", ">>> $= 2 \\times 10^{20} $\n", ">>>\n", ">> this is a 2 followed by 20 zeroes.\n", "\n", "\n", "\n", "\n", "> *Exercise.* Calculate the probability of success of 1000 monkeys to solve a DNA string 100 bases long if they work during the age of the Earth.\n", ">\n", "> *Answer.* The 1000 monkeys can succeed at the very first trial, or at the second, or at the third, or at any one repetition. This means that we must deal with the CDF (Cumulative Distribution Function):\n", ">\n", "> The CDF (Cumulative Distribution Function) of the Geometric Distribution is\n", ">>\n", ">> $F_X(m) = P(X < m) = 1 -(1-p)^{m+1} $\n", ">>\n", "> This function outputs the cumulative probability of success when $m$ repetitions are allowed and the probability of success is $p$.\n", "\n", ">> Therefore, the cumulated probability of success of an ensemble of 1000 monkeys for the age of the Earth is:\n", ">>\n", ">>> $F_X(n) = 1 - (1 - 10^{-58})^{ 2 \\times 10^{20} } $\n", "\n", "\n", "> Using the binomial expansion for small $b$ up to the second term:\n", ">>\n", ">> $(a+b)^n = a^n + na^{n-1}b$\n", ">>\n", "> we get\n", ">>\n", ">> $F_X(n) = 1 - (1 + 2 \\times 10^{20}(- 10^{-58}) )$\n", ">>\n", ">> $F_X(n) = 1 - (1 - 2 \\times 10^{20}( 10^{-58}) )$\n", ">>\n", ">> $F_X(n) = 1 - 1 + 2 \\times 10^{20}( 10^{-58}) $\n", ">>\n", ">> $F_X(n) = 2 \\times 10^{20}( 10^{-58}) $\n", ">>\n", ">> $F_X(n) = 2 \\times 10^{-38}$\n", "\n", "\n", "This result says that randomness working in parallel in 1000 fronts might be an explanation of life on Earth, but no feasible experiment can support that. Rather, this result strongly claims for inventing and testing other explanations. Observe that we have taken a DNA string 100 bases long as the representation of life.\n", "\n", "We have proved the following result:\n", "\n", "\n", "> *Many Monkeys Theorem for the EARTH.*\n", ">>\n", ">> The cumulated probability of success of randomness working in parallel in 1000 fronts during the age of the Earth is experimental zero. What is that?\n", ">>\n", ">> *Definition.* **Experimental zero** is the non-zero probability of an event that is so small that no feasible experiment can demonstrate that it is possible.\n", "\n", " \n", "> *Exercise.* Calculate the number of necessary repetitions of 1000 monkeys before succeeding with a cumulated probability of 0.05 when $p = 10^{-58}$. The task is to match a DNA string 100 bases long.\n", ">>\n", ">> *Answer.* $F_X(m) $ is the cumulative probability of success after $m$ failures. We must equate $F_X(m) $ to $0.05$ and clear for $m$.\n", ">>>\n", ">>> $F_X(m) = 1 -(1-p)^{1 + m} = 0.05$\n", ">>>\n", ">> We cannot approximate $(1-p)$ by 1 because we would get $0 = -0.05$. We must go by a longer path. Passing 1 to the right side\n", ">>>\n", ">>> $ -(1-p)^{1 + n} = -1 + 0.05$\n", ">>>\n", ">>> $ (1-p)^{1 + n} = 1 - 0.05 = 0.95$\n", ">>>\n", ">> Taking natural logarithms of positive numbers, we get\n", ">>>\n", ">>> $ln( (1-p)^{1 + n} ) = ln(0.95) = -0.051293294$\n", ">>>\n", ">>> $(1+n)ln( (1-p) ) = -0.051293294$\n", ">>\n", ">> Because $p$ is so small, $1-p$ is in the close vicinity of 1 and, given that the $ln$ is smooth, the value of $ln( (1-p) )$ can be found by the tangent line, which results from the derivative of $ln(1-x)$ at $x= 0$:\n", ">>>\n", ">>> $\\frac{d(ln(1-x)) }{dx}= \\frac{-1}{1-x}$\n", ">>>\n", ">> The tangent line has the form $y = mx + b$. The slope of the tangent line $m$ at the graph of the function $ln(1-x)$ at $x = 0$ is\n", ">>>\n", ">>> $m =\\frac{-1}{1-x} = -1 $\n", ">>>\n", ">> So, \n", ">>\n", ">>> $y = -x + b$\n", ">>>\n", ">> To know the value of $b$, we replace $x= 0$ in $y = ln(1-x) = -x + b + error$. We get:\n", ">>>\n", ">>> $ y = 0 = b$ \n", ">>>\n", ">> This means that the equation of the tangent line is $y = -x$. Therefore, the series of $ln(1-x)$ in the vicinity of $x=0$ up to the first term is\n", ">>>\n", ">>> $ln(1-x) = -x$\n", ">>>\n", ">> Hence\n", ">>>\n", ">>> $(1+n)ln( 1-p ) = -0.051293294$\n", ">>>\n", ">> becomes\n", ">>>\n", ">>> $(1+n)( -p ) = -0.051293294$\n", ">>>\n", ">>> $(1+n)( p ) = 0.051293294$\n", ">>>\n", ">>> $1+n = \\frac{0.051293294}{p}$\n", ">>>\n", ">>> $n = \\frac{0.051293294}{p} -1$\n", ">>>\n", ">> Since $p = 10^{-58}$ we have at last:\n", ">>>\n", ">>> $n = \\frac{0.051293294}{10^{-58}} -1$\n", ">>>\n", ">>> $n = 0.051293294 \\times 10^{58} -1$\n", ">>>\n", ">>> $n = 0.05 \\times 10^{58} $\n", ">>>\n", ">>>> $ = 5 \\times 10^{-2} \\times 10^{57} $\n", ">>>\n", ">>> $n = 5 \\times 10^{55} $\n", ">>>\n", ">> This is a 5 followed by 55 zeroes.\n", "\n", "\n", "Therefore, our scientific result reads: to cumulate a significance of $0.05$, 1000 monkeys need to make, on average, $5 \\times 10^{55} $ repetitions before the first success, which consists in matching a DNA target string 100 bases long. But the allowed number is of the order of $10^{20}$. There is a defficit of more than $10^{35}$ ages of the Earth.\n", "\n", "Our conclusions are so extravagant that everyone would want testable predictions, not just simulations, but proposal of experiments to be carried in a lab of Molecular Biology.\n", "\n", "What shall we propose?\n", "\n", "We shall propose a feasible experiment that allows the spontaneous arising of a simple conlcusion: too many trials must be done before success. Or, in our words, Randomness cannot reproduce a result about matching a target DNA string unless huge quantities of garbage are produced. This also implies that we are also garbage. This means that we are full of malformations and malfunctions. Now, look at yourself and decide: is randomness working on many fronts an explnation for your existence?\n", "\n" ], "metadata": { "id": "TbBSm-COo-oZ" } }, { "cell_type": "markdown", "source": [ "# A FEASIBLE AND CRUCIAL EXPERIMENT\n", "\n", "For lovers of labs, we must propose an experiment in which the same sensation that we feel must spontaneously arise: **Even tiny experiments are extremely costly because of the huge quantity of demanded resources**. In the following proposal, each laboratory has the opportunity to select a level of difficulty in agreement with its possibilities.\n", "\n", "> *Proposal.* Synthesize a DNA string of length $H = 1, 2, 3, ...$ using 10 random strings per repetition. Count and report the number of repetitions until success.\n", "\n", "Let us predict what is faced to: we will exhibit our mathematical predictions together with the results of a simulation. The fitting of one to the other must be taken as a guide of the expected difficulties. So, the probability $p(E)$ of synthesizing a DNA string $H$ bases long using $n$ monkeys for one repetition is\n", "\n", "> $p(E) = 1- (1 -\\frac{1}{4^H})^n$\n", ">\n", "Therefore, the cost $C(E)$ of synthesyzing the string of length $H$ using $n$ monkeys is, in terms of repetitions,\n", ">\n", "> $C(E) = \\frac{1}{p(E)}$\n", ">\n", "> $C(E) = \\frac{1}{1- (1 -\\frac{1}{4^H})^n}$\n", ">\n", "Approximating $(1 -\\frac{1}{4^H})^n $ by $1 - \\frac{n}{4^H}$, we get\n", ">\n", "> $p(E) = 1- (1 - \\frac{n}{4^H})$\n", ">\n", "> $p(E) = 1- 1 + \\frac{n}{4^H}$\n", ">\n", "> $p(E) = \\frac{n}{4^H} $\n", "\n", "Therefore, the cost in terms of repetitions $C$ can be approximated by\n", ">\n", "> $C(E) = \\frac{1}{p(E)}$\n", ">\n", "> $C = \\frac{1}{\\frac{n}{4^H} }$\n", ">\n", "> $C(E) = \\frac {4^H}{n}$\n", "\n", "> *Interpretation.* The last equation has a simple reading: one monkey needs in average $4^H$ rounds to match a DNA string with $H$ bases. Therefore, $n$ monkeys need $\\frac {4^H}{n}$ rounds to do the same job. But this is an approximation. How good it is?\n", "\n", "> *Test.* Let us test our mathematical predictions with a simulation. The corresponding code follows. It is included a numerical exploration to assess how good is the proposed approximation of Cost = $\\frac {4^H}{n}$. \n", "\n" ], "metadata": { "id": "H72tMf6iuXb9" } }, { "cell_type": "code", "source": [ "import random\n", "import matplotlib.pyplot as plt\n", "import numpy as np\n", "import time\n", "\n", "start_time = time.time() # Record the start time\n", "\n", "num_monkeys = 10\n", "n = num_monkeys\n", "\n", "\n", "def generate_random_dna_string(length):\n", " \"\"\"Generates a random DNA string of a given length.\"\"\"\n", " return ''.join(random.choice('ATCG') for _ in range(length))\n", "\n", "def simulate_dna_matching(target_string):\n", " \"\"\"Simulates attempts to match a target DNA string and returns the number of trials.\"\"\"\n", " trials = 0\n", " while True:\n", " trials = trials + 1\n", " for _ in range(n):\n", " if generate_random_dna_string(len(target_string)) == target_string:\n", " return trials\n", "\n", "# Define the range of string lengths to test\n", "string_lengths = range(1, 12) # From 1 to 11\n", "\n", "observed_trials = []\n", "predicted_trials = []\n", "\n", "for length in string_lengths:\n", " # Create a target DNA string (e.g., 'A' * length)\n", " target = 'A' * length\n", " # Simulate matching and record the number of trials\n", " observed = simulate_dna_matching(target)\n", " observed_trials.append(observed)\n", "\n", " # Calculate the theoretical prediction (4^n)\n", " # predicted = 4**length\n", " # predicted_trials.append(predicted)\n", " prob_of_E = 1-(1-(1/4**length))**n\n", " predicted = int(np.round(1 / prob_of_E ))\n", "\n", " predicted_trials.append(predicted)\n", " approx = int(4**length/n)\n", " print(f\"Length: {length}, Observed Trials: {observed}, Predicted Trials : {predicted}, approx: {approx}\")\n", "\n", "# Plot the results\n", "plt.figure(figsize=(12, 8))\n", "plt.plot(string_lengths, observed_trials, 'o-', label='Observed Repetitions')\n", "plt.plot(string_lengths, predicted_trials, 's-', label='Predicted repetitions ( ~ 4^length/n)')\n", "\n", "plt.yscale('log') # Use a logarithmic scale for better visualization of exponential growth\n", "\n", "plt.title(f'Observed vs. Predicted repetitions to Match a DNA String for {n} monkeys')\n", "plt.xlabel('DNA String Length ')\n", "plt.ylabel('Number of Repetitions(log scale)')\n", "plt.legend()\n", "plt.grid(True)\n", "plt.show()\n", "\n", "end_time = time.time() # Record the end time\n", "elapsed_time = end_time - start_time\n", "\n", "print(f\"Script execution time: {elapsed_time:.4f} seconds\")" ], "metadata": { "id": "Y9ZMawglLXxl" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "> *Exercise.* Run the program and assess the results. The program runs for lengths of target DNA strings of length 1,2,..., 11. Before attempting running it until length 12 or larger, predict the execution time which grows as a cancer.\n", ">\n", ">> *Answer.* The program shows the cost of finding a DNA sequence of length 1, 2, ..., 11, using 10 monkeys that generate a random sequence per repetition. The cost is expressed as a function of the number of observed repetitions that fit a mathematical prediction. This prediction is given by the approximation $4^H/n$, where $H$ is the length of the target sequence and $n$ is the number of monkeys, in this case, 10. The graph of the mathematical prediction is a nearly perfect line on a semi-logarithmic scale. This indicates that the cost is dominated by the exponential term $4^H$. The fit between observed and expected values ​​is good, but not perfect, indicating that there is considerable variance.\n", ">>\n", ">> The observed cost for length 11 was nearly 100000 rounds, with execution time of 20 seconds. The cost for length 12 must be 4 times larger, with execution time by Gemini of 1 minute and some seconds. For 13, the predicted cost is 4 times larger or 5 minutes. For 14 is 20 minutes, and for 15 is more than an hour. For length 100, the predicted cost is $4^{100}/10 = 4^{98} = 10^{59}$ repetitions with execution time of around $10^{45}$ hours or $10^{40}$ years, or $10^{25}$ times the age of the Universe.\n", "\n", "We have shown the following result:\n", "\n", "> *Theorem.* The cost in terms of repetitions of matching a DNA string using $n$ monkeys is exponential in the length of the string and inverse to the number of monkeys. This implies that for slightly large values of the length, the exponential trend dominates. In our words: **No feasible number of monkeys can overcome complexity**. Or, the battle between resources and complexity is won by complexity.\n", ">\n", ">> *Proof.* We need to show that when both, the length and the number of monkeys grow, the exponential cost dominates. Let us suppose that per iteration or repetition, we add one monkey to the working ensemble, and one basis to the DNA string. And that we repeat this over and over. If we begin with 1 and 1, this amounts to a definition of the function\n", ">>\n", ">> $C(x) = \\frac{4^x}{x} $\n", ">>\n", ">>> $ = \\frac{(e^{ln 4})^x}{x}$\n", ">>>\n", ">>> $ = \\frac{(e^{xln 4})}{x}$\n", ">>\n", ">> When $x \\to ∞$, $C(x) \\to \\frac{∞}{∞}$. Thus, to know the limit, we take derivatives:\n", ">\n", ">> $C(x) \\to \\frac{(ln 4) e^{xln 4}}{1} = ln 4 \\times 4^x \\to ∞$.\n", ">\n", "> This says, that when $x$ is very large, the exponential dominates. What does happens when $x$ is of moderate size? The answer can be seen in the output of the following program:\n", "\n" ], "metadata": { "id": "3pt5_gtHXjiY" } }, { "cell_type": "code", "source": [ "import matplotlib.pyplot as plt\n", "import numpy as np\n", "\n", "#Cost in repetitions of matching a DNA string x bases long with x monkeys\n", "x_vals = np.linspace(1, 20, 20)\n", "cost_vals = (4**x_vals)/x_vals\n", "# Plot the results\n", "plt.figure(figsize=(12, 8))\n", "plt.plot(x_vals, cost_vals, 'o-')\n", "plt.title('Cost in repetitions of matching a DNA string $x$ bases long with $x$ monkeys')\n", "plt.xlabel('DNA String Length ')\n", "plt.ylabel('Number of Repetitions ')\n", "plt.legend()\n", "plt.grid(True)\n", "plt.show()" ], "metadata": { "id": "JeT-aAF6dWZ2" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "> *Exercise.* Run the propgram and evaluate it.\n", ">\n", "> *Answer.* If we add one monkey and one basis at the same time over and over, at the beginning the impact on the necessary number of trials to accomplish a task is tolerable. But when $x$ surpases 15, things change and the exponential begins to dominate. Its dominance is so sharp that by 20 bases the signature of an exponential is perfectly visible arriving at a cost of a multiple of $10^{10}$.\n", "\n", "> *Challenge.* Prove that the dominance of the exponential is stable even in the case in which we add a number of monkeys that is a polynomial function in the iteration number of our procedure.\n", "\n", "\n", "> *Challenge.* Decide whether the following objection is correct and realizable. In that case, resolve it. The objection is\n", ">>\n", ">> The exponential cost is not the winner in all escenarios. Just consider the case in which we add one basis while we let the monkeys reproduce along a Fibonacci series. In that case, the needed number of repetitions to match the updated binary string is kept in within low bounds because the number of monkeys is also exponential.\n", "\n", "\n" ], "metadata": { "id": "MlL08gjeJ44z" } }, { "cell_type": "markdown", "source": [ "# CONCLUSION\n", "\n", "We study the cost of matching a target string by a machine that outputs random strings of the same length. We already know that if the machine outputs one string by iteration, depicted figuratively as one monkey that taps over typewriter, then the monkey is defenseless against complexity, given by the length of the target string. Our purpose in this article was to inquire what could happen if instead of one monkey we deal with many.\n", "\n", "> *Exercise.* Extract and redact your conclusions.\n", ">\n", ">> *Answer.* In realizable scenarios, many monkeys are a not reproducible solution to the problem of matching a target string of length as short as 100 DNA bases. In fact, many monkeys are better but not too much than one. Nevertheless, the process has a high variance and so, one cannot exclude that by mere chance many monkeys could solve the task in whatever predefined lapse of time. Nevertheless, this is not reproducible. Anyway, it is possible, but with so low a probability that the Scientific Method advices to create another explanation. Anyway, if no other explanation exists, the hypothesis of the many monkeys might be accepted. In that case, that acceptance would be more tolerable if the predicted huge amount of garbage is found, say, in the ancestral seas. And, fossils together with all living exponents of all species shall be filled in every type of defects, malformations and malfunctions. That is the meaning of garbage when speaking of DNA. Therefore, each person can look at her or his own body and decide whether or not the explanation of the many monkeys is the cause of our existence." ], "metadata": { "id": "MDkX-3awOFpT" } } ] }