The Incredible Shrinking BernoulliSimulating Hacker News inter-arrival times distribution with the flip of a coinJean-Frederic PlanteBlockedUnblockFollowFollowingJun 29Joey Kyber via PexelsBernoulli counting processBernoulli distributions sounds like a complex statistical construct, but they represent flipping a coin (possibly biased).
What I find fascinating is how this simple idea can lead to modeling more complex processes such as the probability to get a post upvoted for which I will post a story at a later date.
A Bernoulli counting process evaluates the distributions of events for a certain number of flip trials n.
For a sequence n of random binaries, we evaluate the probability that the sum of is a certain number.
For example, for those 10 trials, the sum would be S([0,0,1,0,1,1,0,0,0,0]) = 3.
With a process having a probability p, the expectation for S over n trials is p*n.
For example if p=0.
3, the expectation over 10 trials is to have 3 events.
Poisson counting process intuition from Bernoulli counting processPoisson processes are an extension of Bernoulli to the continuous space.
It is used to model arrival times, or event counts probabilities for a certain period of time.
In the simplifying case of an homogeneous Poisson process, it is defined by λ its rate or intensity.
λ is the average number of events per unit of time, so the expectation for time t for the number of events is λ*t.
For example if λ = 0.
3 (per second), the expectation over 10s is to have 3 events.
We can see that both as related, and if you imagine the Bernoulli trial as a time sampled version of the Poisson point process.
We can arbitrarily define the Bernoulli increment as 1/k, and simulating a poisson distribution of rate λ leads us to define the probability as p = λ/k.
Notebook for this simulation is here.
Shrinking Bernoulli converges to PoissonBernoulli and Poisson process inter-arrival times distributionThe unintuitive part for Bernoulli process comes with the inter-arrival times.
Continuing with the example above for p=0.
3, you may first guess the distribution of inter-arrival distribution would be peaking around 3.
However, the distribution is actually geometric and we can similarly simulate the inter-arrival times of the Poisson process.
Consider an initial condition where the event occurred.
Let’s call Yᵢ the value of the event at increment i after initial event occurred.
If the distance is 1, then then Y₁=1 and the probability of this is p.
For the distance to be 2, we need Y₁=0, Y₂=1 which probability is (1-p)*p.
For 3, Y₁=0, Y₂=0, Y₃=1 which probability is (1-p)²p.
And so on, with the probability for distance X to be i beingInter-arrival distance is geometricA quick simulation confirms thisThis inter-arrival time also helps get the intuition for Poisson inter-arrival time as being the extension of Bernoulli to continuous time.
One key property of Poisson process is they are memoryless.
Extending Bernoulli to continuous, if the event still hasn’t happened at time t, the probability for it to not happen within t+x is independent of t.
Just like in Bernoulli, you’re flipping a coin (just super fast) and it is independent of past events.
It can be written asMemoryless propertyWe can derive from this the inter-arrival distribution for the Poissonthus h(x) has to be linear, we use -lambda as the prob is <1following a similar logic as per Bernoulli, P(X>x) means no events have happened prior to x which we can rewriteWith our Poisson rate of 0.
3, we can overlap the Poisson theoretical and Bernoulli distribution to see they match.
Bernoulli simulating Poisson inter-arrival timesFor a great resource on this, check MIT’s discrete stochastic process course here, and the chapter on Poisson processes.
A real world example: Hacker News posts inter-arrival timesHacker News regularly publishes a dataset to Kaggle.
The inter-arrival times for the stories posted would typically be modeled as a Poisson process.
You can find the analysis below in this Kaggle notebook.
Let’s take a look at the data.
We’re only looking at time (epoch) and deriving the inter-arrival time in sec (delta_s)Select columns of the HN dataset with added inter-arrival timesOn average, we calculate the inter-arrival time is 101s.
This should give us a distribution with the density:with inter-arrival rate of 101sLet’s plug in real data and the theoretical one.
Very close but not perfect.
However, the constant rate assumption is likely not true, let’s look at it.
We can see the arrival rate is much higher during the week than weekend for Hacker News, relatively similar during weekdays and highest during a 6–12 Pacific time.
Selecting weekdays, 6–12 Pacific, we get an almost perfect fit.
And where is my coin flip?All of this is interesting, but not fascinating.
What is fascinating however, is how—and here comes Bernoulli again—we can flip a biased coin to simulate that distribution.
The average arrival rate for that high usage period of 6–12 is 1 story every 51s.
If you take a coin flip that has a probability of being “1” of 1/51s, giving an expectation of 1 story every 51s, you get the same distribution.
The “flipping events” would look like array([0, 0, 0, 1, 0, 0, 0, 0, 0, 0,…]) and as above we process the distance between 1s.
If you run that process many times, here is what you get.
Flipping a biased coin to simulate HN inter-arrival times (Bernoulli)Thanks for reading.
.