Algorithm

A monoid is one of the smallest useful abstractions in algebra: a set closed under an associative binary operation, with an identity element. That simplicity is exactly why it shows up everywhere—from summing numbers and concatenating strings to powering divide-and-conquer algorithms and elegant data structures like finger trees. This post walks through what monoids are, why they give you “compute power” for free when you can phrase a problem in terms of them, and how to think about choosing the right monoid and predicate when you do.

In bitcoin, the total size of transactions added to the chain in a specific time is limited. This creates a fee market. Transactions with a higher fee rate are likely to be confirmed more quickly. A good fee estimator predicates which fee rate to pay where there is a high probability the transaction will be confirmed into the chain within the target period. Bitcoin core has the builtin support to estimate the fee rate. Understanding its algorithm can help us to migrate it and improve it. This first part of this article introduces the core estimation algorithm. The algorithm determines which statistics data to track, and the second part shows how Bitcoin Core tracks them. The last part describes the extensions to the core algorithm for better performance.

@miloyip has published a post recently which motioned the Alias Method to generate a discrete random variable in O(1). After some research, I find out that it is a neat and clever algorithm. Following are some notes of my study on it.