Reply
 
Thread Tools Display Modes
  #1  
Old 11-06-2019, 10:46 AM
brossa is offline
Guest
 
Join Date: Feb 2005
Posts: 1,169

Group self-sorting: a math question


I have a question about the math of self-sorting behavior in groups.

Let's say I have a high school band of 60 kids. All band kids are introverts who only know x number of other kids from their own band - to start with, we'll say that x = 10. I take the band to a band convention in the big city, where they mingle with 29 other bands to form a superband of 1800 kids. At the end of the day, the superband breaks up. A band kid will spot one of the 10 people she knows and move toward that person, who is moving toward one of the 10 people he knows, who is moving toward one of the 10 people she knows, etc. There may be other rules needed which I'm kind of ignoring. But by this process the original 30 bands reform.

I'm curious about the math of this sort of process. Naively, it seems that if x is 60, the bands will easily reform perfectly. If x is 1, there will probably be a some pairs forming that don't know what band they belong to, as well as a distribution of subgroups with up to 60 members. Somewhere in between those extremes is a magic x where, say, half of the bands reform properly. What branch of mathematics addresses this type of situation, and is the magic number closer to 1 or 60?
  #2  
Old 11-06-2019, 11:45 AM
septimus's Avatar
septimus is offline
Guest
 
Join Date: Dec 2009
Location: The Land of Smiles
Posts: 19,964
I think this question is related to percolation theory.
  #3  
Old 11-06-2019, 02:15 PM
md2000 is offline
Guest
 
Join Date: Feb 2009
Posts: 15,161
The other problem is - how do you guarantee that in the band all subsets of 10 (or is it 11?) intersect? At the end of the day, a band of 60 might end up as two separate groups where nobody from group A knows anyone from Group B or vice versa?

Now in a group of 1800, what geographical restriction makes all the sub-groups eventually find each other, you don't end up with half the band by the south entrance and half by the north entrance? Presumably everyone converges to roughly the same point at the end of the day?

Definition of problem needs to be better...

(I.e. with friends=x, group=60 what are the odds of distinct not-overlapping subgroups?)

Last edited by md2000; 11-06-2019 at 02:16 PM.
  #4  
Old 11-06-2019, 02:21 PM
iamthewalrus(:3= is offline
Guest
 
Join Date: Jul 2000
Location: Santa Barbara, CA
Posts: 12,095
Quote:
Originally Posted by brossa View Post
What branch of mathematics addresses this type of situation, and is the magic number closer to 1 or 60?
Assuming that we're not considering any kind of line-of-sight issues, and all band members can see all the people they know (maybe they all have GPS sharing on their phones with their x friends), this is a graph theory/combinatorics problem.

You have a graph with 60 nodes (students) each of which have 10 edges connected (know-relationship). Depending on whether you want the "knows" relationship to be symmetrical (if Alice knows Bob, does Bob know Alice), then the edges may be directional. It sounds like you're thinking it's asymmetric, because if it's symmetric, then n=1 will always leave you with 30 2-person pairs.

Then there's a combinatorics problem: What fraction of such graphs are fully connected. I don't have a neat closed-form solution to this but it'd be easy enough to do a Monte Carlo simulation. WAG: It's way closer to 1 than 60.

Last edited by iamthewalrus(:3=; 11-06-2019 at 02:24 PM.
  #5  
Old 11-06-2019, 02:58 PM
brossa is offline
Guest
 
Join Date: Feb 2005
Posts: 1,169
Let's assume that the 'knows' are random, so if Alice knows Bob, there is an x/60 chance that Bob also knows Alice.

The 1800 students mill around a common area until the group that each person is in contains all the people that that person knows; then each group stops looking for friends and looks for a bus . People do not leave groups once they are in them. Perhaps the group moves toward the closest person not yet in-group that at least one member of the group recognizes.
  #6  
Old 11-06-2019, 04:18 PM
ftg's Avatar
ftg is offline
Member
 
Join Date: Feb 2001
Location: Not the PNW :-(
Posts: 20,506
Quote:
Originally Posted by md2000 View Post
The other problem is - how do you guarantee that in the band all subsets of 10 (or is it 11?) intersect? At the end of the day, a band of 60 might end up as two separate groups where nobody from group A knows anyone from Group B or vice versa?
The good news: This sort of stuff is studied in Ramsey Theory. The bad news: there are problems in this field that are really, really, amazingly, gawd-awful hard. 60 people and subsets of 10? That's very far off the chart of what is known.

And this is a preliminary sub-problem to the OP's question.

So, have a nice day. Ta.
  #7  
Old 11-06-2019, 05:56 PM
iamthewalrus(:3= is offline
Guest
 
Join Date: Jul 2000
Location: Santa Barbara, CA
Posts: 12,095
Quote:
Originally Posted by ftg View Post
The good news: This sort of stuff is studied in Ramsey Theory. The bad news: there are problems in this field that are really, really, amazingly, gawd-awful hard. 60 people and subsets of 10? That's very far off the chart of what is known.

And this is a preliminary sub-problem to the OP's question.

So, have a nice day. Ta.
No, lots of the OP's question isn't nearly that hard. It's trivially easy to answer by the description in your link "Problems in Ramsey theory typically ask a question of the form: "how many elements of some structure must there be to guarantee that a particular property will hold?"" The answer is 30. If each person knows 30 other people, then the band is sure to reform, and if each person knows 29 others, then it might not.

The second claim is easy to show. If persons 1-30 know each other and no one else, and persons 31-60 know each other and no one else, you will get a terminal 2 groups. There's no way to construct such a division if each person knows 30 others.

The specific question the OP asked about how large N has to be for half such bands to reform isn't that hard either, and is easily simulated. The math is left as an exercise to the reader or until I have an hour of free time and the desire to hack something together.

Last edited by iamthewalrus(:3=; 11-06-2019 at 05:57 PM.
  #8  
Old 11-06-2019, 08:09 PM
brossa is offline
Guest
 
Join Date: Feb 2005
Posts: 1,169
I hadn't thought of it in terms of everyone needing, at most, to know just over half of the members of their group in order to self-assemble with 100% reliability. Neat!
  #9  
Old 11-07-2019, 12:51 AM
md2000 is offline
Guest
 
Join Date: Feb 2009
Posts: 15,161
I was thinking about it more along the lines of probability after giving some more thought - if A has a bond with 10 others picked randomly from 60; and each of those has a bond with 10 others, picked randomly... Then B knows A and 9 others (I presume these are 2-way bonds). for each of those 9, there's a 5-in-6 chance that the person is not known to A. This becomes the 6-degrees-of-separation game, where A is Kevin Bacon.

Count bonds, not groups. There are N(N-1)/2 possible bonds in a group. So in 60 people, 60*59/2=1770 bonds. In 30 or less, a max of 30*29/2= 435 bonds. What are the odds when picking a set of bonds for a group of 30 that none of them were picked from the pool of 60? I'm guessing it's in the neighbourhood of 30!/60! off the top of my head. That's a factorial guess if ever there was one.

Yes, if the number of acquaintances was 29, there's what - 60 possible arrangements out of 60! where the band will not congregate. (Coagulate?)
  #10  
Old 11-07-2019, 01:50 PM
brossa is offline
Guest
 
Join Date: Feb 2005
Posts: 1,169
The bonds don't have to be two-way, though: A can know B, with only an x/60 chance of B knowing A in return.

I think that means that there are (N)(N-1) possible one-way bonds in a group if everyone can remember (N-1) bonds.
  #11  
Old 11-07-2019, 05:46 PM
iamthewalrus(:3= is offline
Guest
 
Join Date: Jul 2000
Location: Santa Barbara, CA
Posts: 12,095
Quote:
Originally Posted by md2000 View Post
Count bonds, not groups. There are N(N-1)/2 possible bonds in a group. So in 60 people, 60*59/2=1770 bonds. In 30 or less, a max of 30*29/2= 435 bonds. What are the odds when picking a set of bonds for a group of 30 that none of them were picked from the pool of 60? I'm guessing it's in the neighbourhood of 30!/60! off the top of my head. That's a factorial guess if ever there was one.

Yes, if the number of acquaintances was 29, there's what - 60 possible arrangements out of 60! where the band will not congregate. (Coagulate?)
I think you're massively undercounting here.

There are way more than 60 ways to have a group of 60, each of whom knows 29 others (asymmetrically) not reform. There are 60C30 ways, or approximately 1.2e17 ways to choose 30 people to be in a subgroup from 60.

For those not familiar with nCk, it's read "n choose k" and it is the number of ways to choose k objects from n distinct objects without replacement, and is n!/(k!*(n-k)!).

To know the probability, we have to know how many total ways there are to choose the bonds. There are 60*59=3540 bonds, but we can't just choose 60*29=1740 of them, because that would just make the *average* number of known people be 29, not the exact number for each person.

I believe the correct number here is (59C29)^60. That is, for each of 60 people, choose 29 of their possible 59 bonds. Wolfram Alpha tells me that that's 2e1006.

In general, the number of ways to have n people who know k other is (n-1 choose k)^n. So that's our denominator for a probability calculation.

It feels like that should get us close to a general closed form solution, but I haven't figured out the numerator.
  #12  
Old 11-07-2019, 08:35 PM
brossa is offline
Guest
 
Join Date: Feb 2005
Posts: 1,169
I just spent an hour making graphs of smaller groups in which each person only knew one other, and finding interesting things about closed subgroups vs. groups with 'tails', when I realized that I was assuming that everyone was known by at least one person. So much for that.
  #13  
Old 11-08-2019, 12:29 PM
iamthewalrus(:3= is offline
Guest
 
Join Date: Jul 2000
Location: Santa Barbara, CA
Posts: 12,095
I think it's useful to think about the N=6 K=1 case.

It's the smallest case where you can do more than just split the group into two even fully connected groups to end up with a disjoint group.

The possibilities are:
1. Fully connected 6
2. 2 groups of 3
3. 3 groups of 2
4. A group of 2 and a group of 4.

The total (denominator) possible ways they can be linked is (5C1)^6.

The numerator is (6C3) + (6C2)*[(4C2)+(4C4)]. That is, the number of ways to end up with a disjoint graph is the number of ways to choose 3 people from the 6 + the number of ways to choose 2 people from the six multiplied by the number of ways to do something with the remaining 4 people (either choose all 4 for a group or choose 2 for a group).
  #14  
Old 11-08-2019, 12:34 PM
iamthewalrus(:3= is offline
Guest
 
Join Date: Jul 2000
Location: Santa Barbara, CA
Posts: 12,095
Crap, no, that's not right. You have to then multiply the groups larger than 2 by the number of ways you could distribute the links within that subgroup. Ugh.
  #15  
Old 11-08-2019, 12:52 PM
ftg's Avatar
ftg is offline
Member
 
Join Date: Feb 2001
Location: Not the PNW :-(
Posts: 20,506
Quote:
Originally Posted by iamthewalrus(:3= View Post
I believe the correct number here is (59C29)^60. That is, for each of 60 people, choose 29 of their possible 59 bonds. Wolfram Alpha tells me that that's 2e1006.
FWIW, I consider 280 to be infinity for all practical purposes when it comes to computing. If anything requires that number of: steps, bits, gates, whatever; forget it and work on something else.

Something which is more than the 12th power of that is a Really Big Number.
  #16  
Old 11-08-2019, 01:55 PM
brossa is offline
Guest
 
Join Date: Feb 2005
Posts: 1,169
Yeah, for a group of 3 with k=1, I count eight unique connection patterns, depending on whether there's a 'double bond' somewhere. But for a group of 4, that number shoots way up.
  #17  
Old 11-08-2019, 02:15 PM
brossa is offline
Guest
 
Join Date: Feb 2005
Posts: 1,169
whoops double post

Last edited by brossa; 11-08-2019 at 02:16 PM. Reason: double post
  #18  
Old 11-08-2019, 02:28 PM
iamthewalrus(:3= is offline
Guest
 
Join Date: Jul 2000
Location: Santa Barbara, CA
Posts: 12,095
Quote:
Originally Posted by ftg View Post
FWIW, I consider 280 to be infinity for all practical purposes when it comes to computing. If anything requires that number of: steps, bits, gates, whatever; forget it and work on something else.

Something which is more than the 12th power of that is a Really Big Number.
Yeah, but since we're discussing probability, there's going to be some really big numbers to balance them out.

For N=60, there's going to be some k where the other side of the equation is like 1/3 that ginormous number, so you can't just handwave away numbers as really big in this case. Both numbers are going to be really big, and we want one where their ratio is 1/2

Like, imagine we're playing poker with 9 card hands from a deck with 40 suits with 27 values each. The numbers involved are going to be trans-astronomical, but the odds that you're going to get a hand with 1 pair aren't going to be.
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump


All times are GMT -5. The time now is 03:33 AM.

Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2019, vBulletin Solutions, Inc.

Send questions for Cecil Adams to: cecil@straightdope.com

Send comments about this website to: webmaster@straightdope.com

Terms of Use / Privacy Policy

Advertise on the Straight Dope!
(Your direct line to thousands of the smartest, hippest people on the planet, plus a few total dipsticks.)

Copyright 2019 STM Reader, LLC.

 
Copyright © 2017