Subscribe: A Neighborhood of Infinity
Language: English
Tags:
bernoulli  data  free  function  functions  functor  import  monad  number  point  probability  problem  random  return  state
Rate this Feed

Feed Details and Statistics
Preview: A Neighborhood of Infinity

# A Neighborhood of Infinity

Last Build Date: Fri, 16 Mar 2018 11:22:23 +0000

A tail we don't need to wag

Sat, 14 Oct 2017 20:42:00 +0000

What is a photon?

Sat, 12 Aug 2017 03:22:00 +0000

IntroductionPopular science writing about quantum mechanics leaves many people full of questions about the status of photons. I want to answer some of these without using any tricky mathematics. One of the challenges is that photons are very different to ordinary everyday objects like billiard balls. This is partly because photons are described by quantum mechanics whereas billiard balls are better modelled with classical Newtonian mechanics. Quantum mechanics defies many of our intuitions. But it's also because the word photon plays by different linguistic rules to billiard ball. I hope to explain why. One of my goals is to avoid saying anything original. I'm largely going remove the mathematics from material I first learnt from three or so courses I took at Cambridge University many years ago: Quantum Mechanics, Solid State Physics and Quantum Field Theory. I also learnt about some of this from David Miller at Stanford University who talked a little about what properties it is meaningful to apply to a photon. (I hope I haven't misrepresented him too badly.) The simple harmonic oscillatorHere's a mass hanging on a spring: Suppose it's initially sitting in equilibrium so that the net force acting on it is zero. Now we lift the mass a small distance and let it go. Because we lifted it, we shortened the spring, reducing its tension. This means the force due to gravity is now more than the spring tension and the mass falls. Eventually it falls below the equilibrium point, increasing the tension in the spring so there is a net force pulling it back up again. To a good approximation, the force restoring the mass to its equilibrium point is proportional to how far it has been displaced. When this happens we end up with oscillating motion where the mass bounces up and down. Here's what a graph of its displacement looks like over time: It's actually a sine wave but that detail doesn't matter for us right now. An oscillator where the restoring force is proportional to the displacement from the equilibrium point is called a simple harmonic oscillator and its oscillation is always described by a sine wave. Note that I'm ignoring friction here. This is a reasonable approximation for many physical systems. Masses on springs aren't all that important in themselves. But simple harmonic oscillators are very common. Another standard example is the pendulum swinging under the influence of gravity: At a more fundamental level, an example might be an atom in a crystal being held in place by electrostatic forces from its neighbouring atoms. If you have one of these systems, then in principle you can set it in motion with as little energy as you like. Pull a mass on a spring down a little bit and it will bounce back up, oscillating a certain amount. Pull the mass down half the amount and it'll bounce with oscillations half the size. In principle we could keep repeating this experiment, each time starting with the mass displaced half the amount we tried previously. In other words, a simple harmonic oscillator can have any energy we like. The spectrum of possible energies of one of these oscillators is continuous. (Note that the word spectrum here is merely physicist-speak for a set of possible values.) If we can set one in motion with 1 unit of energy then we can also set it oscillating with 0.5 units, or 0.01 units, or 0.000123 units of energy. Quantum mechanicsEverything I've said above is assuming that classical Newtonian mechanics is valid. But we know that for very small systems, around the size of a few atoms or smaller, we need to use quantum mechanics. This is an enormous topic but I'm only going to extract one basic fact. According to quantum mechanics, a simple harmonic oscillator isn't free to oscillate with any energy you like. The possible energy levels, the spectrum of the system, is discrete. There is a lowest energy level, and then all of the energy levels above that are equally spaced like so, going up forever: We usually call the lowest energy level the ground state or vacuum state and call the hig[...]

Self-referential logic via self-referential circuits

Sat, 15 Jul 2017 16:09:00 +0000

A relaxation technique

Wed, 07 Jun 2017 03:32:00 +0000

Logarithms and exponentials of functions

Sun, 05 Feb 2017 18:30:00 +0000

Building free arrows from components

Mon, 09 Jan 2017 16:33:00 +0000

IntroductionGabriel Gonzalez has written quite a bit about the practical applications of free monads. And "haoformayor" wrote a great stackoverflow post on how arrows are related to strong profunctors. So I thought I'd combine these and apply them to arrows built from profunctors: free arrows. What you get is a way to use arrow notation to build programs, but defer the interpretation of those programs until later. HeteromorphismsUsing the notation here I'm going to call an element of a type P a b, where P is a profunctor, a heteromorphism. A product that isn't much of a productAs I described a while back you can compose profunctors. Take a look at the code I used, and also Data.Functor.Composition. data Compose f g d c = forall a. Compose (f d a) (g a c)An element of Compose f g d c is just a pair of heteromorphisms, one from each of the profunctors, f and g, with the proviso that the "output" type of one is compatible with the "input" type of the other. As products go it's pretty weak in the sense that no composition happens beyond the two objects being stored with each other. And that's the basis of what I'm going to talk about. The Compose type is just a placeholder for pairs of heteromorphisms whose actual "multiplication" is being deferred until later. This is similar to the situation with the free monoid, otherwise known as a list. We can "multiply" two lists together using mappend but all that really does is combine the elements into a bigger list. The elements themselves aren't touched in any way. That suggests the idea of using profunctor composition in the same way that (:) is used to pair elements and lists. Free ArrowsHere's some code: > {-# OPTIONS -W #-}> {-# LANGUAGE ExistentialQuantification #-}> {-# LANGUAGE Arrows #-}> {-# LANGUAGE RankNTypes #-}> {-# LANGUAGE TypeOperators #-}> {-# LANGUAGE FlexibleInstances #-}> import Prelude hiding ((.), id)> import Control.Arrow> import Control.Category> import Data.Profunctor> import Data.Monoid> infixr :-> data FreeA p a b = PureP (a -> b)> | forall x. p a x :- FreeA p x bFirst look at the second line of the definition of FreeA. It says that a FreeA p a b might be a pair consisting of a head heteromorphism whose output matches the input of another FreeA. There's also the PureP case which is acting like the empty list []. The reason we use this is that for our composition, (->) acts a lot like the identity. In particular Composition (->) p a b is isomorphic to p a b (modulo all the usual stuff about non-terminating computations and so on). This is because an element of this type is a pair consisting of a function a -> x and a heteromorphism p x b for some type x we don't get to see. We can't project back out either of these items without information about the type of x escaping. So the only thing we can possibly do is use lmap to apply the function to the heteromorphism giving us an element of p a b. Here is a special case of PureP we'll use later: > nil :: Profunctor p => FreeA p a a> nil = PureP idSo an element of FreeA is a sequence of heteromorphisms. If heteromorphisms are thought of as operations of some sort, then an element of FreeA is a sequence of operations waiting to be composed together into a program that does something. And that's just like the situation with free monads. Once we've build a free monad structure we apply an interpreter to it to evaluate it. This allows us to separate the "pure" structure representing what we want to do from the code that actually does it. The first thing to note is our new type is also a profunctor. We can apply lmap and rmap to a PureP function straightforwardly. We apply lmap directly to the head of the list and we use recursion to apply rmap to the PureP at the end: > instance Profunctor b => Profunctor (FreeA b) where> lmap f (PureP g) = PureP (g . f)> lmap f (g :- h) = (lmap f g)[...]

Addressing Pieces of State with Profunctors

Sat, 07 Jan 2017 21:46:00 +0000

Attempted segueSince I first wrote about profunctors there has been quite a bit of activity in the area so I think it's about time I revisited them. I could just carry on from where I left off 5 years ago but there have been so many tutorials on the subject that I think I'll have to assume you've looked at them. My favourite is probably Phil Freeman's Fun with Profunctors. What I intend to do here is solve a practical problem with profunctors. The problemArrows are a nice mechanism for building circuit-like entities in code. In fact, they're quite good for simulating electronic circuits. Many circuits are very much like pieces of functional code. For example an AND gate like this can be nicely modelled using a pure function: c = a && b. But some components, like flip-flops, have internal state. What comes out of the outputs isn't a simple function of the inputs right now, but depends on what has happened in the past. (Alternatively you can take the view that the inputs and outputs aren't the current values but the complete history of the values.) We'll use (Hughes) arrows rather than simple functions. For example, one kind of arrow is the Kleisli arrow. For the case of Kleisli arrows built from the state monad, these are essentially functions of type a -> s -> (b, s) where s is our state. We can write these more symmetrically as functions of type (a, s) -> (b, s). We can think of these as "functions" from a to b where the output is allowed to depend on some internal state s. I'll just go ahead and define arrows like this right now. First the extensions and imports: > {-# OPTIONS -W #-}> {-# LANGUAGE Arrows #-}> {-# LANGUAGE RankNTypes #-}> {-# LANGUAGE FlexibleInstances #-}> import Prelude hiding ((.), id)> import Control.Arrow> import Control.Category> import Data.Profunctor> import Data.TupleAnd now I'll define our stateful circuits. I'm going to make these slightly more general than I described allowing circuits to change the type of their state: > newtype Circuit s t a b = C { runC :: (a, s) -> (b, t) }> instance Category (Circuit s s) where> id = C id> C f . C g = C (f . g)> instance Arrow (Circuit s s) where> arr f = C \$ \(a, s) -> (f a, s)> first (C g) = C \$ \((a, x), s) -> let (b, t) = g (a, s)> in ((b, x), t)This is just a more symmetrical rewrite of the state monad as an arrow. The first method allows us to pass through some extra state, x, untouched. Now for some circuit components. First the "pure" operations, a multiplier and a negater: > mul :: Circuit s s (Int, Int) Int> mul = C \$ \((x, y), s) -> (x*y, s)> neg :: Circuit s s Int Int> neg = C \$ \(x, s) -> (-x, s)And now some "impure" ones that read and write some registers as well as an accumulator: > store :: Circuit Int Int Int ()> store = C \$ \(x, _) -> ((), x)> load :: Circuit Int Int () Int> load = C \$ \((), s) -> (s, s)> accumulate :: Circuit Int Int Int Int> accumulate = C \$ \(a, s) -> (a, s+a)I'd like to make a circuit that has lots of these components, each with its own state. I'd like to store all of these bits of state in a larger container. But that means that each of these components needs to have a way to address its own particular substate. That's the problem I'd like to solve. Practical profunctor opticsIn an alternative universe lenses were defined using profunctors. To find out more I recommend Phil Freeman's talk that I linked to above. Most of the next paragraph is just a reminder of what he says in that talk and I'm going to use the bare minimum to do the job I want. Remember that one of the things lenses allow you to do is this: suppose we have a record s containing a field of type a and another similar enough kind of record t with a field of type b. Among other things, a lens gives a way to take a ru[...]

Expectation-Maximization with Less Arbitrariness

Sun, 16 Oct 2016 23:04:00 +0000

Dimensionful Matrices

Sun, 07 Aug 2016 02:23:00 +0000

IntroductionProgramming languages and libraries for numerical work tend not to place a lot of emphasis on the types of their data. For example Matlab, R, Octave, Fortran, and Numpy (but not the now defunct Fortress) all tend to treat their data as plain numbers meaning that any time you have a temperature and a mass, say, there is nothing to prevent you adding them. I've been wondering how much dimensions (in the sense of dimensional analysis) and units could help with numerical programming. As I pointed out on G+ recently (which is where I post shorter stuff these days), you don't have to limit dimensions to the standard ones of length, mass, time, dollars and so on. Any scale invariance in the equations you're working with can be exploited as a dimension giving you a property that can be statically checked by a compiler. There are quite a few libraries to statically check dimensions and units now. For example Boost.Units for C++, units for Haskell and even quantities for Idris. A matrix that breaks thingsEven if a language supports dimensions, it's typical to define objects like vectors and matrices as homogeneous containers of quantities. But have a look at the Wikipedia page on the metric tensor. There is a matrix which has the curious property that 3 entries on the diagonal seem to be dimensionless while the first entry is a squared velocity with dimension . This will break many libraries that support units. An obvious workaround is to switch to use natural units, which is much the same as abandoning the usefulness of dimensions. But there's another way, even if it may be tricky to set up with existing languages. Heterogeneous vectors and matricesAccording to a common convention in physics, a 4-vector has dimensions where I'm using the convention that we can represent the units of a vector or matrix simply as a vector or matrix of dimensions, and here is time and is length. The metric tensor is used like this: (where I'm using the Einstein summation convention so the 's and 's are summed over). If we think of having units of length squared (it is a pseudo-Riemannian metric after all) then it makes sense to think of having dimensions given by We can write this more succinctly as where is the usual outer product. I'll use the notation to mean is of type . So, for example, . I'll also use pointwise notation for types such as and . Now I can give some general rules. If is a matrix, and are vectors, and is a scalar, then only makes sense if . Similarly the "inner product" only makes sense if . Generic vectors and matricesAlthough these kinds of types might be useful if you're dealing with the kind of heterogeneous matrices that appear in relativity, there's another reason they might be useful. If you write code (in the imaginary language that supports these structures and understands dimensions and units) to be as generic as possible in the types of the vector and matrix entries, failures to type check will point out parts of the code where there are hidden assumptions, or even errors, about scaling. For example, consider a routine to find the inverse of a 3 by 3 matrix. Writing this generically as possible means we should write it to operate on a matrix of type , say. The result should have type . If this type checks when used with a suitably powerful type checker then it means that if we replace the units for type A, say, with units twice as large, it should have no effect on the result, taking into account those units. In this case, it means that if we multiply the numbers of the first row of the input by 0.5 then the numbers of the first column of the output should get multiplied by 2. In fact this is a basic property of matrix inverses. In other words, this mathematical property of matrix inverses is guaranteed by a type system that can handle units and heterogeneous matrices. It woul[...]

Cofree meets Free

Sat, 24 May 2014 05:21:00 +0000

Types, and two approaches to problem solving

Sat, 17 May 2014 15:22:00 +0000

Sat, 26 Apr 2014 04:42:00 +0000

Reinversion Revisited

Sun, 02 Feb 2014 01:53:00 +0000

Distributed computing with alien technology

Sat, 26 Oct 2013 04:00:00 +0000

What stops us defining Truth?

Sat, 12 Oct 2013 16:12:00 +0000

Why Heisenberg can't stop atomic collapse

Mon, 15 Apr 2013 01:08:00 +0000

TL;DRA heuristic argument to show that hydrogen atoms are stable and have a minimum energy level is wrong. I will assume undergraduate level quantum mechanics in the discussion.IntroductionThere's a popular argument used to explain why atoms are stable. It shows there is a lower bound on the energy level of an electron in the atom that makes it impossible for electrons to keep "falling" forever all the way down to the nucleus. You'll find it not only in popular science books but in courses and textbooks on quantum mechanics.A rough version of the argument goes like this: the closer an electron falls towards the nucleus the lower its potential energy gets. But the more closely bound to the nucleus it is, the more accurately we know its position and hence, by Heisenberg's uncertainty principle (HUP), the less accurately we know its momentum. Increased variance in the momentum corresponds to an increase in kinetic energy. Eventually the decrease in potential energy as the electron falls is balanced by an increase in kinetic energy and the electron has reached a stable state.The problem is, this argument is wrong. It's wrong related to the kind of heuristic reasoning about wavefunctions that I've talked about before.Before showing it's wrong, let's make the argument a bit more rigorous.Bounding wavefunctionsThe idea is to show that for any possible normalised wavefunction ψ of an electron in a Coulomb potential, the expected energy is bounded below by some constant. So we need to show thatis bounded below whereand p is momentum.Consider a wavefunction that is confined mainly around the nucleus soThe first fact we need is that Heisenberg uncertainty principle tells us that (assuming we're in a frame of reference where the expected values of p and x are zero).If the wavefunction is spread out with a standard deviation of a then the electron is mostly around a distance a from the nucleus. So the second fact is that we can roughly approximate the expected value of 1/r as 1/a.Combine these two facts and we get, roughly, thatI hope you can see that the right hand side, as a function of a, is bounded below. The graph of the right hand side as a function of a looks like:It's now an exercise in calculus to find a lower bound on the expected energy. You can find the details in countless places on the web. Here a link to an example from MIT, which may have come directly from Feynman's Lectures on Physics.The problemThe above discussion assumes that the wavefunction is basically a single packet confined around a distance a from the nucleus, something like that graphed above. But if a lower energy state can be found with a different wavefunction the electron will eventually find it, or an even lower energy state. In fact, by using a wavefunction with multiple peaks we will find that the Heisenberg uncertainty principle doesn't give a lower bound at all.We'll use a wavefunction like this:It has a packet around the origin just like before but it also has a sharp peak around r=l. As I'm showing ψ as a function of r this means we have a shell of radius l.Let's saywhere ψ1 is normalized and peaked near the original and ψ2 is our shell of radius l. Assume no overlap between ψ1 and ψ2.In this case you can see that we can makeas large as we like by making l as large as we like while still leaving us free to make the central peak whatever shape we want. This means that the estimate of coming from HUP can be made as small as we like while making the central peak as close to a Dirac delta as we want. Informally, HUP controls of the overall sp[...]

Aliasing and the Heisenberg uncertainty principle.

Mon, 14 Jan 2013 00:59:00 +0000

TL;DRThe Dirac comb is an example of a wavefunction whose position and momentum aren't fuzzy.IntroductionThe Heisenberg uncertainty principle says that if you have a particle in some state and observe either its momentum or its position then the products of the standard deviations of distributions of the outcomes satisfy this identity:I think many people have a mental picture a bit like this:You can know the position and momentum with some degree of fuzziness and you can trade the fuzziness between the two measurements as long as the product of their sizes is larger than ℏ/2.Here's another way of thinking about that kind of picture (assuming some units I haven't specified):position=123.4???momentum=65?.???The idea is that the question mark represents digits we don't know well. As you move towards the right in the decimal representation our certainty in the accuracy of the digit quickly goes downhill to the point where we can't reasonably write digits.But this picture is highly misleading. For example, the following state of affairs is also compatible with the uncertainty principle, in suitably chosen units:position=...???.123...momentum=...???.654...In other words, it's compatible with the uncertainty principle that we could know the digits beyond the decimal point to as much accuracy as we like as long as we don't know the digits before the point. It trivially satisfies Heisenberg's inequality because the variance of the position and the momentum aren't even finite quantities.But being compatible with Heisenberg uncertainty isn't enough for something to be realisable as a physical state. Is there a wavefunction that allows us to know the digits to the right of the decimal point as far as we want for both position and momentum measurements?Sampling audio and graphicsMaybe surprisingly, the worlds of audio and graphics can help us answer this question. Here's what a fraction of a second of music might look like when the pressure of the sound wave is plotted against time:But if we sample this signal at regular intervals, eg. at 44.1KHz for a CD, then we can graph the resulting signal as something like this:The red curve here is just to show what the original waveform looked like. The black vertical lines correspond to regular samples and we can represent them mathematically with Dirac delta functions multiplied by the amplitude measured at the sample.There is a well known problem with sampling like this. If you sample a signal that is a sine wave sin(ωt) at rate f then the signal sin((ω+2πnf)t) will generate exactly the same samples for any integer n. The following illustration shows what might happen:The two waveforms are sampled at the same regular intervals (shown by vertical lines) and give exactly the same amplitudes at those samples.This forms the basis for the famous Nyquist-Shannon sampling theorem. You can reconstruct the original signal from regularly spaced samples only if it doesn't contain frequency components higher than half your sampling rate. Otherwise you get ambiguities in the form of high frequency parts of the signal masquerading as low frequency parts. This effect is known as aliasing. As a result, the Fourier transform of a sampled function is periodic with the "repeats" corresponding to the aliasing.In the audio world you need to filter your sound to remove the high frequencies before you sample. This is frequently carried out with an analogue filter. In the 3D rendering world you need to do something similar. Ray tracers will send out many rays for each pixel, in effect forming a much higher resolution image than the resolution of the final result, and that high re[...]

Shuffles, Bayes' theorem and continuations.

Sun, 30 Dec 2012 16:49:00 +0000

A pictorial proof of the hairy ball theorem

Mon, 19 Nov 2012 00:10:00 +0000

The hairy-ball theorem says that there is no continuous non-zero vector field on the surface of a sphere. There are lots of popular accounts that tell you what this means, giving great examples. Here's a Youtube video for example: allowFullScreen='true' webkitallowfullscreen='true' mozallowfullscreen='true' width='320' height='266' src='https://www.youtube.com/embed/B4UGZEjG02s?feature=player_embedded' FRAMEBORDER='0' />My goal is to show why it's always true.A simply connected domain in the plane is one with the property that any loop in it can be shrunk down to a point. Here's an example of a domain D with an example loop L being shrunk down to a point P:Here's an example of a domain that's not simply connected. It has a hole in the middle. I've drawn a L loop around the hole. You can't shrink that loop to a point because the hole gets in the way:Here's a simply connected domain with a vector field on it:Think of the vectors as being drawn literally in the surface so that if we were to pick up the surface and stretch it like a piece of rubber the vectors would get stretched with it. Remember that a vector field is defined everywhere in the domain so the arrows are just a random sprinkling of examples to show what's going on. For this to be an accurate picture you want to imagine an infinity of arrows, one at every single point of the domain.Let's put a loop, starting and ending at P, in our simply-connected domain:Now imagine travelling along the loop, starting at P and ending at P. As you move along there's an arrow at each point in your journey. Here's what the arrows look like as you travel from P to P anti-clockwise, plotted as a kind of graph:The vectors start off pointing to the right. They swing anti-clockwise by about 45º and then swing back to where they started. As the journey is a loop they clearly must end where they started. A different, really swirly vector field, might have resulted in arrows that that rotated around hundreds of times along your journey. But by time you reach the end of the journey they must swing back to where they started. What's slightly less obvious is that they'd also have to rotate back to cancel out the hundreds of swings. You might think "the vectors could rotate round a hundred times but as long as they make exactly 100 turns they'll return to where they started and there's no need for them to unwind". But actually, every bit of rotation in the journey must be unwound. The total amount of rotation, adding all the positive rotations, and subtracting off the negative rotations, is called the winding number for the loop. We count anti-clockwise rotation as positive and clockwise as negative. So I'm claiming that the winding number for a closed loop in a simply-connected domain is always zero.(Note: in most books the winding number normally refers to how many times the loop itself winds around a point. I'm using it to refer to how many times the vector winds around itself you follow the loop. To help with your intuition: the hour hand of a working clock normally accumulates a winding number of -2 in one day. If it ran forward for a day, but then ran backwards for half a day, the winding number would be -1.)Here's why the winding number for simply connected domains must be zero: firstly - it's pretty clear that the winding number for any loop must be an integer. If the winding number was a half, say, the arrow wouldn't end up pointing 180º from where it started which makes no sense for a closed loop. Now the domain is simply connected, so the loop can be shrunk to a point. Now imagine doing the shri[...]

Generalised entropy

Sat, 07 Apr 2012 23:22:00 +0000

Sat, 17 Mar 2012 20:30:00 +0000

Using Lawvere theories to combine effects

Sat, 11 Feb 2012 15:47:00 +0000

Lawvere theories made a bit easier

Sun, 05 Feb 2012 15:57:00 +0000

Some parallels between classical and quantum mechanics

Sat, 21 Jan 2012 21:38:00 +0000