User chris taylor - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T19:58:51Z http://mathoverflow.net/feeds/user/11727 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50737/generalization-of-a-horse-racing-puzzle Generalization of a horse-racing puzzle Chris Taylor 2010-12-30T16:48:54Z 2011-05-26T08:03:02Z <p>A well-known puzzle goes:</p> <p>"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)?"</p> <p>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$.</p> <p>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.</p> <p>The question: Does this strategy generalize to $m$ horses and $n$ tracks where you want to find the fastest $k$ horses?</p> http://mathoverflow.net/questions/63056/an-elementary-problem-in-euclidean-geometry An elementary problem in Euclidean geometry Chris Taylor 2011-04-26T16:07:32Z 2011-04-27T05:20:09Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/61839/efficient-algorithm-for-finding-the-minima-of-a-piecewise-linear-function Efficient algorithm for finding the minima of a piecewise linear function Chris Taylor 2011-04-15T17:12:59Z 2011-04-19T15:30:04Z <p>Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by</p> <p>$f(x) = \max_i ( a_i + b_i x )$</p> <p>We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two lines:</p> <p>$x = - \frac{a_i - a_j}{b_i - b_j}$</p> <p>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?</p> <p>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)$).</p> http://mathoverflow.net/questions/53122/mathematical-urban-legends/61562#61562 Answer by Chris Taylor for Mathematical "urban legends" Chris Taylor 2011-04-13T16:30:31Z 2011-04-13T16:30:31Z <p>A certain Greek professor, let's call him AF, happened to have attended medical school in the US before becoming a professional mathematician.</p> <p>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.</p> <p>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.</p> <p>Undeterred, AF used his medical training to revive the speaker before returning to his seat.</p> http://mathoverflow.net/questions/61125/system-of-two-second-order-differential-equations/61384#61384 Answer by Chris Taylor for system of two second order differential equations Chris Taylor 2011-04-12T10:55:12Z 2011-04-12T10:55:12Z <p>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</p> <p>$\dot{u} = w$</p> <p>$\dot{v} = z$</p> <p>$\dot{w} = \frac{cu + z^2 + (v-du)(1-w^2)}{1-(du-v)(u-v/d)}$</p> <p>$\dot{z} = \frac{(v/d-u)(cu+z^2) + 1 - w^2}{1-(du-v)(u-v/d)}$</p> <p>with</p> <p>$u(0)=\tilde{a}$, $v(0)=w(0)=z(0)=0$.</p> <p>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.</p> http://mathoverflow.net/questions/60284/computing-missing-eigenvectors/60287#60287 Answer by Chris Taylor for Computing missing Eigenvectors Chris Taylor 2011-04-01T13:01:16Z 2011-04-01T13:01:16Z <p>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.</p> http://mathoverflow.net/questions/55890/card-game-options-pricing-brownian-bridge-question Card game / options pricing / Brownian bridge question Chris Taylor 2011-02-18T18:45:16Z 2011-02-19T17:11:59Z <p>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?</p> <hr> <p>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.</p> <p>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</p> <p>$e_{r,b} = \frac{r}{r+b} f_{r-1,b} + \frac{b}{r+b} f_{r,b-1}$</p> <p>and hence the value of the game at this point, assuming we play the optimal strategy, is</p> <p>$f_{r,b} = \max ( \frac{r}{r+b} f_{r-1,b} + \frac{b}{r+b} f_{r,b-1}, b-r )$</p> <p>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).</p> <hr> <p>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).</p> <p>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.</p> http://mathoverflow.net/questions/50739/the-mystic-rose The Mystic Rose Chris Taylor 2010-12-30T17:03:34Z 2010-12-30T17:09:20Z <p>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.</p> <p>For example, $g(3) = 1$, $g(4) = 8$, $g(5) = 35$, $g(6) = 110$.</p> <p>What is the general formula for $g(n)$?</p> <p>You can see my initial progress on this puzzle <a href="http://crntaylor.wordpress.com/2010/07/03/why-the-mystic-rose-puzzle-is-hard-part-i/" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/50049/secret-santa-expected-no-of-cycles-in-a-random-permutation Secret Santa (expected no of cycles in a random permutation) Chris Taylor 2010-12-21T10:27:10Z 2010-12-21T22:47:52Z <p>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).</p> <p>My question: how many loops of present-giving do you expect to see? (e.g. A -> B -> C -> A)</p> <p>More mathematically: what is the expected number of cycles in a random $n$-permutation which contains no fixed points?</p> <p>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.</p> <p><img src="http://www.freeimagehosting.net/uploads/330281fbea.png" alt="alt text"></p> http://mathoverflow.net/questions/49979/statistics-of-a-simple-markov-chain Statistics of a simple Markov chain Chris Taylor 2010-12-20T17:16:59Z 2010-12-20T22:34:21Z <p>Imagine a two-state Markov chain which hops between the states $\pm 1$ with probability $p&lt;1/2$, so that the autocorrelation function after $k$ steps is</p> <p>$\rho_k = (2p-1)^k$</p> <p>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?</p> <p>Probably the answer is "gaussian, centered on 0" but what is the variance? Is there a known result that makes this computation trivial?</p> http://mathoverflow.net/questions/61839/efficient-algorithm-for-finding-the-minima-of-a-piecewise-linear-function Comment by Chris Taylor Chris Taylor 2011-04-17T16:29:28Z 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 &quot;good enough&quot;. If a general purpose LP solver can solve in, say, less than 100ms, that will be well within the bounds of &quot;good enough&quot;. http://mathoverflow.net/questions/61839/efficient-algorithm-for-finding-the-minima-of-a-piecewise-linear-function/61853#61853 Comment by Chris Taylor Chris Taylor 2011-04-17T16:27:34Z 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 &quot;extremely large&quot; under your definition! http://mathoverflow.net/questions/53122/mathematical-urban-legends/53125#53125 Comment by Chris Taylor Chris Taylor 2011-04-15T11:07:11Z 2011-04-15T11:07:11Z Have you ever tried reading a mathematics textbook in Greek? It's surprisingly easy. http://mathoverflow.net/questions/61412/new-system-of-two-second-order-differential-equations Comment by Chris Taylor Chris Taylor 2011-04-13T11:08:26Z 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. http://mathoverflow.net/questions/46883/examples-of-using-physical-intuition-to-solve-math-problems/46918#46918 Comment by Chris Taylor Chris Taylor 2011-04-01T11:19:45Z 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). http://mathoverflow.net/questions/50737/generalization-of-a-horse-racing-puzzle/53179#53179 Comment by Chris Taylor Chris Taylor 2011-02-02T15:58:18Z 2011-02-02T15:58:18Z By &quot;relative speed&quot; it was meant that you get a relation $v_1 &gt; v_2 &gt; \cdots &gt; v_5$ after the race, not that you can express the speeds $v_2,\dots,v_5$ as multiples of the speed $v_1$. http://mathoverflow.net/questions/50739/the-mystic-rose/50740#50740 Comment by Chris Taylor Chris Taylor 2010-12-30T17:28:31Z 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...) http://mathoverflow.net/questions/49670/history-of-irrationality-results Comment by Chris Taylor Chris Taylor 2010-12-23T14:03:21Z 2010-12-23T14:03:21Z My history of math professor always took great pains to point out that the Greeks <i>didn't</i> 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... http://mathoverflow.net/questions/50049/secret-santa-expected-no-of-cycles-in-a-random-permutation Comment by Chris Taylor Chris Taylor 2010-12-22T09:36:25Z 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. http://mathoverflow.net/questions/50049/secret-santa-expected-no-of-cycles-in-a-random-permutation/50050#50050 Comment by Chris Taylor Chris Taylor 2010-12-21T10:46:08Z 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.