text:
## In defense of semicolon

I've noticed a lot of noise recently about getting rid of mandatory semicolons in mainstream imperative languages because...well...we can! I remember when this move was made in Scala, it was a bit painful with corner cases and error messages, but most of the community was happier with it. But I thought we lost something, let's look at the good and bad of semicolons:

• That semicolons can be inferred deterministically means that they are redundant.
• Visual verbosity and clutter.
• extra (keyboard) typing.
• Anachronistic.

Good:

• Redundancy enhances error detection (and robust IDE tooling in general).
• They aren't really that hard to type.
• Inference that depends on parsing probably goes a bit too far (Scala) in that its not always obvious to human readers where semicolons are inferred.

Did I miss anything?

## Comment viewing options

### Another case of implicit vs. explicit

With IDEs we can adopt the hybrid approach: implicit resolution (of lines in this case) at edit time coupled with explicit, even if subtle, feedback explicitly indicating the resolution. I'd argue this is a best of both worlds approach.

### Yes. The IDE can permanently

Yes. The IDE can permanently infer a semicolon as a service to the user. By this, I mean, the semicolons become sticky and future changes to the code will not blow them away, and this is probably a good thing. But many users are uncomfortable about this kind of reference; they also get annoyed when the IDE infers a closing brace.

These inferences could also be made invisible and transient--the IDE infers a semicolon closing brace so it can provide decent feedback. But this, and then, if the code is left untouch (a semicolon, closing brace wasn't typed manually), can add a permanent token as above.

### invisible and transient ...

invisible and transient

... or visible but faded and semi-transparent, such that the user must type it or move on for it to become permanent.

### Ya, that's how it worked in

Ya, that's how it worked in the Scala IDE (for parenthesis at least, we didn't bother with semi-colon inference, but probably should have).

### Redundancy doesn't always enhance readability.

I don't think redundancy always enhances readability.

I'm against having semicolons, but I think braces vs indentation is a simpler argument. In brace-based programming languages, programmers still typically indent their code so humans can easily see what's going on. The braces end up being just for the compiler.

Indentation-sensitive languages make the compiler use the same indicator of structure that humans use. Adding redundant braces, I believe, harms readability (though maybe you already covered this case in your "visual verbosity and clutter" point).

I think that, roughly, semicolons are for compilers and newlines are for humans. But this doesn't always work out as well as the braces vs indentation situation. (And then there's omitting parens on function calls, which gets even messier.)

### Well, look at Haskell, which

Well, look at Haskell, which is minimally non-redundant, and just see how hard it is for new users to grock Haskell's syntax compared to something more redundant like Java (where redundancy comes from syntax and formatting). I believe some amount of redundancy is beneficial to readability.

Semicolons are for humans, its obvious that the compiler can do without them. However, semicolons do make the job of the compiler easier in forming decent error messages, but I argue that is for humans also.

Haskell does a lot of things non-redundantly, and I think it's useful to look at the features independently.

For example, do you think adding braces and semicolons to Haskell would improve readability of the code (for someone who has been using the language for, say, one month)?

### I must remark (in reaction

I must remark (in reaction to Kannan's reply) that Haskell syntax *has* semicolon and braces, that can be used anywhere locally as an alternative to the most common whitespace-sensitive syntax.

Sean, I am not at all convinced by your statement that "it is hard for new users to grock Haskell's syntax compared to something more redundant like Java". This typically sounds like a claim that is believed but has not been empirically validated (orelse I would be interested in references).

I think any unease you could observe may very well be a "familiar vs. new" difference rather than something about Java or Haskell syntax (as Java syntax is basically C syntax and therefore minimally different from what people already see all around). I have heard of Haskell being used to teach non-programmers (ie. a programming course in a mathematics programme), and have not heard of particular syntactic difficulties.

We also often hear the argument that Python syntax (not that far to Haskell's) is nice and easy to work with, and look like most intuitive pseudo-code. My guess is that there is some truth in this idea, though I haven't heard of concrete experiments. On the other hand, Chris Okasaki reports that indentation-sensitivity was a great help to teach programming to beginners, by forcing them to pay more attention to the code structure.

### Of course optional doesn't

Of course optional doesn't mean required, but dealing with other peoples' styles is a curse to having "choice;" language consistency is another dead horse to beat later.

I would argue that some amount of redundancy leads to reinforcement, which leads to both (a) quicker learning of the language and (b) better readability when looking at some code you didn't write. Oddly enough, books used to be written without periods. Punctuation is actually a recent and extremely useful invention. Familiarity is obvious one factor that would have to be accounted for in an empirical study, right now I'm just working off of anecdote.

When I look at Haskell code, is that I always get lost without redundant syntactic signage and type annotations. I'm not really talking so much about semicolons in this case (type annotations are probably more important), I was only using Haskell to make a point (I would use Scala more to debate semicolons).

### Thanks, I just fixed it. In

Thanks, I just fixed it. In the process I noticed that it had been mentioned on LtU before, but without really starting a discussion.

### oh the humanity

and we all know how easy it is to copy-and-paste-and-auto-indent-correctly python code of any significant length. not that we should actually be doing much copy and paste, but it does have to happen sometimes, and i freaking hate whitespace sensitive languages then. and other times, to boot.

### Whitespace Programming Language

It is possible to program using only whitespaces Link

Edit : Link is to the wikipedia page of the language not sure what the person below is referring to.

### Is there anything that you

Is there anything that you find valuable in the link you gave? I've glanced over it and found little more than trivia and unstructured discussion -- with the historical remark that whitespace significance was promoted by ISWIM a long time ago.

If it makes specific points that are pertinent to this discussion, please feel free to quote them more precisely.

### JavaScript semicolon insertion considered problematic

JavaScript code that returns a nicely formatted object literal can be problematic because of semicolon insertion that is algorithmic but does something the programmer doesn't expect. Consider this example due to Colin Ihrig:

function getObject() {
return
{
foo : 1
// many more fields
};
}

This does not return the object, but rather the undefined value, due to semicolon insertion after return (and likewise after throw). Furthermore, the semicolons in for statements must be literal; newlines cannot replace them.

### JavaScript ASI

The way JavaScript does automatic semicolon insertion is very hacky and hence shouldn't be taken as an argument either way. If you want to look at a more reasonable example, look at Haskell.

### Consider indentation

In Python, where indentation decides block levels, I would argue that semicolons do not (significantly) enhance error detection or readability, because both of those are already served so much better by the identation/significant whitespace. In Python, it's also generally quite obvious to human readers where the end of statements/expressions would be inferred.

So, I would argue that three of your "Good" points aren't significant in Python, and then the arguments for semicolons are quite weak.

### I don't get it, indentation

I don't get it, indentation is about blocks, not statements, which are demarcated by new lines right? Then I have know idea why python would be any better than scala, unless you are saying python doesn't support unblocked multiline statements. If so then semicolons aren't necessary.

### I'm not sure about Scala.

I'm not sure about Scala. Python does support unblocked multiline statements. But I'm not sure how that validates the case for the semicolon?

The very fact that we're even having this debate says to me that programming languages- at least the popular ones, the ones defined as some combination of features found in either Algol-68 or Smalltalk-80, is dead. The design space has been exhausted, the optimal points in the design space have been discovered, and the only thing left to distinguish new languages are utter trivialities. Like whether semicolons are needed or not, or how fast the compiler runs.

This isn't to say that language design outside of the mainstream is dead, quite the contrary. One only has to compare, say, Haskell and Ocaml, to find large, important differences. Type classes or modules and functors? Lazy or strict evaluation? Monadic side effects or unlimited side effects? Which is better or worse is subject to debate, but my point here is that differences are not trivial. Note, basically no one says "I use Ocaml because I don't like Haskell's significant white space", or vice-versa. Or consider Scheme vr.s Lisp- same deal.

If some one were to show up and go "Hey, I implemented an Ocaml, but changed so you only have to use one colon for list cons, instead of two!", everyone would be like "Um, why?" That's the level of triviality we're at here. "My language is better because of some small syntactic difference." Your language is virtually indistinguishable from what it came from.

### Yeesh

I don't think Sean was at all attempting to elevate semicolons vs whitespace into the level of lazy vs strict or pure vs impure. He was just raising a discussion about one aspect of concrete syntax design. If you think it's too trivial to discuss then by all means don't discuss it.

### If, however...

If some one were to show up and go "Hey, I implemented an Ocaml, but changed so you only have to use one colon for list cons, instead of two!", everyone would be like "Um, why?"

If, however, somebody showed up saying "Hey, I implemented a Haskell, but fixed it to properly use single colon for type ascription", then that would be a BFD indeed. :)

### Innovation in Mainstream

Finding yet another example of Parkinson's Law of Triviality does not indicate the design space, even for languages near Smalltalk-80 and Algol-68, is even close to fully explored or optimal, not even within the mainstream features. A few areas of significant variation today include traits/inheritance models, reflection, concurrency, persistence, partial failure handling, module systems, libraries, and even syntax (which is often more significant than a semicolon).

### If you leave the mainstream, there's lots going on

Granted. But I don't see those ideas having much of an impact on the mainstream. Maybe I just read too much hacker news and reddit, but as far as I can see, to the extent that there is a debate in the mainstream about what languages to adopt, many if not most of the arguments are about trivialities- semicolons and compilation speed.

And I don't even mean to cast aspersions on the importance of syntax in language design. I suppose the no-semicolons claim could be a stand in for a much larger collection of syntactic changes, which in aggregate make for a sufficiently improved programming experience. But I haven't seen that argument made. And I would expect if that were the case, there'd be something less trivial that could be the symbolic change- maybe significant white space or something like that.

### Orders of magnitude

Orders of magnitude improvement in any facet, even compilation speed, is never a trivial detail. Quantity impacts quality! If the arguments are about small differences in compilation times, it's trivial. If the arguments are about the orders of magnitude difference between Go and C compile times, it is not trivial - at that point you'll have a significant and visceral impact on programmer experience and productivity.

But, that aside, people will persist in arguing trivialities. I think you'll find that people arguing trivialities on hacker news and redd.it are also consistent in failing to convince anyone to adopt a language. There is at least a subconscious recognition of the triviality in most participants. But people tend to argue where they feel they can contribute, even if only for the trivial.

### not bike shedding

Really, bike shedding is focusing on a trivial aspect of a language when there are more important things to argue about while I'm bringing up the semicolon topic in isolation of other issues, which admittedly would often take priority. However, making semicolons optional in Scala was a big deal with many important consequences. Its a detail to be sure, but a very important detail.

Once we figured out how to eliminate the need for semicolons via clever parsing (talking Scala here, Javascript is much less sophisticated in its semicolon inference), many people thought it was a no brainer to just get rid of them. If they aren't necessary, why should they exist? However, I'm arguing that the extra signals they provide about programmer intent (I meant here to be a statement boundary) as well as an invested reader (ah, the statement boundary is really here) can be very useful, that we lose something and therefore "optional semicolons" must be considered as another tradeoff to be made. Or to put it another way, a minimal syntax is not necessarily an ideal one.

No one is going to bother building a language out of one syntax improvement. Rather, there is a buffet of features to grab on to. In the context of my current research, live programming, I need the compiler to be extremely responsive, I need the compiler to be incredibly robust with respect to transient errors, so having non-optional semicolons might be very useful in that regard.

### Feature Buffet

While semicolons might serve your purpose, I think you could find other features that would serve the same purpose without the visual clutter of semicolons. Syntax can be designed with localizing errors in mind, as can be IDEs.

One useful technique is to build localization rules into your probabilistic, error-robust parser: multiple blank lines indicate progressively lower probability of a relationship. Even without an offsides rule or significant whitespace, this should often be sufficient.

### I would argue that such

I would argue that such techniques are orthogonal and probably composable in their benefits.

### I agree with that.

I agree with that. Unfortunately, such techniques are also composable in their disadvantages. Be careful what you choose.

### Casual Dismissal of Syntax

It sometimes seems like PL folks are all in a hurry to prove how little they care about syntax. This is sometimes a benefit, because we all want to avoid "bikeshedding," but it also speaks to an endemic resistance to actually considering user interface/experience as an aspect of language design.

Syntax is user interface; so are error/diagnostic messages. User interface is never a "triviality" when a human is in the loop.

As a small, concrete example: anybody with even moderate experience using a language that has comma-separated lists will probably have run into a situation where they want to be able to have a "dangling" comma at the end (that is, treat the comma like a terminator rather than a separator). This may be a "triviality" in some respects, but it makes it easier for a programmer to reorder items in the list, or to merge changes in a version-control system, without a lot of tedious busywork.

Making a language with the right underlying concepts, and then failing to think carefully about the interface through which programmers access those concepts strikes me as like building an elegant race car that you can only enter/exit by climbing through the window.

### race car

Strange analogy since most track race cars designs don't have doors that open and the driver enters and exits through either the window or open cockpit. That's done not because of a misstep in user interface design but to improve safety and weight. Which is to say it's a good design for that domain.

To bring this back to ground. racing is often justified as a research bed for technology improvements that might make it into consumer cars. I don't expect anybody will be climbing through the window of their family minivan, but it does seem as least plausible to do research on say engine monitoring technology in a racing domain without worrying about user interface elements like cupholders and doors.

Same deal with language research - not all research needs to deal with every aspect of language design equally.

### Should have said "sports car"

Yeah, not exactly a perfect analogy.

Certainly much research (investigating new "engine" designs) can be done on languages without all the amenities that the average programmer expects. That said, there is also plenty of room for research on the human/social aspects of language design.

For anybody who isn't doing pure research, though, and intends to make languages that programmers actually use, it seems worthwhile to take a measured, pragmatic interest in issues of user interface.

Novices certainly have a tendency to get over-invested in issues of syntax, but that doesn't mean that disinterest in syntax is required for expertise.

The C# language is an interesting example to me. While we may disagree with this or that choice, it is clear that many of their design choices with respect to syntax, scoping, etc. were motivated by actual study of programmer practices. For example, C# has rules related to local variable scoping that are intended to reduce the likelihood of certain errors caused by copy-paste programming.

### Bringing up C#, its also a

Bringing up C#, its also a language where eliminating the need semicolons is pretty straightforward (with the rest of its grammar mostly unchanged, like Scala) but will probably never happen given that the developers they target really value good error messages and consistency in readability.

### Syntax not Dismissed

There are many PL folk who consider syntax very important. John Shutt, William Cook, Sean McDirmid, Jonathan Edwards, and myself are just a few among them.

One of my goals is to unify UX and PX - bringing them together via live programming, reactive semantics, tangible values (or naked objects). I have ideas for programming grammars based on widget composition, and I'm especially interested in set-based or proximity-based composition (similar to traits models in OOP) where the system can auto-wire the components in a predictable manner. The effects of PL semantics on UI - on what is easy, and therefore on what is actually achieved - is deeper than one might expect. I'd like to elevate both PX and UX, e.g. to support programmable UIs, open composition, mashups, cooperative work (externalize state, @unhosted), secure interaction designs (object capability model).

Sean is another who considers UX a very important part of PL design. There seems to be a group of such people gathering (slowly) in the augmented-programming google group.

With this kind of layout:

foo() {
; doThis (
, bar
, baz
)
; thenThat ()
}

### Semicolons can be useful syntax.

They can be useful. Perhaps they aren't absolutely necessary in correct programs in most languages. But they certainly help localize errors in their role as a statement terminator/separator. They enable the compiler to recover from errors so it can report more than one error at a time, and in most languages reduce the ambiguity of intermediate parses so that the compiler can proceed faster.

Those are all services to the programmer and IMO worthwhile design points depending on what you're doing with your language.

You can't say "useless" or "needed" or "trivial" or "significant" without knowing the set of jobs that the language in question is intended to do. If you're doing compiles of million-plus line monolithic operating system kernels for example, the extra speed is no joke.

Unfortunately, even in languages that have separators/terminators for their statements, the error messages produced by popular compilers could definitely be better. Near-useless error messages, it seems, have gotten more common over time rather than less. Few of the lexer-parser generation tools available have a well-thought-out strategy for generating good error messages, and lots of older, revamped, or often-revised languages have a syntax that has grown over time to be very complex with lots of obscure corners.

So, yeah. Potentially useful, I just wish people would more reliably use 'em to their full potential for error reporting.

Ray


text:
Virtual reality moral dilemmas.

VR_dilemma

## Format

A data frame with 68 rows and 4 variables

• id. Dummy identity number for each participant.

• order. The order in which the participants completed the two sessions: "text_first" (0) or "text_second" (1).

• modality. Describes how the moral dilemmas were presented to the participants: either in text format ("text") or in Virtual Reality ("vr").

• score. Proportion of "utilitarian" decisions. In other words, of the 4 decisions, how many affirmative were responses. Range: 0 (all utilitarian) - 1 (none utilitarian).

## Source

https://psyarxiv.com/ry3ap/

## Details

Dataset from a study where participants completed identical moral dilemmas in two different sessions held on separate days: in one session, they read text description of the scenario, while in another session they completed the same scenarios in Virtual Reality (videos: https://www.youtube.com/watch?v=ebdU3HhhYs8). The study investigated if there was a discrepancy between how people judged the same scenarios while reading them in text versus experiencing them in virtual reality.

## Examples

dim(VR_dilemma)
#> $id <dbl> 1, 6, 7, 8, 9, 10, 12, 14, 15, 17, 20, 22, 28, 31, 34, 35,... #>$ order    <chr> "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0"...
#> $modality <chr> "text", "text", "text", "text", "text", "text", "text", "t... #>$ score    <dbl> 0.25, 1.00, 1.00, 1.00, 0.50, 0.75, 1.00, 1.00, 0.75, 0.00...

format: plain


text:
# Tag Info

The terms you are looking for are Major and Minor pressure losses. Which are a misnomer for systems on the scale your are talking about, since "Minor" losses are usually the greater. The pressure drop across any feature of the system (sudden expansion, sudden contraction, a split, a component like a valve) is: $\Delta P = 0.5 k\rho Q^2/A^2$ $\rho$...


text:
# 1-motivic sheaves and the Albanese functor

Ayoub, J; Barbieri-Viale, L (2009). 1-motivic sheaves and the Albanese functor. Journal of Pure and Applied Algebra, 213(5):809-839.

## Abstract

Using sheaf theoretic methods, we define functors View the MathML source and View the MathML source. The functor View the MathML source extends the one in [L. Barbieri-Viale, B. Kahn, On the derived category of 1-motives, I. Prépublication Mathématique de l’IHÉS (M/07/22), June 2007, 144 pages] to non-necessarily geometric motives. These functors are then used to define higher Néron–Severi groups and higher Albanese sheaves.

## Abstract

Using sheaf theoretic methods, we define functors View the MathML source and View the MathML source. The functor View the MathML source extends the one in [L. Barbieri-Viale, B. Kahn, On the derived category of 1-motives, I. Prépublication Mathématique de l’IHÉS (M/07/22), June 2007, 144 pages] to non-necessarily geometric motives. These functors are then used to define higher Néron–Severi groups and higher Albanese sheaves.

## Statistics

### Citations

Dimensions.ai Metrics
9 citations in Web of Science®
8 citations in Scopus®


text:
## Nearest neighbors and vector models – part 2 – algorithms and data structures

This is a blog post rewritten from a presentation at NYC Machine Learning on Sep 17. It covers a library called Annoy that I have built that helps you do nearest neighbor queries in high dimensional spaces. In the first part, I went through some examples of why vector models are useful. In the second part I will be explaining the data structures and algorithms that Annoy uses to do approximate nearest neighbor queries.

Let’s start by going back to our point set. The goal is to find nearest neighbors in this space. Again, I am showing a 2 dimensional point set because computer screens are 2D, but in reality most vector models have much higher dimensionality.

Our goal is to build a data structure that lets us find the nearest points to any query point in sublinear time.

We are going to build a tree that lets us do queries in $\mathcal{O}(\log n)$. This is how Annoy works. In fact, it’s a binary tree where each node is a random split. Let’s start by splitting the space once:

Annoy does this by picking two points randomly and then splitting by the hyperplane equidistant from those two points. The two points are indicated by the gray line and the hyperplane is the thick black line.

Let’s keep splitting each subspace recursively!

A very tiny binary tree is starting to take shape:

We keep splitting again:

… and so on. We keep doing this until there’s at most K items left in each node. At that point it looks something like this (for K=10):

With the corresponding binary tree:

Nice! We end up with a binary tree that partitions the space. The nice thing is that points that are close to each other in the space are more likely to be close to each other in the tree. In other words, if two points are close to each other in the space, it’s unlikely that any hyperplane will cut them apart.

To search for any point in this space, we can traverse the binary tree from the root. Every intermediate node (the small squares in the tree above) defines a hyperplane, so we can figure out what side of the hyperplane we need to go on and that defines if we go down to the left or right child node. Searching for a point can be done in logarithmic time since that is the height of the tree.

Let’s search for the point denoted by the red X in the plot below:

The path down the binary tree looks like this:

We end up with 7 nearest neighbors. Very cool, but this is not great for at least two reasons

1. What if we want more than 7 neighbors?
2. Some of the nearest neighbors are actually outside of this leaf polygon

Trick 1 – use a priority queue

The trick we’re going to use is to go down on both sides of a split if we are “close enough” (which I will quantify in a second). So instead of just going down one path of the binary tree, we will go down a few more:

With the corresponding binary tree:

We can configure the threshold of how far we are willing to go into the “wrong” side of the split. If the threshold is 0, then we will always go on the “correct” side of the split. However if we set the threshold to 0.5 you get the search path above.

The trick here is we can actually use a priority queue to explore nodes sorted by the max distance into the “wrong” side. The nice part is we can search increasingly larger and larger thresholds starting from 0.

Trick 2 – build a forest of trees

The second trick we are going to use is is to construct many trees aka a forest. Each tree is constructed by using a random set of splits. We are going to search down all those trees at the same time:

We can search all trees at the same time using one single priority queue. This has an additional benefit that the search will focus on the trees that are “best” for each query – the splits that are the furthest away from the query point.

Every tree contains all points so when we search many trees we will find some points in multiple trees. If we look at the union of the leaf nodes we get a pretty good neighborhood:

At this point we have nailed it down to a small set of points. Notice so far we have not even computed distances to a single point. Next step is to compute all distances and rank the points:

We then sort all nodes by distance and return the top K nearest neighbors. Nice! And that is how the search algorithm works in Annoy.

Except one thing. In this case it turns out we actually did miss a couple of points outside:

But the A in Annoy stands for approximate and missing a few points is acceptable. Annoy actually has a knob you can tweak (search_k) that lets you trade off performance (time) for accuracy (quality).

The whole idea behind approximate algorithms is that sacrificing a little bit of accuracy can give you enormous performance gains (orders of magnitude). For instance we could return a decent solution where we really only computed the distance for 1% of the points – this is a 100x improvement over exhaustive search.

More trees always help. By adding more trees, you give Annoy more chances to find favorable splits. You generally want to bump it up as high as you can go without running out of memory.

Summary: Annoy’s algorithm

Preprocessing time:

1. Build up a bunch of binary trees. For each tree, split all points recursively by random hyperplanes.

Query time:

1. Insert the root of each tree into the priority queue
2. Until we have search_k candidates, search all the trees using the priority queue
3. Remove duplicate candidates
4. Compute distances to candidates
5. Sort candidates by distance
6. Return the top ones

Feel free to check out _make_tree and _get_all_nns in annoylib.h

That’s it for this post! More is coming from the presentation shorly. Btw, the take a look at the slides, and the check out the code to generate all graphs in this post.

## Nearest neighbor methods and vector models – part 1

This is a blog post rewritten from a presentation at NYC Machine Learning last week. It covers a library called Annoy that I have built that helps you do (approximate) nearest neighbor queries in high dimensional spaces. I will be splitting it into several parts. This first talks about vector models, how to measure similarity, and why nearest neighbor queries are useful.

Nearest neighbors refers to something that is conceptually very simple. For a set of points in some space (possibly many dimensions), we want to find the closest k neighbors quickly.

This turns out to be quite useful for a bunch of different applications. Before we get started on exactly how nearest neighbor methods work, let’s talk a bit about vector models.

Vector models and why nearest neighbors are useful

Vector models are increasingly popular in various applications. They have been used in natural language processing for a long time using things like LDA and PLSA (and even earlier using TF-IDF in raw space). Recently there has been a new generation of models: word2vec, RNN’s, etc.

In collaborative filtering vector models have been among the most popular methods since going back to the Netflix Prize – the winning entry featured a huge ensemble where vector models made up a huge part.

The basic idea is to represent objects in a space where proximity means two items are similar. If we’re using something like word2vec it could look something like this:

In this case similarity between words is determined by the angle between them. apple and banana are close to each other, whereas boat is further.

(As a side note: much has been written about word2vec’s ability to do word analogies in vector space. This is a powerful demonstration of the structure of these vector spaces, but the idea of using vector spaces is old and similarity is arguably much more useful).

In the most basic form, data is already represented as vectors. For an example of this, let’s look at one of the most canonical data sets in machine learning – the MNIST handwritten digits dataset.

Building an image search engine for handwritten digits

The MNIST dataset features 60,000 images of size 28×28. They each feature a handwritten digits in grayscale. One of the most basic ways we can play around with this data set is to smash each 28×28 array into a 784-dimensional vector. There is absolutely no machine learning involved in doing this, but we will get back and introduce cool stuff like neural networks and word2vec later.

Let’s define a distance function in this space. Let’s say the distance between two digits is the squared sum of the pixel differences. This is basically the squared Euclidean distance (i.e. the good old Pythagorean theorem):

This is nice because we can compute the distance of arbitrary digits in the dataset:

This now lets us search for neighbors in this 784-dimensional space. Check out some samples below – the leftmost digit is the seed digit and to the right of it are the ten most similar images using the pixel distance.

You can see that it sort of works. The digits are visually quite similar, although it’s obvious to a human that some of the nearest neighbors are the wrong digit.

This was pretty nice and easy, but this also an approach that doesn’t scale very well. What about larger images? What about color images? And how to we determine similars not just in terms of visual similarity but actually what a human would think of as similar. This simple definition of “distance” leaves a lot of room for improvement.

Dimensionality reduction

A powerful method that works across a wide range of domains is to take high dimensional complex items and project the items down to a compact vector representation.:

1. Do a dimensionality reduction from a large dimensional space to a small dimensional space (10-1000 dimensions)
2. Use similarity in this space instead

Dimensionality reduction is an extremely powerful technique because it lets us take almost any object and translate it to a small convenient vector representation in a space. This space is generally referred to as latent because we don’t necessarily have any prior notion of what the axes are. What we care about is that objects that are similar end up being close to each other. What do we mean with similarity? In a lot of cases we can actually discover that from our data.

So let’s talk about one approach for dimensionality reduction on images: deep convolutional neural networks. I had a side project about a year ago to classify food. It’s a pretty silly application but the eventual goal was to see if you could predict calorie content from pictures, and a side goal was to learn how to use convolutional neural networks. I never ended up using this for anything and wasted way to much money renting GPU instances on AWS, but it was fun.

To train the model, I downloaded 6M pics from Yelp and Foursquare and trained a network quite similar to the one described in this paper using Theano.

The final layer in this model is a 1244-way multi-classification output using softmax so we’re training this in a supervised way. These are words that occurred in the description text, eg. “spicy ramen” for the one above. However the nice thing is we have a “bottleneck” layer just before the final layer – a 128-dimensional vector that gives us exactly what we want.

Using the neural network as an embedding function and using cosine similarity as a metric (this is basically Euclidean distance, but normalize the vectors first) we get some quite cool nearest neighbors:

These similars look pretty reasonable! The top left picture is similar to a bunch of other fries. The second row shows a bunch of different white bowls with Asian food – more impressively they are all in different scales and angles, and pixel by pixel similarity is quite low. The last row shows a bunch of desserts with similar patterns of chocolate sprinkled over it. We’re dealing with a space that can express object features quite well.

So how do we do find similar items? I’m not going to describe dimensionality reduction in great detail – there are a million different ways that you can read about. What I have spent more time thinking about is how to search for neighbors in vector spaces. In fact, finding the neighbors above takes only a few milliseconds per picture, because Annoy is very fast. This is why dimensionality reduction is so extremely useful. At the same time that it’s discovering high level structure in data, it also computes a compact representation of items. This representation makes it easy to compute similarity and search for nearest neighbors.

Vector methods in collaborative filtering

Reducing dimensionality isn’t just useful in computer vision, of course. As mentioned, it’s incredibly useful in natural language processing. At Spotify, we use vector models extensively for collaborative filtering. The idea is to project artists, users, tracks, and other objects into a low dimensional space where similarity can be computed easily and recommendations can be made. This is in fact what powers almost all of the Spotify recommendations – in particular Discover Weekly that was launched recently.

Exhaustive search as a baseline

So how do we find similar items? Before we go into detail about how Annoy works, it’s worth looking at the baseline of doing a brute force exhaustive search. This means iterating over all possible items and computing the distance for each one of them to our query point.

word2vec actually comes with a tool to do exhaustive search. Let’s see how it compares! Using the GoogleNews-vectors-negative300.bin dataset and querying for “chinese river”, it takes about 2 minutes 34 seconds to output this:

• Qiantang_River
• Yangtse
• Yangtze_River
• lake
• rivers
• creek
• Mekong_river
• Xiangjiang_River
• Beas_river
• Minjiang_River

I wrote a similar tool that uses Annoy (available on Github here). The first time you run it, it will precompute a bunch of stuff and can take a lot of time to run. However the second time it runs it will load (mmap) an Annoy index directly from disk into memory. Relying on the magic page cache, this will be very fast. Let’s take it for a spin and search for “chinese river”:

• Yangtse
• Yangtze_River
• rivers
• creek
• Mekong_river
• Huangpu_River
• Ganges
• Thu_Bon
• Yangtze
• Yangtze_river

Amazingly, this ran in 470 milliseconds, probably some of it overhead for loading the Python interpreter etc. This is roughly 300x faster than the exhaustive search provided by word2vec.

Now – some of you probably noticed that the results are marginally different. That’s because the A in Annoy stands for approximate. We are deliberately trading off some accuracy in return for a huge speed improvement. It turns out you can actually control this knob explicitly. Telling Annoy we want to search through 100k nodes (will get back to that later) we get this result in about 2 seconds:

• Qiantang_River
• Yangtse
• Yangtze_River
• lake
• rivers
• creek
• Mekong_river
• Xiangjiang_River
• Beas_river
• Minjiang_River

This is exactly the same as the exhaustive search it turns out – and still about 50x faster.

Other uses of nearest neighbors

Finally just as a fun example of another use, nearest neighbors is useful when you’re dealing with physical spaces too. In an earlier blog post, I was showing this world map of how long it takes to ping IP addresses from my apartment in NYC:

This is a simple application of k-NN (k-nearest neighbors) regression that I’ve written earlier about on this blog. There is no dimensionality reduction involved here – we just deal with 3D coordinates (lat/long projected to the unit sphere).

In the next series, I will go in depth about how Annoy works. Stay tuned!

## Presentations about Spotify music recommendations

A couple of people in my old team have been around talking about how Spotify does music recommendations and put together some quite good presentations.

First one is Neville Li’s presentation about Scala Data Pipelines @ Spotify:

The second one is Chris Johnson’s presentation from RecSys 2015 about Interactive Recommender Systems:

## Antipodes

I was playing around with D3 last night and built a silly visualization of antipodes and how our intuitive understanding of the world sometimes doesn’t make sense. Check out the visualization at bl.ocks.org!

Basically the idea is if you fly from Beijing to Buenos Aires then you can have a layover at any point of the Earth’s surface and it won’t make the trip longer.

## Software Engineers and Automation

Every once in a while when talking to smart people the topic of automation comes up. Technology has made lots of occupations redundant, so what’s next?

What about software engineers? Every year technology replaces parts of what they do. Eventually surely everything must be replaced? I just ran into another one of these arguments: Software Engineers will be obsolete by 2060.

This might be a Lump of Labor Fallacy. Think about how much around us is currently powered by software and how much could be powered by software. The opportunity to apply software is probably 100x larger than what’s currently being used. So why aren’t we using software 100x more? Because software engineers are expensive.

It’s easy to see this if you look back ten years. Say you wanted to build a web shop ten years ago. This was before the cloud, before API’s, good web frameworks etc. Building a web shop was probably 100x more expensive back then. As a result – there were a lot fewer web shops available. Of course, it’s harder to know what latent demand will be unlocked in the next ten years, but there’s always new things coming out that you didn’t realize you needed.

Somewhat counterintuitively, for many goods the latent demand is so big that what happens when the price drops is that the total demand increases. This is called Jevons Paradox after an economist noticed in the 1800s that increased efficiency of coal use lead to an increase in consumption of coal.

The key here is whether technology replaces a job or whether it increases the efficiency of a job. Technology did not increase the output of switchboard operators, so they were replaced. Similarly, technology is not going to make truck drivers 100x as efficient, so they will be replaced by self driving trucks at some point. But technology actually has the opportunity to increase the output of software engineers by another few orders of magnitude. This will unlock a lot of latent demand, and we will need more software engineers, not less.

The other key is of course whether demand is bounded. So if you want to identify which occupations will be automated, I would look for (a) limited latent demand (b) little technical leverage.

Is this rationalization? Maybe!

Also for a good quick read, check out Race Against the Machine by Erik Brynjolfsson and Andrew McAfee.

## coin2dice

Here’s a problem that I used to give to candidates. I stopped using it seriously a long time ago since I don’t believe in puzzles, but I think it’s kind of fun.

1. Let’s say you have a function that simulates a random coin flip. It returns “H” or “T”. This is the only random generator available. How can write a new function that simulates a random dice roll (1…6)?
2. Is there any method that guarantees that the second function returns in finite time?
3. Let’s say you want to do this $n$ times where $n \to \infty$. What’s the most efficient way to do it? Efficient in terms of using the fewest amount of coin flips.

The first part is old, I think. The second and third part are follow up questions that I came up with.

I’ll give you some time to think about it!

Don’t peak!

Did you figure it out?

Solutions

1. There’s a multitude of ways to do this. The easiest way to do it is probably to flip the coin three times and map the outcomes like this: (HHH, 0), (HHT, 1), (HTH, 2), (HTT, 3), (THH, 4), (THT, 5), (TTH, 6), (TTT, 7). If you end up getting HHH or TTT, you flip again.
2. Impossible! If you flip the coin $n$ times then there’s exactly $2^n$ outcomes. But we can’t partition this space evenly into 6 buckets since $3\nmid 2^n$
3. This one is trickier. Think about it in terms of the amount of information you extract. Every coin flip extracts 1 bit, but every dice roll consumes $\log_2 6\approx 2.585$ bits. This is a lower bound – you need at least that many coin flips per dice roll.

Is there a way to achieve that lower bound? Turns out there is: basically encode a long series of coin flip as a binary representation of a number between 0 and 1, then convert it to base 6. This idea resembles Arithmetic coding. Sample code:

Hope you enjoyed geeking out with a math problem this time!

## Benchmark of Approximate Nearest Neighbor libraries

Annoy is a library written by me that supports fast approximate nearest neighbor queries. Say you have a high (1-1000) dimensional space with points in it, and you want to find the nearest neighbors to some point. Annoy gives you a way to do this very quickly. It could be points on a map, but also word vectors in a latent semantic representation or latent item vectors in collaborative filtering.

I’ve made a few optimizations to Annoy lately and I was curious to see how it stacks up against other libraries out there, so I wrote a benchmark suite: ann-benchmarks. It supports any library with a Python interface and I added a bunch of them. It even has Travis integration!

The results so far for Annoy are pretty great. The only method that consistently beats Annoy is SW-graph from nmslib which is about 2-3x faster at the same precision. But Annoy beats both FLANN and KGraph at high precisions (>95%). At lower precisions (<95%) and cosine distance, Annoy is not quite as fast as FLANN and KGraph.

A surprising result was that Panns, Nearpy, and LSHForest all are very low performance. They are roughly 1,000 times slower than the other ones, and even worse, Panns & LSHForest don’t even produce high precision scores. I created an issue in scikit-learn about LSHForest’s performance. Of course, it might be that I did something wrong in the benchmark.

Annoy was actually never built with performance in mind. The killer feature was always to be able to load/unload indexes quickly using mmap – which no other package supports – but it’s fun to see that it’s actually very competitive on performance too. One of the things that made a difference was that I recently changed the interface for Annoy slightly (don’t worry, it’s backwards compatible). There is now a query-time tradeoff knob which lets you vary how many nodes are inspected.

The other factor not covered by the graph above is how hard it is to install most of these libraries. Annoy should compile and run almost anywhere (Linux, Win, OS X) very easily, but the other libraries can be challenging to install. For instance, both kgraph and nmslib depend on GCC-4.8, so they require custom installations. There are scripts to install all libraries in the repo tested with Ubuntu 12.04 and 14.04. For other platforms – good luck!

I might do a talk in September at the NYC Machine Learning meetup about this, we’ll see! Until then, I found this really great presentation by Stefan Savev (with corresponding web site). He claims his own implementation is a bit faster than Annoy! It’s in Scala so I haven’t tested it yet.

## More Luigi alternatives

The workflow engine battle has intensified with some more interesting entries lately! Here are a couple I encountered in the last few days. I love that at least two of them are direct references to Luigi!

Airflow (Blog Post) (GitHub)

Airflow from Airbnb is probably the most interesting one. I’ve only glanced at it, but here are some very superficial notes

• Seems mostly targeted to run raw UNIX commands using a pretty simple syntax with Jinja templates
• Tasks don’t have support for parameters but it seems like you can build tasks dynamically by just putting them in a function
• It seems to be built around daily jobs, meaning dates and backfill by dates is a foundational concept of the package (whereas in Luigi dates are just one out of many different parameters)
• There is a database of task history which is great
• The visualization seems great
• It also supports farming out jobs to other machines. This is something Luigi definitely needs
• It also comes with built-in support for HDFS, S3, MySQL and Postgres, similar to Luigi
• There’s a built-in triggering mechanism (also something Luigi needs)

Mario (Blog post(GitHub)

Mario seems to be a “Luigi in Scala”. It seems extremely simplistic, so it’s probably more conceptual at this point than meant to be full-fledged.

The choice of Scala is interesting. First of all, I think it’s fair to say that the JVM has taken over the data stack. A lot of Luigi’s core concept are really functional in nature and a language like Scala might be a better choice. A cool thing is that the RPC between Luigi clients and the scheduler is actually just a simple REST interface and Luigi’s scheduler could in fact support clients running other languages. Mario doesn’t do this but it’s something I’ve been meaning to explore for a long time.

Ruigi (GitHub)

Ruigi is “Luigi in R”. It follows the same set of conventions but seems to be pretty simple in that it runs everything locally.

Makeflow (Web site)

Seems to be some academic project mostly for publishing papers. What’s up with not using GitHub in 2015? And also having a “download” section with tarballs!

The benefit of Makeflow seems to be support for a bunch of batch systems commonly used in HPC in academia. The dependencies are specified using their own DSL with some simple Makefile-like notation.

Conclusions

So what’s the state of workflow engines at the moment? Allow me to say something provocative just for the sake of it: they all kind of suck. Including Luigi. There is basically so much trial and error when building a workflow engine and everytime I encounter one I just see a bunch of bad design decisions. Same when I look at Luigi. Luigi was the result of a bunch of many iterations and it avoids roughly 100 pitfalls we encountered in earlier attempts, but there are still some parts of the design that can be addressed.

I don’t mean to bash my own open source project here. Open sourcing Luigi has helped a lot of people building awesome stuff and I think it’s better than anything else out there.

I hope with the explosion of workflow engines lately, we will see a convergence of ideas to a second generation of much better, much more scalable, and much easier ones. My dream is that someone combines every god damned workflow engine in the world and write a new one, preferably in some JVM based language like Scala. I sincerely have no idea how that would look like, but I would love to do that some day as a Luigi 2.0!

## 3D in D3

I have spent some time lately with D3. It’s a lot of fun to build interactive graphs. See for instance this demo (will provide a longer writeup soon).

D3 doesn’t have support for 3D but you can do projections into 2D pretty easily. It’s just old school computer graphics. I ended up adding an animated background to this blog based on an experiment. The math is simple.

First, there’s the rotation. Given a bunch of 3D coordinates, how do you rotate them in 3D space? The cleanest way is to define angles $\alpha, \beta, \gamma$ and use them for rotation in the yz-plane, xz-plane, and xy-plane, respectively. Each of them define a rotation matrix. For the xy-plane, we get the rotation matrix $R_{xy}$ (see code):

$R_{xy} = \begin{pmatrix} \cos(\gamma) & -\sin(\gamma) & 0 \\ \sin(\gamma) & \cos(\gamma) & 0 \\ 0 & 0 & 1 \end{pmatrix}$

We get three of these matrices in total: $R_{yz}, R_{xz}, R_{xy}$.

The rotation of any vector $\mathbf{v}$ can now be described as $R_{yz} R_{xz} R_{xy}\mathbf{v}$. The nice thing is we can precompute the product of these matrices $R$ (see code). Math porn:

$R = \begin{pmatrix} 1 & 0 & 0 \\ 0 & \cos(\alpha) & -\sin(\alpha) \\ 0 & \sin(\alpha) & \cos(\alpha) \end{pmatrix} \begin{pmatrix} \cos(\beta) & 0 & \sin(\beta) \\ 0 & 1 & 0 \\ -\sin(\beta) & 0 & \cos(\beta) \end{pmatrix} \begin{pmatrix} \cos(\gamma) & -\sin(\gamma) & 0 \\ \sin(\gamma) & \cos(\gamma) & 0 \\ 0 & 0 & 1 \end{pmatrix}$

Now going forward we can use the matrix $R$ to rotate any vector $\mathbf{v}$ (see code).

The other thing you want to do is to make distant objects look further away. Thinking through proportionalities you can derive a pretty simple equation (see code). $x' = x / (z/d + 1)$, and same for $y$. The constant $d$ is just a hack to scale down the $z$ values.

Not sure whether the 3D animation is cool or just annoying, but I’ll prob keep it for a bit – enjoy!

## The hardest challenge about becoming a manager

Note: this post is full of pseudo-psychology and highly speculative content. Like most fun stuff!

I became a manager back in 2009. Being a developer is fun. You have this very tangible way to measure yourself. Did I deploy something today? How much code did I write today? Did I solve some really cool machine learning problem on paper?

But as 1:1’s and emails and architecture discussions started filling up my day I often walked home with this gnawing feeling of having accomplished nothing. I saw my team build and deploy some really cool stuff, but I had this sort of guilt as if I was pretty useless.

To feel better about myself, I started coding more. But I noticed when I started coding it was like smoking crack. I couldn’t stop doing it. I would come in at 9am thinking about some fun problem, then get completely sucked into it. I would find myself at 9pm drinking Red Bull deep in some highly optimized C++ latent factor model. That felt great until I realized I had missed a bunch of 1:1’s and had 43 unread emails in my inbox.

I think what happens in your brain is you create all these proxies for accomplishments that take years to retrain. I would be incredibly costly if every action was judged in terms of its benefits amortized over your entire life time. Instead, we humans have an ability to invent pretty arbitrary proxies, such as getting high scores on exams, or in my case, write shitloads of code.

Proxies are great because they let you make decisions much quicker. If I have decided that it’s good for me to write code, then I will start doing it, and eventually feel great about it. After a few years of doing something very consciously (programming is good because I can build this cool game and show it to my friends) you build up this great rewards system (kind of like Pavlov’s dogs?) that makes you feel good about it in itself (programming is cool because I feel good when I do it).

The problem is when your ultimate goal changes and your old proxies are still in effect. You rational side might tell you: hey, look at you, you’re team is really happy, they are learning new stuff, and delivering lots of stuff. But still, you have this really weird feeling that you are not getting anything useful done.

This took me literally years to retrain. I remember at some point I saw someone in my team that did something unexpectedly impressive and I got really excited. I got excited because I realized this person had grown tremendously since joining, and presumably some small fraction of it was due to me. With enough exposure finally this starts to be the new proxy for delivering value. Something the irrational side immediately detects and makes you feel a sense of accomplishment about.

Anyway… once an addict, always an addict. I still have relapses and fall back into programming sometimes. In general I’ve noticed it’s extremely hard to balance and try to do 50-50 development and management. Basically one of the sides take over until it’s 90-10. Either you start coding and you fall back to your old crack habits. Or you manage to break out of it, and you go into this opposite mode where you just don’t have the energy to go into the zone.

I don’t know what my conclusion is. Programmers are the most irrational people I know and I think they are really driven by more of a irrational, System 1 kind of thinking, the pattern matching brain. That’s why I think so many super smart people get stuck in habits (I really want to just solve super cool graph algorithm problems!). The most powerful way to make progress is to put your rational System 2 on and constantly remind the other side what’s really making impact and what’s really long term beneficial. It takes a few year, but with enough persistence, your rational self can really train the primitive pattern matching brain to feel a sense of accomplishment in doing almost anything.

Sorry for offending anyone with my drug references!


text:
# Does there exist some sort of classification of horny groups?

It is well known, that any finite group of order $$n$$ is isomorphic to a subgroup of $$S_n$$. Let’s call a finite group $$G$$ horny iff it is not isomorphic to any subgroup of $$S_{|G|-1}$$ . Does there exist some sort of classification of horny groups?

What I currently know:

Any non-trivial horny group has non-trivial center

If the center of a group $$G$$ is trivial, then it acts faithfully by conjugation on $$G \setminus \{e\}$$.

If a horny group is non-trivially decomposed into a direct product of two its subgroups, it is isomorphic to $$C_2 \times C_2$$

One can construct a faithful action of $$H \times K$$ on $$H \cup K$$. It is defined as $$(h, k)h_0 \mapsto hh_0$$ and $$(h, k)h_0 \mapsto kk_0$$ for $$h, h_0 \in H$$, $$k, k_0 \in K$$.

$$|H| + |K| \geq |H||K|$$ iff either one of the groups is trivial, or both of them are isomorphic to $$C_2$$.

$$C_2 \times C_2$$ is the only possible group and indeed is not contained in $$S_3$$.

I also conjecture, that «direct product» in this statement can be replaced with «semidirect product», but do not know how to prove that.

All cyclic $$p$$-groups are horny

If $$p$$ is prime, then $$S_{p^n - 1}$$ does not have an element of order $$p^n$$

$$Q_8$$ is horny

$$S_7$$ does not contain $$Q_8$$ as a subgroup

• According to Jack Schmidt's answer to mathoverflow.net/questions/16858, the only examples are $C_2\times C_2$, cyclic groups of prime power order, and (generalized) quaternion groups. He gives a reference to a paper by D.L Johnson. – Derek Holt Jun 4 at 8:51
• – Arnaud D. Jun 4 at 9:01
• You could have considered another word for the definition. 😂 – MathematicsStudent1122 Jun 4 at 9:06
• Why "horny"?!?! – user1729 Jun 4 at 9:16
• At the risk of being boring, I have seen such groups be called 'incompressible' – Robert Chamberlain Jun 4 at 9:47

• Cyclic group of prime power order $$C_{p^n}$$
• Generalised quaternion $$2$$-group $$\langle x,y|x^{2^n}=1,x^{2^{n-1}}=y^2,x^y=x^{-1}\rangle$$
• the Klein four-group $$C_2\times C_2$$


text:
Showing that $Q_n=D_n+D_{n-1}$

Let $$T_n$$ be the set of permutations of $$\{1,2,\ldots,n\}$$ which do not have $$i$$ immediately followed by $$i+1$$ for $$1\le i\le n-1$$; in other words, let \begin{align} T_n=\{\sigma \in S_n: \sigma(i)+1\ne\sigma(i+1) \text{ for all } 1\le i\le n-1\} . \end{align} Let $$Q_n$$ be the number of elements of $$T_n$$.

Let $$D_n$$ be the number of derangements of $$\{1,2,\ldots,n\}$$.

It is not hard to show algebraically that $$Q_n=D_n+D_{n-1}$$, but I am having difficulty coming up with a combinatorial argument to show why this is true. (I believe there are $$D_{n-1}$$ elements of $$T_n$$ that leave $$n$$ fixed, and $$D_n$$ elements of $$T_n$$ that move $$n$$, but I don't know how to justify this combinatorially.)

• just to be clear, "i followed by i+1" means that $\sigma(i)+1$ is never equal to $sigma(i+1)$, for all $i\leq n-1$ ? – Denis Jul 25 '13 at 0:52
• I'm sorry if my statement of the problem wasn't completely clear, but that's what I meant. (In other words, when you arrange the images of 1,..., n in order, i is never followed by i+1.) – user84413 Jul 26 '13 at 2:10
• It seems that your question has been asked and answered previously. I do have some doubt about Brian Scott's answer, and I've left a comment there requesting clarification, but it may just be a simple misunderstanding on my part. – Will Orrick Sep 10 '13 at 2:42
• @ Will Orrick Thank you for pointing out that my question had been asked previously. I read the answer posted, but I wasn't able to see how to make it work. (For example, it seemed to me that the permutations 1324 and 4132 would both map to the permutation 2314, if I am interpreting the answer correctly.) I like your argument to show that the number of elements of $T_n$ that fix n is equal to $D_{n-1}$, even though it isn't what I originally had in mind. Can you use the same idea to show that the number of elements in $T_n$ which do not fix n is equal to $D_n$? Thanks again. – user84413 Sep 10 '13 at 17:45
• It turns out Persi Diaconis, Steven Evans, and Ron Graham have a recent paper exploring this problem in some depth. (arxiv.org/abs/1308.5459 ) – Kevin P. Costello Oct 14 '13 at 23:53

(Note: this answer does not contain a bijection between the two sets, which is what the OP was originally hoping for, but it does show that the two counting problems are structurally equivalent and therefore have the same answer.)

The belief stated in the last paragraph of your question is correct: we can show that the set $\mathcal{D}_{n-1}$ of derangements of $\{1,2,3,\ldots,n-1\}$ and the set of permutations $\sigma$ of $\{1,2,3,\ldots,n\}$ with the properties

• $\sigma(n)=n$,
• $\sigma(i+1)\ne\sigma(i)+1,$ for $1\le i\le n-1,$

are equinumerous. That is, $\mathcal{D}_{n-1}$ and the set of elements of $T_n$ that fix $n$ have the same size. Call the latter set $\overline{T}_n.$

This result will prove the equation in your title since there is an obvious bijection between the set of elements of $T_n$ that do not fix $n$ and the set $\overline{T}_{n+1}$ of elements of $T_{n+1}$ that do fix $n+1,$ which will then be equinumerous with $\mathcal{D}_n.$

To enumerate $\mathcal{D}_{n-1}$, let $F=S_{n-1}$ be the set of permutations of $1,2,\ldots,n-1.$ Let $F_j$ be the set of elements of $F$ that fix $j,$ that is, elements $\sigma$ such that $\sigma(j)=j.$ In general, let $F_{ijk\ldots}=F_i\cap F_j\cap F_k\cap\ldots$ be the set of elements that fix $i,$ $j,$ $k,\ldots$, that is, elements $\sigma$ such that $\sigma(i)=i,$ $\sigma(j)=j,$ $\sigma(k)=k,\ldots$ Observe that $\lvert F_{i_1i_2\ldots i_k}\rvert=(n-1-k)!$ since only $n-1-k$ elements are free to move. Since the derangements are those elements that fix no element, the principle of inclusion-exclusion gives \begin{aligned}\lvert\mathcal{D}_{n-1}\rvert&=\lvert F\rvert-\sum_{i=1}^{n-1}\lvert F_i\rvert+\sum_{1\le i<j\le n-1}\lvert F_{ij}\rvert-\ldots\\ &=(n-1)!-\binom{n-1}{1}(n-2)!+\binom{n-1}{2}(n-3)!-\ldots\end{aligned}

To enumerate $\overline{T}_n$, let $G$ be the set of permutations of $1,2,\ldots,n$ that fix $n.$ Let $G_i,$ $1\le i\le n-1,$ be the subset of $G$ consisting of elements $\sigma$ such that $\sigma(i+1)=\sigma(i)+1.$ In general, let $G_{ijk\ldots}=G_i\cap G_j\cap G_k\cap\ldots$ be the set of elements of $G$ such that $\sigma(i+1)=\sigma(i)+1,$ $\sigma(j+1)=\sigma(j)+1,$ $\sigma(k+1)=\sigma(k)+1,\ldots$ We claim that, once again, $\lvert G_{i_1i_2\ldots i_k}\rvert=(n-1-k)!.$ This follows by noting that every constraint $\sigma(i_j+1)=\sigma(i_j)+1$ reduces the number of elements that can move independently by $1,$ leaving only $n-1-k$ elements that are free to move. One can imagine element $i$ becoming "glued" to element $i+1,$ so that they must move as a block.

For example, let $n=9$ and consider $G_{12478}.$ Since $8$ must immediately precede $9,$ which is fixed, and $7$ must immediately precede $8,$ which is now fixed as well, the elements $789$ are fixed. At the same time, $2$ must immediately precede $3$ and $1$ must immediately precede $2,$ meaning that the string $123$ can only move as a block. Similarly, the string $45$ can only move as a block. As a consequence the number of permutations in $G_{12478}$ is the number of ways of permuting the "objects" $123,$ $45,$ and $6,$ with the object $789$ fixed in place. So $G_{12478}=3!=(9-1-5)!,$ in agreement with the claim.

Since $\lvert G_{ijk\ldots}\rvert=\lvert F_{ijk\ldots}\rvert$ for all choices of subscripts, the principle of inclusion-exclusion implies that the computation of $\lvert\overline{T}_n\rvert$ is identical to that of $\lvert\mathcal{D}_{n-1}\rvert,$ so that they have the same final value: \begin{aligned}\lvert\overline{T}_n\rvert&=\lvert G\rvert-\sum_{i=1}^{n-1}\lvert G_i\rvert+\sum_{1\le i<j\le n-1}\lvert G_{ij}\rvert-\ldots\\ &=(n-1)!-\binom{n-1}{1}(n-2)!+\binom{n-1}{2}(n-3)!-\ldots\end{aligned}

Let $[a,b]=\{i\in\mathbf{Z}\mid a\le i\le b\}$ and let $[b]=[1,b].$ Let $S_{a,b}$ be the set of permutations of $[a,b]$ and let $S_n$ be the set of permutations of $[n].$ Let $\overline{S}_{a,b}=\{\sigma\in S_{a,b}\mid \sigma(b)=b\}$ be the set of permutations of $[a,b]$ that fix $b.$ Similarly, Let $\overline{S}_n=\{\sigma\in S_n\mid \sigma(n)=n\}$ be the set of permutations of $[n]$ that fix $n.$

The result will follow by exhibiting a bijective mapping $\rho_n:S_n\to\overline{S}_{n+1}$ that has the property that if $\sigma$ is an element of $S_n,$ $\tau$ is the element of $\overline{S}_{n+1}$ given by $\tau=\rho_n(\sigma),$ $f$ is an element of $[n],$ and $e$ is given by $\tau(e)=f,$ then the property $\tau(e+1)=\tau(e)+1=f+1$ holds if and only if $f$ is a fixed point of $\sigma.$

To define $\rho_n$ we introduce some notation. For distinct elements $i_1,\ldots,i_n\in[n]$ let $\langle i_1i_2\ldots i_n\rangle$ denote the element $\sigma\in S_n$ that satisfies $\sigma(j)=i_j$ for $1\le j\le n.$

We use usual cycle notation to represent swaps, which act from the left. So $(35)\langle123456\rangle=\langle125436\rangle,$ and $(23)(35)\langle123456\rangle=\langle135426\rangle.$ Every element of $S_n$ has a unique swap representation $(a_1b_1)(a_2b_2)\ldots(a_kb_k)\langle12\ldots n\rangle$ where $0\le k\le n-1,$ $a_1<a_2<\ldots<a_k,$ and $a_i<b_i$ for all $1\le i\le k.$ For example, $$\langle 326451\rangle=(13)\langle 126453\rangle=(13)(36)\langle 123456\rangle.$$ Observe that $f$ is a fixed point of $\sigma\in S_n$ if and only if $f$ does not appear among the $i_1,\ldots,i_k,j_1,\ldots,j_k$ in the swap representation of $\sigma.$

We define the insertion operator $[ai]:\overline{S}_{a+1,n+1}\to\overline{S}_{a,n+1},$ where $a\in[1,n]$ and $i\in[a,n].$ Let $\tau\in\overline{S}_{a+1,n+1}.$ Then $[ai]\tau$ is defined to be the element of $\overline{S}_{a,n+1}$ obtained by inserting $a$ immediately in front of $i+1.$ So, for example, $[24]\langle3546\rangle=\langle32546\rangle.$ Every element of $\overline{S}_{n+1}$ has a unique insertion representation $[1b_1][2b_2]\ldots[nb_n]\langle (n+1)\rangle,$ where $b_j\ge j$ for all $1\le j\le n.$ For example, \begin{aligned} &\langle 1456237\rangle=[13]\langle 456237\rangle=[13][22]\langle 45637\rangle =[13][22][36]\langle 4567\rangle\\ &=[13][22][36][44]\langle 567\rangle=[13][22][36][44][55]\langle 67\rangle=[13][22][36][44][55][66]\langle 7\rangle. \end{aligned} Observe that $a$ immediately precedes $a+1$ in $\tau\in\overline{S}_{n+1}$ if and only if the only occurrence of $a$ in the insertion representation of $\tau$ is of the form $[aa].$

The bijective mapping $\rho_n:S_n\to\overline{S}_{n+1}$ is now defined as follows. Let $\sigma\in S_n$ and compute the swap representation of $\sigma.$ We may add null swaps of the form $(aa)$ so that the swap representation of $\sigma$ takes the form $(1b_1)(2b_2)\ldots(nb_n)\langle 123\ldots n\rangle,$ where $b_j\ge j$ for all $1\le j\le n.$ Then define $\rho_n(\sigma)$ by replacing swaps with insertions and replacing $\langle 123\ldots n\rangle$ with $\langle (n+1)\rangle:$ $$\rho_n(\sigma)=[1b_1][2b_2]\ldots[nb_n]\langle (n+1)\rangle.$$

Examples: We show $\rho_3:S_3\to\overline{S}_4$ and $\rho_4:S_4\to\overline{S}_5$ explicitly. On the left, dots mark fixed points; on the right, overscores mark sequences of consecutive elements. \begin{aligned} \langle\dot{1}\dot{2}\dot{3}\rangle=(11)(22)(33)\langle123\rangle&\mapsto[11][22][33]\langle4\rangle=\langle\overline{1234}\rangle\\ \langle\dot{1}32\rangle=(11)(23)(33)\langle123\rangle&\mapsto[11][23][33]\langle4\rangle=\langle3\overline{12}4\rangle\\ \langle21\dot{3}\rangle=(12)(22)(33)\langle123\rangle&\mapsto[12][22][33]\langle4\rangle=\langle21\overline{34}\rangle\\ \langle231\rangle=(12)(23)(33)\langle123\rangle&\mapsto[12][23][33]\langle4\rangle=\langle1324\rangle\\ \langle312\rangle=(13)(23)(33)\langle123\rangle&\mapsto[13][23][33]\langle4\rangle=\langle3214\rangle\\ \langle3\dot{2}1\rangle=(13)(22)(33)\langle123\rangle&\mapsto[13][22][33]\langle4\rangle=\langle\overline{23}14\rangle \end{aligned} Observe that the two derangements, $\langle231\rangle$ and $\langle312\rangle,$ have images that contain no sequences of consecutive elements.

\begin{aligned} \langle\dot{1}\dot{2}\dot{3}\dot{4}\rangle=(11)(22)(33)(44)\langle1234\rangle&\mapsto[11][22][33][44]\langle5\rangle=\langle\overline{12345}\rangle\\ \langle\dot{1}\dot{2}43\rangle=(11)(22)(34)(44)\langle1234\rangle&\mapsto[11][22][34][44]\langle5\rangle=\langle4\overline{123}5\rangle\\ \langle\dot{1}32\dot{4}\rangle=(11)(23)(33)(44)\langle1234\rangle&\mapsto[11][23][33][44]\langle5\rangle=\langle3\overline{12}\,\overline{45}\rangle\\ \langle\dot{1}342\rangle=(11)(23)(34)(44)\langle1234\rangle&\mapsto[11][23][34][44]\langle5\rangle=\langle\overline{12}435\rangle\\ \langle\dot{1}423\rangle=(11)(24)(34)(44)\langle1234\rangle&\mapsto[11][24][34][44]\langle5\rangle=\langle43\overline{12}5\rangle\\ \langle\dot{1}4\dot{3}2\rangle=(11)(24)(33)(44)\langle1234\rangle&\mapsto[11][24][33][44]\langle5\rangle=\langle\overline{34}\,\overline{12}5\rangle\\ \langle21\dot{3}\dot{4}\rangle=(12)(22)(33)(44)\langle1234\rangle&\mapsto[12][22][33][44]\langle5\rangle=\langle21\overline{345}\rangle\\ \langle2143\rangle=(12)(22)(34)(44)\langle1234\rangle&\mapsto[12][22][34][44]\langle5\rangle=\langle42135\rangle\\ \langle231\dot{4}\rangle=(12)(23)(33)(44)\langle1234\rangle&\mapsto[12][23][33][44]\langle5\rangle=\langle132\overline{45}\rangle\\ \langle2341\rangle=(12)(23)(34)(44)\langle1234\rangle&\mapsto[12][23][34][44]\langle5\rangle=\langle24135\rangle\\ \langle2413\rangle=(12)(24)(34)(44)\langle1234\rangle&\mapsto[12][24][34][44]\langle5\rangle=\langle41325\rangle\\ \langle24\dot{3}1\rangle=(12)(24)(33)(44)\langle1234\rangle&\mapsto[12][24][33][44]\langle5\rangle=\langle1\overline{34}24\rangle\\ \langle312\dot{4}\rangle=(13)(23)(33)(44)\langle1234\rangle&\mapsto[13][23][33][44]\langle5\rangle=\langle321\overline{45}\rangle\\ \langle3142\rangle=(13)(23)(34)(44)\langle1234\rangle&\mapsto[13][23][34][44]\langle5\rangle=\langle21435\rangle\\ \langle3\dot{2}1\dot{4}\rangle=(13)(22)(33)(44)\langle1234\rangle&\mapsto[13][22][33][44]\langle5\rangle=\langle\overline{23}1\overline{45}\rangle\\ \langle3\dot{2}41\rangle=(13)(22)(34)(44)\langle1234\rangle&\mapsto[13][22][34][44]\langle5\rangle=\langle14\overline{23}5\rangle\\ \langle3412\rangle=(13)(24)(33)(44)\langle1234\rangle&\mapsto[13][24][33][44]\langle5\rangle=\langle31425\rangle\\ \langle3421\rangle=(13)(24)(34)(44)\langle1234\rangle&\mapsto[13][24][34][44]\langle5\rangle=\langle14325\rangle\\ \langle4123\rangle=(14)(24)(34)(44)\langle1234\rangle&\mapsto[14][24][34][44]\langle5\rangle=\langle43215\rangle\\ \langle41\dot{3}2\rangle=(14)(24)(33)(44)\langle1234\rangle&\mapsto[14][24][33][44]\langle5\rangle=\langle\overline{34}215\rangle\\ \langle4\dot{2}13\rangle=(14)(22)(34)(44)\langle1234\rangle&\mapsto[14][22][34][44]\langle5\rangle=\langle4\overline{23}15\rangle\\ \langle4\dot{2}\dot{3}1\rangle=(14)(22)(33)(44)\langle1234\rangle&\mapsto[14][22][33][44]\langle5\rangle=\langle\overline{234}15\rangle\\ \langle4312\rangle=(14)(23)(34)(44)\langle1234\rangle&\mapsto[14][23][34][44]\langle5\rangle=\langle24315\rangle\\ \langle4321\rangle=(14)(23)(33)(44)\langle1234\rangle&\mapsto[14][23][33][44]\langle5\rangle=\langle32415\rangle \end{aligned} Observe that the images of the nine derangements contain no sequences of consecutive elements.

Since there is a one-to-one correspondence between the set of derangements of $[n]$ and the set of permutations of $[n+1]$ that fix $n+1$ and contain no sequences of consecutive elements (we let $\overline{T}_{n+1}$ denote this set), we have $$D_n=\lvert \overline{T}_{n+1}\rvert.$$ But there is an immediate bijection between $\overline{T}_{n+1}$ and $T_n-\overline{T}_n,$ the set of elements of $T_n$ that do not fix $n.$ Therefore $$D_n=\lvert T_n-\overline{T}_n\rvert$$ and $$D_n+D_{n-1}=\lvert T_n-\overline{T}_n\rvert+\lvert \overline{T}_n\rvert=\lvert T_n\rvert.$$

• Thanks - this is a great answer! – user84413 Oct 6 '13 at 16:40
• Very nice indeed, and thank you. – Kevin P. Costello Oct 7 '13 at 17:21

Let $\sigma$ be the circular permutation $i\mapsto i+1$.

Then, you can establish a bijection $D_n\cup D_{n-1}\to T_n$ (I abuse notation for $D_n$ to design the set as well as the cardinal) by mapping any $\tau$ to $\tau\circ\sigma$,where elements of $D_{n-1}$ are naturally extended with $n\mapsto n$. It is straightforward to verify that this is a bijection.

• If I take the derangement 54123 of {1,...,5} and compose it with $\tau$, does that give the permutation 41235 (which is not in $T_n$)? – user84413 Jul 24 '13 at 20:33
• I might have misunderstood your encoding of permutations. I understood "do not have i followed by i+1" as "the image of i is never i+1". I change the answer. (But the image of 54123 was 15234) – Denis Jul 25 '13 at 0:49

EDIT: What's below is actually WRONG, due to multiple issues noted in the comments (the equation taken modulo $n$ leads to situations where a consecutive $n1$ causes problems, and it's not necessarily a bijection.

I think a variant on dkuper's argument can be made to work.

If I understand correctly, the permutations in $Q_n$ are those which satisfy $\sigma(i)+1 \neq \sigma(i+1)$ for $1 \leq i \leq n-1$. Conversely, we can think of $D_n+D_{n-1}$ as consisting of those permutations satisfying $\tau(i) \neq i$ for $1 \leq i \leq n-1$ ($D_n$ corresponds to those permutations with $\tau(n) \neq n$ as well, while $D_{n-1}$ corresponds to fixing $\tau(n)=n$).

This suggests that we construct our bijection in such a way that $\sigma(i)+1=\sigma(i+1)$ if and only if $\tau(i)=i$. The former equation can be rewritten as $i=\sigma^{-1} (\sigma(i+1)-1)$. So if we define our bijection by taking $\sigma$ to the permutation satisfying $$\tau(i)=\sigma^{-1}\left(\sigma(i+1)-1\right),$$ where addition and subtraction are taken modulo $n$, things work the way we want them to.

• Great answer! I'm not sure if in the question the addition is taken modulo, but if it is, it's finally the answer to one of my favourite questions:) – savick01 Sep 9 '13 at 19:40
• This is exactly what I tried at one point, because it looked as if this should work; but I ran into some difficulties. For example, the permutation 4132 (so $\sigma(1)=4, \sigma(2)=1$, etc) in $T_n$ maps to 1423, which is not in $D_4$; and the permutation 2413 maps to 4213, which also is not in $D_4$ (if I am computing these correctly). Also, 3214 maps to 3412, which is not in $D_3$. Maybe some modification of this will work, though, if this doesn't already. – user84413 Sep 9 '13 at 21:07
• There's actually multiple issues here (in addition to the issue you noted where I'm treating $41$ appearing consecutively as bad, $\sigma \rightarrow \tau$ isn't even a bijection!). I'm not sure what the proper etiquette in terms of deletion is, but for now I'm leaving it up with a note explaining what's wrong, and I'll eventually edit the answer if it seems fixable. – Kevin P. Costello Sep 9 '13 at 21:39
• Thanks for your response, and I don't know about the proper etiquette either. I have had to delete some of my answers to problems, since they were totally wrong; but yours is actually a pretty reasonable approach, which hopefully is fixable in some way. – user84413 Sep 9 '13 at 22:52
• @Kevin Costello It was pointed out to me that my question had been asked previously (see above), and the answer that was given before is identical to yours (although written differently). – user84413 Sep 11 '13 at 19:32


text:
Algebra 2 (1st Edition)

Published by McDougal Littell

Chapter 7 Exponential and Logarithmic Functions - 7.2 Graph Exponential Decay Functions - 7.2 Exercises - Mixed Review - Page 491: 43

Answer

The answer is below.

Work Step by Step

We see that there are no restrictions on the inputs of the function, so the domain is all real numbers. This is an exponential growth function, so $y\geq 0$.

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.


text:
## e is irrational

Proving a number is irrational is mostly done by contradiction. So first suppose e is rational: e = p/q where p, q are coprime integers.

We know that q≥2 as e is not an integer (in fact, it’s in between 2 and 3). Then

Note that, as q!e and n are natural numbers, we must have that x is a natural number.

However,

And so we can bound x in the following way

This is a contradiction since q!e must be a natural number, but it is a sum of an integer n plus a non-integer x. Hence, e is irrational.

M x


text:
# Show that $X$ has no mean [duplicate]

$X$ is said to have a Cauchy distribution iff $X$ has a probability distribution of the form:

$$f(x)= \begin{cases} \frac{a}{\pi(ax^2+x^2)} & \text{,x>0} \\ \ \ \ \ 0 & \text {,otherwise} \end{cases}$$ where $a>0$

How can I show that $X$ has no mean?

## marked as duplicate by Did, user147263, Najib Idrissi, Daniel FischerOct 16 '15 at 13:22

Hint: Try to compute it: $\mathbb{E}[X]$ would be equal to $$\int_{(-\infty,\infty)} xf(x) dx$$ Does this integral exist (in a proper sense)? (i.e., is the function $x\mapsto x f(x)$ integrable on $(-\infty,\infty)$?)
In particular, look at what asymptotically $xf(x)$ becomes when $x\to \infty$:$\frac{x}{a^2+x^2} \sim_{x\to\infty} ?$


text:
Volume 395 - 37th International Cosmic Ray Conference (ICRC2021) - DM - Dark Matter
Optical Microlensing by Primordial Black Holes with IACTs
K.J. Pfrang
Full text: pdf
Pre-published on: July 05, 2021
Published on:
Abstract
Primordial black holes (PBHs), hypothesized to be the result of density fluctuations during the early universe, are candidates for dark matter. When microlensing background stars, they cause a transient apparent enhancement of the flux. Measuring these signals with optical telescopes is a powerful method to constrain the PBH abundance in the range of $10^{-10}\,M_{\odot}$ to $10^{1}\,M_{\odot}$. Especially for galactic stars, the finiteness of the sources needs to be taken into account.
For low PBH masses (in this work $\lesssim 10^{-8}\,M_{\odot}$) the average duration of the detectable event decreases with the mass $\langle t_e\rangle \propto M_{\mathrm{PBH}}$.
For $M_{\mathrm{PBH}}\approx 10^{-11}\,M_{\odot}$ we find $\langle t_e\rangle \lesssim\,1 \mathrm{s}$.
For this reason, fast sampling detectors may be required as they could enable the detection of low mass PBHs.
Current limits are set with sampling speeds of 2 minutes to 24 hours in the optical regime. Ground-based Imaging Atmospheric Cherenkov telescopes (IACTs) are optimized to detect the $\sim$ns long optical Cherenkov signals induced by atmospheric air showers.
As shown recently, the very-large mirror area of these instruments provides very high signal to noise ratio for fast optical transients ($\ll 1\,$s) such as asteroid occultations.
We investigate whether optical observations by IACTs can contribute to extending microlensing limits to the unconstrained mass range $M_{\mathrm{PBH}}<10^{-10}M_\odot$. We discuss the limiting factors to perform these searches for each telescope type. We calculate the rate of expected detectable microlensing events in the relevant mass range for the current and next-generation IACTs considering realistic source parameters.
DOI: https://doi.org/10.22323/1.395.0495
How to cite

Metadata are provided both in "article" format (very similar to INSPIRE) as this helps creating very compact bibliographies which can be beneficial to authors and readers, and in "proceeding" format which is more detailed and complete.

Open Access