User chris taylor - MathOverflow

Generalization of a horse-racing puzzle

2010-12-30T16:48:54Z

A well-known puzzle goes:

"Suppose that you have 25 horses and a racetrack on which you can race up to 5 horses. If the outcome of each race only tells you the relative speeds of the horses in the race, how many races do you need to determine the fastest 3 horses (and what is the strategy)?"

The solution (look away now if you don't want a spoiler) is to arrange the horses into groups of five and race them, labeling the horses $a_1,\dots,a_5$, ..., $e_1,\dots,e_5$ -- for example, the horse in position 3 in the second race gets the label $b_3$.

Then race horses $a_1, b_1, c_1, d_1, e_1$, and relabel the horses so that all those in the same group as the winner of this race get the label $a_j, j=1,\dots,5$ and so on. Finally, race horses $a_2, a_3, b_1, b_2, c_1$ -- the three fastest horses are now $a_1$ and the two fastest from the final race.

The question: Does this strategy generalize to $m$ horses and $n$ tracks where you want to find the fastest $k$ horses?

An elementary problem in Euclidean geometry

2011-04-26T16:07:32Z

This problem was first put to me by Luke Pebody (who did not know the answer at the time) and after some work I am yet to find a proof or counterexample. I would be grateful of any insights.

Call a vector $v$ in $\mathbb{R}^2$ 'short' if it has modulus less than 1. Let $v_1,\dots,v_6$ be short vectors such that $\sum_{i=1}^6 v_i = 0$. Prove that some three of the $v_i$ have a short sum.

Efficient algorithm for finding the minima of a piecewise linear function

2011-04-15T17:12:59Z

Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by

$f(x) = \max_i ( a_i + b_i x )$

We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two lines:

$x = - \frac{a_i - a_j}{b_i - b_j}$

for $b_i\neq b_j$ and there are at most $n(n-1)/2$ such intersections. For large $n$ it may be impractical to manually check all possible points. Does there exist an efficient way of checking only a subset of the points, ideally one which completes in $O(n)$ rather than $O(n^2)$ time?

I'm thinking something along the lines of the simplex method, which moves from corner to corner of a convex set (the relevant set in this case being the area above the curve $f(x)$).

Answer by Chris Taylor for Mathematical "urban legends"

2011-04-13T16:30:31Z

A certain Greek professor, let's call him AF, happened to have attended medical school in the US before becoming a professional mathematician.

He attended a talk by another mathematician, who claimed to have proved in N dimensions a result which AF had struggled to prove for N=2. Disconcerted, he spent the entirety of the talk constructing a counterexample to the speaker's result.

At the end of the talk, when questions were invited, AF walked up to the board and wrote down his counterexample. He turned around as he heard a loud thump from behind him. The speaker had fainted.

Undeterred, AF used his medical training to revive the speaker before returning to his seat.

Answer by Chris Taylor for system of two second order differential equations

2011-04-12T10:55:12Z

It is unlikely that there is an analytic solution but you may be able to make some progress by rewriting as a first-order system. For example, with the equations as in Hans Engler's answer, you can define $w=\dot{u}$ and $z=\dot{v}$, and get a system of equations

$\dot{u} = w$

$\dot{v} = z$

$\dot{w} = \frac{cu + z^2 + (v-du)(1-w^2)}{1-(du-v)(u-v/d)}$

$\dot{z} = \frac{(v/d-u)(cu+z^2) + 1 - w^2}{1-(du-v)(u-v/d)}$

with

$u(0)=\tilde{a}$, $v(0)=w(0)=z(0)=0$.

This looks more complicated than the original set of equations, but you have the advantage that it's first-order and autonomous, and hence amenable to the techniques applicable to first-order autonomous nonlinear dynamical systems, such as linearization about fixed points, analysis of periodic orbits, energy theorems etc.

Answer by Chris Taylor for Computing missing Eigenvectors

2011-04-01T13:01:16Z

Compute the determinant, factor out 0 as a known root and solve for the other two. This question is probably not appropriate for this site, which is aimed towards research-level mathematics - you could try asking at Math Exchange instead.

Card game / options pricing / Brownian bridge question

2011-02-18T18:45:16Z

We play a game. I shuffle a deck of cards and start dealing them face up. After any card you can say "stop", at which point I pay you 1 dollar for every red card dealt and you pay me 1 for every black card dealt. What is your optimal strategy, and how much would you play to pay this game?

Clearly the game is worth at least 0, since you can follow the strategy 'wait until all the cards are dealt' and get paid 0.

We can conclude that at any stage of the game, we will ask for another card if the expected value of continuing to play is greater than the amount of money already won; otherwise we will say stop. Mathematically, if $r$ is the number of red cards remaining and $b$ is the number of black cards remaining, and $f_{r,b}$ is the expected value of the game at this point, then the expected value of taking another card is

$e_{r,b} = \frac{r}{r+b} f_{r-1,b} + \frac{b}{r+b} f_{r,b-1}$

and hence the value of the game at this point, assuming we play the optimal strategy, is

$f_{r,b} = \max ( \frac{r}{r+b} f_{r-1,b} + \frac{b}{r+b} f_{r,b-1}, b-r )$

with $f_{r,0} = 0$ (if there are only red cards remaining, we have a guaranteed payout of 0) and $f_{0,b} = b$ (if there are only black cards remaining we won't take any more cards).

Solving numerically gives an expected value for this game of 2.624 with 52 cards. I'm interested in what the value is for a deck of $2n$ cards, and if the optimal strategy can be expressed analytically as a function of $r$ and $b$ (ie keep taking cards until you have made $g(r,b)$ dollars, then stop).

I've tried changing coordinates to $u=b-r$, $v=b+r$, and I've tried approximating the difference equation as a PDE, but no luck with an analytical solution yet - or even any decent approximations.

The Mystic Rose

2010-12-30T17:03:34Z

Consider $n$ points equally spaced around the unit circle, joined by all possible combinations of lines to make a complete graph. Let $g(n)$ be the number of triangles formed in the resulting diagram.

For example, $g(3) = 1$, $g(4) = 8$, $g(5) = 35$, $g(6) = 110$.

What is the general formula for $g(n)$?

You can see my initial progress on this puzzle here.

Secret Santa (expected no of cycles in a random permutation)

2010-12-21T10:27:10Z

In a Secret Santa game, each of $n$ players puts their name into a hat and then each player picks a name from the hat, who they buy a Christmas present for. Obviously, if someone picks their own name then they put it back and draw again (if they're the only person remaining in the hat then everyone heaves an exasperated sigh, and you start again).

My question: how many loops of present-giving do you expect to see? (e.g. A -> B -> C -> A)

More mathematically: what is the expected number of cycles in a random $n$-permutation which contains no fixed points?

The twelve-fold way doesn't appear to answer this question. Some brief Monte Carlo suggests that the limiting answer as $n\to\infty$ is $c\log n$ for some constant $c\approx 0.95$ (see attached graph, where circles are Monte Carlo approximation, straight line is $\log n$) but I'd like to see an analytical argument for this.

Statistics of a simple Markov chain

2010-12-20T17:16:59Z

Imagine a two-state Markov chain which hops between the states $\pm 1$ with probability $p<1/2$, so that the autocorrelation function after $k$ steps is

$\rho_k = (2p-1)^k$

If I take an exponential moving average of this series with weighting parameter $\lambda$, what does the distribution of values of the new series look like?

Probably the answer is "gaussian, centered on 0" but what is the variance? Is there a known result that makes this computation trivial?

Comment by Chris Taylor

2011-04-17T16:29:28Z

Brian, typically this problem will need to be solved multiple times per second on a rolling basis - so speed is important, but it only needs to be "good enough". If a general purpose LP solver can solve in, say, less than 100ms, that will be well within the bounds of "good enough".

Comment by Chris Taylor

2011-04-17T16:27:34Z

Thanks. I will experiment with this and see how it turns out. Typically I will be considering n ~ 10^6 which may or may not be "extremely large" under your definition!

Comment by Chris Taylor

2011-04-15T11:07:11Z

Have you ever tried reading a mathematics textbook in Greek? It's surprisingly easy.

Comment by Chris Taylor

2011-04-13T11:08:26Z

You can get numerical solutions for a given set of constants by time-stepping using an appropriate numerical scheme (fourth-order Runge-Kutte is popular, and implemented in most numerical mathematics packages, eg Matlab, Scilab, Octave). You can then use a numerical continuation software package (eg AUTO) to explore the solution as the constants vary.

Comment by Chris Taylor

2011-04-01T11:19:45Z

It's nearly trivial if you find the minimum of the square of the length rather than the length (they are related by a monotonic function, hence they have the same minima).

Comment by Chris Taylor

2011-02-02T15:58:18Z

By "relative speed" it was meant that you get a relation $v_1 > v_2 > \cdots > v_5$ after the race, not that you can express the speeds $v_2,\dots,v_5$ as multiples of the speed $v_1$.

Comment by Chris Taylor

2010-12-30T17:28:31Z

Yep - the difficult part is computing the corrections for multiple intersections. But that OEIS link points to some papers which look like they might clear it up (not sure why I didn't think to check OEIS first...)

Comment by Chris Taylor

2010-12-23T14:03:21Z

My history of math professor always took great pains to point out that the Greeks didn't know that \sqrt{n} was irrational for all nonsquare n, because they didn't have a concept of a rational or irrational number. Instead, they knew that certain geometric lengths were incommensurable: for example you can't find A, B so that A diagonals of a square is equivalent to B sides of the same square. Perhaps this is just semantics...

Comment by Chris Taylor

2010-12-22T09:36:25Z

Thanks for your comment John. Rejection sampling was exactly what I was doing. Thankfully 1/e of randomly generated permuations are derangements, so it doesn't take too long.

Comment by Chris Taylor

2010-12-21T10:46:08Z

Thanks Qiaochu. I suspect that with some careful accounting and a few judicious approximations, you can probably turn that argument into one which accounts for the conditioning on the number of 1-cycles, and derive the constant multiplicative factor. I'll have a crack at that if I get some spare time later today.