Search Results

Let me see if I understand the procedure. We have two piles, which I will call the deck and the pile. If KH is not in the pile, we pull three cards off the top of the deck and put them in the pile. If …

One way to calculate the expected number of cycles of length $k$ is by the inclusion-exclusion formula. You can get the set of permuations of length $n$ with no fixed points by taking the set of permu …

What you're doing wrong is stopping when the first matchbox runs out. You have to allow $k=0$ to get the probabilities sum to 1, so you have to stop the simulation the first time an empty matchbox is …

Having screwed up the answer by getting the wrong answer for a really simple calculation the first time, I'm now going to try to redeem myself. First, to make things easier, let each point be present …

You should be able to get $O(\sqrt{n/k})$ by choosing a smaller square of area $1/k$, which will contain one point from most of the point sets, and use the BHH theorem to find a TSP tour of this. Now, …

Here's the answer. The main claims (Claims 1-4) I am fairly sure I got right, but I could easily have missed a case (or counted an extra case) in the later enumeration. If anybody finds a mistake, ple …

Isn't this very much related to the problem of a transversal in a Latin square? Suppose we have an $(n,n)$ bipartite graph with $n$ edge colors, such that every vertex has one edge of each color. This …

The expected degree for the Delaunay triangulation on hyperbolic space will depend on the density of the points. With low enough density points, you should get arbitrarily high degree. You should be a …

Consider an equilateral triangle with altitude 1. It is not hard to show that if you choose a point randomly in this triangle, the distances to the three sides gives the same distribution of lengths t …

Michel Talagrand has a number of open problems (with bounty) listed on his website. I haven't looked at them all, but knowing him, I guarantee you that they are very hard and quite important. These ar …

This is the simple stochastic games problem, but for only one player, and there is a polynomial-time algorithm for it based on linear programming, which is described in Anne Condon's paper "On Algorit …

You can't talk about "the" Gaussian measure on an infinite-dimensional Hilbert space, for the same reason that you can't talk about a uniform probability distribution over all integers. It doesn't exi …