Going back to trying to make sense of the 1D problem, the number of valid configurations for N people satisfies a[0]=a[1]=a[2]=1, a[n+3]=a[n]+a[n+1]. There are about half a dozen sequences in OEIS with this "tribonacci" rule, with minor differences in offset and initial conditions. Let b[N] be the aggregate number of singletons in all valid N-person configurations. I'm getting a recurrence b[n+3] = a[n] + b[n] + b[n+1]. Now b[0] = 0, b[1] = 1, b[2] = 0, and then the recurrence gives 2, 3, 3, 6, 7, 10, 15, 19 ... The last entry diverges from A121833, but the rule is so simple that I can't believe it's not in OEIS, so I must have miscalculated. Anyway, the wanted expected number of singletons is lim b[n]/a[n]. Peering at the small entries I realize I must have blundered somewhere. Can somebody with more attention to give it please repeat this reasoning but do it correctly? On Wed, Nov 28, 2012 at 3:09 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Good point, but it wasn't intentional -- I was just careless.
So, I should've said "then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand and no two singles are adjacent."
Or, put another way: After giving each pair of adjacent hands an independent ½ probability of holding each other, restrict attention to the configurations having a maximal set of adjacent pairs of gridpoints each connected by the line segment between them, such that no line segment touches another one.
(This almost suggests a way to obtain the results for 1D.)
--Dan
On 2012-11-28, at 11:44 AM, Andy Latto wrote:
On Wed, Nov 28, 2012 at 1:49 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Whether in the 1D or 2D grid case (or for that matter in nD), one way to give this problem well-defined probabilities (that I think is in some sense the most natural way) is to first give each pair of adjacent hands an independent probability of ½ as to whether they or not they hold each other -- and then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand.
That's a different problem, because you're ignoring the second condition of the problem; no two adjacent single people. If you restrict attention to those, you have a formulation equivalent to Allan's, I think, but different from both of mine.
Andy
I'm not sure if this agrees with the probabilities in one of Andy's two methods.
The problem becomes more symmetrical if the 1D case is a circle instead of a line (and in nD a K^n grid on an n-dimensional torus) -- but this won't affect the asymptotic expected fraction of singles.
--Dan
On 2012-11-28, at 6:49 AM, Andy Latto wrote:
On Wed, Nov 28, 2012 at 12:17 AM, Gary Antonick <gantonick@post.harvard.edu> wrote:
Cornell mathematician Steven Strogatz thinks this is an unsolved
problem
but am wondering if there's something being overlooked.
Here's the basic -- and solved -- problem. There's a long line of people standing near each other. They're told to hold hands with someone - either the person to their right or to their left, if available, but not both. The ratio of the resulting singles to all the people in line approaches 1/e^2 as the line increases.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun