User - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T20:46:00Z http://mathoverflow.net/feeds/user/7234 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32626/how-to-shuffle-a-deck-by-parts/32871#32871 Answer by davidcary for How to shuffle a deck by parts? davidcary 2010-07-22T00:15:16Z 2010-07-22T00:15:16Z <p>Assuming you want a practical answer to "I have too many cards to hold in my hands at once; how do I shuffle them reasonably well in a relatively short amount of time?", you might want to consider a "parallel shuffle", distributing the work over several players in hopes that we can get an adequately shuffled deck in less wall-clock minutes than a single-person shuffle, even if it requires more total operations and player-minutes than a single-person shuffle.</p> <p>I am reminded of the "FFT butterfly diagram" used in digital signal processing and the "Omega Network" used in some computer clusters, based on the "perfect shuffle interconnection".</p> <p><a href="http://www.ece.ucsb.edu/~kastner/ece15b/project1/fft_description_files/image032.jpg" rel="nofollow">http://www.ece.ucsb.edu/~kastner/ece15b/project1/fft_description_files/image032.jpg</a></p> <p><a href="http://github.com/vijendra/Omega-network/raw/master/16X16.png" rel="nofollow">http://github.com/vijendra/Omega-network/raw/master/16X16.png</a></p> <p>Parallel shuffle-deal-shuffle algorithm: (for $k \le n$)</p> <ul> <li>somehow give k players n cards each (either grab a block of n cards off the top for each player, or evenly deal the cards to the k players)</li> <li>shuffle: each of the k players uniformly shuffles their sub-deck of n cards</li> <li>deal: each of the k players evenly deals -- face down -- her sub-deck to the k other players (including herself). Equivalently, each player breaks her sub-deck into k equal sub-sub-decks, and distributes one sub-sub-deck to each player (including herself). After all the players have dealt, each player gathers her cards (a few from each player, including herself) into one sub-deck of n cards.</li> <li>shuffle: (as above)</li> </ul> <p>By this stage (1 round), we have done the equivalent to randomizing each row of a matrix, then each column. Any particular single card could be <em>anywhere</em> after one round of shuffle-deal-shuffle, with equal probability. Alas, at this stage, there are still a few permutations that have probability zero. For example, the possible permutations equivalent to a rotation by shear (RBS) ("how do I rotate a bitmap?") require 3 shears. The closest that a single round of shuffle-deal-shuffle can produce is 2 shears, which is not enough to produce those permutations. So we continue with the second round:</p> <ul> <li>deal: (as above)</li> <li>shuffle: (as above)</li> <li>gather all the sub-decks into one large full deck</li> </ul> <p>The full 2-round shuffle-deal-shuffle-deal-shuffle algorithm can produce any possible permutation, but each permutation does not have exactly the same probability.</p> <p>Each of the two "deal" steps mixes at least as well as a single riffle shuffle of the entire kn cards. The paper -- by Dave Bayer and Persi Diaconis -- that David Speyer mentioned proves that $m = \frac{3}{2} \log_2 (kn) + \theta$ riffle shuffles are sufficient.</p> http://mathoverflow.net/questions/32479/what-are-some-mathematical-sculptures/32596#32596 Answer by davidcary for What are some mathematical sculptures? davidcary 2010-07-20T05:05:01Z 2010-07-20T05:05:01Z <p>I like the <a href="http://www.bathsheba.com/math/" rel="nofollow">4 dimensional mathematical sculptures</a> by Bathsheba Grossman, such as the 24-cell:</p> <p><a href="http://www.bathsheba.com/math/24cell/24cell_new_th.jpg" rel="nofollow">http://www.bathsheba.com/math/24cell/24cell_new_th.jpg</a></p> <p>Are the cryptographic sculptures by Jim Sanborn -- <a href="http://en.wikipedia.org/wiki/Cyrillic_Projector" rel="nofollow">Cyrillic Projector</a>, etc. -- close enough to a "mathematical sculpture"?</p> <p><a href="http://www.ncarts.org/images/afsb_art/workpix/14.jpg" rel="nofollow">http://www.ncarts.org/images/afsb_art/workpix/14.jpg</a></p> http://mathoverflow.net/questions/3428/grid-with-nice-mathematical-properties/30232#30232 Answer by davidcary for Grid with nice mathematical properties davidcary 2010-07-01T20:50:27Z 2010-07-01T20:50:27Z <p>Unfortunately, the sphere is not a "developable surface". This fact has annoyed map-makers for more than a millennium.</p> <p>I find your focus on "cells" fascinating. Most people seem fixated on trying to get points on the globe to correspond with points on a flat image, and don't seem concerned about dividing it up into areas. The simplest way to convert (lat,long) coordinates to standardized areas is the <a href="http://en.wikipedia.org/wiki/Natural_Area_Code" rel="nofollow">"Natural Area Code"</a>, but it has the same problems near the poles as latitude and longitude.</p> <p>Your "too many close grid cells" and "Distance between a cell and a point" criteria reminds me of the "Thomson problem". I suspect you're trying to rule-out map projections like the Gall–Peters projection that, while they do have nice "equal area" properties, end up having a hundred little squares at the top and bottom of the on the map projected to a hundred long, narrow pie-slices that all touch a pole of the globe.</p> <p>Perhaps you could pick one of the known <a href="http://en.wikipedia.org/wiki/Thomson_problem" rel="nofollow">solutions to the "Thomson problem"</a> to build a nice grid. Most of those solutions look similar to a geodesic sphere -- but there are a few exceptions.</p> <p>Perhaps the most famous application for "almost equal" patches is the Cosmic Background Explorer (COBE), which has inspired several mappings:</p> <ul> <li>the <a href="http://en.wikipedia.org/wiki/Quadrilateralized_spherical_cube" rel="nofollow">COBE sky cube</a> (quadrilateralized spherical cube) -- an <a href="http://www.progonos.com/furuti/MapProj/Normal/ProjPoly/projPoly2.html" rel="nofollow">equal-area projection of the sphere onto a cube</a> -- the 6 large squares divide easily into a nice square grid.</li> <li><a href="http://space.mit.edu/home/tegmark/icosahedron.html" rel="nofollow">An icosahedron-based method for pixelizing the celestial sphere</a> -- an equal-area projection of the sphere onto an icosahedron -- the 20 large equilateral triangles divide easily into a nice equilateral triangle grid; or into a nice regular hexagonal grid.</li> <li>the HEALPix projection</li> </ul> <p>The COBE "bins" are, as far as I can tell, a synonym for your "cells".</p> <p>Are those COBE-inspired mappings adequate for you?</p> http://mathoverflow.net/questions/24850/is-there-a-generalisation-of-the-sunflower-spiral-to-higher-dimensions/30142#30142 Answer by davidcary for Is there a generalisation of the "sunflower spiral" to higher dimensions? davidcary 2010-07-01T04:57:15Z 2010-07-01T04:57:15Z <p>One possible way to fill R<sup>3</sup> is to divide up R<sup>3</sup> into onion-layers, and use some sort of "generalized spiral points" to fill each onion-layer -- kind of like winding a string from N pole to S pole to N pole to S pole.</p> <p>In each layer, the spiral starts at the North pole and spirals out something like the "sunflower spiral", eventually crosses the equator. The Southern equator is (more or less) identical to the Northern equator. After the path crosses the equator, it spirals in smaller and tighter curves until it reaches the South pole. The whole spiral is vaguely similar to <a href="http://clowder.net/hop/Riemann/Riemann.html" rel="nofollow">Sphere Spirals by M.C. Escher</a>. This spiral is one solution to the "place n equally-spaced points on a sphere" problem -- it may not be "the best way to pixelize a sphere", it may not be the best solution to the "Thomson problem", but there is no one "best way to pixelize a sphere". Then you move out an onion-layer and start spiralling back from South to north.</p> <p>Going at it from another direction: perhaps somehow number the <a href="http://simplydifferently.org/Polyhedra_Notes?page=7#Waterman%2520Polyhedra" rel="nofollow">spheres used to form Waterman polyhedra</a>? That gives a much more regular and close-packed set of points (sphere centers) -- but it's not obvious to me if there is any nice formula to convert from sphere-number to xyz coordinates.</p>