Tag Archives: mathematics

Banaszczyk’s theorem on convex bodies

Posted on by

I meant to blog about this a while back, but somehow starting a new job/teaching are very time consuming (who knew?). Luckily, it’s about an older result of Banaszczyk (pronounced bah-nahsh-chik, I think):

Wojciech Banaszczyk. Balancing vectors and gaussian measures of n-dimensional convex bodies. Random Structures & Algorithms, 12(4):351–360, 1998.

This result came to my attention from a talk given by Sasho Nikolov here at Rutgers on his paper with Kunal Talwar on approximating hereditary discrepancy (see Kunal’s post from last year). The result is pretty straightforward to state.

Banaszczyk’s Theorem. There exists a universal constant C such that the following holds. Let A = [a_1\ a_2\ \cdots \ a_n] be an m \times n real matrix such that the i-th column a_i satisfies \|a_i\|_2 \le 1 for i = 1, 2, \ldots, n, and let \mathcal{K} be a convex body in \mathbb{R}^m such that \mathbb{P}( G \in K ) \ge 1/2, where G \sim \mathcal{N}(0, I_m). Then there exists a vector x \in \{-1,1\}^n such that Ax \in C \cdot \mathcal{K}.

This is a pretty cool result! Basically, if your convex body \mathcal{K} is big enough to capture half of the probability of a standard Gaussian, then if you blow it up by C to get C \cdot \mathcal{K}, then for any arbitrary collection of sub-unit-norm vectors \{a_i\}, I can find a way to add and subtract them from each other so that the result ends up in C \cdot \mathcal{K}.

I haven’t found a use for this result, but it’s a neat fact to keep in the bucket. Maybe it would be useful in alignment/beamforming schemes? Unfortunately, as far as I can tell he doesn’t tell you how to find this mysterious x, so…

Advertisement

expected time for an optimal game of memory

Posted on by

Via Dan Katz, I learned about a recent problem (warning: JSTOR) from the American Mathematical Monthly (a publication of the Mathematics Association of America, making shaded icosahedrons look cool for almost 100 years):

What to Expect in a Game of Memory
Author(s): Daniel J. Velleman, Gregory S. Warrington
The American Mathematical Monthly, Vol. 120, No. 9 (November), pp. 787-805

The game of memory is played with a deck of n pairs of cards. The cards in each pair are identical. The deck is shuffled and the cards laid face down. A move consists of flipping over first one card and then another. The cards are removed from play if they match. Otherwise, they are flipped back over and the next move commences. A game ends when all pairs have been matched. We determine that, when the game is played optimally, as n \rightarrow \infty
• The expected number of moves is (3 - 2 \ln 2) n + 7/8 - 2 \ln 2 \approx 1.61 n.
• The expected number of times two matching cards are unwittingly flipped over is \ln 2.
• The expected number of flips until two matching cards have been seen is 2^{2n} / \binom{2n}{n} \approx \sqrt{\pi n}.

This is not a competitive game of memory, but the singe player version. It’s a kind of explore-exploit tradeoff with a simple structure — if you know how to exploit, do it. Note that one could do 2 n moves by flipping every card over once (there are 2n cards) to learn all of their identities and then removing all of the pairs one by one. The better strategy is

  1. Remove any known pair.
  2. If no known pair is known, flip a random unknown card and match it if you can.
  3. If the first card is not matchable, flip another random unknown card to learn its value (and remove the pair if it matches.

This strategy exploits optimally when it can and explores optimally when it can’t. The second bullet point in the abstract is the gain from getting lucky, i.e. two randomly drawn cards matching.

The paper is an interesting read, but the arguments are all combinatorial. Since the argument is a limiting one as n \to \infty, I wonder if there is a more “probabilistic” argument (this is perhaps a bit fuzzy) for the results.

Readings

Posted on by

The Wizard of The Crow [N’gugi wa Thiong’o] — This is an epic political farce about an African dictatorship. It’s a bit slow getting into it, but once I was about 70 pages in I was hooked. It’s absolutely hilarious and tragic at the same time. I’ve not read a book like this in a while. Ngugi’s imagination is broad and open, so the absurd situations just keep escalating and mutating. One of the effects is that if you looked at the situation midway through the book, you would ordinarily have no idea how things came to such a state, but thanks to the storytelling you can see the absurd (yet stepwise somewhat reasonable) sequence of events that led there. From now on I will always have the phrase “queueing mania” in my head. Highly recommended.

Proofs and Refutations [Imre Lakatos] — “Why did I not read this book years ago?” I asked myself about a third of the way through this book. Lakatos breaks down the process of mathematical reasoning by example, showing how arguments (and statements) are refined through an alternating process of proof-strategies and counterexamples. It’s a bit of a dry read but it made me more excited about trying to take on some new and meatier theoretical problems. It also made me want to read some Feyerabend, which I am doing now…

The Crown of Embers [Rae Carson] — a continuation of Carson’s YA series set in a sort of pseudo Spanish colonialist fantasy land. It’s hard to parse out the politics of it, but I’m willing to see where the series goes before deciding if it is really subverts the typical racial essentialization that’s typical of fantasy. The colonial aspect of it makes it most problematic.

The Wee Free Men [Terry Pratchett] — a YA Discworld novel. Feels fresher than the other later Pratchett Discworld books.

Equal Rites [Terry Pratchett] — an early Discworld novel. Feels a little thinner than some of the others, but it had some cute moments.

The Republic of Wine [Mo Yan] — Another political farce, this time set in China. This has to be one of the more grotesque and crass novels I have read… maybe ever. The title might be better translated (and Americanized) as “Boozelandia.” The novel is part correspondence between an author (named Mo Yan) and an aspiring writer from the state of “Liquorland,” partly short stories by said aspiring writer, and partly a story about an investigator sent to ascertain whether state officials are raising children to be eaten at fancy dinners. It’s got a kind of gonzo style that will definitely appeal to some. I liked it in the end but I was also totally unaware of what I was getting into when I opened it.

Linkage

Posted on by

A rather pretty video of an L-system made by my friend Steve.

LACMA, which I finally saw with a friend in February, has decided to offer high-resolution downloads of many of the items in its collection. This Ganesha has a pretty impressive belly. Via MeFi.

This may answer David Bowie’s question.

This slideshow makes me want to go to Slurping Turtle again.

Sometimes I wish we could just name p-values something else that is more descriptive. There’s been a fair bit of misunderstanding about them going on lately.

Mo’ math, mo’ solutions

Posted on by

I was in New York on Sunday afternoon and on the suggestion of Steve Severinghaus we took a trip to the brand-new Museum of Mathematics, which is a short walk from the Flatiron building.

The Museum of Mathematics

The Museum of Mathematics


It’s a great little place to take kids — there are quite a few exhibits which illustrate all sorts of mathematics from recreational math and Martin Gardner-esque pastimes like tessellations to an interactive video-floor which draws minimum distance spanning trees between the people standing on it. It apparently does Voronoi tessellations too but it wasn’t in that mode when I was there. There’s also a video wall which makes your body into a tree fractal, games, and a car-racing game based on the brachistochrone problem. The kids were all over that so I just got to watch.

One of the nice things was that there was a touch-screen explanation of each exhibit from which you could get three different “levels” of explanation depending on how much detail you wanted, and also additional information and references in case you wanted to learn more. That’s good because I think it will let parents learn enough to help explain the exhibit to their kids at a level that the parents feel comfortable. That makes it a museum for everyone and not just a museum for math-y parents who want to indoctrinate their children. On the downside, a lot of the exhibits were broken or under repair or under construction, so we really only got to see about 2/3 of the things.

Apparently it’s also a good place to go on a first date, as evidenced by some surreptitious people-watching. So if you’re in New York and want a romantic or educational time (aren’t they the same thing?), go check it out!

Video : “Matrices and their singular values” (1976)

Posted on by

Via Allie Fletcher, here is an awesome video on the SVD from Los Alamos National Lab in 1976:

From the caption by Cleve Moler (who also blogs):

This film about the matrix singular value decomposition was made in 1976 at the Los Alamos National Laboratory. Today the SVD is widely used in scientific and engineering computation, but in 1976 the SVD was relatively unknown. A practical algorithm for its computation had been developed only a few years earlier and the LINPACK project was in the early stages of its implementation. The 3-D computer graphics involved hidden line computations. The computer output was 16mm celluloid film.

The graphics are awesome. Moler blogged about some of the history of the film. Those who are particularly “attentive” may note that the SVD movie seems familiar:

The first Star Trek movie came out in 1979. The producers had asked Los Alamos for computer graphics to run on the displays on the bridge of the Enterprise. They chose our SVD movie to run on the science officer’s display. So, if you look over Spock’s shoulder as the Enterprise enters the nebula in search of Viger, you can glimpse a matrix being diagonalized by Givens transformations and the QR iteration.

Linkage

Posted on by

An animation of integer factorizations. Goes well with music. (h/t BK).

Graphics from the Chicago L (via Chicagoist)

Tony Kushner is kind of a tool. I find this unfortunate. But I still want to see Lincoln.

Aaron Roth reports that the DIMACS tutorial videos have been posted. A perfect time to brush up on your differential privacy!

An analysis of the Thai government’s menu served to President Obama.

A Choose Your Own Adventure version of Hamlet, from the creator of Dinosaur Comics.

The ACME Catalog, for your roadrunner-catching needs.

Linkage

Posted on by

An initiative to prevent irreproducible science.

A video about Graham’s number.

I don’t tweet, but all of this debate seems ridiculous to me. I think the real issue is who follows twitter? I know Sergio is on Twitter, but is anyone else?

Food : An Atlas is a book project on kickstarter by people who do “guerrilla cartography.” It is about food, broadly construed. $25 gets you a copy of the book, and it looks awesome, especially if you like maps. And who doesn’t like maps?

I remember reading about the demise of the American Chestnut tree, but apparently it may make a comeback!

William Thurston on proof and progress

Posted on by

William Thurston passed away a little over a month ago, and while I have never had the occasion to read any of his work, this article of his, entitled “On Proof and Progress in Mathematics” has been reposted, and I think it’s worth a read for those who think about how mathematical knowledge progresses. For those who do theoretical engineering, I think Thurston offers an interesting outside perspective that is a refreshing antidote to the style of research that we do now. His first point is that we should ask the question:

How do mathematicians advance human understanding of mathematics?

I think we could also ask the question in our own fields, and we can do a similar breakdown to what he does in the article : how do we understand information theory, and how is that communicated to others? Lav Varshney had a nice paper (though I can’t seem to find it) about the role of block diagrams as a mode of communicating our models and results to each other — this is a visual way of understanding. By contrast, I find that machine learning papers rarely have block diagrams or schematics to illustrate the geometric intuition behind a proof. Instead, the visual illustrations are plots of experimental results.

Thurston goes through a number of questions that interrogate the motives, methods, and outcomes of mathematical research, but I think it’s relevant for everyone, even non-mathematical researchers. In the end, research is about communication, and understanding the what, how, and why of that is always a valuable exercise.

Juggling, (a)synchrony, and queues

Posted on by

Research often takes twisty little paths, and as the result of a recent attempt to gain understanding about a problem I was trying to understand the difference between the following two systems with k balls and n (ordered) bins:

  1. Synchronous: take all of the top balls in each bin and reassign them randomly and uniformly to the bottoms of the bins.
  2. Asynchronous: pick a random bin, take the top ball in that bin, and reassign it randomly and uniformly to the bottom of a bin.

These processes sound a bit similar, right? The first one is a batch version of the second one. Sort of. We can think of this as modeling customers (balls) in queues (bins) or balls being juggled by n hands (bins).

Each of these processes can be modeled as a Markov chain on the vector of bin occupation numbers. For example, for 3 balls and 3 bins we have configurations that look like (3,0,0) and its permutations, (2,1,0) and its permutations, and (1,1,1) for a total of 10 states. If you look at the two Markov chains, they are different, and it turns out they have different stationary distributions, even. Why is that? The asynchronous chain is reversible and all transitions are symmetric. The synchronous one is not reversible.

One question is if there is a limiting sense in which these are similar — can the synchronous batch-recirculating scheme be approximated by the asynchronous version if we let n or k get very large?