thetwiceler

It's a rough heuristic that to achieve a certain accuracy for a linear/Gaussian system with a particle filter, you need a number of particles exponential in the number of dimensions of the system. I feel like this could probably be stated more formally and shown, but I don't think I've seen anything in that vein. The Kalman filter, being simply matrix operations, should scale as the number of dimensions cubed.

So yes, Kalman filtering is computationally more efficient, and (obviously) more accurate.

I also wouldn't discount the fact that the Kalman filter is, in a sense, simpler than the particle filter for a linear/Gaussian system; you don't need to worry about resampling or setting a good number of particles, and you don't need to compute estimates of the mean/covariance statistics (which are sufficient since the posterior should be a Gaussian).

Perhaps a nice way to say it is that the mathematical objects necessary for physics that I can think of are separable (such as the real numbers). Basically, whenever you have uncountable sets, they come along with some topological structure which must be handled continuously.

Just like you might define computable real numbers, you may similarly describe the "definable" real numbers, that is, those numbers which are uniquely specified by logical statements. You will inevitably find that the definable real numbers, like the computable reals, appear to be countable.

So the fact that something is computable, per se, isn't exactly what makes the real numbers countable rather than uncountable.

I use the vocabulary of meta-theory and models, because the practice of defining either the countable reals or the definable reals within a formal system looks a whole lot like defining a formal system within itself (i.e., metatheory). So the fact that the computable reals and the definable reals appear countable, is, at least to me, much like the statement that there are countable models of your favorite formal system.

You need to be very, very careful when talking about the size of the constructive reals. If you are working within constructive mathematics, if you describe the real numbers as setoids of Cauchy sequences with Cauchy-equivalence as the equivalence relation, then there are uncountably many real numbers. From a meta-theoretic perspective, it is obvious (as we are working in constructive mathematics) that every real number is in some sense "computable".

Your notion that there are countably many constructive reals probably comes from definitions of the constructive reals from within classical set theory, wherein you must internalize some notion of what it means for a real number to be constructible, and so you are, in a sense, working meta-theoretically. Then it is no surprise that the computable real numbers are countable. After all, Skolem's paradox says that, meta-theoretically, we could have countable models of the classical real numbers as well.

Additionally, meta-theoretically, we see that our definition of real numbers in constructive mathematics will also have a countable model when seen from the outside.

The sleight-of-hand comes in around 14:30 into the video, where we are told to create the sequence for an "uncountably infinite number of starting points." That's exactly the point where the construction is non-constructive, and the infamous Axiom of Choice is used. There is no construction - in the sense of constructive mathematics - that can achieve what is described at this point.

Banach-Tarski is not generally regarded as some deep fact about mathematics, a point the video mistakenly belabors. Rather, it is a consequence about particular axiomatizations of set theory which admit the Axiom of Choice. Banach-Tarski is only valid with the Axiom of Choice, and in fact that is the main interest in the paradox.

In my personal opinion, the Banach-Tarski paradox isn't much more enlightening than the simpler construction of the Vitali set (assuming the Axiom of Choice), which is a non-measurable set of real numbers (with Lebesgue measure, i.e., length).

Another part of the video I find misleading has to do with the hyper-dictionary, where he describes the hyper-dictionary by putting some parts of the dictionary "after" other parts which are infinitely long.

The putative applications of Banach-Tarski to physics are ridiculous. Uncountable sets are fundamentally unphysical. The Axiom of Choice serves mainly as a convenience to mathematicians when either a proof avoiding the Axiom of Choice would be more complicated, or so that mathematicians can state properties of objects which are set-theoretically larger than anything that can be relevant to physics anyways.

    E[x^2] - E[x]^2

    E[ (x - E[x])^2 ]

Also, it is not necessary that there be a base case for recursion (only well-founded recursion). For instance, the Haskell definition

  repeat :: a -> [a]
  repeat x = x : repeat x

Saying unconditionally that all operations for a hash set or hash map are O(1) is wrong.

Opening quotation in LaTeX is accomplished by "``".

I also think that the comparison between the human brain and CPU is completely unjustified. Given that most people could not remember the sequence of results of 32 coin tosses, why shouldn't I say they have no greater than 4 bytes of memory? (For myself, I think the most appropriate unit of memory is "10 seconds of commonly spoken English language").

There are already so many terrific sources for learning algorithms that I don't understand why the author created this book. It is not only inaccurate, but more difficult to understand than other resources I have come across (e.g., Coursera).

This is an example of a Markov chain that is not aperiodic; what that means is that, given a starting node, at any point in time in the future, it will always be the case that it is impossible to be at a certain node. This ends up meaning that the Markov chain never ends up reaching a steady state; rather, its behavior is periodic!

  Probability Theory: The Logic of Science
  ET Jaynes
  2003

http://bayes.wustl.edu/etj/prob/book.pdf

Arithmetic is a very small part of mathematics, and perhaps the least important. But even as far as arithmetic goes, I don't see this game giving children a good "number sense". Why are different numbers the same size? If we don't relate the abstract concept of numbers to counts or sizes, then arithmetic is just meaningless manipulation of symbols.

Worse, the game doesn't seem open-ended. Children need not figure the answer out themselves, because they can just try an action and see what happens. I can see children just trying different actions over and over until they finally perform the winning combination. And I can also imagine the possibility of children thinking that they understand a subject when they really don't (for example, not being able to generalize beyond what they've seen in the game).

On a much smaller note, I hope the game has more to it than "when the result is zero, things disappear." For multiplication and division, doesn't it make more sense for that to be 1?

I don't see a video game like this helping kids to learn math and to learn to enjoy math. The children like the game because most video games (such as Mathbreakers, I'd say) are stimulating. What kid doesn't love video games?

So I've been quite a curmudgeon. What do I think kids should do to learn math in a fun way? I totally agree that games are a great idea. But I think a game such as the ruler/compass construction game [1] (featured on HN before) is a much better game. The ruler/compass construction game allows you to interact with the mathematics in a much more open-ended way than Mathbreakers. It emphasizes the importance of thinking logically, rather than simply manipulating symbols. Unlike Mathbreakers, which takes a complex system of base-10 arithmetic and adds to it even more complex game mechanics, the geometry game has extremely simple mechanics. You can let children simply play and come up with their own shapes, or they can try to make certain specific shapes (the link has several challenges). And the geometry game is deep! With these simple mechanics, we can encode some of the most interesting and challenging problems. For example, whether someone can construct a 17-gon [2] (and if so, how to do so) was only answered by Gauss (in the affirmative) in 1796. (Of course, that's not a puzzle we'd give to children! But how about a hexagon?)

So really, the geometry game is one that should be appropriate and challenging for people of all ages and math backgrounds! And it doesn't need to "dress up" the math with auxiliary puzzles and cartoon characters and 3D worlds. The math is already interesting as it is.

And finally, from Lockhart's Lament [3]:

  Simplicio: Then what *should* we do with young children in math class?

  Salviati: Play games! Teach them Chess and Go, Hex and 
  Backgammon, Sprouts and Nim, whatever. Make up a game. Do 
  puzzles. Expose them to situations where deductive reasoning
  is necessary. Don’t worry about notation and technique, help
  them to become active and creative mathematical thinkers.

I don't know where you got the idea that compactness is in any way relevant to the formulation of calculus. Compactness is a property of topological spaces that, to an approximation, is a generalization of sets being finite or infinite. For example, with the discrete topology, a set is compact iff it is finite. There are many related notions of compactness. In R^n, a set is compact (and sequentially compact) iff it is closed and bounded.

Compactness is important for some ideas related to calculus, but it's not related to formulating calculus. For example, if a continuous function maps from a compact space to R, then it achieves a maximum/minimum (this can be seen of a generalization that there is always a maximum/minimum of a finite set of real numbers, but not necessarily for an infinite set).

The word infinitesimals is also a tricky word to use. To a mathematician, an infinitesimal would probably mean an algebraic object that formalizes the idea of a number smaller than any positive real number. This is not what is taught in calculus or analysis classes, and is only relevant for non-standard developments of calculus.

The winner in the modern formulation in calculus is the "epsilon-delta" formulation of limits; that's what's taught in both calculus classes (at least to an extent) and analysis classes. The weird thing is that calculus is stuck with Leibniz's notation, which does, in a sense, refer to infinitesimals. I think that's what you're really thinking of (rather than compactness) as how you can formulate calculus without infinitesimals. The thing is that, save notation, this is how calculus is taught today.

Second of all, it's bad because it runs through the list xs twice. Instead, they should use the partition function to get both the left-hand and right-hand sides at once.

And thirdly, it's inefficient by use of the (++) operator, which takes time proportional to the length of the left-hand list. A better (out-of-place) implementation of quicksort would use an accumulator so this wouldn't happen (and actually, this means that we should do the partitioning ourselves rather than using the partition function as mentioned above).

Here is an example that makes these improvements with quicksort [1].

[1] http://en.literateprograms.org/Quicksort_(Haskell)#Using_an_...

Yale has historically been very supportive of these things. A couple of years ago, they acquired another very slick course catalog website, Yale Bluebook, for a good chunk of money [1].

[1] http://yaledailynews.com/blog/2012/08/01/university-acquires...

For example, if X has a standard deviation of s, and Y has a standard deviation of t, then the standard deviation of X + Y is sqrt(s^2 + t^2). There is a geometry of statistics, and the standard deviation is the fundamental measure of length.

To retire the standard deviation is to ignore the wonderful geometry inherent in statistics. Covariance is one of the most important concepts in statistics, and it is a shame to hide it from those who use statistics.

Additionally, I will mention that we do not need normal distributions to make special the idea of standard deviations. In fact, it is the geometry of probability - the fact that independent random variables have standard deviations which "point" in orthogonal directions - which causes the normal distribution to be the resulting distribution of the central limit theorem.

The median, which I don't think you're referring to, is something else (I imagine it would be substantially less than the mean).

(See http://en.wikipedia.org/wiki/Geometric_distribution)

I'll make the argument that in Haskell, functions BOTH support only a single input value and a single output value. For example, consider the function (+) which takes two numbers and returns their sum. The type of (+) is (+) :: Num a => a -> (a -> a). I have added the parentheses to emphasize the syntax of the type. (+) is a function which takes a single number as input and gives a single function as output!

Now, we can do something like f :: (a,b) -> (x,y,z) and write:

  let (x0,y0,z0) = f (a0,b0)

I think that any elegant language should support as few "primitive features" as possible - it should be simple, and let a few powerful ideas (e.g., first-class functions, currying, and pattern matching) let the rest fall out. I think Haskell really embodies this idea.

"How many people actually use any of this “practical math” they supposedly learn in school? Do you think carpenters are out there using trigonometry? How many adults remember how to divide fractions, or solve a quadratic equation? Obviously the current practical training program isn’t working, and for good reason: it is excruciatingly boring, and nobody ever uses it anyway. So why do people think it’s so important? I don’t see how it’s doing society any good to have its members walking around with vague memories of algebraic formulas and geometric diagrams, and clear memories of hating them. It might do some good, though, to show them something beautiful and give them an opportunity to enjoy being creative, flexible, open-minded thinkers— the kind of thing a real mathematical education might provide."

For some reason, the math curriculum is completely about learning techniques, which roughly correspond to formulaic manipulation of symbols. We basically learn to apply algorithms for manipulating symbols, and we do it over and over again. And of course, this is easy to test.

But it's also the absolute least important aspect we need to know! It's the part that doesn't involve thinking. And so we end up with some farce of an education where we learn the procedures without the context why people created them in the first place!

Take the quadratic formula: something wholly useless in real life, but taught to every middle-schooler in the US. Somehow, even though the name has "quad" in it, we learn it without learning the context of the ancient Greek concept of quadrature, and problems relating to whether it is possible to find a rectangle with a certain area and perimeter. In the derivation, we "complete the square", but nobody draws the said square!

And then we do a hundred problems involving applying the quadratic formula, which is neither enlightening nor useful.

[1] http://www.maa.org/sites/default/files/pdf/devlin/LockhartsL...

Let's say that Apple sees the price of its stock drop to something that it thinks is unreasonably low. They may choose to spend some of their cash on hand to buy back some of their stock. This is a wise investment that shareholders would applaud - Apple is getting a good deal.

Same deal with the Federal Reserve. Federal Reserve notes are nominally liabilities for the Fed, and are much like the concept of Apple stock. If the Fed notices the price of the dollar drops, it's in their best interest to trade some of their holdings to buy back some dollars.

Our currency has not been pinned to gold for 40 years (when the Bretton Woods system collapse), but the Federal Reserve still maintains the holdings.

Before the Bretton Woods system collapsed, the US government was required to allow large entities to exchange their USDs for gold. Now, it isn't required to. But the fact that the Federal Reserve holds the gold, and that it is well known that they would use it to support the value of the USD, helps maintain the value of the USD.

The USD is not literally backed by gold, but part of the Federal Reserve's mission is to moderate the rate of inflation; that means holding the value of the USD steady. And the way they do it is beyond the scope of this discussion, but it certainly depends on the Federal Reserve trading its holdings on the market (which, as you point out, is mainly debt (in terms of USD), not gold).

If taxation were the only form of backing, things would be a little more strange. The currency could work, but taxes would have to be defined differently. Somewhere in the tax rules, there would have to be some statement that pins the value of the USD.

For some reason, many people believe that this is true. I believe that it is not.

Technically, yes, if people all decide the currency has value, then it will have value. But this is a ridiculous argument! How much is this currency supposed to be worth? According to this argument, any number is potentially valid! This means that there is absolutely nothing that should hold the value of the currency fixed, and with a few "no free lunch" arguments (anyone can claim any random thing has value and try to trade with it), we see that things with no intrinsic value should NOT have value.

So why does the US Dollar have value? It's just paper (cotton), right? Not true! If the exchange rate of the dollar decreases, you'll see the Federal Reserve will start trading some of its goodies from Fort Knox (gold, etc.) for US Dollars, in order to maintain the dollar's exchange rate/value.

So in reality, the US Dollar is backed by holdings that have intrinsic value.

EDIT: As pointed out, I should mention that another important backing of the USD is taxation.

Also, what I said about the Federal Reserve isn't technically true. What's important is that they have a mission to moderate the rate of inflation of the USD (i.e., maintain its value), and their asset holdings are critical in allowing them to do this.

[1] http://stackoverflow.com/questions/7961604/fixing-issues-not...

In other programming languages, I'm sure you already use the very same functions that are fundamental to monads; you just don't have a syntactic construct that says "Hey, these things share a similar structure!"

Most of the other replies focus on IO (and on the do-notation side of things), and so I'm not sure that they'll help your confusion.

We'll need to start with functors. Without getting too formal, functors describe "containers" that can hold objects of any type. A list is a functor, a "Maybe" is a functor, the result of a computation (i.e., "IO") is a functor… lots of things are functors!

And since functors can contain anything, they can certainly recursively contain themselves - that is, they can be nested! We can have a list of lists, or a "Maybe (Maybe a)" (hey,… that seems like an awfully redundant thing to construct). When we talk about "IO", we can have an "IO (IO a)": that is, we can describe a computation that returns to us another computation!

And with these functors that I've mentioned, we realize something interesting: We would often like to flatten these nested structures. We use "concat" to reduce a list of lists to just a list; how to reduce a "Maybe (Maybe a)" to a "Maybe a" is obvious; for IO, we might want to take our description of a computation that returns a description of another computation ("IO (IO a)") and convert that into a description of a computation that runs the first computation, and upon receiving the result of that computation (which is a computation itself), run the resulting computation, and then return the result of THAT as our final result.

Also, for these things, we have an idea of how we would inject a pure value into the structure. We can create a list with a singleton element, or "Just" our element, or the computation that does nothing interesting (no missile launches) and just returns our element.

Haskell is just wacky enough to let us use the same syntax for all of these rather different ideas (which only share the similarity of having the monadic structure)!

NOW, I personally don't think that the trouble that people have with monads is related to the abstraction and the shared syntax - I think it has more to do with the use of the use of Haskell's "do" notation. Learn what "do" notation is sugar for! Learn what "bind" (>>=) is (it's basically a neat combination of the two operations ("bind" and "return", for what it's worth) that I described above).

I can't promise you that learning monads is something necessarily pragmatic (except for the fact that I think Haskell is the perhaps the MOST pragmatic language, and you'll need to learn monads to be comfortable with Haskell). But the world would be a pretty dull place if we only did what was pragmatic.

[1] http://en.wikipedia.org/wiki/Shannon's_source_coding_theorem