Related observations on NIST's longest runs test

longest_runs.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dataclasses import dataclass\n",
    "from typing import Any\n",
    "\n",
    "    \n",
    "@dataclass\n",
    "class Run:\n",
    "    value: Any\n",
    "    length: int = 1\n",
    "\n",
    "def asruns(seq):\n",
    "    firstval = seq[0]\n",
    "    pointer = Run(firstval, length=0)\n",
    "    for value in seq:\n",
    "        if value == pointer.value:\n",
    "            pointer.length += 1\n",
    "        else:\n",
    "            yield pointer\n",
    "            pointer = Run(value)\n",
    "    else:\n",
    "        yield pointer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "size = 8\n",
    "candidate = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "\n",
    "maxlengths = []\n",
    "for seq in product([0, 1], repeat=size):\n",
    "    runs = asruns(seq)\n",
    "    \n",
    "    candidateruns = (run for run in asruns(seq) if run.value == candidate)\n",
    "\n",
    "    maxlen = 0\n",
    "    for run in candidateruns:\n",
    "        if run.length > maxlen:\n",
    "            maxlen = run.length\n",
    "                \n",
    "    maxlengths.append(maxlen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "maxlen=0, count=1, prop=0.0\n",
      "maxlen=1, count=54, prop=0.21\n",
      "maxlen=2, count=94, prop=0.37\n",
      "maxlen=3, count=59, prop=0.23\n",
      "maxlen=4, count=28, prop=0.11\n",
      "maxlen=5, count=12, prop=0.05\n",
      "maxlen=6, count=5, prop=0.02\n",
      "maxlen=7, count=2, prop=0.01\n",
      "maxlen=8, count=1, prop=0.0\n"
     ]
    }
   ],
   "source": [
    "from collections import Counter\n",
    "\n",
    "counts = Counter(maxlengths)\n",
    "nsequences = sum(counts.values())\n",
    "\n",
    "for maxlen, count in counts.items():\n",
    "    prop = count / nsequences\n",
    "    propf = round(prop, 2)\n",
    "    print(f\"maxlen={maxlen}, count={count}, prop={propf}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "<div id=\"altair-viz-ddf6d005eda846d48e047f4445886695\"></div>\n",
       "<script type=\"text/javascript\">\n",
       "  (function(spec, embedOpt){\n",
       "    let outputDiv = document.currentScript.previousElementSibling;\n",
       "    if (outputDiv.id !== \"altair-viz-ddf6d005eda846d48e047f4445886695\") {\n",
       "      outputDiv = document.getElementById(\"altair-viz-ddf6d005eda846d48e047f4445886695\");\n",
       "    }\n",
       "    const paths = {\n",
       "      \"vega\": \"https://cdn.jsdelivr.net/npm//vega@5?noext\",\n",
       "      \"vega-lib\": \"https://cdn.jsdelivr.net/npm//vega-lib?noext\",\n",
       "      \"vega-lite\": \"https://cdn.jsdelivr.net/npm//[email protected]?noext\",\n",
       "      \"vega-embed\": \"https://cdn.jsdelivr.net/npm//vega-embed@6?noext\",\n",
       "    };\n",
       "\n",
       "    function loadScript(lib) {\n",
       "      return new Promise(function(resolve, reject) {\n",
       "        var s = document.createElement('script');\n",
       "        s.src = paths[lib];\n",
       "        s.async = true;\n",
       "        s.onload = () => resolve(paths[lib]);\n",
       "        s.onerror = () => reject(`Error loading script: ${paths[lib]}`);\n",
       "        document.getElementsByTagName(\"head\")[0].appendChild(s);\n",
       "      });\n",
       "    }\n",
       "\n",
       "    function showError(err) {\n",
       "      outputDiv.innerHTML = `<div class=\"error\" style=\"color:red;\">${err}</div>`;\n",
       "      throw err;\n",
       "    }\n",
       "\n",
       "    function displayChart(vegaEmbed) {\n",
       "      vegaEmbed(outputDiv, spec, embedOpt)\n",
       "        .catch(err => showError(`Javascript Error: ${err.message}<br>This usually means there's a typo in your chart specification. See the javascript console for the full traceback.`));\n",
       "    }\n",
       "\n",
       "    if(typeof define === \"function\" && define.amd) {\n",
       "      requirejs.config({paths});\n",
       "      require([\"vega-embed\"], displayChart, err => showError(`Error loading script: ${err.message}`));\n",
       "    } else if (typeof vegaEmbed === \"function\") {\n",
       "      displayChart(vegaEmbed);\n",
       "    } else {\n",
       "      loadScript(\"vega\")\n",
       "        .then(() => loadScript(\"vega-lite\"))\n",
       "        .then(() => loadScript(\"vega-embed\"))\n",
       "        .catch(showError)\n",
       "        .then(() => displayChart(vegaEmbed));\n",
       "    }\n",
       "  })({\"config\": {\"view\": {\"continuousWidth\": 400, \"continuousHeight\": 300}}, \"data\": {\"name\": \"data-0d55b3ddb1f8ff3585c37575acc85a61\"}, \"mark\": \"bar\", \"encoding\": {\"x\": {\"type\": \"quantitative\", \"field\": \"maxlen\"}, \"y\": {\"type\": \"quantitative\", \"field\": \"occurences\"}}, \"$schema\": \"https://vega.github.io/schema/vega-lite/v4.8.1.json\", \"datasets\": {\"data-0d55b3ddb1f8ff3585c37575acc85a61\": [{\"maxlen\": 0, \"occurences\": 1}, {\"maxlen\": 1, \"occurences\": 54}, {\"maxlen\": 2, \"occurences\": 94}, {\"maxlen\": 3, \"occurences\": 59}, {\"maxlen\": 4, \"occurences\": 28}, {\"maxlen\": 5, \"occurences\": 12}, {\"maxlen\": 6, \"occurences\": 5}, {\"maxlen\": 7, \"occurences\": 2}, {\"maxlen\": 8, \"occurences\": 1}]}}, {\"mode\": \"vega-lite\"});\n",
       "</script>"
      ],
      "text/plain": [
       "alt.Chart(...)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "import altair as alt\n",
    "\n",
    "sortedcounts = sorted(counts.items(), key=lambda item: item[0])\n",
    "\n",
    "data = pd.DataFrame(sortedcounts, columns=[\"maxlen\", \"occurences\"])\n",
    "\n",
    "alt.Chart(data).mark_bar().encode(\n",
    "    x=\"maxlen\",\n",
    "    y=\"occurences\"\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.0"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from math import log\n",
    "\n",
    "sum((-1)**j+1 *\n",
    "    (p + ((n - j*m + 1)/j) * (1-p)) *\n",
    "    (n))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}