Author: Neil

I wanted to be able to decode a stream that had multiple, undelineated, JSON string representations in it. For example, a file like this:

[1, 2, 3] [4, 5, 6] [7, 8] [9, 10, 11, 12]

Which has multiple JSON arrays in it, separated only by (optional) whitespace. Perhaps they might be separated by other characters in other applications (e.g., comma separated JSON strings)

First stop, as always, was stackoverflow, which had some relevant answers, like this one:

https://stackoverflow.com/questions/6886283/how-i-can-i-lazily-read-multiple-json-values-from-a-file-stream-in-python

I decided to write a variant of the several “read it in chunks, try to JSONDecode it, keep reading more if it doesn’t yet parse” solutions. Here is my take at this problem, as a gist:

https://gist.github.com/outofmbufs/bcf3bccc1fe0bb0824871ec5e02cc60e

Posting this in the hopes, as always, that someday someone will be looking for something like this and stumble across it via google (if I’ve somehow worked enough key phrases into this posting)

The coin flip experiment I described before is still running… so far for 62 days. It is running on a dedicated linux box on my network:

nw@randomlinux$ uname -a
Linux randomlinux 4.9.0-6-amd64 #1 SMP Debian 4.9.88-1 (2018-04-29) x86_64 GNU/Linux

nw@randomlinux:~$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
Thread(s) per core:    1
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 76
Model name:            Intel(R) Atom(TM) x5-Z8350  CPU @ 1.44GHz
Stepping:              4
CPU MHz:               482.695
CPU max MHz:           1920.0000
CPU min MHz:           480.0000
BogoMIPS:              2880.00
Virtualization:        VT-x
L1d cache:             24K
L1i cache:             32K
L2 cache:              1024K
NUMA node0 CPU(s):     0-3

and the updated results are:

• Trials Completed: 5,008,009
• Total Coin Flips: 8,604,595,583,786
• Longest Trial: 2,785,974,537,774
• Trials Ending in 2 flips: 2,504,265 (50.005%)

Updated breakdown of the percentages of trials completed in N flips, and the corresponding prediction:

length (flips)	actual %	theoretical %
2	50.005%	50.00%
4	12.503%	12.50%
6	6.244%	6.25%
8	3.903%	3.906%
10	2.736%	2.734%
12	2.062%	2.051%
14	1.610%	1.611%
16	1.316%	1.309%

I’m letting this run until the next power failure terminates the experiment. Unfortunately the little box this is running on is not set up on a UPS. My power typically glitches (short outages) a few times each year (I’ve written about this before) so I don’t know how long to expect this run to get, but as long as it is still running I will keep collecting the data. Let’s hope for no thunderstorms in the hilltop area any time soon.

 

In a previous post I wrote about this question:

On average, how many times do you have to flip a (fair) coin to get an equal number of heads and tails?

and suggested that the answer was probably infinite (on average), although half the time you get there in just two flips: HT or TH, which are half the possible cases for two flips: HH, HT, TH, TT.

To review: there are 4 possible combinations of two flips: HH, HT, TH, TT. Each is equally likely. Two of them – HT and TH – reach equal heads/tails equality. Let’s call this “reaching delta zero” where delta refers to the difference in heads vs tails count. Since two out of four equally-likely sequences reach delta zero, there is a 50% chance of getting there in just two flips.

The next stage has four flips (three flips will never have delta zero), and there are sixteen possibilities for four flips. However, half of them were eliminated at two flips, leaving only the sequences that start with HH or TT:

HHHH, HHHT, HHTH, HHTT
TTHH, TTHT, TTTH, TTTT

Two of these sequences reach delta zero: HHTT and TTHH. So there is a 2 out of 8 ( i.e., 1 out of 4) chance of reaching delta zero at four flips, except we have to account for the 50% chance of never even getting to four flips, so there is a 1 out 8 = 12.5% chance of finishing at four flips.

In the prior post I discussed the catalan numbers and how they relate to the number of these sequences. From that discussion we can compute the probabilities of a given trial run ending (reaching delta zero) at any particular stage. This works out as follows:

# FLIPS      % reaching equality here
    2            50%
    4            12.5%
    6             6.25%
    8             3.91%
   10             2.73%
   12             2.05%
   14             1.61%

Unlike the chart shown in the previous posting, these numbers are the chance of the trial ending at the specific level (e.g., a 3.91% chance any given trial run will take exactly 8 flips, no more / no fewer).

I wrote a simulation in python to test this, and I have been running it for over three weeks. Highlights of key results:

• • Trials Completed: 3,414,318. This is how many runs were made where each run consisted of python code along these lines (except the actual code used some unrolling and optimization techniques I’ve written about  before). This code is essentially simulating flipping a coin and counting the “delta” between the number of heads and tails, so each flip either adds one or subtracts one from that running delta and equality of heads and tails is reached when the delta becomes zero.

delta = random.choice((-1, 1))
flips = 1
while delta != 0:
    delta += random.choice((-1, 1))
    flips += 1

• • Total number of coin flips: 3,197,243,199,696. Yes, you are reading that correctly, over 3 trillion simulated flips. I will point out that python, like many (most? all?) runtimes these days uses the Mersenne Twister random number generator with period 2**19937-1; no older style random number generators that have much much shorter periods would be suitable for this sort of experiment.
  • Longest run: 1,204,531,561,152. Yes, that’s another “you read that right”. The longest string of coin flips it took to reach equality was a little over 1.2 trillion. That is, after the first flip generated a delta of +1 or -1, in that sequence it wasn’t until 1.2 trillion flips later that the delta was back down to zero.
  • Runs ending at 2 flips: 1,707,887 (50.02%). This is as we predicted. experimental results error is 728 out of over 3.4M trials, which comes to a difference of about 213 ppm (or however you want to think of that difference from the perfect 50%).

Here’s a breakdown of the percentages of trials completed in N flips, and the corresponding prediction:

length (flips)	actual %	theoretical %
2	50.02%	50.00%
4	12.498%	12.50%
6	6.251%	6.25%
8	3.901%	3.906%
10	2.739%	2.734%
12	2.061%	2.051%
14	1.613%	1.611%
16	1.312%	1.309%

I found this write-up nicely describing the math of this and in particular analyzing that the average will indeed diverge to infinity.

The results of seemingly-simple probability questions are often counter-intuitive. “How long will it take me to get an equal number of heads and tails while flipping a coin?” and the answer is “fairly often it could take a very very long time”