Everything the human brain is capable of is the product of a complex symphony of interactions between many distinct signaling events and myriad of individual computations. The brain’s ability to learn, connect abstract concepts, adapt, and imagine, are all the result of this vast combinatorial computational space. Even elusive properties such as self-awareness and consciousness presumably owe themselves to it. This computational space is the result of thousands of years of evolution, manifested by the physical and chemical substrate that makes up the brain — its ‘wetware’.
Physically, the brain is a geometric spatial network consisting of about 86 billion neurons and 85 billion non-neuronal cells. There is tremendous variability within these numbers, with many classes and sub-classes of both neurons and non-neuronal cells exhibiting different physiological dynamics and morphological (structural) heterogeneity that contribute to the dynamics. A seemingly uncountable number of signaling events occurring at different spatial and temporal scales interacting and integrating with each other are responsible for the brain’s computational complexity and the functions that emerge.
Despite a size that is intuitively difficult to grasp, this computational space is finite. It’s limited by the the physical constraints imposed on the brain, the result of the physical substrate that makes up its wetware. Taking these constraints into consideration can guide the analyses and interpretation of experimental data and the construction of mathematical models that aim to make sense about how the brain works and how cognitive functions emerge. The most basic such constraint is a fundamental structure-function constraint imposed by the interplay between the spatial geometry and connectivity of brain networks. This constraint regulates the dynamic signaling events that neurons use to communicate with each other.
In fact, this fundamental structure-function constraint is so important, that along with my colleagues Alysson Muotri at the University of California San Diego and Christopher White at Microsoft Research, we recently proposed that any theoretical or computational model that makes claims about its relevance to neuroscience and how the brain works must be able to account for it. Even if the intent and original construction of the model do not not take this fundamental structure-function constraint into consideration.
Another fundamental constraint are energy constraints imposed on the brain. The brain has evolved algorithms and tricks to make the most of the energy it has access to. It does this because it needs to. Thebrain uses a lot of the total metabolic energy produced by the body, but in absolute terms it is nothing compared, to say, a high performance computing system. It uses about as much energy as that needed to run a dim lightbulb. But more than the absolute energy limitations imposed on the brain, we have the most to learn about its ability to optimize its performance in the face of such limitations. Energy constraints and the strategies the brain has evolved to optimize the resources available to it are important considerations we should also take into account in order to understand the brain’s engineering design and algorithms.
If we are able to understand how these constraints determine and regulate dynamic signaling and information flows at different scales of brain networks — from individual neurons as mini-networks, to networks of neurons, to networks of brain regions — we will begin to understand the brain from an engineering systems perspective in ways we simply don’t yet. This is easy to say, but much harder to do and fill in the details. In truth, engineers, physicists, neuroscientists, and mathematicians, each bringing to bare a different perspective and complimentary toolsets, are collectively just beginning to scratch the surface. This approach currently drives much of our lab’s own research and work.
A fundamental constraint imposed by graph geometry, connectomics, and signaling dynamics
The fundamental structure-function constraint is the result of the interplay between anatomical structure and signaling dynamics. The integration and transmission of information in the brain are dependent on the interactions between structural organization and signaling dynamics across a number of scales. This fundamental structure-function constraint is imposed by the geometry — the connectivity and path lengths — of the structural networks that make up the brain at different scales, and the resultant latencies involved with the flow and transfer of information within and between functional scales. It is a constraint produced by the way the brain is wired, and how its constituent parts necessarily interact, e.g. neurons at one scale and brain regions at another.
Consider for example the cellular network scale. Individual neurons are the nodes in the network, connected by geometrically convoluted axons of varying lengths. Discrete signaling events called action potentials travel between neurons. Arriving action potentials at a receiving neuron add with each other until a threshold is reached, which then causes that neuron to fire and send out its own action potentials to the downstream neurons its connected to. Action potentials though aren’t instantaneously fast, they travel down axons at finite signaling speeds — their conduction velocities — which are dictated by the biophysics of the cell membranes that makes up the axon portion of the neuron. The physical path lengths (geometry) of the axons aren’t straight lines though. They are convoluted; twisting and turning. This creates latencies in the signals encoded by action potentials arriving at downstream neurons, which in turn affect the timing of their contributions to the summation towards reaching the threshold.
From a combinatorial perspective, consider also that the timing and summation of action potentials at one specific neuron is occurring independently from all other neurons and action potentials. There are order of magnitude 10 quadrillion connections between neurons in an adult human brain, every single one of them essentially doing their own thing unaware and not caring what the rest are doing. And as if this wasn’t complicated enough, neurons receiving signals can be in a refractory state that doesn’t allow them to respond to incoming action potentials, further amplifying the effect that the timing of arriving signals (driven by the geometry of the network and signaling latencies) will have on the overall computations of the brain. The subtle interplay between these competing effects, expressed mathematically in a quantity called the refraction ratio, can have a profound on the dynamics of the brain. In fact, we have shown that individual neurons seem to optimize the design of their shapes to preserve this refraction ratio.
From a more general information theoretic perspective, these principles apply not jut to biological neural networks, but any physically constructible network. The networks that make up the brain are physical constructions over which information must travel. The signals that encode this information are subject to processing times and signaling speeds (i.e. conduction velocities in the case of the brain) that must travel finite distances to exert their effects — in other words, to transfer the information they are carrying to the next stage in the system. Nothing is infinitely fast. The same concepts will apply to any constructed physical network, whether it is the brain or not.
Importantly, when the latencies created by the interplay between structural geometries and signaling speeds occur at a temporal scale similar to the functional processes of the network, as is the case in the brain, the interplay between structure and geometry and signaling dynamics has a major effect on what that network can and cannot do. You cannot ignore it. So unlike turning on a light switch, where the effect to us seems instantaneous and we can ignore the timescales over which electricity travels, the effect of signaling latencies imposed by the biophysics and geometry of the brain’s networks have a profound effect on its computations. They determine our understanding of how structure determines function in the brain, and how function modulates structure, for example, in learning or plasticity.
The dramatic effect the structure-function constraint can have on network dynamics can be easily illustrated with a numerical simulation of a geometric biological neural network. If there is a mismatch in the balance between network geometry and network dynamics — in the refraction ratio — then network dynamics and its ability to process information can completely break down, even though the network itself remains unchanged.
In numerical experiments, we stimulated a geometric network of 100 neurons for 500 ms and then observed the effects of modifying the refraction ratio by modifying the signaling speed. The results are summarized in the figure below. While leaving the connectivity and geometry (edge path lengths) unchanged, we tested three different signaling speeds (action potential conduction velocities) at 2, 20, and 200 pixels per ms. We then observed the network to see how well it was able to sustain inherent recurrent signaling in the absence of additional external stimulation. At the lowest signaling speed, 2 pixels per ms, after we stopped driving the network externally, we saw recurrent low-frequency periodic activity that qualitatively resembled patterns of activity seen in certain parts of the brain and spinal cord. When we increased the speed to 20 pixels per ms, there was still some recurrent activity but it was more sporadic and irregular. Not really patterns you would actually see in a typical brain. At 200 pixels per ms the entire activity of the network just dies. There was no signaling past the half second stimulus period. This is the direct consequence of a mismatch in the refraction ratio: when signals arrive to quickly at downstream neurons, the neurons have not had enough time to recover from their refractory periods and the incoming signals do not have an opportunity to induce downstream activations. The activity in the entire network dies.
Effects of the structure-function constraint on the dynamics of a geometric network. A. We simulated a 100 node network of (Izhikevitch) neurons with a geometric construction, with each neuron having a physical location in the plane. B. Functional connections were assigned random uniformly distributed weights between -1 and 1. C. Raster plots of the dynamics of the network for three different signaling speeds (conduction velocities). Time is along the x-axis, while each row of the y-axis corresponds to each of the 100 neurons in the network. Every time a tick mark is recorded that particular neuron at that particular time point fired an activation event. Reproduced from Buibas and Silva (2011) Neural Computation.
A systems engineering understanding of the brain: Constraint-based modeling of experimental systems
Ultimately, the impact constraint-based modeling will have on our understanding of the brain as an engineered system will be realized when we apply it to experimental data and measurements about the brain.
In particular, individualized human-derived brain organoids are a potentially unique experimental model of the brain because of their putative relevance to human brain structure and function. Brain organoids are likely a prime experimental model of the brain capable of guiding the development and testing of constraint-based mathematical models. One of the unique features of organoids is their ability to bridge mechanistic neurobiology with higher level cognitive properties and clinical considerations in the intact human. Including potentially consciousness.
And while direct relevance to the human brain will be variable, other experimental models offer the opportunity to ask specific questions that take advantage of each model’s unique properties which organoids might not share. There are likely aspects of neurobiology that are invariant to taxa, and considering them in the context of what also happens in an organoid could establish an abstraction about the the brain’s wetware. For example, the deterministic and reproducible neurobiological connectivity of the worm C. elegans across individuals, or the opportunity to observe and measure the physiology and metabolic properties of intact zebra fish during behavioral experiments. The mathematics used for modeling different experimental systems is agnostic to the neurobiological details, and fundamental constraints such as the structure-function constraint or energy considerations are universal. Rigorous constraint-based mathematical models that integrate data across experimental models offer the opportunity to generate insights about how the brain works that no single approach by itself can produce.
“The examiner was intelligent enough to quickly quieten Gödel and say ‘Oh god, let’s not go into this’ and broke off the examination at this point, greatly to our relief” — Oskar Morgenstern Kurt Gödel (1906–1978) was the greatest logician who ever lived. At the age of 24, he
Applied Statistics
The Lacking Wisdom of Crowds
Implications of Condorcet’s jury theorem
Abel
The Mozart of Mathematics — Niels Henrik Abel
“Although Abel shared with many mathematicians a complete lack of musical talent, I will not sound absurd if I compare his kind of…
Ramanujan
Ramanujan’s Early Work on Continued Fractions
“I had never seen anything in the least like [it] before” — G.H. Hardy On or about the 31st of January 1913, mathematician G.H. Hardy (1877-1947) of Trinity College at Cambridge University received a parcel of papers from Madras, India. The package included a cover letter where a young
Mathematics
The Martians of Budapest
The Martians of Budapest”, sometimes referred to as simply “The Martians” is a colloquial term used to describe a group of prominent Hungarian physicists and mathematicians who emigrated to the United States following the Great Purge of 1933.
Analysis
Cantor’s Diagonal Argument
“Diagonalization seems to show that there is an inexhaustibility phenomenon for definability similar to that for provability” — Franzén…
Feynman
Richard Feynman’s First Lecture (1940)
“I went through fire on my first.” While still a graduate student at Princeton University in 1940, Richard P. Feynman (1918–1988) gave his first lecture in a seminar on electrodynamics, the topic that would eventually earn him the 1965 Nobel Prize in physics. In front of a prestigious audience
Gödel
Kurt Gödel’s Brilliant Madness
Hungarian polymath John von Neumann (1903–1957) once wrote that Kurt Gödel was “absolutely irreplaceable” and “in a class by himself”.
Ramanujan
Ramanujan’s First Letter to G.H. Hardy (1913)
On or about the 31st of January 1913, mathematician G.H. Hardy (1877-1947) of Trinity College at Cambridge University received a parcel of papers from Madras, India which included a cover letter from an aspiring young Indian mathematician by the name of Srinivasa Ramanujan (1887–1920).
Game Theory
The El Farol Bar Problem
“Oh that place. It’s so crowded nobody goes there anymore.” — Yogi Berra
Physics
The Einstein-Szilárd Letter (1939)
The now famous Einstein-Szilárd letter was written at the initiative of Hungarian nuclear physicist Leó Szilárd with help from Edward Teller and Eugene Wigner in 1939.
Feynman
Richard Feynman’s Advice to a Young Stephen Wolfram (1985)
«You don’t understand “ordinary people”. To you they are “stupid fools”» Entrepreneur Stephen Wolfram is a unique egg. By age 14, he had written three books on particle physics. He earned his Ph.D. at age 20 and began publishing research papers at the age of 18, some of
You may have heard of this incredibly large number called Graham’s number, but more often than not when this subject is discussed, Graham’s number is rarely given in context. What does it mean? Did mathematicians decide to write down a really big number one Sunday afternoon because they were bored?
No.
In fact, Graham’s number is related to a very elegant field of mathematics called Ramsey theory. I will give you a beginner’s guide to Ramsey theory before diving into the deep end with Graham’s Number.
Suppose you are at a party. How many people need to be present such that you are guaranteed that at least three of them are (pairwise) mutual strangers or at least three of them are (pairwise) mutual friends?
I claim that the answer is six.
To prove this, we first turn this into a graph theory problem. We reduce each person attending to a point (formally known as a vertex) and draw lines (edges) between all the attendees. Below is an example of a party of five people:
Example of 5 attendees
This is known as a complete graph on 5 vertices (denoted K_5). Next step is we colour an edge red to denote that the two people it connects are strangers and blue if they are friends.
Example of a party colouring
A specific case of such an arrangement is known as an edge colouring.
If three people mutually know each other (or don’t know each other resp.) then we are looking for a triangle of edges that are all the same colour.
Here we see that the people A, B, E form a red triangle and so are all mutual strangers. Similarly, C, D, E form a blue triangle and so all know each other.
This triangle is known as a 3-clique (3 because there are 3 vertices)and more generally is a subset of a graph where each vertex is connected to each other.
This graph has a 4-clique: A, B, C, D
The problem can now fully be restated into a mathematical one:
What is the smallest integer N such that the complete graph K_N is guaranteed to either have a red 3-clique or blue 3-clique?
To answer, firstly we must show that 5 vertices (people) are insufficient. This is easily done by counter example:
This is an example of a coloured K_5 that has no monochromatic 3-cliques.
Ok so five doesn’t work. Consider now K_6:
In essence we want to attempt to construct a graph without a monochromatic 3-clique. If we can’t then that must mean that all edge colourings of K_6 satisfy the conditions.
Choose an arbitrary vertex (for simplicity, choose A) and consider its edges to the five other vertices, then by the good old Pigeon Hole Principle, you are guaranteed that there are at least three edges of the same colour.
Without loss of generality, let us say that there are (at least) 3 blue edges.
Now we look at how the other 3 edges connecting B, C, D can be drawn and attempt to draw them such that there is no 3-clique.
Firstly, the edge between B and C cannot be blue or else the clique A, B, C will all be blue. Similarly for the edges between C, D and B, D.
This forces us to colour all three of those edges red. But hang on! Three red edges sounds very much like a red 3-clique. Indeed we have been forced to construct a red 3-clique.
Therefore, any complete graph on six vertices must contain at least one monochromatic 3-clique.
Q.E.D
Notice that I have been very careful in saying 3-clique. This is because (as all of mathematics) it can be generalised:
We define the Ramsey number R(m,n) as being the minimum number of vertices (R) such that the complete graph on R vertices is guaranteed to have either a red m-clique or a blue n-clique.
It is trivial to see that R(m,n) = R(n,m) and slightly less trivial (but still quite easy) to see that R(m,2)=m.
Other than this, some values for low numbers are known (R(4,4) = 18, R(4,5) = 25) and a few interesting bounds can be made. And that is it.
Very little is known for higher numbers. We know R(5,5) is bounded between 43 and 49.
This may seem astounding — 49 after all is not that big a number, why can’t we just use computers to brute force it?
Numbers in this field grow quickly: suppose we just want to computationally verify a lower bound. So we are considering a complete graph on 43 vertices, this gives 903 edges (43 choose 2), each edge can be coloured in 2 different ways (red or blue) giving approximately 10²⁷² different graphs to verify…
To give you a perspective of how stupidly big this number is:
Suppose every atom in the universe is actually a super powerful computer that can check a googol graphs every second (that is 10¹⁰⁰ per second) and they started running at the big bang, then by now they won’t even have made a dent into computing all the possibilities. In fact the number of graphs they would have checked is approximately equivalent to removing one atom from the observable universe.
Granted you can reduce the computations by saying that the problem is invariant under permuting the vertices or by swapping red and blue but that doesn’t quite cut it — it only reduces the number of graphs by two orders of magnitutdes, i.e about 10²⁷⁰.
Many articles and posts are floating around that give you a sense of awe to how large Graham’s number is but very few actually explain what it means and why it exists. I will try to do both.
In essence, Graham’s Number (GN) is the upper bound to R(4,4) with some additional restrictions.
The first restriction is that the graphs we are considering are N dimensional complete hyper-cubes. A 2-dimensional complete cube is just K_4, a 3-dimensional complete cube is pictured below, and so on. In general, an N-d complete cube is a graph with vertices on each vertex point of the hypercube (equivalently, all points {±1}ᴺ) and every vertex is connected to every other vertex via an edge. Note that the structure is isomorphic to the complete graph on 2ᴺ vertices.
The next is that we don’t want any old clique, we require that the cliques are coplanar (in the geometric sense) in the hyper-cube. That is, all 4 vertices of our clique must lie in the same plane.
An example of a complete 3-cube with a red coplanar 4-clique
As of the writting of this article, it is known that the answer is greater or equal to 13 and less than GN (even though a much ‘smaller’ bound was given by Erik Lipka in his paper “Further improving of upper bound on a geometric Ramsey problem” arXiv:1905.05617).
Now how is GN defined? First we look at Knuth’s arrow notation, which is defined as such:
Firstly for positive integers a, b, a↑b = aᵇ. So for example, 3↑3 = 3³=27.
Next a↑↑b = a↑²b = a↑a↑a↑…↑a (where a is repeated b times). So 3↑²3 = 3↑3↑3 = 3²⁷ which is approximately 7.6 trillion.
We continue in this way: a↑³b = a↑↑a↑↑a↑↑….↑↑a (again, repeated b times).
So 3↑³3 = 3↑↑3↑↑3 = 3↑↑3²⁷ = (((3³)³)³…)³ where this ‘tower’ of threes is about 7 trillion threes tall. This is ‘scientifically’ known as off-the-charts big.
Okay, we are nearly there, I promise.
We start by defining g_1 = 3↑↑↑↑3 = 3↑⁴3 which is even more mindbogglingly bigger than the 3↑↑↑3.
Next we define g_2 via g_1 as being 3↑↑…↑↑3 where there are g_1 arrows. And more generally g_(n+1) = 3↑↑…↑↑3 with g_n arrows.
Recall that already with 2 arrows, we have a number slightly larger than the GDP of Japan (as of 2019 according to the IMF) or the number of miliseconds the average human lives for. With 3 arrows it already starts to fall out of comprehension, we have a stack of 3s that if we wrote out, would reach the sun. So imagine how big already g_1 is (spoiler: you can’t).
Graham’s Number is g_64.
Recall what the point of GN is: an upper bound the problem outlined above, a lower bound is 13.
To give you an idea of how stupidly, insanely, mind-bogglingly big Graham’s number is:
But don’t forget that even this number is huge, in reality, it is peanuts compared to infinity.
Note that the current upper bound given by Lipka mentioned above is merely 2↑↑↑5. To understand this, we start with a tower of twos: ((2)²)²…)² that is 65536 tall, call this number K, then construct a second tower of twos that is K twos tall. This is a much lower upper bound.
Now if like me, your brain is starting to hurt, I will leave you with a nice quote from a wonderful documentaryabout Paul Erdős (a major contributor to Ramsey theory)
Suppose aliens invade the earth and threaten to obliterate it in a year’s time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world’s best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.
From elementary mathematics, we are familiar with the four basic mathematical operations associated with numbers — addition, subtraction, multiplication and division. There are many kinds of numbers in mathematics with their own set of unique operations. Here we are concerned about the most commonly used numbers that we deal with everyday, which are technically called “real” numbers — like 43, 14/223, 7.381, 0.001 and so on.
The use of these four operations have been taught to us at a very young age, which makes the use of such operations a trivial task for most of us. It’s possible that a particular calculation involving these operations might be time consuming, but the rules are simple to follow. In particular, we find it quite easy to perform the operations of addition and subtraction even on big numbers. Unfortunately, we cannot say that for multiplication and division operations — they are notoriously hard to understand and execute even for relatively small numbers. In particular, the algorithm of division is arguably much harder to execute than multiplication.
After many centuries of progress, we have developed machines that could perform these operations — first mechanical and then electronic calculators. These machines are remarkably efficient and fast. Electronic calculators are amazingly fast — so fast that we do not stop to think, if these machines use exactly the same algorithms that we learned as kids. In fact, it was (and still is) one of the toughest problems for an engineer to design a machine that performs multiplications and divisions on arbitrarily small or large numbers in a fast and efficient manner.
If we talk about digital computers, division is a particularly tricky operation to design a hardware for. All modern, mainstream CPUs have special hardware blocks to perform division (also multiplication), which are quite sophisticated. But this was not the case for early computers, where they had hardware blocks to perform only additions and subtractions. The operations of multiplication and division were built using software routines on top, using repeated additions and subtractions respectively. Even today, many of the tiny, low powered CPUs still do not have a hardware multiplier and/or divider built into them — simply because these two operations are very resource hungry. So, in case we end up with such restrictive CPUs, which are pretty common in tiny, low powered gadgets like wrist watches (not smartwatches) and cheap pocket calculators, we would need a software based solution.
If we focus our attention on the process of division of a number, b, by another number, a, we can write it as,
This equation shows that the division of two numbers is equivalent to a multiplication of the numerator b with 1/a, which is called the reciprocal of the denominator a. If we are able to find an efficient algorithm for finding reciprocals, we could use the much simpler operation of multiplication, to solve the division problem.
In this article, we will study in detail, a method of finding the reciprocal of a number. There are many ways to do this, but one of the best known methods to solve several kinds of mathematical problems is the Newton’s method (also known as the Newton-Raphson method). It is an iterative method, which provides only an approximate result, up to a desired level of precision. There are times, when one could come up with a clever method of solving a particular problem which might be faster or more efficient than Newton’s method, but for problems when there is no clever way out, Newton’s method is often the best option — it’s basically a really powerful general-purpose method.
For using Newton’s method, we require a good understanding of calculus, which is beyond the scope of this article. Therefore, here we are going to see a non-calculus based method, which is at least as good, and we might be able improved it further.
For a beginner friendly introduction to calculus, check out this article.
Need For An Algorithm
Let us have a look at a few simple known cases. Suppose, we need to evaluate the reciprocal of 5, which we know from the definition to be 1/5 = 0.2. It looks like a fairly straight forward calculation, but the problem comes when the numbers are relatively bigger (or smaller) — for example, what would be the reciprocal of 1178 or 89243752 or an even bigger number? We can follow the rules and obtain the result, but it is not hard to imagine that these kinds of calculations, if performed manually, can sometimes be quite tedious if not too difficult.
The real problem comes, when we choose to do this on a computer system. We tend to write an algorithm exactly like the one we use with pen-and-paper calculations. It’s called the “long division method”, and is not the easiest (and the most efficient) algorithm to learn and use, even for computers.
One of the most intriguing things about humans is that we absolutely hate doing repetitive tasks, and always try to find clever tricks to avoid repetitions. Most of our mathematical methods are driven by the desire to be non-repetitive. It turns out, this is exactly opposite to how computers are designed to work. Computers tend to excel at doing repetitive tasks — in fact, they are so powerful because they are very efficient at doing simple repetitive tasks. This is why it is very hard to write good computer algorithms, because we have to leave behind most of the methods that were optimized for manual calculations, to be done by humans.
So, if we want a method of solving a problem which is optimized for a computer, we must think in terms of small, incremental and repetitive tasks. Such methods are called iterative methods.
If you are liking the story, you might consider subscribing to a newsletter to receive more stories like this, directly in your inbox !
Developing The Algorithm
Let us say that we want the reciprocal of the number a. Now, we may not have an exact result, but we could make an educated guess. Suppose that our first guess is x₁, which may or may not be good, but we can write the following equation,
where x₁ is the guess value which should not be too far away from the exact result, and e₁ is the error in the guess. This error could be big if we made a poor guess, or it could be tiny, in case of a good guess. If we are very lucky and our guess is perfect, the error will be zero.
We can rearrange this equation in the following way,
Now, if our first guess, x₁ is sufficiently good, then the error, e₁, will also be sufficiently small (compared to 1). By looking at the equation, it is clear that if the numerator on the left hand side is really small, it would imply that the error, e₁ is also really small. Therefore, we can relate the size of the error with the size of the numerator on the left side.
An important property of (positive) numbers smaller than 1 is that — a multiplication with itself, will result in an even smaller number, as shown below.
We see that squaring a small number, gives us an even smaller number, and perhaps we could use this fact in finding an improved guess by demanding that,
The error in the next guess must be proportional to the square of the error in the previous guess
In mathematical terms, this is written as,
But, according to the discussion above, this is equivalent to the following equation,
We can remove the proportionality by choosing a constant k, and get,
Using basic algebra, we simplify this equation to obtain the value of x₂ as follows,
It can be seen from this equation that there is a 1/a term on the right hand side, which is nothing but the reciprocal of a. This doesn’t help because it is exactly what we are looking to find in first place, and is still unknown. It may seem like we are going in circles, but there is a simple way out. If we choose, k=1, then 1/agets canceled, and we don’t have any problems. Therefore, with this choice of k, the previous equation can be written as,
This gives us the second guess to our problem, which should be an improvement over the first guess. We can repeat this exercise, and obtain a third guess, which would be much better than the second, and so on. Instead, we can generalize the equation by writing it as,
This is the master formula that we can use for an iterative process, to find the reciprocal of a number a, by calculating as many successive values of xₙ as we need, till the desired level of precision is reached.
Let us take an example and see how it works. Suppose we want to find the reciprocal of 13, with an initial guess, x₁ = 0.1. The table below shows the first three iterations of the master formula.
Third column contains the approximate values of 1/13, after three iterations, starting with x₁ = 0.1
The exact value of 1/13 is 0.076923…. We can see that only after three iterations, we have found a result which is correct up to five decimal places. We can improve the precision as much as we want, by increasing the number of iterations. We also see from the fourth column of the table, that the error is successively getting smaller, which suggests that we are converging towards the correct answer.
Interestingly, the master formula that we have obtained, is exactly the same formula that we would have obtained if we used Newton’s method based on calculus. The formula is compact, efficient and accurate enough to be used in early computers and portable calculators which had very limited computing power, and could be used even today.
The following python code can be used to try out the algorithm for different numbers.
Improving The Algorithm
We already have a pretty good algorithm, and may not require anything more. But, it might be interesting to see if it is possible to improve it further.
The central idea behind the algorithm is that we have used the fact that numbers smaller than 1, get even smaller upon multiplication with themselves. Earlier, we used the squaring or quadratic operation (power of 2) to reduce the successive errors in computation. But, we could have tried the cubic (power of 3) or quartic (power of 4) operations, making the errors even smaller. Let us see if such an algorithm offers any advantage.
If we choose to work with the cubic operation, the equation for errors, would look like the following,
By choosing the value of k=1, and simplifying it further, we will obtain the following master formula,
Similarly, for the quartic case, the master formula would be,
If the reader wants to try out, the python code listed earlier has a few commented lines of code, corresponding to the cubic and quartic algorithms as well.
In the following table, we have shown the successive errors for the quadratic, the cubic, and the quartic algorithms after three iterations, for the case of a=13, with the first guess, x₁ = 0.1
Comparison of errors for different algorithms, after same number of iterations
It is clear that if we use the improved algorithms, we can drastically reduce the errors, in the same number of iterations, but at the cost of increasing the complexity of the computation.
Originally published at https://physicsgarage.com on June 15, 2020.
Which student hasn’t been there? It’s exam time and the multiple-choice questions are waiting for you. Can’t be that hard to guess yourself to success, can it?
An exam has 20 questions. Each question has four choices. Exactly one choice is correct for each question. You need at least 10 correct answers to pass. What is the probability of passing if you pick one random answer for each question?
Before you read on (or scroll down to check the answer), I want you to make a rough guess. Just (mentally) tick one of the boxes above.
This is a common problem that can be described using the Binomial Distribution. And we encounter a lot of such problems in our everyday lives.
For example:
You roll the dice 3 times. What are the chances of getting exactly one six? What are the chances of getting at least one six?
You play the lottery every day for one year. What are the chances of winning at least once?
You make 3 penalty shots. What are the chances of hitting the goal at least two times?
The probability of having a certain disease is 1 %. What are the chances that in a group of 10 people at least two people have the disease?
All of these problems can be described using a Binomial Distribution. Before we look at it mathematically, let’s look at it from a more general perspective.
What do we need for a Binomial Distribution?
one base experiment which will be repeated many times (n times).
only two outcomes in the base experiment: success or no success; property fulfilled or not fulfilled.
a success probability p that does not change from one experiment to the next (this means the experiments are independent).
What are we looking for?
We are looking for the probability of a certain number of successes. The order in which the successes happen does not matter. We don’t care whether we answered the first five questions or the last five questions on our exam correctly. What matters is that we answered exactly five questions correctly. The goal is to pass the exam — not to pass the exam by answering the first x questions correctly.
The Exam Problem — Mathematically
To understand the problem, let’s look at a simplified version of a multiple-choice exam first. Let’s say our exam only has three questions and for each question, there are four possible answers out of which exactly one is correct and the other three are incorrect. You are only allowed to mark one question and you do follow these rules. You pass the exam if you answer at least two questions correctly. Let’s call this event A and find out how to calculate the probability for this event.
If you have no clue on how to solve such a problem, the easiest or most intuitive way to start is by drawing a probability tree.
For every question, there are two outcomes: Either you answer correctly or you don’t. If you pick a random answer, the probability of guessing the right answer is one out of four, 1/4, or 0.25. Consequently, the probability of guessing wrong is a lot higher at 3/4 or 0.75.
After answering the first question, we answer the second question. Again, we have the same two possible outcomes: Correct answer or incorrect answer. We repeat the process for the third question.
This leads to the following probability tree.
Theoretically, we could continue drawing this tree for as many exam questions as we like.
Now we can use this tree to calculate probabilities. Before you look at the calculation, I encourage you to always make a rough guess of what you think the probability will be. You might be surprised, but we humans have a massive tendency of misguessing probabilities!
To calculate the probability for a given path, we only need to multiply the numbers along the path.
The probability for guessing all three questions correctly is thus
The probability for getting the first and the second answer correct and the third incorrect is
What about getting the first one incorrect and the other two correct? As the calculation shows,
the probability is the same as the probability before. This makes sense because multiplication is commutative, i.e. the order in which we multiply the numbers does not matter.
Now we go back to our original question: We want to know what the chances are of passing, this means of getting at least two questions right. We don’t care which ones we get correct as long as we get at least two correct.
To calculate this probability, we calculate the probabilities for each of the paths and then add these probabilities.
Let’s say the exam is passed if at least two questions are answered correctly. To calculate this, all we need to do is mark all interesting paths, calculate the probabilities for each path, and add all of them.
This leads to a probability of
of passing this exam by guessing. That’s probably a lot lower than you may have guessed, isn’t it?
In the same way, we could also solve our original exam problem with 20 questions even though we would have to draw a massive tree!
And nobody ain’t got time for that.
This is where the Binomial Distribution comes into play. But before we introduce it, we will draw imaginary trees in our head and make some considerations.
Let us first define a random variable X. A random variable is a variable that depends on randomness. In our case, X is the number of successes, whatever a success may be. Maybe that’s getting an answer right. Maybe it’s being a girl. Maybe it’s winning the lottery.
In our case, success means getting the correct answer, so
Let’s say we are first looking for the probability of getting exactly 0 answers right, P(X=0). Remember that our exam consists of 20 questions with four answers each of which exactly one is correct.
In our (imaginary) probability tree, this event is visualized by the path on the right with twenty incorrect answers in a row.
Thus the probability for this event is given by
Next up we may look at the probability of getting one answer correctly and everything else wrong. This is already a bit more complicated as there is not just one single path anymore that fulfills this condition, but many.
Let’s first consider the possibility of getting the first answer right and everything else wrong. So we first go to the left and then always to the right and get the probability
What happens if instead of getting the first answer right, we get the second answer right?
As we are still multiplying the same numbers (just in a different order), this probability doesn’t change.
No matter at which position we get the answer right, the probability will always be the same as we only change the order of the multiplication. There are 20 possibilities to position the one correct answer, we say that we choose one question out of twenty. In our (imaginary) probability tree, we have 20 paths with the same probability each. Thus the probability of getting exactly one answer right is
Now let’s look at the probability of getting exactly two answers right. To start, we might calculate the probability of getting the first two answers correct and everything else incorrect.
As we may have already guessed, again, it doesn’t matter which two questions we get right, the probability for getting two specific questions correct and the rest incorrect will always be the same. What’s more interesting now is to figure out the number of paths in our tree.
There are 20 questions in total, 18 of which we will answer incorrectly and 2 correctly. there are
possibilities to order 20 questions. Out of these 20 questions, 18 will be incorrect. These 18 can be ordered in
different ways. The two correct answers can be ordered in
ways.
Thus, there are
possible paths to get exactly two questions correct. Seems like a pretty big number, doesn’t it? Write them down, if you don’t believe me.
We now have 190 paths in which exactly two answers are correct. The probability of getting exactly two answers right is thus given by
The Binomial Coefficient
One big step in generalizing this is to understand the number of paths in the probability tree. Our above consideration can be generalized to the so-called binomial coefficient. Instead of wanting to calculate the number of paths for getting exactly 2 answers right, we want to calculate it for k answers.
With the same reasoning as above, we get
We could make this even more general and substitute the 20 with n. This gives us the general formula for the binomial coeffient.
In the probability tree as described above, it is the number of paths with exactly k successes.
In literature, the binomial coefficient is usually described as the number of possibilities to pick k people out of n.
The Binomial Distribution Probability Function
I hope you’re still with me. Because we can now put everything together and finally get our binomial distribution!
We can now generalize this to getting exactly k answers right. To get exactly k answers out of 20 right, we have to get k answers right and 20-k answers wrong. This happens with a probability of
because again, we multiply the number of paths with the probability of getting k answers right and the probability of getting 20-k answers wrong!
For a general n, this leads to
or, even more general, if we don’t know the probabilities yet:
The Probability Distribution Function
We can now calculate probabilities to get exactly k answers correct for any number of exam questions and probabilities.
But what we really want to know is the probability of at least 10 correct answers or however many correct answers it takes to pass the exam.
To calculate the probability for up to k correct answers, we only need to add the probabilities for 0, 1, 2,…k correct answers.
Why? Because in our probability tree, these events are all made of different paths, so to calculate the joined probability of all of these events, we can simply add them add.
And with this knowledge, we can answer our initial question.
Finally: Will you pass?
We can finally calculate the probability of answering at least 10 questions correctly. To calculate this probability we could either calculate the probabilities of answering 10, 11, 12,…20 questions correctly or calculate the probabilities of answering 0,1,…9 questions correctly, adding these probabilities up and subtracting the answer from 1.
No matter which option we prefer, we end up with the following probability:
This means that the probability of passing is roughly 1.4 %. If 100 students guess the complete exams, we would expect 1.4 of them to pass (on average).
What was your guess? Was it close to the correct answer?
About the Author: Maike is a coffee-fueled Mathematician who loves to teach, talk and write about Math. If you want to support her work, feel free to buy her a coffee: https://www.buymeacoffee.com/maikeelisa
The Monty hall problem became famous when Marilyn vos Savant published it in response to a reader’s question in her column in Parade magazine in 1990. It is as famous for the virulence with which Marilyn was mansplained as it is for the subtlety of the problem itself. Even the legendary Paul Erdos, one of the great names of 20th century mathematics was only finally convinced by a computer simulation.
This article will show how a causal framework can help elucidate the structure of the problem, which I will argue helps avoid the logical pitfalls that makes the correct answer so intuitively uncomfortable. In doing so, I will show the steps of a causal approach to problem-solving, and we’ll also solve the Monty Hall problem on the way.
The problem
You are a contestant on a game show. You’re shown three doors. Behind one of the doors is a car; behind the two others are goats. You like cars. You need a car, or you can sell it. You don’t like goats. You don’t need a goat. None of your friends need a goat. And they’re worth much less than cars.
You are asked to pick a door. The game show host (whose name is Monty Hall) then opens one of the other two doors to reveal a goat.
Monty then asks whether you want to stick to the door you’ve already chosen or to switch to the other. What is the best strategy?
The causal framework
Decisions and objectives are the poles of the axis on which causal models are built. We start with them. Our objective is to win the car, the variable that captures that outcome is “What’s behind the door that you finally choose, car or goat?”
Then we have two decisions:
Which door to choose first
Whether to switch or stick.
Our causal map starts out looking like this.
A causal map decomposes the relationship between decisions and objectives into causally related elements. We build backward from objectives and forward from decisions and reconcile the causal chains in between.
In this simple case, we start by observing that the outcome is a function of, is causally dependent on:
Which door we finally choose
Where the car is placed
The placement of the car is a primary node in this problem; it is not causally dependent on anything, so there are no arrows into it and we need go back no further.
On the other hand, our final choice of door is clearly a function of both our first choice and whether we switch or stick. But it is also a function of which door Monty opens.
There’s no basis to prefer any one door over any other to start with, so for the sake or argument, we may as well choose door 1. Then Monty can choose which of doors 2 and 3 he can reveal.
Monty’s move
Here’s the key insight the causal framework provides: Which door Monty chooses also depends on the placement of the car. This is the yellow arrow from car to Monty’s move on the map. This is obvious, but the causal framework reveals its significance. Information about the car propagates into Monty’s move.
The car can be behind any of the three doors, but Monty knows which one. If you have chosen the car — if the car is behind door 1 — then Monty can choose either door 2 or 3. If it isn’t, Monty has to be careful not to reveal the car. Thus at least some of the time, Monty is giving you information: the car is behind the door he has chosen not to open.
There is an intuitive argument that it doesn’t matter whether you stick or switch because the car is behind one of the two doors so the probability the car is behind either of them must be 50:50. But this argument only holds in the absence of any other information and, at least some of the time, you have information. Monty just gave it to you.
Stick or switch?
The causal framework does not solve the problem on its own, you still have to do the math. If the car is behind door 1 then sticking wins you a car and switching, well, baaaaad luck. If the car is behind one of the other two doors then sticking brings only caprine compensation, where as switching wins the car. You have a one in three chance of picking the car, so switching wins you a car 2 times out of 3 and sticking just 1. Switching doubles your chances of winning.
Takeaways
The Monty Hall problem is ingenious in three distinct ways: The sneaky way Monty slides you information; that he only does so in some cases, but that is still information to you because you don’t know which case you’re in; and that the winning strategy requires you to give up the car if you picked it in the first instance.
A causal map doesn’t give you the winning strategy on its own, but it’s a powerful and intuitive method of understanding how the problem works, and why seemingly intuitively obvious answers fail.
In the 19th century, many paradoxical statements, formed either in natural language or mathematics, caused concern leading to questions around the reliability of mathematical reasoning. Rigorous attempts were made to address such concerns.
One of the most notable works in this regard is Principia Mathematica, written by Alfred North Whitehead (1861–1947) and Bertrand Russell (1872–1970) in the early 1900s, with one of its primary goals as “solving paradoxes that plagued logic and set theory”. This was a bold attempt to summarize the foundations of mathematics. The idea was to get rid of paradoxes by getting rid of self-references and in efforts to make this happen, type theory was developed. Type theory essentially placed constraints on mathematical grammar, thereby disallowing the formation of ill-formed sets discussed in the likes of Russell’s Paradox.
Let R be the set of all sets that are not members of themselves. If R is not a member of itself, then its definition dictates that it must contain itself, and if it contains itself, then it contradicts its own definition as the set of all sets that are not members of themselves.
And finally, the claim that no self-referential statements can be constructed using the theory of Principia Mathematica was made.
Axioms, Rules, and Theorems
Let’s discuss a bit about formal systems, first. A formal system also referred to as an axiomatic system, is basically defined by
a set of symbols
a grammar that dictates how to put the symbols together to form statements (well-formed formulas, or WFF for brevity).
a set of WFFs called axioms that are simply assumed to be true.
a set of rules of inference, that dictate the transformation of axioms into new WFFs that are also true.
For a statement to be a WFF, it should be constructed by following the system’s grammar. It is an ill-formed formula, otherwise. Each WFF is either true or false. Applying rules of inference on WFFs give us WFFs. A rudimentary example of a WFF:
843 is a prime number.
For any WFF S, a proof of S (if exists) is a sequence of WFFs starting with an axiom and ending with S obtained using the inference rules. When such proof exists, S is referred to as a theorem.
Truth and Provability
We will now look at two desired properties of any formal system.
All provable statements must be true.
This property is called soundness and soundness implies the consistency of a system. Consistency means to not have any statement be proved both true and false.
All true statements must be provable.
This property is called completeness.
Essentially, we want truth and provability to be equivalent.
Fun question: If you could satisfy only one of completeness and consistency, which one would you pick?
Fibonacci Numbers vs Collatz Numbers
A little detour to explore two properties of numbers: Fibonacci numbers and Collatz numbers.
Fibonacci numbers start from 0 and 1 and are further defined as the sum of the last two numbers. The following are examples of Fibonacci numbers: 5, 8, 987, 1597. Given any number, say 233, it is easy to determine if it’s a Fibonacci number. We simply start from 0 and 1 and add repeatedly until we reach 233 or overshoot 233. In a sense, we have a well defined straight path from 0 and 1 to 233. Even for incredibly large numbers, the path is well defined, albeit longer.
A simple path to check if 244 is a Fibonacci number
On the other hand, Collatz numbers start from 1 and are further obtained either by doubling the number or by subtracting 1 and dividing by 3 (if such operation results in a positive integer). The following are examples of Collatz numbers: 1, 2, 4, 82, 484. To find if a number, say 24, is a Collatz number, we start from 1 and at each step, we either double it or subtract 1 and divide by 3 until we reach 24. How would we ever know if 24 is not a Collatz number? We can’t rely on overshooting in this case, since we are allowed to subtract 1 and divide by 3 which results in reducing the number. The “path” isn’t well defined and we cannot determine if a given number is a Collatz number easily, simply because we don’t know when to give up on the search.
A zig-zag path to check if 24 is a Collatz number.
Well-Formed Formulas vs Theorems
Why did we just talk about Fibonacci and Collatz numbers? Well, it’s because the nature of these properties is similar to the nature of well-formed formulas and theorems.
Well-formed formulas are similar to Fibonacci numbers, in the sense that given a statement, it is easy to check if the statement is a WFF using the grammar rules of the formal system. The “path” to well-formedness is straightforward.
Theorems, on the other hand, are similar to Collatz numbers. The inference rules make it difficult to check if a statement is a theorem because there are many zig-zag routes and it’s not quite clear which path will lead us to the theorem. The path in the case of a theorem is essentially the theorem’s proof.
WFFs and Theorems are formal properties of a statement. One is easy, predictable and trivial. The other is unpredictable and elusive.
Gödel’s Encoding
Kurt Gödel (1906–1979) came up with a clever encoding scheme where he uses prime factorization to encode statements in Principia Mathematica. The idea is that the integers could easily simulate complex structures and objects.
In this encoding scheme, each symbol in the grammar is assigned a unique natural number and by raising primes to use these unique numbers as powers, we get the unique encoding for each sentence.
Consider the statement S: 1+1=2, which can be encoded as shown below.
Encoding “1+1=2” using primes. Such encodings are unique and their decoding is well defined too
Each statement in Principia Mathematica has a unique encoding. The inference rules are encoded as numerical operations so that they can work on the encoded statements. Asking questions about the encodings would mean asking questions about the statements in Principia Mathematica.
The whole of Principia Mathematica can be expressed using numbers and numerical operations. There are numbers representing statements and operations on numbers that transform the numbers according to the rules of inference. There is a perfect one-to-one correspondence between statements and numbers and the correspondence is held even after applying the operations.
For any given statement, we encode it and ask questions as follows. Is the integer a well-formed formula? Is the integer a theorem? We just reduced the formal properties of statements in Principia Mathematica into number-theoretical properties.
To check if an integer is a WFF number, we try to factorize it into primes and obtain the sequence of integers associated with the symbols and check the grammar rules to see if it’s a WFF. WFF numbers are very much like Fibonacci numbers. Checking if a number is a WFF number is easy and to continue the analogy, the path to a WFF is clear and straightforward.
On the other hand, checking if an integer is a theorem number is similar to the likes of checking if an integer is a Collatz number. It’s not quite clear which axiom numbers to start from, which inference rule operations to apply to reach the theorem number and we simply don’t know when to give up on the search for this integer. The path is zagged and unclear.
The Dreaded Self-Reference and Associated Paradoxes
The incredible efforts of Russell and Whitehead to prevent self-references creep into Principia Mathematica were to be deemed futile. Using the clever coding scheme one can construct a well-formed formula which essentially says:
24789102 is a prime number.
The number 24789102 is arbitrary but the idea holds. This number is such that the encoding of the statement G is the number itself.
And this is it! We have a statement in Principia Mathematica that speaks about itself. The dreaded and disconcerting self-references are discovered in Principia Mathematica putting its reliability in jeopardy. Did Russell and Whitehead miss something? Or is type theory to be blamed? We’ll seek the answer in a while.
We only showed that Principia Mathematica is capable of self-referential statements. The final nail in the coffin would be to show the presence of paradoxical statements. To show a paradoxical statement, we construct another self-referential statement, G:
43311341 is not a theorem number.
This too is a self-referencing statement. The number 43311341 is the encoding of the statement G itself. The statement G is basically saying:
This statement is not a theorem.
So is G a theorem? Let g be the encoding of the statement G. There are two possibilities:
If G is true, then g is not a theorem number (follows from what the statement says). But since G is true, g should be a theorem number (follows from the character of encoding). We have a contradiction.
If G is false, then g is a theorem number (follows from what the statement says). But since G is false, g should not be a theorem number (follows from the character of encoding). We have a contradiction.
Both possibilities lead us to inconsistency. We cannot have as the foundations of mathematics, a system where there are statements that are both true and false!
The only way to resolve this inconsistency is to give up the equivalency of truth and provability. If G is not provable, then g is not a theorem number (follows from what the statement says). G remains true but unprovable!
This is the price we pay for the consistency of Principia Mathematica. There are going to be statements that are true but unprovable! So, the property of completeness — that all true statements must be provable, is compromised to retain consistency.
Kurt Gödel’s achievement in modern logic is singular and monumental — indeed it is more than a monument, it is a landmark which will remain visible far in space and time. … The subject of logic has certainly completely changed its nature and possibilities with Gödel’s achievement.
— John von Neumann
Maybe It is Just Principia Mathematica?
Unfortunately, it’s not just Principia Mathematica. These results apply to any sufficiently rich formal system. To justify intuitively, rich formal systems are representationally powerful and therefore can form sentences that talk about themselves making self-references and paradoxes inevitable. Since we do not want to compromise on the consistency of the system, we sacrifice completeness.
This post is largely based on this elegant lecture by Douglas Hofstadter.
Edit: Many thanks to Emmanuell Tshim for pointing out a couple of mistakes in my post.
Natural numbers were created by God, everything else is the work of men — Kronecker (1823–1891).
Infinity
There are Different Kinds of Infinities
From Brilliance to Madness
Logic
Only So Much We Can Prove
A Glimpse of Incompleteness
Set Theory
When Cantor Taught us to Count
My theory stands as firm as a rock; every arrow directed against it will return quickly to its archer. — Georg Cantor
Infinity
Number Of Numbers: Infinite Weirdness
How many numbers of each type are there? Can two infinities be equal? Can one infinity be larger than another infinity?
Logic
Mind vs. Machine: A Philosophical Corollary of Gödel’s Incompleteness Theorem
Canadian mathematician Simon Kochen recalled in his tribute to Kurt Gödel how during his PhD exam, he was asked to name five of Gödel’s theorems. The essence of the question was that each of the theorems either gave birth to a new branch of, or revolutionized, modern mathematical logic.
Set Theory
Sets, Relations and Logic
Yet a bit more Introduction to Foundational Mathematics
Set Theory
Refuting the Refutation of Cantor
On August 2. 2020 Cantor’s Paradise published Bruno Campello’s brief critique of Cantor’s approach in transfinite mathematics. The author…
Probability Theory
Probability and Borel Sets
On the modern definition of probability
Set Theory
What Is Zorn’s Lemma?
The quick and dirty guide to one of the stranger mathematical curiosities.
Prime Numbers
Discovering Zero Among the Prime Numbers
It was a big surprise discovering zero when I was really looking for prime numbers. Back in 1992, I had a simple computer at my disposal …
Set Theory
Proving Cantor’s Theorem
“No one will drive us from the paradise which Cantor created for us” — David Hilbert
With nothing but a good model, a few definitions, and some math, we’ll derive a fundamental relationship of chemistry.
Anyone who has ever taken a chemistry class has seen the Ideal Gas Law:
Chemistry classes tend to teach the Ideal Gas Law as a combination of Boyle, Charles, Gay-Lussac, and Avogadro’s Laws. Although they derived these laws empirically, we’re going to take a different approach in this article. We’re going to derive the Ideal Gas Law from nothing but statistical mechanics, a few laws, and some definitions. We’re going to use the concept of entropy, so check out my article on entropy if you’re unfamiliar with entropy. If you think entropy measures disorder, check out the article because it doesn’t.
The Rules
For this derivation, I will only use the definition of an ideal gas, the Laws of Thermodynamics:
First Law: In a closed system, the change in internal energy is equal to the heat put into the system minus the work the system does on its environment.
Second Law: An isolated system will tend towards its most likely macrostate.
(I won’t need the Third Law and I won’t use the Zeroth Law directly, so I’ve left them out.)
both definitions of entropy:
the Fundamental Counting Theorem (I’ll explain in a later section), Stirling’s Approximation:
the Gamma Function:
the definitions of work, pressure, temperature, volume, and number of particles, and (sort of) the Heisenberg Uncertainty Principle:
I’ll go into more detail about why we sort of need the Heisenberg Uncertainty Principle when it comes up.
What is an Ideal Gas?
An ideal gas is a gas of uniform particles whose particles do not interact and do not take up space. Although no gas has these properties, many gases consist of particles that rarely interact and take up a negligible amount of space. Ideal gases can approximate these gases over a wide range of values of pressure, volume, temperatures, etc.
If you want a video demonstration, here you go:
The Multiplicity of an Ideal Gas
Since we want to calculate entropy with statistical mechanics, we need to calculate the multiplicity of an ideal gas. The multiplicity represents the number of ways you can change the system under some constraints. In the case of the ideal gas, we’re looking at the number of ways you can choose the positions and momenta of the particles given a pressure, a temperature, the number of particles, and a volume.
We will look at one particle first to get a foothold in what we have to consider with the multiplicity. Then, we will move onto a many particle system.
One Particle
Let’s consider some thermodynamic variables and how we can use them to help us.
Number of Particles: We’ve already used this when we established that we were using one particle.
Volume: Since particles in our model can only move inside the given volume, the volume constrains the total number of possible positions.
Temperature: Temperature is a measure of the average kinetic energy of a gas. Since it’s trivial to convert to internal energy through entropy or the Equipartition Theorem, we won’t need it.
Internal Energy: The sum of all the kinetic energies of the particles must equal the internal energy. We can use kinetic energy to find momenta, so the internal energy constrains the total number of possible momenta.
Pressure: I don’t see how we can use pressure to get us something without us putting in significant effort. We’ll skip it for now.
Finding the Number of Possible Positions
We won’t be able to get an exact number of all possible positions since space is continuous (as far as we know). We can say that if we have twice the volume, we have twice the number of positions as we did before, so we can say
Finding the Number of Possible Momenta
As with position, we won’t be able to get an exact number of all possible momenta. The derivation is going to be a little weirder. As we said before, the sum of all the kinetic energies of each particle must equal the internal energy, which leaves us with
As weird as this looks, this equation describes the surface of a sphere. The number of possible momenta is proportional to the surface area of a sphere with a radius of the square root of 2mU.
Why Does a Sphere Show up in the Derivation?
If we look at the equation for kinetic energy, it only contains the magnitude of the momentum, so any momentum with that magnitude is possible. The set of all possible vectors with a given magnitude is the formal definition of a sphere, so that’s where we get the sphere.
The Equipartition Theorem
The system has no reason to give one component of kinetic energy more energy than any other component. Therefore, we assume that the energy of the system is spread evenly among all components of kinetic energy. This assumption is the Equipartition Theorem. While this theorem doesn’t hold when quantum effects are significant, it holds in classical mechanics. I’m mentioning the Equipartition Theorem so that we can assume that the system can be any point on the sphere with the same probability.
The Fundamental Counting Theorem
The Fundamental Counting Theorem states
If there aremoutcomes for one event andnoutcomes for an independent event, there aremnpossible outcomes for the combined event.
For example, if you roll a die, you have six possible outcomes ({1, 2, 3, 4, 5, 6}). If you flip a coin, you have two possible outcomes ({H, T}). If you roll a die and flip a coin, you have twelve possible outcomes ({H1, H2, H3, H4, H5, H6, T1, T2, T3, T4, T5, T6}).
In our case, we have m possible positions and n possible momenta, so we have mnpossible microstates. Since m is proportional to the volume and n is proportional to the surface area of the sphere, the multiplicity is proportional to
Removing the Units
If I asked you how many possible outcomes you could have for something happening, you could say two or two million, but you couldn’t say two million meters. The number of anything can’t have units behind it, which presents us with a problem since our multiplicity has units of Joule³ Seconds³. To get rid of this, we can divide by some constant with units of Joule³ Seconds³. h³ has the right units and kind of makes sense since the Heisenberg Uncertainty Principle states
If we include all three dimensions, we end up with
which is volume times momentum cubed, so you can imagine chopping up the momentum-position space into “cubes” with a size of h³.
Why h instead of h/4π?
I’ve never seen an adequate explanation for why Sackur and Tetrode chose to use h³ instead of (h/4π)³. Before Heisenberg’s Uncertainty Principle, everyone tended to solve problems by restricting things to integer multiples of h or h/2π (e.g. Planck’s Blackbody Equation, the Bohr atom, etc.). I think Sackur and Tetrode did the same without a theoretical reason. I found someone on the internet saying that you can also get some mathematical justification forhinstead ofh/4πby expanding out some quantum density matrix, but I wasn’t able to see it in the source the person named. Furthermore, he was the only source I could find online that gave a reason besides (it has the right units). If anyone has a strong reason for using h instead of h/4π, let me know in a response to this article.
Back to the Multiplicity
Regardless of what we choose, the exact value of the entropy won’t matter for our purposes, as we’ll focus only on differences in entropy. At this point, we now have the following expression for the multiplicity of a singular particle:
Problem with the Units
This expression doesn’t have the right units. 2mU is momentum² and we need momentum³. We can fix this issue by either multiplying by a constant or raising the square root of 2mU to the power of three. Once we start working with a large number of particles, we’ll choose the second option. I’ll explain more when we get to that section. For now, I’m going to leave it and move on.
Multiple Particles
We can use the Fundamental Counting Theorem for any independent quantities.
Constants
Since constants are independent of the system, we will divide the multiplicity by h³ for each of the N particles, leaving us with
Positions
As I said earlier in my definition of an ideal gas, the particles do not take up space and do not interact. The position of each particle is therefore independent of any other particle. Since we have independent positions, we will multiply the multiplicity by V for each particle, leaving us with
Momenta
Unlike the constants and the positions, the momenta depend on each other. Consider the kinetic energies of each particle with respect to the total energy.
Remember that we’re looking for the number of possible ways to distribute momenta for a given amount of energy. If we change the energy to X Joules, then we’re looking for the number of possible ways to distribute momenta such that the total amount of energy is X Joules. For this reason, we consider the energy to be constant in this part of our analysis.
The next part sounds worse than it actually is. If we look at the momenta terms, we have a bunch of squared values adding up to a constant. If we had two squared values adding together to get a constant, we would have a circle. If we had three squared values, we would have a sphere. We have more than three squared values, though, so we have a hypersphere. To find the multiplicity of the momenta, we need to find the surface area of an n-dimensional hypersphere. Don’t freak out, though. Math allows us to talk about things without seeing them. If we trust the math, we can make our way through this problem. Before we go any further, I recommend checking out 3Blue1Brown’s video Thinking outside the 10-dimensional box. In our case, we are looking for the surface area of a sphere with 3N dimensions and radius of the square root of 2mU.
Hyperspheres
There are many ways to find the surface area of an n-dimensional sphere. I’d rather not do the direct integral in this derivation since I’d have to cover hyperspherical coordinates. Instead, we’ll use properties of n-dimensional spheres. We’ll need three facts:
We can express an n-dimensional sphere as a sum of squares adding up to a radius squared.
The volume of any n-dimensional object is proportional to its radius raised to the nth power.
The surface area is the derivative of the volume in any dimension with respect to the radius. (For squares and cubes, the “radius” is any length from the center to a point on the surface of the cube.)
The proportionality relationship should make sense. You need units of length to the n for n-dimensional volume and volume should increase as the radius increases. The relationship between surface area and volume should also make sense. Imagine painting a ball bearing with thousands of layers of paint. Each layer increases the volume of the ball by a small amount while still keeping it spherical. If you kept adding layers, you would get a sphere as large as the Earth. If you want a visual example in 2D, take the following image:
Made using pyplot. You can see that I’ve filled in the area by drawing circles.
If we combine the last two facts, we end up with
With this result, we can see that we only need to find vn to get our answer.
Our Plan for the Hypersphere
We’re going to come up with two different expressions that equal each other. One of these ways will contain vn and the other will not. Both the sum of squares and the n-dimensional volume differential element (dVn) need to show up in at least one of these expressions.
We can then set these two expressions equal to each other and solve for vn.
Sum of Squares in One of the Expressions
We’ll want to be able to add as many squares as we would like, so we’ll look for a function f and an operation ★ (addition, subtraction, multiplication, division, or any function that takes in two values and spits out another value) that satisfies f(a + b) = f(a) ★ f(b). If we find such a function and operation, then
This equation will allow us to work with f(r²) and f(x²), which can make our job easier.
If we let ★ be addition and f(x) = x, then we’ll end up integrating in hyperspherical coordinates, which I wanted to avoid. I can’t see any other way to satisfy the above restrictions on f with ★ being addition than to let f(x) = x, so let’s try something else. Subtraction won’t work since f(a + b) = f(b + a), which means f(a) ★ f(b) = f(b) ★ f(a). In math terms, ★ must be commutative. Since subtraction isn’t commutative, we can’t use it. Same goes for division. Multiplication is the only basic operation we have left. In that case, we want some function that satisfies f(a + b) = f(a) f(b).
I don’t want to beat around the bush too much, so we’ll take f(x) to be an exponential function. I don’t care if f(x) could be anything else since exponential functions will work. Since we’re working with calculus, we’ll want to work with e (Euler’s number) or 1/e being the base. These two numbers have nice properties. We have two main contenders: f(x) = exp(x) (e is the base) and f(x) = exp(-x) (1/e is the base). Since x² is always positive, exp(x²) will go to infinity as x goes to infinity, which makes the integral harder to evaluate. On the other hand, exp(-x) goes to zero as x goes to infinity, so we’ll take f(x) = exp(-x).
Volume Differential Element in One of the Expressions
So now, we just need an expression with dVn. The dVn suggests an integral or a derivative. We’re dealing with volumes, so we’ll try the integral. Remember that we’re working with exp(-x²), which has the famous integral
I’ll link to a proof since I wouldn’t be able to add anything. If you want to derive it on your own, look for a similar integral that you can integrate (say if you multiplied the integrand by x) and try to convert the original integral into the easier integral. You might want to look into polar coordinates since dA = r dθ dr and you could use that r or look into the Leibniz Rule/Feynman’s Differentiation Under the Integral. Anyway, if we multiply n Gaussian Integrals, we can use f(a) f(b) = f(a + b) and we end up with
We’re integrating over the x’s, so we can call them whatever we like without changing the value of the integral. Regardless, we have a sum of squares in the left half and our right half is a known value.
To use this equation, we’ll need to make a few notes and come up with some definitions. First, note that the integral is over all space in n dimensions. We’ll use something to denote the region independent of the coordinate expression. Second, note that the combination of all the dx’s is a volume element in n dimensions, i.e. dVn. Lastly, we can use the fact that the sum of squares equals r². As a quick summary:
Putting it all together gives us
Solving for vn
Now, we’ll use the relationship between dVn and dr:
Substituting it back into the integral and setting the appropriate bounds (r = 0 to r = ∞) leaves us with
Now, we do a little bit of algebra and calculus
We let u = r² for a u-substitution, then we recognized the definition of the gamma function, the analytic continuation ofn!. You can think of the gamma function as connecting all the values of n! with a smooth curve. In specific terms, Γ(n) = (n – 1)!. If you’d like a proof, you could use a proof by induction with integration by parts.
Note that Stirling’s Approximation applies to the Gamma Function as well as it does to the factorial. We’ll make use of this fact later. At this point, if we solve for vn, we can get the volume and the surface area.
Plug in n = 2 and you get the circumference and area of a circle. Then plug in n = 3and you get the surface area and volume of a sphere.
Plugging in our specific values for the radius and the number of dimensions, we get
Double Counting
Say that we have two particles for now. Each has a specific momentum and position. Say we switch the two particles so that the first particle has the position and momentum of the second and vice versa. Both these situations describe the same microstate, meaning we have to divide by 2. If we didn’t divide by 2, we would count this state multiple times. With more particles, any permutation will describe the same microstate. We have to divide our multiplicity by the number of permutations, N! to avoid counting the same microstate multiple times. If we don’t account for the indistinguishable particles, we could violate the Second Law of Thermodynamics.
The Multiplicity of a Monatomic Ideal Gas
Putting everything together, we have:
I made two simplifications. First, the 2 out front adds a small constant to the entropy that we can ignore. Second, I have increased the power of the square root of 2mU by 1 since we’re dealing with very large numbers and we need the units to work out. You can imagine this as converting a surface area to a volume by multiplying by a small thickness. If you want to see why these approximations work, don’t make them and see the difference between the values (remember that N is on the order of 10²³). Other than that, I cleaned up the expression.
The Entropy of a Monatomic Ideal Gas
Now that we have the multiplicity of an Ideal Gas, we can use it to find the entropy:
We went from the first line to the second line by substituting in the multiplicity for N particles. Then, we used logarithm rules to split up products. Then, we applied Stirling’s approximation so we ended up with N ln N – N instead of ln N!. Since Γ(n) = (n – 1)!, we can also use Stirling’s approximation. We can ignore the -1 in Stirling’s approximation of the gamma function since n >> 1 (Don’t approximate if you don’t believe me and check the accuracy of the approximation.). Then, we factored out N, added 3/2 and 1 to get the 5/2, brought the two terms with a 3/2 in front into one logarithm, and combined the two remaining logarithms. For the last line, we combined all the logarithms into one logarithm. We have derived the the Sackur-Tetrode Equation for the entropy of an Ideal Gas! We’re quite close to the Ideal Gas Law, but we’ll need to do some more work (pun not intended and not funny) to get pressure and temperature into our math.
The First Law of Thermodynamics
Now that we have the Sackur-Tetrode Equation, we can use the First Law of Thermodynamics to derive the Ideal Gas Law. In its current form, the First Law of Thermodynamics can’t help us much, so we’ll have to rewrite it in terms of temperature, entropy, pressure, and volume. First, we’ll rewrite both sides in terms of differentials
where dU is an exact differential and both 𝛿Q and 𝛿W are inexact differentials.
Exact and Inexact Differentials
The integral of an exact differential only depends on its endpoints (a.k.a. path independence) while an inexact differential depends on how you get from one endpoint to another. As a practical example, gravitational potential energy is an exact differential. If you lift a weight in the air, you’ve increased its potential energy. If you put it back down, you’ve decreased its potential energy back to its original value. You, on the other hand, have lost energy lifting the weight and putting it back down. The work must therefore be an inexact differential. As this Khan Academy article explains (at the end), your body is doing work to keep the tension in your muscles. To calculate the work done, you would have to do the work integral and account for efficiency.
We’ll end up with exact differentials in the next step, so the distinction doesn’t matter for us.
Heat in Terms of Entropy and Temperature
Given the definition of entropy, this part is trivial:
Work in Terms of Pressure and Volume
Work depends on force and distance, so we’re going to need some way of getting force and distance from pressure and volume. We can get a pretty good guess by looking at the units. Pressure is [force] / [distance]² and volume is [distance]³. We want [force] ꞏ [distance]. If we multiplied pressure and volume, we would get something with the right units. How do we know that their product is work?
Consider a piston.
The piston pushes an object with a force over a distance through expansion (a.k.a. a change in volume). If we think about the side of the piston that pushes the object, we’ll have an area. With force and area, we get pressure. With area and distance, we get volume.
The little s is the path element and it’s an infinitesimal distance with a direction. Pressure always points in or out of the surface, so it’s always in the same or opposite direction as the volume change. Regardless, we can turn the dot product into a regular product of their magnitudes. We end up with
This principle applies to far more than just pistons. If you imagine a small square on a balloon, you can treat it like the piston above.
What About Changes in Pressure?
If the volume doesn’t change, then the force is applied over zero distance, so no work is done. If the pressure changes as the volume changes, then we can rewrite pressure as a function of volume. If the volume is constant but the pressure changes, any change in the internal energy will show up as heat.
Putting it all Together
At this point, we have
This equation is the Fundamental Thermodynamic Relation.
Some Useful Derivatives
For the moment, let’s say that we keep the system at constant volume. In that case, we recover the definition of entropy:
The subscript outside the parentheses means we kept that variable constant. In this case, we kept the volume and the number of particles constant. Since you usually get entropy as a function of total energy, the second derivative is used more often.
Now, let’s say that we keep the entropy constant. We then have a useful relationship between pressure, volume, and internal energy:
Let’s say the internal energy is constant. We then have a useful relationship between entropy, temperature, pressure, and volume:
We can only use these derivatives if we can assume something is constant, however. Luckily for us, we can use the Second Law of Thermodynamics.
If you’re a mathematician, then we’re either doing nonstandard analysis or using the chain rule/u-substitution (same thing) to get the derivative out of the result.
I’m taking a shortcut because we’re doing physics, not rigorous real analysis.
The Second Law of Thermodynamics
If you change any of the macroscopic properties fast enough, the rest will take some time to catch up. If you expanded the piston from earlier at half the speed of light, part of the added volume would be empty. At that point, it doesn’t make sense to talk about the pressure or temperature of the entire system since it varies throughout the system. In a similar manner, if we added particles or energy in one corner of a box, we would also have differences in pressure throughout the box and it no longer makes sense to talk about the pressure or temperature of the system. In any of these cases, we couldn’t use any law that relies on one uniform pressure or temperature throughout the system. We have to restrict ourselves to the specific case of thermal equilibrium.
The Second Law of Thermodynamics guarantees that there is a thermal equilibrium for an isolated system: the most likely macrostate. If we’re in thermal equilibrium, none of the macroscopic properties (pressure, volume, number of particles, temperature, internal energy, and entropy) of the system will change.
You might worry that we can’t use the derivatives since all the variables are constant, but that means dS, dV, dU, etc. are all “zero” (technically limits approaching zero), which they were anyway by virtue of being differentials.
We could probably try to maximize the entropy, but I don’t think we’d get too much out of it.
Deriving the Ideal Gas Law
We can assume constant energy, which means we can use one of the derivatives we derived in the section on the First Law of Thermodynamics:
Some algebra yields the Physicist’s Ideal Gas Law:
If we make the substitutions R = kB A (where R is the Ideal Gas Constant and A is Avogadro’s number) and n = N/A, we end up with the Chemist’s Ideal Gas Law:
Q.E.D.
Internal Energy of an Ideal Gas
We can also get some useful quantities, such as an exact expression for the internal energy of the gas. If we assume constant volume, we get:
What About Gases with More Atoms per Particle?
With multi-atomic gases, you still have volume and momenta, but now you have to consider angular momenta, orientation, and energy from vibrations. Because the position is independent of everything else, the multiplicity will still be proportional to V to the N. The Ideal Gas Law still holds.
There are more ways to distribute energy (a.k.a. degrees of freedom) for multi-atomic gases, so the expression for the internal energy changes. Since rotational kinetic energy and bond energy (modeled as a spring) are both represented as some constant times a number squared, we end up with something like the following for diatomic molecules:
I neglected one of the angular momenta components because the moment of inertia for the bond axis is so high that the molecule will not rotate around it for most reasonable temperatures. Quantum Mechanics restricts systems to discrete states, so the bond axis component of angular momentum must either be zero or a large number for the system. In a similar manner, low temperatures will end up freezing the energy stored in the bond at a fixed number, so you’ll end up with
In the first case where bond energy can vary, we have a 6N dimensional sphere. In the second case where bond energy is fixed, we have a 5N dimensional sphere. In either case, we need the surface area of the hypersphere. Since no other term contains the internal energy, you end up with
where f is the degrees of freedom (6 with bond energy and 5 without the bond energy).
We also need the orientation and how far the bond is stretched in the multiplicity, so we have a few more terms. We also add some more h’s in the denominator because each position-momentum component pair has an uncertainty principle. Regardless, the Ideal Gas Law and the Equipartition Theorem still hold, so it doesn’t matter for this derivation. For multi-atomic gases, you would be better off measuring quantities than calculating them.
Addendum: Chemical Reactions
If we had any chemical reactions happening (say in a car’s engine), we would also add some chemical potential terms for each chemical in the system to the Fundamental Thermodynamics Relation like so:
Each μ represents the chemical potential energy for each chemical in the system. Each dN represents the change in the amount of each chemical in the system.
Ideal gases do not have chemical reactions, so we left the chemical potential terms off.
Why Go through all this Trouble?
Benoît Paul Émile Clapeyron had derived the Ideal Gas Law decades earlier using the empirical observations of Boyle, Charles, Gay-Lussac, and Avogadro. So why go through this proof? Why not use Clapeyron’s proof and move on?
Understanding
Nothing promotes understanding like practical application. As I said in my power rule article:
Students tend to see math as a list of random facts to memorize with little to no connection between them.
This mindset applies to almost all fields of study, including physics. Students should feel as if each topic flows into every other topic — that they can learn new things from what they already know. By giving this proof, we can see the relationship between all these thermodynamic quantities. We see how to use the tools of statistical mechanics and thermodynamics to get useful results.
Consistency
If we had done this derivation and ended up with anything but the Ideal Gas Law, we would have to rebuild a large section of thermodynamics. One of the laws or theorems used in the derivation must have been wrong, and we would have to modify the erroneous law or theorem. In a way, this proof was an experiment to verify all the theorems and laws we used in this proof.
Ideal Gas Constant
Let’s say you derive the Ideal Gas Law purely through empirical means. Why does the Ideal Gas Constant (R) have a value of around 8.314 J / (K · mol)? We’re not done yet, though. If we look at the Dulong-Petit Law, we get that the molar heat capacity (the amount of energy required to raise the temperature of 1 mole of atoms by one Kelvin) of most solids is usually around 24.942 J / (K · mol), or 3 R. Why does the Ideal Gas Constant show up in the molar heat capacity for solids?
Without statistical mechanics (either by using the Equipartition Theorem or going through this same process of deriving the entropy of an Einstein or Debye solid and taking the high-temperature approximation), you can’t explain why these two values are related. It’s a happy coincidence and nothing more.
Practical Applications of Math
I can’t stand the question “When am I ever going to use this?” for many reasons, but I’ll focus on one here: I don’t know when anyone is going to use anything in math or science. If I did know every possible use for each mathematical concept, I would stop global warming, cure every single disease, end poverty and hunger, unify the four fundamental forces, solve the six remaining Millennial problems, build an interdimensional warp drive, etc.
What we consider impractical with our limited foresight may turn out to be not just practical, but fundamental to our understanding. I could list thousands of examples, including number theory leading to modern cryptography, curved manifolds leading to Einstein’s General Relativity, gambling games leading to probability leading to Quantum Mechanics, etc., but I won’t. Instead, I’ll use this article as an example.
Before this article, could you name a practical application of knowing the surface area of an n-dimensional sphere? In a similar manner, do you think the mathematician who derived the formula knew that you could use it to derive the Ideal Gas Law? Even if you knew statistical mechanics, would you have thought you would need the surface area of an n-dimensional sphere? I’d bet money on “no” to all these answers. After reading this article, do you think the formula for the surface area of an n-dimensional sphere is useless?
To be clear, I’m not saying everyone is going to use the formula in their daily lives. In fact, I doubt most people will ever use it. I’m saying that you don’t know what’s going to be useful before you need to use it.
Conclusion
If you’d like to see more discussions about entropy, check out my other two articles on the subject: Stop Saying Entropy is Disorder and Creationism and Entropy. If you want to see another derivation from scratch, check out my article Let’s Derive the Power Rule from Scratch. If you want an entire series with a similar style and mathematical rigor, check out The Road to Quantum Mechanics. If you’d like to see me derive something else from scratch, leave a suggestion in a response to this article and I’ll see what I can do.
Effects of the structure-function constraint on the dynamics of a geometric network. A. We simulated a 100 node network of (Izhikevitch) neurons with a geometric construction, with each neuron having a physical location in the plane. B. Functional connections were assigned random uniformly distributed weights between -1 and 1. C. Raster plots of the dynamics of the network for three different signaling speeds (conduction velocities). Time is along the x-axis, while each row of the y-axis corresponds to each of the 100 neurons in the network. Every time a tick mark is recorded that particular neuron at that particular time point fired an activation event. Reproduced from Buibas and Silva (2011) Neural Computation.
Paul Erdős, a prolific mathematician who contributed a lot to the field — Archives of the Mathematisches Forschungsinstitut Oberwolfach ©Gabriella Bollobas
Example of 5 attendees
Example of a party colouring
This graph has a 4-clique: A, B, C, D
An example of a complete 3-cube with a red coplanar 4-clique
Third column contains the approximate values of 1/13, after three iterations, starting with x₁ = 0.1
Comparison of errors for different algorithms, after same number of iterations
A simple path to check if 244 is a Fibonacci number
A zig-zag path to check if 24 is a Collatz number.
Encoding “1+1=2” using primes. Such encodings are unique and their decoding is well defined too
Made using pyplot. You can see that I’ve filled in the area by drawing circles.
