2d:null 2e:["$","title",null,{"children":"Flippin' switches (Noisy XOR) | Bryan | Observable"}] 33:T4ce,__chart = { const height = 350 const svg = d3.select(DOM.svg(width, height)); const margin = { top: 20, right: 20, bottom: 20, left: 60 }; const data = dist_to_counter_dict(dist_of_error_counts); const x = d3.scaleLinear() .domain([0, d3.max(data.map((d) => d.x))]) .range([margin.left, width - margin.right]) const y = d3.scaleLinear() .domain([0, d3.max(data.map((d) => d.y))]) .range([height - margin.top, margin.bottom]); svg.selectAll('line.stick') .data(data) .enter() .append('line') .attr('x1', (d) => x(d.x)) .attr('x2', (d) => x(d.x)) .attr('y1', (d) => y(d.y)) .attr('y2', (d) => height - margin.top) .attr('stroke', 'black') svg.selectAll('circle') .data(data) .enter() .append('circle') .attr('r', 3) .attr('cx', (d) => x(d.x)) .attr('cy', (d) => y(d.y)) .attr('fill', 'red'); svg.append("g") .attr("class", "axis axis--x") .attr("transform", `translate(${-0.5},${height - margin.bottom})`) .call(d3.axisBottom(x)); svg.append("g") .attr("class", "axis axis--y") .attr("transform", `translate(${margin.left - 10},0)`) .call(d3.axisLeft(y)); return svg.node() }34:T4c1,{ const height = 350 const svg = d3.select(DOM.svg(width, height)); const margin = { top: 20, right: 20, bottom: 20, left: 60 }; const data = dist_to_counter_dict(dist_of_seed_sums); const x = d3.scaleLinear() .domain([0, d3.max(data.map((d) => d.x))]) .range([margin.left, width - margin.right]) const y = d3.scaleLinear() .domain([0, d3.max(data.map((d) => d.y))]) .range([height - margin.top, margin.bottom]); svg.selectAll('line.stick') .data(data) .enter() .append('line') .attr('x1', (d) => x(d.x)) .attr('x2', (d) => x(d.x)) .attr('y1', (d) => y(d.y)) .attr('y2', (d) => height - margin.top) .attr('stroke', 'black') svg.selectAll('circle') .data(data) .enter() .append('circle') .attr('r', 3) .attr('cx', (d) => x(d.x)) .attr('cy', (d) => y(d.y)) .attr('fill', 'red'); svg.append("g") .attr("class", "axis axis--x") .attr("transform", `translate(${-0.5},${height - margin.bottom})`) .call(d3.axisBottom(x)); svg.append("g") .attr("class", "axis axis--y") .attr("transform", `translate(${margin.left - 10},0)`) .call(d3.axisLeft(y)); return svg.node() }35:T98d,md` Let \`Y\` be a discrete random variable such that \`Y = i\` indicates \`i\` lights are remain on after our switching. Let's calculate ${tex.block` P(Y=1 | j=1) `} One can see that there are two distinct ways for us to start with 1 light, and end up with 1 light: - we randomly flip 0 switches - we reandomly flip 2 switches, and one of the ones we flip is the one that was already on. We will write \`X\` for the discrete random variable such that \`X = k\` indicates that we randomly flip \`k\` switches. Thus ${tex` P(X=k)`} is that probability, and we remind you that we earlier observed that this is the binomial distribution. Let's analyze the two cases above: - ${tex` P(X=0)`} - ${tex` P(X=2)*\binom{N-1}{1}/\binom{N}{2}`} The second case is easy to simplify, but we'll see a pattern more simply if we don't. Just to summarize: ${tex.block` P(Y=1 | j=1) = P(X=0) + P(X=2)*\dfrac{\binom{N-1}{1}}{\binom{N}{2}} `} Let's do one more example, for ${tex` P(Y=2 | j=1)`}: - we randomly switch 1 switch, and it's not the on switch - we randomly switch 3 switches, and one of them is already on then: ${tex.block`\begin{aligned} P(Y=2 | j=1) &= P(X=1)*\dfrac{\binom{N-1}{1}}{\binom{N}{1}} \\ &+ P(X=i+1)*\dfrac{\binom{N-1}{i}}{\binom{N}{i+1}} \end{aligned} `} a quick observation that: ${tex.block` P(Y=0 | j=1) = P(X=1)*\dfrac{1}{N} `} and one can extract: ${tex.block`\begin{aligned} P(Y=i | j=1) &= P(X=i-1)*\dfrac{\binom{N-1}{i-1}}{\binom{N}{i-1}} \\ &+ P(X=i+1)*\dfrac{\binom{N-1}{2}}{\binom{N}{3}} \end{aligned} `} Which in words are the same two cases: - one less than the number of lights you want to leave on, avoiding the light that's on - one more than the number of lights you want to leave on, cancelling out the light that's on. And this leads the way to the general case for ${tex`P(Y=i | j=2)`}: - 2 less than the number of lights you want to leave on, avoiding the lights that are on - the number of lights you want to leave on, cancelling one that is already on - 2 more than the number of lights you want to leave on, cancelling out the lights that are on. ${tex.block`\begin{aligned} P(Y=i | j=2) &= P(X=i-2)*\dfrac{\binom{N-2}{i-2}}{\binom{N}{i-2}} \\ &+ P(X=i)*\dfrac{\binom{2}{1}\binom{N-1}{i-1}}{\binom{N}{i}} \\ &+ P(X=i+2)*\dfrac{\binom{N-2}{i}}{\binom{N}{i+2}} \end{aligned}`} It's possible to extend this argument to a general formula, but it involves a lot of algebra, so let's take a step back. `36:T873,md` ## Less convoluted (more convolution) To find a general solution, we're going to change our strategy a little. Let's consider the light switches as two little groups, the ones that are on, and the ones that are off. We write random variables ${tex`X_0`} for the number that end up on from those that are off, and ${tex`X_1`} for those that remain on. Recall that we start with \`j\` switches on, and recall that the binomial describes our distribution of switches. Thus: ${tex.block`\begin{aligned} X_0 &= \sum_0^{N-j}p^i(1-p)^{N-j-i}\binom{N-j}{i}, \\ m_0(i) &= p^i(1-p)^{N-j-i}\binom{N-j}{i} \end{aligned} `} But ${tex`X_1`} has a slight gotcha—since we _start_ with these \`j\` lights on, the binomial in this case describes which ones we turn off! This means the probabilities are switched for the binomial. _(for those paying really close attention, we also use symmetry of the binomial coefficients)_. ${tex.block`\begin{aligned} X_1 &= \sum_0^{j}(1-p)^{i}p^{j-i}\binom{j}{j-i}, \\ m_1(i) &= (1-p)^{i}p^{j-i}\binom{j}{i} \end{aligned} `} We now will use a beautiful result about the _sum of independent random variables_ which states that for two discrete random variables which are independent, the random variable that describes their sum, is given by the convolution of the two random variables. In symbols, let ${tex`S=X_0+X_1`} and ${tex`m_S`} its distribution, then ${tex.block`m_S(i) = \sum_k m_o(k)*m_1(i-k)`} Before we do our computation, let's take another moment to remind ourselves what we are thinking about... We are asking for the number of lights that remain on in both the group that start on, and the group that start off, to add up to \`i\`. Now we compute: ${tex.block`\begin{aligned} m_S(i) &= \sum_k p^k(1-p)^{N-j-k}\binom{N-j}{k}*(1-p)^{i-k}p^{j-i+k}\binom{j}{i-k} \\ &= \dfrac{p^j}{p^i}\dfrac{(1-p)^i}{(1-p)^j} \sum_{k=0}^i p^{2k}(1-p)^{N-2k}\binom{N-j}{k}\binom{j}{i-k} \end{aligned}`} _(Important observation: we obtain our bounds by simply examining when the coefficients would go to zero)_ _(Unimportant observation: that last term looks a lot like a Vandermonde term, i.e. the hypergeometric distribution)_ `37:T4a5,{ const height = 350 const svg = d3.select(DOM.svg(width, height)); const margin = { top: 20, right: 20, bottom: 20, left: 60 }; const data = light_probs; const x = d3.scaleLinear() .domain([0, d3.max(data.map((d) => d.x))]) .range([margin.left, width - margin.right]) const y = d3.scaleLinear() .domain([0, d3.max(data.map((d) => d.y))]) .range([height - margin.top, margin.bottom]); svg.selectAll('line.stick') .data(data) .enter() .append('line') .attr('x1', (d) => x(d.x)) .attr('x2', (d) => x(d.x)) .attr('y1', (d) => y(d.y)) .attr('y2', (d) => height - margin.top) .attr('stroke', 'black') svg.selectAll('circle') .data(data) .enter() .append('circle') .attr('r', 3) .attr('cx', (d) => x(d.x)) .attr('cy', (d) => y(d.y)) .attr('fill', 'red'); svg.append("g") .attr("class", "axis axis--x") .attr("transform", `translate(${-0.5},${height - margin.bottom})`) .call(d3.axisBottom(x)); svg.append("g") .attr("class", "axis axis--y") .attr("transform", `translate(${margin.left - 10},0)`) .call(d3.axisLeft(y)); return svg.node() }38:T4a8,md` Earlier we showed that the mean, median, and mode don't do the best job of quickly converging to the number of lights that were on already. Now we'll turn to likelihood. Likelihood is generally used to answer the question "given the data I've seen, what is the most likely value for some parameter that I don't know?" In our case, the parameter is \`j\`, and since we've just worked out the probability distribution based on \`j\`, we can compute these likelihoods! _Note: distributions depending on a parameter like this are written as ${tex`P(i;j)`}_, We will consider each observation as a datapoint ${tex`x_1\ldots x_m`} and the set of data written as a vector ${tex`\vec{x}`}. Then the _likelihood_ of observing ${tex`\vec{x}`} dependent on j, is written: ${tex.block` \mathcal{L}(\vec{x};j) = P(x_1;j)P(x_2;j)\ldots P(x_m;j) `} The process of computing a _Maximum Likelihood Estimator_ is computing ${tex`\mathcal{L}(\vec{x};j)`} for all values of \`j\` and picking the highest probability. In some examples, you can use calculus to find an analytic solution, but our equation for ${tex`P(i;j)`} is tricky and I don't see a nice solution. _(if you do, please reach out!)_ `39:T445,md`### An example If our \`N=2\`, let's see what happens when we observe the data \`1,0,1\`. First, we need to compute ${tex`P(1;j)`} for each j: ${tex.block` \begin{aligned} P(1;0) &\simeq .095 \\ P(1;1) &\simeq .905 \\ P(1;2) &\simeq .095 \end{aligned} `} _(it may look strange that these don't sum to 1 but that's ok)_ So after our first sample, the MLE would be \`j=1\` because it has the highest probability. Let's compute for the next sample; we now need to look at ${tex`P(0;j)`} for each j: ${tex.block` \begin{aligned} P(0;0) &\simeq .903 \\ P(0;1) &\simeq .048 \\ P(0;2) &\simeq .003 \end{aligned} `} So now, we multiply ${tex`P(1;j)P(0;j)`} for all \`j\`, to get the MLE for both samples: ${tex.block` \begin{aligned} P(1,0;0) &\simeq .086 \\ P(1,0;1) &\simeq .043 \\ P(1,0;2) &\simeq .000 \end{aligned} `} After two datapoints, our prediction for \`j\` is \`0\`! After our last datapoint: ${tex.block` \begin{aligned} P(1,0,1;0) &\simeq .008 \\ P(1,0,1;1) &\simeq .039 \\ P(1,0,1;2) &\simeq .000 \end{aligned} `} So we're back to predicting \`j=1\` `3a:T517,{ const height = 350 const svg = d3.select(DOM.svg(width, height)); const margin = { top: 20, right: 20, bottom: 20, left: 60 }; const data = transpose(progressive_mle_simulation_data)[visualized_sample_size].map(function(j,p) { return {x: j, y: p || 0}; }); const x = d3.scaleLinear() .domain([0, d3.max(data.map((d) => d.x))*1.1]) .range([margin.left, width - margin.right]) const y = d3.scaleLinear() .domain([0, d3.max(data.map((d) => d.y))]) .range([height - margin.top, margin.bottom]); svg.selectAll('line.stick') .data(data) .enter() .append('line') .attr('x1', (d) => x(d.x)) .attr('x2', (d) => x(d.x)) .attr('y1', (d) => y(d.y)) .attr('y2', (d) => height - margin.top) .attr('stroke', 'black') svg.selectAll('circle') .data(data) .enter() .append('circle') .attr('r', 3) .attr('cx', (d) => x(d.x)) .attr('cy', (d) => y(d.y)) .attr('fill', 'red'); svg.append("g") .attr("class", "axis axis--x") .attr("transform", `translate(${-0.5},${height - margin.bottom})`) .call(d3.axisBottom(x)); svg.append("g") .attr("class", "axis axis--y") .attr("transform", `translate(${margin.left - 10},0)`) .call(d3.axisLeft(y)); return svg.node() }3b:T4c3,{ const height = 250 const svg = d3.select(DOM.svg(width, height)); const margin = { top: 20, right: 20, bottom: 20, left: 60 }; const data = dist_to_counter_dict(lights_observations); const x = d3.scaleLinear() .domain([0, d3.max(data.map((d) => d.x))]) .range([margin.left, width - margin.right]) const y = d3.scaleLinear() .domain([0, d3.max(data.map((d) => d.y))]) .range([height - margin.top, margin.bottom]); svg.selectAll('line.stick') .data(data) .enter() .append('line') .attr('x1', (d) => x(d.x)) .attr('x2', (d) => x(d.x)) .attr('y1', (d) => y(d.y)) .attr('y2', (d) => height - margin.top) .attr('stroke', 'black') svg.selectAll('circle') .data(data) .enter() .append('circle') .attr('r', 3) .attr('cx', (d) => x(d.x)) .attr('cy', (d) => y(d.y)) .attr('fill', 'red'); svg.append("g") .attr("class", "axis axis--x") .attr("transform", `translate(${-0.5},${height - margin.bottom})`) .call(d3.axisBottom(x)); svg.append("g") .attr("class", "axis axis--y") .attr("transform", `translate(${margin.left - 10},0)`) .call(d3.axisLeft(y)); return svg.node() }3c:[] 31:{"id":"25cf164abb085dbe","slug":"noisy-xor","title":"Flippin' switches (Noisy XOR)","thumbnail":"ae9c6f20ab29cda1e7e4fd8a3a0cd90fc2f3dcc4e22cefadf3e4532bb6a989d9","access_level":"public","create_time":"$D2018-11-09T23:07:08.939Z","update_time":"$D2020-05-04T06:57:54.600Z","view_time":null,"first_public_time":"$D2018-11-10T17:08:56.504Z","has_unpublished_edits":null,"fork":false,"stars":9,"starred":false,"owner":{"type":"team","id":"a8afac7fc0f0a766","login":"bbischof","name":"Bryan","avatar_url":"https://avatars-next.observableusercontent.com/c71257ace95ae262b20ea3ea4f4b2a09891e92c86bf45e64d1b97d82d212a332","tier":"starter_2024"},"version":1916,"publish_version":1916,"role":null,"authored":false,"authors":[{"type":"individual","id":"32ac87846a6eed40","login":"bbischof","name":"Bryan","avatar_url":"https://avatars-next.observableusercontent.com/c71257ace95ae262b20ea3ea4f4b2a09891e92c86bf45e64d1b97d82d212a332","tier":null}],"members":[{"type":"individual","id":"32ac87846a6eed40","login":"bbischof","name":"Bryan","avatar_url":"https://avatars-next.observableusercontent.com/c71257ace95ae262b20ea3ea4f4b2a09891e92c86bf45e64d1b97d82d212a332","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Flippin' switches (Noisy XOR)","cells":[{"id":0,"value":"md`# Flippin' switches (Noisy XOR)\n\n

\n\n_In this explorable, I want to talk though a little probability problem, and some ways you might approach thinking about it. We are going to talk a bit about binomial distributions, combinatorics, convolutions, and maximum likelihood estimates. This requires very little previous knowledge, only about things like binomial coefficients and such._\n\n〰️〰️〰️〰️〰️\n\nLet's consider the following question:\n\n> Given N lightswitches with \\`j\\` of them already turned on, if while walking past, you independently have a likelihood, \\`p\\`, of flipping each switch, what is the probability that afterwords, there are still \\`j\\` lights on?\n\nA convenient observation, is to see that this can be modeled with binary strings and the XOR function, so let's take a look at some simulations.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1790,"value":"toc()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"viewof N = slider(\n {\n min: 4, \n max: 16, \n step: 1, \n value: 8,\n title: \"Let N =\", \n description: \"Length of our bitstrings\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1748,"value":"md`For the purposes of most of this, setting p fixed to ${p} will make things easier. Later, feel free to adjust \\`p\\`. It won't break anything, but this way is easier to understand.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":213,"value":"md`Let's generate an initial configuration of on and off switches. We'll just assume each has a 50% chance of being on.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":119,"value":"RandSeed = N_length_bitstring_with_prob_p(.5)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":239,"value":"md`We see that this has \n\n\\`j=\\` ${RandSeed.reduce((a, b) => a + b, 0)} \n\non-switches.` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":216,"value":"md`Similarly, using our probability \\`p\\`, let's generate a random list of switches to flip:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"e = N_length_bitstring_with_prob_p(p)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":218,"value":"md`\nThen, the remaining switches on is the sum of the bits of these two bitstrings' XOR:\n\nRemaining switches on = ${xor_lists(RandSeed, e).split(\"\").map(_ => parseInt(_)).reduce((a, b) => a + b, 0)}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":228,"value":"md`OK, let's simulate doing this many times. First, let's see the distribution of how many flips in ${M} random trials:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":102,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":230,"value":"md`This is actually just the Binomial distribution! This follows because we have \\`N\\` independent trials with probability \\`p\\`. Later, we will care about its mean and variance, which are:\n\n${tex.block`\n\\mu = Np,\\hspace{20pt} \\sigma^2 = Np(1-p)\n`}\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":235,"value":"md`Let's now examine the effect on the original lightswitch array, what does that distribution look like? \n\nNote: We are keeping the original lightswitch array fixed, and changing our flip patterns`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":178,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":242,"value":"md`\nCompare the mode _(the largest bar)_ to the number of on-switches _(${j})_. \n\nThe mean is ${dist_of_seed_sums.reduce((previous, current) => current += previous)/dist_of_seed_sums.length}, however, which isn't necessarily valid number of switches, how close is it to ${j}?\n\nThe median, is ${sorted_seed_sums[Math.floor(sorted_seed_sums.length / 2)]}, how bout that one?\n\nThese are all for a ${M} iterations. \n\nWe're interested in seeing how they change as we play more rounds. \n\n_(increment and decrement N to see how things change as the total lightswitches changes)_\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":489,"value":"{\n const div = html`

`\n div.appendChild(incdec(\"N\", viewof N));\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":494,"value":"\nmd`N=${N}, Remember the number of lights on at first is ${RandSeed.reduce((a, b) => a + b, 0)}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1821,"value":"vl.markLine()\n .data(running_means_of_ss.slice(0,100).map((y, x) => ({'sample': x, 'mean': parseInt(y)})))\n .width(width)\n .height(100)\n .title('Running (rounded)mean calculation (first 100 samples)')\n .encode(\n vl.x().fieldQ('sample'),\n vl.y().fieldQ('mean')\n )\n .render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1828,"value":"vl.markLine()\n .data(running_medians_of_ss.slice(0,50).map((y, x) => ({'sample': x, 'median': y})))\n .width(width)\n .height(100)\n .title('Running median calculation (first 50 samples)')\n .encode(\n vl.x().fieldQ('sample'),\n vl.y().fieldQ('median')\n )\n .render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1834,"value":"vl.markLine()\n .data(running_modes_of_ss.slice(0,50).map((y, x) => ({'sample': x, 'mode': y})))\n .width(width)\n .height(100)\n .title('Running mode calculation (first 50 samples)')\n .encode(\n vl.x().fieldQ('sample'),\n vl.y().fieldQ('mode')\n )\n .render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":576,"value":"md`The point of these is to see the _convergence rate_ of these statistics. Sometimes they converge quickly, but not always. We're hoping to find something consistent!`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1105,"value":"md`Let's now run our entire experiment ${iters} times, and see—at each iteration—what percentage of these statistics have already converged to the right value, ${j}. Convergence means that in 99% of our ${iters} iterations that statistic has settled onto the value ${j}.\n\n(Recall also N= ${N}).\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1121,"value":"{\n const div = html`

`\n div.appendChild(incdec(\"N\", viewof N));\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1837,"value":"vl.markLine()\n .data(\n metrics_dictionary['prog_means'].slice(\n 0,\n metrics_dictionary['means_conv_val']*1.5\n ).map(\n (y, x) => (\n {'sample': x, 'percentage': y}\n )\n )\n )\n .width(width)\n .height(100)\n .title(\n 'Percentage of running means matching '\n + j \n + ' (Exceeds threshold @ ' \n + metrics_dictionary['means_conv_val'] \n + ')'\n )\n .encode(\n vl.x().fieldQ('sample'),\n vl.y().fieldQ('percentage')\n )\n .render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1844,"value":"vl.markLine()\n .data(\n metrics_dictionary['prog_medians'].slice(\n 0,\n metrics_dictionary['medians_conv_val']*1.5\n ).map(\n (y, x) => (\n {'sample': x, 'percentage': y}\n )\n )\n )\n .width(width)\n .height(100)\n .title(\n 'Percentage of running medians matching '\n + j \n + ' (Exceeds threshold @ ' \n + metrics_dictionary['medians_conv_val'] \n + ')'\n )\n .encode(\n vl.x().fieldQ('sample'),\n vl.y().fieldQ('percentage')\n )\n .render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1847,"value":"vl.markLine()\n .data(\n metrics_dictionary['prog_modes'].slice(\n 0,\n metrics_dictionary['modes_conv_val']*1.5\n ).map(\n (y, x) => (\n {'sample': x, 'percentage': y}\n )\n )\n )\n .width(width)\n .height(100)\n .title(\n 'Percentage of running modes matching '\n + j \n + ' (Exceeds threshold @ ' \n + metrics_dictionary['modes_conv_val'] \n + ')'\n )\n .encode(\n vl.x().fieldQ('sample'),\n vl.y().fieldQ('percentage')\n )\n .render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1171,"value":"md`Let's consider all possible values for j with our fixed \\`N= \\`${N}, and summarize in a table. Note that \\`-1\\` means it failed to converge within the 100 trials.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1147,"value":"table( convergences_lookup[N]\n, { title: \"Length of convergence for varying j\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1759,"value":"md`Generally we see that the mean and mode do alright. But we can do better.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":600,"value":"md`# Computing some probabilities mathematically`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":602,"value":"md`\nI'm happy to say that we succeeded at seeing the behavior from our simulations, but let's try to work out some of this more precisely for our future goals. We're going to do some combinatorial probablity now, but nothing gets too complicated.\n\nRecall that \\`N\\` is the length of our array of light switches(which we've thought of as a bitstring), and also recall that we use \\`j\\` to refer to the number of on-switches in our initial light-switch array.\n\nWe will simplify some things by fixing \\`j\\`, and looking at how the probabilities of different light counts are after our random switching.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":606,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":634,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":658,"value":"md`Maybe it's time we get back to computing some things and looking at numbers.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":746,"value":"md`With our seed, ${RandSeed}, and N=${N}, p=${p}, then let's plot the probabilities of leaving \\`i\\` remaining lights on:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":741,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":744,"value":"{\n const div = html`

`\n div.appendChild(incdec(\"N\", viewof N));\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":824,"value":"md`N= ${N}, j=${j}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":754,"value":"md`The sum of these values multiplied by their respective probabilities gives the _expected value_: ${exp_val}. \n\nSimilarly, we compute the variance by computing the expected value of the random variable ${tex`Z=(i-\\mu)^2`}, where ${tex`\\mu`} is that expected value we just calculated. This looks like:\n${tex.block` \\sum_i m_s(i) * (i- \\mu)^2`}\nin our case. Which works out to ${variance}.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":822,"value":"md`If you want to look at all the combinations for \\`i\\` and \\`j\\`, with our \\`N= \\` ${N} we've produced a table:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":811,"value":"table(light_probs_general_lookup[N], { title: \"Probabilities of various i, j combinations with fixed N\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1331,"value":"md`## Using likelihood to converge faster`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1333,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1348,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1361,"value":"md`### Simulating the performance of MLE\n\nLet's run a bunch of simulations and see how well they predict. In this data we ran \\`1000\\` simulations, and we took enough samples for the MLE to actually converge. We show the results for \\`N=\\`${N}, and varying \\`j\\`.\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1367,"value":"table(progressive_mle_simulation_data.map(function(l, j) {\n return {\n j: j, \n mle_convergence_value: l.findIndex(function (el) {return el > .99;}),\n };\n }\n ), { title: \"Convergence of MLE's with varying j and fixed N\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1371,"value":"md`Let's play with visualizing this as we adjust j:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1373,"value":"viewof visualized_j = slider(\n {\n min: 0, \n max: N, \n step: 1, \n value: 2,\n title: \"Let visualized j =\", \n description: \"Convergence plot for specified j value\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1849,"value":"vl.markLine()\n .data(\n progressive_mle_simulation_data[visualized_j].map(\n (y, x) => ({'sample': x, 'MLE accuracy %': y})\n )\n )\n .width(width)\n .height(100)\n .title(\n 'With initial lights = ' \n + visualized_j \n + ', then MLE converges after ' \n + progressive_mle_simulation_data[visualized_j].findIndex(\n function (el) {return el > .99;}\n )\n + ' samples'\n )\n .encode(\n vl.x().fieldQ('sample'),\n vl.y().fieldQ('MLE accuracy %')\n )\n .render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1378,"value":"md`As we take more and more samples, how does the accuracy of MLE look spread across the various \\`j\\` for a fixed \\`N\\`?\n\nTry adjusting the sample size and seeing:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1380,"value":"viewof visualized_sample_size = slider(\n {\n min: 0, \n max: progressive_mle_simulation_data[0].length-1, \n step: 1, \n value: 2,\n title: \"Let sample size =\", \n description: \"Number of datapoints used to validate MLE\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1384,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1388,"value":"md`\n\nThe takeaway here is that MLE converges much more quickly than the mean, median, or mode, and it's much more consistent. \n\nWe can look at the worst j for each value of N to see how many samples we're required to converge:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1392,"value":"viewof scatter = vegaEmbed ({\n $schema: \"https://vega.github.io/schema/vega-lite/v2.json\",\n width: 400,\n data: {values: worst_cases},\n mark: {type: \"circle\"},\n encoding: {\n x: {field: \"N\", type: \"quantitative\", scale: {domain: [3,17]}},\n y: {field: \"samples_required\", type: \"quantitative\"}, \n },\n config: {\n axis: {grid: false},\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1398,"value":"md`## Let's play\n\nPick your initial lights, click sample, and watch our metrics evolve!\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1636,"value":"{\n const div = html`

`\n div.appendChild(incdec(\"N\", viewof N));\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1494,"value":"viewof your_lights = {\n const form = html``;\n form.value = [];\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1763,"value":"md` You've turned on ${your_lights.length} lights.` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1489,"value":"viewof lights_observations = {\n const form = html``;\n form.sample.onclick = event => {\n form.value = form.value.concat( \n xor_lists(\n Array(N).fill().map(\n (_,i) => your_lights.includes((i)) ? 1: 0\n ),\n N_length_bitstring_with_prob_p(p)\n ).split(\"\").map(_ => parseInt(_)).reduce((a, b) => a + b, 0)\n );\n form.dispatchEvent(new CustomEvent(\"input\"));\n event.preventDefault();\n };\n form.reset.onclick = event => {\n form.value = [];\n form.dispatchEvent(new CustomEvent(\"input\"));\n event.preventDefault();\n };\n form.value = [];\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1670,"value":"md`So far we've seen: ${JSON.stringify(lights_observations.reduce(function(obj, item) {\n obj[item] = (obj[item] || 0) + 1;\n return obj;\n }, {}) )}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1673,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1857,"value":"vl.markLine()\n .data(\n lights_observations.map(\n (num,i) => lights_observations.slice(0,i + 1)\n .reduce(\n (prev,curr) => prev + curr\n )\n ).map(\n (_,idx) => _/(idx+1)\n ).map(\n (y, x) => (\n {'observations': x, 'mean': parseInt(y)}\n )\n )\n )\n .width(width)\n .height(100)\n .title(\n 'With your initial lights = ' \n + your_lights.length\n + \", the mean's evolution\"\n )\n .encode(\n vl.x().fieldQ('observations'),\n vl.y().fieldQ('mean')\n )\n .render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1864,"value":"vl.markLine()\n .data(\n lights_observations.map(\n (num,i) => lights_observations.slice(0,i + 1)\n )\n .map(\n _ => _.sort()[Math.floor(_.length / 2)]\n ).map(\n (y, x) => (\n {'observations': x, 'median': parseInt(y)}\n )\n )\n )\n .width(width)\n .height(100)\n .title(\n 'With your initial lights = ' \n + your_lights.length\n + ', the median evolution'\n )\n .encode(\n vl.x().fieldQ('observations'),\n vl.y().fieldQ('median')\n )\n .render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1868,"value":"vl.markLine()\n .data(\n lights_observations.map(\n (num,i) => lights_observations.slice(0,i + 1)\n )\n .map(\n _ => dist_to_counter_dict(_)\n )\n .map(\n obj => Object.keys(obj).reduce((a, b) => obj[a]['y'] > obj[b]['y'] ? a : b)\n )\n .map(\n (y, x) => (\n {'observations': x, 'mode': parseInt(y)}\n )\n )\n )\n .width(width)\n .height(100)\n .title(\n 'With your initial lights = ' \n + your_lights.length\n + ', the mode evolution'\n )\n .encode(\n vl.x().fieldQ('observations'),\n vl.y().fieldQ('mode')\n )\n .render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1570,"value":"md`and now, our MLE observations:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1879,"value":"vl.markLine()\n .data(\n lights_observations.map(\n (num,i) => lights_observations.slice(0,i + 1)\n ).map( \n l => compute_max_likelihood_estimate(l, N)\n ).map(\n (y, x) => ({'observations': x, 'MLE': y})\n )\n )\n .width(width)\n .height(100)\n .title(\n 'With your initial lights = ' \n + your_lights.length\n + ', the MLE evolution'\n )\n .encode(\n vl.x().fieldQ('observations'),\n vl.y().fieldQ('MLE')\n )\n .render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1253,"value":"md`# What's Next`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1255,"value":"md`Our next adventure is to use what we've learned to figure out _which_ light switches are on, despite the random flipping that goes on all the time. \n\nUntil next time... I hope this was _illuminating_. 💡💡💡`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":783,"value":"// md`## Confidence`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":573,"value":"md`🐉`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1774,"value":"md` ### Thanks\n\nMany thanks to [@fil](https://beta.observablehq.com/@fil), [redblob](https://www.redblobgames.com/), [@jashkenas](https://beta.observablehq.com/@jashkenas), [@mbostock](https://beta.observablehq.com/@mbostock), and [dxbydt_jasq](https://twitter.com/dxbydt_jasq) for technical assistance and feedback. \n\nAlso thanks to Will Chernoff, Eric Bunch, and Helen Ip for content feedback.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1771,"value":"md` \n\n〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️〰️\n\n## The sausage making\n\nAll of the code used to produce the above is either in the cells above, or down here. I've included the code used to generate datasets, but some of those datasets were so big, I precomputed and stored them elsewhere. But you could use the below to even compute those datasets ^_^.\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1750,"value":"viewof p = slider(\n {\n min: 0, \n max: 1, \n step: .01, \n value: .05,\n title: \"Let p =\", \n description: \"probability of error\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1365,"value":"progressive_mle_simulation_data = progressive_mle_simulation_lookup[N]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1390,"value":"worst_cases = Object.keys(progressive_mle_simulation_lookup).map( \n (n_data, i) => [\n Math.max(...progressive_mle_simulation_lookup[n_data].map(\n function(l, j) {\n return l.findIndex(function (el) {return el > .99;});\n }\n )\n ), parseInt(n_data)]\n).map(\n function(w) {\n return {N: w[1], samples_required: w[0]};\n }\n) ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1363,"value":"progressive_mle_simulation_lookup = d3.json(\"https://gist.githubusercontent.com/BBischof/695327ce79ce07c9195c43250a4a80a3/raw/16c37ca9593d1e461d9628de53ff820b8596ed28/lightswitch_simulation_mle_percentages.json\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1178,"value":"md`This is a bunch of the underlying code to generate various parts of the above.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":770,"value":"variance = Array(N+1).fill()\n.map( \n (_,k) => k ).map(function(key) {\n return ((key-exp_val)**2)*(conv(key) || 0);\n }) \n.reduce((prev,curr) => prev + curr) ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":761,"value":"exp_val = Array(N+1).fill()\n.map( \n (_,k) => k ).map(function(key) {\n return key*(conv(key) || 0);\n })\n.reduce((prev,curr) => prev + curr) ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1118,"value":"viewof M = slider(\n {\n min: 10, \n max: 1000, \n step: 10, \n value: 100,\n title: \"Let M =\", \n description: \"Number of iterations for our experiment\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1181,"value":"md`Stuff for the simulation part`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1115,"value":"iters = 1000","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1070,"value":"metrics_dictionary = precalculated_sims_and_metrics[N][j]['sims_metrics']","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1233,"value":"convergences_lookup = d3.json(\"https://gist.githubusercontent.com/BBischof/48da595cead3d59888cf93e45d7aca97/raw/fb6afc9546333da829624ee69f283ec038b0247e/lightswitch_simulation_convergences.json\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1244,"value":"generate_convergences_table = (Y) => Array(Y+1).fill()\n .map( \n (_,j) => precalculated_sims_and_metrics[N][j]['sims_metrics']\n ).map(function(key, j) {\n return {\n j: j, \n conv_value_for_mean: key['means_conv_val'], \n conv_value_for_median: key['medians_conv_val'], \n conv_value_for_mode: key['modes_conv_val'], \n };\n }\n )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1067,"value":"make_sims = (_input_j) => {\n const j_seed = make_j_digit_seed(_input_j)\n return Array(iters).fill().map( _ => Array(M).fill().map( \n _ => xor_lists(\n j_seed, \n N_length_bitstring_with_prob_p(p)\n ).split(\"\").map(_ => parseInt(_)).reduce((a, b) => a + b, 0)\n ))\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1261,"value":"simulate_progressive_mles = (_input_j, sims) => {\n const mles = sims.map( run => run.map(\n (num,i) => run.slice(0,i + 1)\n ).map( l => compute_max_likelihood_estimate(l, N))\n )\n return transpose(mles).map( r => r.map( m => m == _input_j ? 1 : 0 ).reduce((a, b) => a+b)/iters )\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1263,"value":"compute_max_likelihood_estimate = (obs, n) => obs.map( \n x => Array(N+1).fill().map(\n (_,k) => [x,k]\n )\n ).map(\n _ => _.map(\n function(key) {\n return conv_general(key[0], n, key[1]) || 0;\n }\n )\n ).reduce( \n (a,b) => dotProd(a,b)\n ).reduce(\n (iMax, x, i, arr) => x > arr[iMax] ? i : iMax, 0\n )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1265,"value":"dotProd = (r, a) => r.map((b, i) => a[i] * b)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1723,"value":"precalculated_sims_and_metrics = d3.json(\"https://gist.githubusercontent.com/BBischof/a0b96ed38dcc57d1ac7e6799f1608e8d/raw/b664006b4a49829f06f21c504cd6786c6bf5c295/lightswitch_simulation_metrics.json\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1063,"value":"make_sims_and_metrics_from_j = (_input_j) => {\n const sims = make_sims(_input_j)\n const means = simulate_progressive_means(_input_j, sims)\n const medians = simulate_progressive_medians(_input_j, sims)\n const modes = simulate_progressive_modes(_input_j, sims)\n return {\n prog_means: means,\n means_conv_val: means.findIndex(function (el) {return el > .99;}),\n prog_medians: medians,\n medians_conv_val: medians.findIndex(function (el) {return el > .99;}),\n prog_modes: modes,\n modes_conv_val: modes.findIndex(function (el) {return el > .99;}),\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1059,"value":"simulate_progressive_modes = (_input_j, sims) => {\n const modes = sims.map( run => run.map(\n (num,i) => run.slice(0,i + 1)\n ).map(_ => dist_to_counter_dict(_)).map(\n obj => Object.keys(obj).reduce((a, b) => obj[a]['y'] > obj[b]['y'] ? a : b)\n )\n )\n return transpose(modes).map( r => r.map( m => m == _input_j ? 1 : 0 ).reduce((a, b) => a+b)/iters )\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1055,"value":"simulate_progressive_means = (_input_j, sims) => {\n const means = sims.map( run => run.map(\n (num,i) => run.slice(0,i + 1)\n .reduce((prev,curr) => prev + curr)\n ).map((_,idx) => _/(idx+1))\n )\n return transpose(means)\n .map( r => r.map( m => Math.round(m) == _input_j ? 1 : 0 ).reduce((a, b) => a+b)/iters )\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1048,"value":"simulate_progressive_medians = (_input_j, sims) => {\n const medians = sims.map( run => run.map(\n (num,i) => run.slice(0,i + 1)\n ).map(\n _ => _.sort()[Math.floor(_.length / 2)])\n )\n return transpose(medians)\n .map( r => r.map( m => m == _input_j ? 1 : 0 ).reduce((a, b) => a+b)/iters )\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1184,"value":"md`Stuff for the distribution explanations and general introduction`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1130,"value":"sorted_seed_sums = dist_of_seed_sums.clone().sort()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1127,"value":"dist_of_seed_sums = {\n const data = Array(M).fill().map( \n _ => xor_lists(\n RandSeed, \n N_length_bitstring_with_prob_p(p)\n ).split(\"\").map(_ => parseInt(_)).reduce((a, b) => a + b, 0)\n );\n data.y = \"count\";\n data.x = \"errors (#)\";\n return data;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1135,"value":"N_length_bitstring_with_prob_p = (p) => Array(N).fill().map((_, idx) => random_boolean(p))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":656,"value":"j = RandSeed.reduce((a, b) => a + b, 0)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1187,"value":"md`stuff to make the probablities explanations`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1215,"value":"light_probs_general_lookup = d3.json(\"https://gist.githubusercontent.com/BBischof/7cfa755c7ae3284a84e5f2d0afffbee2/raw/12f606685604a2f22f22b9e9cb401741dff3e26a/lightswitch_simulation_probabilities.json\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":803,"value":"// light_probs_general = Array(N+1).fill().map( (_,J) => \n// Array(N+1).fill()\n// .map( \n// (_,k) => k ).map(function(key) {\n// return {Initial_lights: J, Remaining_lights: key, probability: conv_general(key, N, J) || 0};\n// })\n// ).flat()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":698,"value":"light_probs = Array(N+1).fill()\n.map( \n (_,k) => k ).map(function(key) {\n return {x: key, y: conv(key) || 0};\n })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1189,"value":"md`stuff to compute the combinatorial things`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":799,"value":"conv_general = (i, n, J) => Math.pow(p, J - i) * Math.pow(1 - p, i - J) * conv_sum_general(i, n, J)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":664,"value":"conv = (i) => Math.pow(p, j - i) * Math.pow(1 - p, i - j) * conv_sum(i)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":795,"value":"conv_sum_general = (i, n, J) => Array(i+1).fill()\n.map( \n (_,k) => conv_sum_term_general(i, n, J, k)\n )\n.reduce((a,b) => a+b)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":675,"value":"conv_sum = (i) => Array(i+1).fill()\n.map( \n (_,k) => conv_sum_term(i,k)\n )\n.reduce((a,b) => a+b)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":791,"value":"conv_sum_term_general = (i, n, J, k) => (\n Math.pow(p, 2*k) * Math.pow(1 - p, n - 2*k) * choose(n - J, k) * choose(J, i - k)\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":666,"value":"conv_sum_term = (i, k) => Math.pow(p, 2*k) * Math.pow(1 - p, N - 2*k) * choose(N - j, k) * choose(j, i - k)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1201,"value":"md`stuff to make the 1 iteration example for the various metrics`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":166,"value":"dist_to_counter_dict = function(dist) {\n const occ = dist.reduce(function(obj, item) {\n obj[item] = (obj[item] || 0) + 1;\n return obj;\n }, {}) \n return Array(N+1).fill().map((_,idx) => idx).map(function(key) {\n return {x: key, y: occ[key] || 0};\n })\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":338,"value":"partial_sums_of_ss = dist_of_seed_sums.map(\n (num,i) => dist_of_seed_sums.slice(0,i + 1)\n .reduce((prev,curr) => prev + curr)\n)\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":391,"value":"running_means_of_ss = partial_sums_of_ss.map((_,idx) => _/(idx+1))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":365,"value":"running_medians_of_ss = dist_of_seed_sums.map(\n (num,i) => dist_of_seed_sums.slice(0,i + 1)\n).map(_ => _.sort()[Math.floor(_.length / 2)])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":400,"value":"running_modes_of_ss = dist_of_seed_sums.map(\n (num,i) => dist_of_seed_sums.slice(0,i + 1)\n).map(_ => dist_to_counter_dict(_)).map(\n obj => Object.keys(obj).reduce((a, b) => obj[a]['y'] > obj[b]['y'] ? a : b)\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1206,"value":"md`intro stuff and imports`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1145,"value":"dist_of_error_counts = {\n const data = Array(M).fill().map( \n _ => N_length_bitstring_with_prob_p(p)\n .reduce((a, b) => a + b, 0)\n );\n data.y = \"count\";\n data.x = \"errors (#)\";\n return data;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"function random_boolean(q) {\n if (Math.random() <= q) {\n return 1;\n }\n else {\n return 0;\n }\n}\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"xor_lists = function(x,y) {\n return (x.join(\"\").b() ^ y.join(\"\").b()).toString(2)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":345,"value":"String.prototype.b = function() { return parseInt(this,2); }","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":"import {binomial, _} from \"@herbps10/binomial-distribution\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"import {slider, text} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"import {margin, height, width} from \"@mbostock/d3-histogram\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":316,"value":"import {visualize} from \"@tmcw/noises\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1794,"value":"import {vz} from \"@bbischof/vizsla-and-vega-lite\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1801,"value":"import {vl} from '@bbischof/vega-lite-api'","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":486,"value":"import {incdec} from \"@bbischof/images-of-monomials-over-z_p-mod-n\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":809,"value":"import {table} from \"@tmcw/tables/2\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":705,"value":"function choose(n, k) {\n if(k<0) return 0;\n if(k>n) return 0;\n if(k > n / 2) return choose(n, n - k);\n let res = 1;\n \n for(let i = 1; i <= k; i++) {\n res *= (n + 1 - i) / i;\n }\n \n return res;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1045,"value":"transpose = function (matrix) {\n return matrix.reduce((prev, next) => next.map((item, i) =>\n (prev[i] || []).concat(next[i])\n ), []);\n}\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":585,"value":"Array.prototype.clone = function() {\n\treturn this.slice(0);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1141,"value":"make_j_digit_seed = (j) => Array(j).fill().map( _ => 1).concat(Array(N-j).fill().map( _ => 0))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":438,"value":"bvisualize = line => {\n let ctx = DOM.context2d(width, 150);\n ctx.moveTo(0, 100 + line[0] * 5);\n for (let i = 1; i < line.length; i++) {\n ctx.lineTo((width / line.length) * i, 100 + line[i] * 5)\n }\n ctx.stroke();\n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1394,"value":"vegaEmbed = require(\"vega-embed@3\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1396,"value":"import {checkbox, button} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1786,"value":"import {toc} from \"@mbostock/toc\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3c","stdlib":"1","titling":"auto"}} 32:"$31:body"