thetwiceler's comments

Zeilberger's Opinion 123 is an April Fool's Day joke.

Firstly, Kalman filtering is optimal, that is, it produces exactly the correct posterior distribution. As you mention, particle filters cannot achieve this.

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).

Yep, this is what I meant to allude to, and you've worded it much better than I could have.

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.

ihm's response to you I think did a great job explaining what I meant to say, but let me elaborate further.

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.

They're usually used synonymously. Yes, Cantor's diagonal argument can still be used to show the uncountability of real numbers in a constructive setting.

It seems misleading to say that intuitionistic logic assigns statements to one of the two values, True or False. There's no symmetry between the notions of truth and falsity as there is in boolean logic.

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.

This video is somewhat misleading. I appreciate the attempt at making Banach-Tarski accessible to a general audience, but it dwells on the wrong aspects of what makes Banach-Tarski interesting, making the construction look more like a magic trick with sleight-of-hand. I wish the video had at least mentioned the Axiom of Choice somewhere, as that is fundamentally what Banach-Tarski is about.

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.

To define variance as

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

and not ever allude to the far more meaningful version,

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

is just criminal. This is not at all a good explanation of variance, covariance, and correlation.

The treatment of Big O notation is not only misleading (and poorly conveyed) but wrong in several ways. Big O is an upper bound that does not need to be tight. The table displaying the "limit of N for 1 second (standard processor)" and the accompanying note that the chart will eventually become outdated is manifestly wrong and misleading. Big O ignores constant factors and so no such comparisons can be made. For any particular duration of time (or for any particular number of elements), an algorithm with complexity `O(f(N))` may be faster than one with complexity `O(g(N))` regardless of `f` and `g`. Big O is not something that can obsolesce.

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

is a recursive definition but it has no base case. Of course, there can also be multiple base cases or other more complicated structures.

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).

In the type theory literature, it is rather the other way: Void is synonymous with the bottom type. I don't know who has first claim to the name "void", but from the type theory perspective, it is C, Java, et. al. who have it backwards.

It is in fact Markov; Markov just means that the probability distribution of the future depends only on the present, and so the past adds no additional information in conjunction with the present. That's certainly the case here.

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!

Oh, I didn't realize that. Well, the book is

  Probability Theory: The Logic of Science
  ET Jaynes
  2003

I highly suggest buying it or finding it from your library!

ET Jaynes is the best! Read the whole book!

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

I don't think this is a great idea, for several reasons:

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.

[1] http://sciencevsmagic.net/geo/ [2] http://en.wikipedia.org/wiki/Heptadecagon [3] http://www.maa.org/external_archive/devlin/LockhartsLament.p...

> The concept of "compactness" is the technical solution that lets you formulate calculus without them -- it's typically only taught to math majors because infinitesimals are less awkward to do algebra with: we can now prove that the shortcut works, so why bother with the long way unless you have good reason?

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.

Absolutely not. I'm actually very frustrated that they give that code as an example. First of all, it misses the most important of quicksort - the fact that it can be implemented in place (and yes, you can write an pure in-place quicksort using STArrays).

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_...

Let's not blow this out of proportion. They scraped private data (that required a Yale login) without permission and accidentally made it available to a wider audience than intended.

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...

It is sad that Taleb does not see the value in the standard deviation; standard deviation is far more natural, and more useful, than MAD.

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 mean would certainly be n! (note that it is possible, and even likely, that you may create the same sorting multiple times by random chance).

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)

Perhaps the more interesting question is why do most programming languages allow several input values?

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)

But this isn't really multiple input or return values. We are just inputting or returning a struct (with constructor (,) or (,,), respectively), and we can pattern match against it for the return value.

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.