the Most crowded room --- (expected # of max. Birthday collisions)
94 views
Skip to first unread message
henh...@gmail.com
Sep 14, 2022, 5:42:33 PM9/14/22
to
Have you encountered this number (63.2 %) some time earlier ?
( i may have, but if so, i had forgotten)
and also ..........
What's the formula that gives me the expected # of ppl in the Most crowded room ( 5, 5, 22 below) ?
(is there a Web-page that explains it? ------ i couldn't find it in SE (StackExchange), etc.)
according to the simulations i've done...
100 ppl are randomly assigned to 100 rooms...
---> the Most crowded room is occupied by 5 people. (A)
1000 ppl are randomly assigned to 1000 rooms...
---> the Most crowded room is occupied by 5 people. (B)
10000 ppl are randomly assigned to 1000 rooms...
---> the Most crowded room is occupied by 22 people.
---------------- what are the theoretical values for (A) and (B) ?
Anton Shepelev
Sep 15, 2022, 8:22:51 AM9/15/22
to
Hen Hanna:
> according to the simulations i've done...
>
> 100 ppl are randomly assigned to 100 rooms...
> ---> the Most crowded room is occupied by 5 people. (A)
Your approach as faulty. The number of people in the most
crowded room is a random variable, and only, when the amount
of experiment is infinite can you rely on your simulations.
--
() ascii ribbon campaign - against html e-mail
/\ http://preview.tinyurl.com/qcy6mjc [archived]
> according to the simulations i've done...
>
> 100 ppl are randomly assigned to 100 rooms...
> ---> the Most crowded room is occupied by 5 people. (A)
crowded room is a random variable, and only, when the amount
of experiment is infinite can you rely on your simulations.
--
() ascii ribbon campaign - against html e-mail
/\ http://preview.tinyurl.com/qcy6mjc [archived]
Richard Heathfield
Sep 15, 2022, 8:38:22 AM9/15/22
to
On 15/09/2022 1:22 pm, Anton Shepelev wrote:
> Hen Hanna:
>
>> according to the simulations i've done...
>>
>> 100 ppl are randomly assigned to 100 rooms...
>> ---> the Most crowded room is occupied by 5 people. (A)
>
> Your approach as faulty. The number of people in the most
> crowded room is a random variable, and only, when the amount
> of experiment is infinite can you rely on your simulations.
I did an infinite simulation, which took a while, and it turns
> Hen Hanna:
>
>> according to the simulations i've done...
>>
>> 100 ppl are randomly assigned to 100 rooms...
>> ---> the Most crowded room is occupied by 5 people. (A)
>
> Your approach as faulty. The number of people in the most
> crowded room is a random variable, and only, when the amount
> of experiment is infinite can you rely on your simulations.
out that the actual answer is 6, possibly because in that room
there was a Charlie's Angels box set binge watch in progress.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within
Ilan Mayer
Sep 15, 2022, 12:01:47 PM9/15/22
to
Analytic values for 1-4 rooms:
1 1
2 1.5 (3/2)
3 1.889 (17/9)
4 2.125 (17/8)
Simulation approximate results for 10,100,1000,10000 rooms:
10 2.75
100 4.23
1000 5.52
10000 6.66
Python program for simulation:
#! python
import sys
import random
def process(bins, trials):
average = 0
counts = []
for n in range(bins):
counts.append(0)
random.seed(None)
for n in range(trials):
for m in range(bins):
counts[m] = 0
for m in range(bins):
counts[random.randint(0, bins - 1)] += 1
maximum = 0
for m in range(bins):
if counts[m] > maximum:
maximum = counts[m]
average += maximum
average /= trials
print("Average maximum bin occupation is " + str(average))
if len(sys.argv) == 3:
error = False
try:
bins = int(sys.argv[1])
trials = int(sys.argv[2])
except ValueError:
print("Number of bins and number of trials must be integers")
error = True
if not error and (bins <= 1 or trials <= 0):
if bins <= 1:
print("Number of bins must be greater than 1")
else:
print("Number of trials must be greater than 0")
error = True
if not error:
try:
process(bins, trials)
except KeyboardInterrupt:
print("Cancelled")
else:
print("Usage: RandomDrop <number-of-bins> <number-of-trials>")
Please reply to ilanlmayer at gmail dot com
__/\__
\ /
__/\\ //\__ Ilan Mayer
\ /
/__ __\ Toronto, Canada
/__ __\
||
henh...@gmail.com
Sep 15, 2022, 9:15:35 PM9/15/22
to
On Thursday, September 15, 2022 at 9:01:47 AM UTC-7, Ilan Mayer wrote:
> On Wednesday, September 14, 2022 at 5:42:33 PM UTC-4, henh...@gmail.com wrote:
> > Have you encountered this number (63.2 %) some time earlier ? ( i may have, but if so, i had forgotten)
100 ppl in 100 (random) rooms --> ~ 63.2 rooms get occupied
> On Wednesday, September 14, 2022 at 5:42:33 PM UTC-4, henh...@gmail.com wrote:
> > Have you encountered this number (63.2 %) some time earlier ? ( i may have, but if so, i had forgotten)
> >
> > and also ..........
> >
> >
> > What's the formula that gives me the expected # of ppl in the Most crowded room ( 5, 5, 22 below) ?
> >
> >
> > (is there a Web-page that explains it? ------ i couldn't find it in SE (StackExchange), etc.)
> >
> >
> >
> > according to the simulations i've done...
> >
> > 100 ppl are randomly assigned to 100 rooms...
> > ---> the Most crowded room is occupied by 5 people. (A)
> >
> > 1000 ppl are randomly assigned to 1000 rooms...
> > ---> the Most crowded room is occupied by 5 people. (B)
> >
> > 10000 ppl are randomly assigned to 1000 rooms...
> > ---> the Most crowded room is occupied by 22 people.
> >
> >
> > ---------------- what are the theoretical values for (A) and (B) ?
> 22 above seems to be wrong.
>
> Analytic values for 1-4 rooms:
> 2 --- 1.5 (3/2)
> 3 --- 1.889 (17/9)
> 4 --- 2.125 (17/8)
6 --------------- 2.408179012345679
8 -------------- 2.5972328186035156
10 ------------- 2.74868911 (exact number) ----------- a very close match with what you got !
henh...@gmail.com
Sep 16, 2022, 1:36:06 PM9/16/22
to
On Thursday, September 15, 2022 at 9:01:47 AM UTC-7, Ilan Mayer wrote:
in my Python code, i was stuck with the idea that i had to use a Dictionary to do the counting (tallying up).
This (what i was doing) must be a much, MUCH slower way to do it.
dic= { }
for digit in Lis:
if (digit in dic): dic[ digit ] += 1
else: dic[ digit ] = 1
MaxVal = max(dic.values())
---------- Also, it must be a bit faster to initialize the Dictionary to all 0's in the beginning.
__________________________________________
> py RanDrop.py 100 100
Average maximum bin occupation is 4
> py RanDrop.py 1000 1000
Average maximum bin occupation is 5
At first i was getting only integer results (as above), and i had to insert one line
(apparently, to convert the int into a Floating Point number). ( i dn't really get it)
average *= 1.0 <----------------- (i inserted this line.)
henh...@gmail.com
Sep 16, 2022, 1:54:30 PM9/16/22
to
On Thursday, September 15, 2022 at 6:15:35 PM UTC-7, henh...@gmail.com wrote:
> On Thursday, September 15, 2022 at 9:01:47 AM UTC-7, Ilan Mayer wrote:
> > On Wednesday, September 14, 2022 at 5:42:33 PM UTC-4, henh...@gmail.com wrote:
> > > Have you encountered this number (63.2 %) some time earlier ? ( i may have, but if so, i had forgotten)
---------- 100 ppl in 100 (random) rooms --> ~ 63.2 rooms get occupied
> On Thursday, September 15, 2022 at 9:01:47 AM UTC-7, Ilan Mayer wrote:
> > On Wednesday, September 14, 2022 at 5:42:33 PM UTC-4, henh...@gmail.com wrote:
> > > Have you encountered this number (63.2 %) some time earlier ? ( i may have, but if so, i had forgotten)
> > > and also ..........
> > >
> > >
> > > What's the formula that gives me the expected # of ppl in the Most crowded room ( 5, 5, 22 below) ?
> > >
> > >
> > > (is there a Web-page that explains it? ------ i couldn't find it in SE (StackExchange), etc.)
> > >
> > >
> > >
> > > according to the simulations i've done...
> > >
> > > 100 ppl are randomly assigned to 100 rooms...
> > > ---> the Most crowded room is occupied by 5 people. (A)
> > >
> > > 1000 ppl are randomly assigned to 1000 rooms...
> > > ---> the Most crowded room is occupied by 5 people. (B)
> > >
> > > 10000 ppl are randomly assigned to 1000 rooms...
> > > ---> the Most crowded room is occupied by 22 people.
> > >
> > >
> > > ---------------- what are the theoretical values for (A) and (B) ?
>
>
> > 22 above seems to be wrong.
i inserted two characters [*10] into your program, to find :
Crowded\iMayer> py RanDrop10.py 1000 100
Average maximum bin occupation is 21.56
Crowded\iMayer> py RanDrop10.py 1000 200
Average maximum bin occupation is 21.615
Crowded\iMayer> py RanDrop10.py 1000 400
Average maximum bin occupation is 21.6375
Crowded\iMayer> py RanDrop10.py 1000 1000
Average maximum bin occupation is 21.616
Jonathan Dushoff
Sep 16, 2022, 3:16:35 PM9/16/22
to
0.632 is 1 - e^-1, and it shows up everywhere. For example, it's the proportion of rooms that will be occupied if you randomly drop a large number of people into the same number of rooms.
Jonathan
Jonathan
duncan smith
Sep 17, 2022, 12:33:32 PM9/17/22
to
from collections import defaultdict
cntr = defaultdict(int)
cntr[6] += 1
cntr[6] += 1
cntr[6]
2
cntr[1]
0
and initialise it to use the float type if you want (I wouldn't as it's
more natural for counts to be integer valued).
cntr = defaultdict(float)
cntr[6] += 1
cntr[6] += 1
cntr[6]
2.0
cntr[1]
0.0
Or there is (in sufficiently recent versions of Python) the Counter
class for counters.
from collections import Counter
cntr = Counter()
cntr[6] += 1
cntr[6] += 1
cntr[6]
2
cntr[1]
0
This also has a most_common method.
cntr[8] = 1
cntr
Counter({6: 2, 8: 1})
cntr.most_common(n=1)
[(6, 2)]
The random module has a choices function for sampling with replacement.
import random
random.choices(range(10), k=10)
[4, 6, 3, 2, 8, 7, 8, 8, 7, 0]
You could combine the above into a one-liner for sampling and finding
the maximum count.
Counter(random.choices(range(10), k=10)).most_common(n=1)[0][1]
2
Counter(random.choices(range(10), k=10)).most_common(n=1)[0][1]
3
Counter(random.choices(range(10), k=10)).most_common(n=1)[0][1]
2
total = 0
for _ in range(10000):
total += Counter(random.choices(range(10),
k=10)).most_common(n=1)[0][1]
total / 10000
2.7497
You must be using Python2 to get integer division by default. So it's
probably time to install Python3. Cheers.
Duncan
duncan smith
Sep 17, 2022, 12:36:53 PM9/17/22
to
I didn't mean integer valued, I meant of type int.
Duncan
henh...@gmail.com
Sep 18, 2022, 11:34:08 AM9/18/22
to
i guess you never (?) use [type declarations] (on variables) in Python (3)
....................
>>> Can you declare a type in Python? -- Python is completely object oriented, and not "statically typed". You do not need to declare variables before using them, or declare their type. Every variable in Python is an object.
___________________________
re: the Most crowded room --- (expected # of max. Birthday collisions)
another, similar topic would be... if all the games in NFL, NBA, MLB... were like a (fair) coin-toss, what is the theoretical , expected Longest winning (and losing) streaks every year (for one team, for all the teams)
------------------ vs. What we actually get.
Can the actual stats be simulated if we assume (model) that the strongest (riches) teams (Yankees, Red Sox...) are likely to win any game by , say, 60 % probability ?
Ilan Mayer
Sep 18, 2022, 4:00:53 PM9/18/22
to
1000 balls, 100 bins, 1000 trials - 18.76
1000 balls, 200 bins, 1000 trials - 12.15
1000 balls, 400 bins, 1000 trials - 8.28
1000 balls, 1000 bins, 1000 trials - 5.50
Intuitively the number should decrease as the number of bins (rooms) increases for the same number of balls (people).
Here is a revised version of my program that allows any number of balls/bins (or people/rooms):
#! python
import sys
import random
average = 0
counts = []
for n in range(bins):
counts.append(0)
random.seed(None)
for n in range(trials):
for m in range(bins):
counts[m] = 0
for m in range(balls):
counts = []
for n in range(bins):
counts.append(0)
random.seed(None)
for n in range(trials):
for m in range(bins):
counts[m] = 0
counts[random.randint(0, bins - 1)] += 1
maximum = 0
for m in range(bins):
if counts[m] > maximum:
maximum = counts[m]
average += maximum
average /= trials
print("Average maximum bin occupation is " + str(average))
if len(sys.argv) == 4:
maximum = 0
for m in range(bins):
if counts[m] > maximum:
maximum = counts[m]
average += maximum
average /= trials
print("Average maximum bin occupation is " + str(average))
error = False
try:
balls = int(sys.argv[1])
bins = int(sys.argv[2])
trials = int(sys.argv[3])
except ValueError:
print("Numbers of balls, bins and trials must be integers")
error = True
if not error and (balls <= 0 or bins <= 0 or trials <= 0):
if balls <= 1:
print("Number of balls must be greater than 0")
elif bins <= 1:
print("Number of bins must be greater than 0")
else:
print("Number of trials must be greater than 0")
error = True
if not error:
try:
process(balls, bins, trials)
print("Number of trials must be greater than 0")
error = True
if not error:
try:
except KeyboardInterrupt:
print("Cancelled")
else:
print("Usage: RandomDrop <number-of-balls> <number-of-bins> <number-of-trials>")
print("Cancelled")
else:
Ilan Mayer
Sep 18, 2022, 4:10:42 PM9/18/22
to
On Wednesday, September 14, 2022 at 5:42:33 PM UTC-4, henh...@gmail.com wrote:
Ilan Mayer
Sep 18, 2022, 4:15:35 PM9/18/22
to
On Thursday, September 15, 2022 at 9:15:35 PM UTC-4, henh...@gmail.com wrote:
> On Thursday, September 15, 2022 at 9:01:47 AM UTC-7, Ilan Mayer wrote:
> > On Wednesday, September 14, 2022 at 5:42:33 PM UTC-4, henh...@gmail.com wrote:
> > > Have you encountered this number (63.2 %) some time earlier ? ( i may have, but if so, i had forgotten)
> 100 ppl in 100 (random) rooms --> ~ 63.2 rooms get occupied
> > >
> > > and also ..........
> > >
> > >
> > > What's the formula that gives me the expected # of ppl in the Most crowded room ( 5, 5, 22 below) ?
> > >
> > >
> > > (is there a Web-page that explains it? ------ i couldn't find it in SE (StackExchange), etc.)
> > >
> > >
> > >
> > > according to the simulations i've done...
> > >
> > > 100 ppl are randomly assigned to 100 rooms...
> > > ---> the Most crowded room is occupied by 5 people. (A)
> > >
> > > 1000 ppl are randomly assigned to 1000 rooms...
> > > ---> the Most crowded room is occupied by 5 people. (B)
> > >
> > > 10000 ppl are randomly assigned to 1000 rooms...
> > > ---> the Most crowded room is occupied by 22 people.
> > >
> > >
> > > ---------------- what are the theoretical values for (A) and (B) ?
>
>
> > 22 above seems to be wrong.
> really ? waht do you propose ?
Sorry, I misread as 10000 people / 10000 rooms. For 10000 people / 1000 rooms 22 is in agreement with my results.
> On Thursday, September 15, 2022 at 9:01:47 AM UTC-7, Ilan Mayer wrote:
> > On Wednesday, September 14, 2022 at 5:42:33 PM UTC-4, henh...@gmail.com wrote:
> > > Have you encountered this number (63.2 %) some time earlier ? ( i may have, but if so, i had forgotten)
> 100 ppl in 100 (random) rooms --> ~ 63.2 rooms get occupied
> > >
> > > and also ..........
> > >
> > >
> > > What's the formula that gives me the expected # of ppl in the Most crowded room ( 5, 5, 22 below) ?
> > >
> > >
> > > (is there a Web-page that explains it? ------ i couldn't find it in SE (StackExchange), etc.)
> > >
> > >
> > >
> > > according to the simulations i've done...
> > >
> > > 100 ppl are randomly assigned to 100 rooms...
> > > ---> the Most crowded room is occupied by 5 people. (A)
> > >
> > > 1000 ppl are randomly assigned to 1000 rooms...
> > > ---> the Most crowded room is occupied by 5 people. (B)
> > >
> > > 10000 ppl are randomly assigned to 1000 rooms...
> > > ---> the Most crowded room is occupied by 22 people.
> > >
> > >
> > > ---------------- what are the theoretical values for (A) and (B) ?
>
>
> > 22 above seems to be wrong.
> really ? waht do you propose ?
henh...@gmail.com
Sep 18, 2022, 4:38:02 PM9/18/22
to
Less than 10 min. would be impressive , but it depends on how fast the PC is
i don't think i can do 1000 people / 1000+ rooms on my slow home PC
> > 1000 ppl are randomly assigned to 1000 rooms...
> > ---> the Most crowded room is occupied by 5 people. (B)
( seems too formal )
Ilan Mayer
Sep 18, 2022, 5:00:19 PM9/18/22
to
On Sunday, September 18, 2022 at 4:38:02 PM UTC-4, henh...@gmail.com wrote:
> On Sunday, September 18, 2022 at 1:10:42 PM UTC-7, Ilan Mayer wrote:
> > On Wednesday, September 14, 2022 at 5:42:33 PM UTC-4, henh...@gmail.com wrote:
> > > Have you encountered this number (63.2 %) some time earlier ?
> > > ( i may have, but if so, i had forgotten)
> > >
> > >
> > >
> > > and also ..........
> > >
> > >
> > > What's the formula that gives me the expected # of ppl in the Most crowded room ( 5, 5, 22 below) ?
> > >
> > >
> > > (is there a Web-page that explains it? ------ i couldn't find it in SE (StackExchange), etc.)
> > >
> > >
> > >
> > > according to the simulations i've done...
> > >
> > > 100 ppl are randomly assigned to 100 rooms...
> > > ---> the Most crowded room is occupied by 5 people. (A)
> > >
> > > 1000 ppl are randomly assigned to 1000 rooms...
> > > ---> the Most crowded room is occupied by 5 people. (B)
> > >
> > > 10000 ppl are randomly assigned to 1000 rooms...
> > > ---> the Most crowded room is occupied by 22 people.
> > >
> > >
> > > ---------------- what are the theoretical values for (A) and (B) ?
>
>
>
> > The exact number for 100 people / 100 rooms is 4.23259523879579 (found by a C# program).
> How long is (was) the execution (run-time) for that program?
>
> Less than 10 min. would be impressive , but it depends on how fast the PC is
>
>
It took about 8 minutes on a rather old laptop.
> On Sunday, September 18, 2022 at 1:10:42 PM UTC-7, Ilan Mayer wrote:
> > On Wednesday, September 14, 2022 at 5:42:33 PM UTC-4, henh...@gmail.com wrote:
> > > Have you encountered this number (63.2 %) some time earlier ?
> > > ( i may have, but if so, i had forgotten)
> > >
> > >
> > >
> > > and also ..........
> > >
> > >
> > > What's the formula that gives me the expected # of ppl in the Most crowded room ( 5, 5, 22 below) ?
> > >
> > >
> > > (is there a Web-page that explains it? ------ i couldn't find it in SE (StackExchange), etc.)
> > >
> > >
> > >
> > > according to the simulations i've done...
> > >
> > > 100 ppl are randomly assigned to 100 rooms...
> > > ---> the Most crowded room is occupied by 5 people. (A)
> > >
> > > 1000 ppl are randomly assigned to 1000 rooms...
> > > ---> the Most crowded room is occupied by 5 people. (B)
> > >
> > > 10000 ppl are randomly assigned to 1000 rooms...
> > > ---> the Most crowded room is occupied by 22 people.
> > >
> > >
> > > ---------------- what are the theoretical values for (A) and (B) ?
>
>
>
> > The exact number for 100 people / 100 rooms is 4.23259523879579 (found by a C# program).
> How long is (was) the execution (run-time) for that program?
>
> Less than 10 min. would be impressive , but it depends on how fast the PC is
>
>
The time grows exponentially with the number of people/rooms, so for 1000/1000 it is not going to be feasible even on the fastest pc.
henh...@gmail.com
Sep 19, 2022, 1:09:24 PM9/19/22
to
On Sunday, September 18, 2022 at 2:00:19 PM UTC-7, Ilan Mayer wrote:
> On Sunday, September 18, 2022 at 4:38:02 PM UTC-4, henh...@gmail.com wrote:
> > On Sunday, September 18, 2022 at 1:10:42 PM UTC-7, Ilan Mayer wrote:
> > > On Wednesday, September 14, 2022 at 5:42:33 PM UTC-4, henh...@gmail.com wrote:
> > > > Have you encountered this number (63.2 %) some time earlier ?
> > > > ( i may have, but if so, i had forgotten)
> > > >
> > > >
> > > >
> > > > and also ..........
> > > >
> > > >
> > > > What's the formula that gives me the expected # of ppl in the Most crowded room ( 5, 5, 22 below) ?
> > > >
> > > >
> > > > (is there a Web-page that explains it? ------ i couldn't find it in SE (StackExchange), etc.)
> > > >
> > > >
> > > >
> > > > according to the simulations i've done...
> > > >
> > > > 100 ppl are randomly assigned to 100 rooms...
> > > > ---> the Most crowded room is occupied by 5 people. (A)
> > > >
> > > > 1000 ppl are randomly assigned to 1000 rooms...
> > > > ---> the Most crowded room is occupied by 5 people. (B)
> > > >
> > > > 10000 ppl are randomly assigned to 1000 rooms...
> > > > ---> the Most crowded room is occupied by 22 people.
> > > >
> > > >
> > > > ---------------- what are the theoretical values for (A) and (B) ?
> >
> >
> >
> > > The exact number for 100 people / 100 rooms is 4.23259523879579 (found by a C# program).
> > How long is (was) the execution (run-time) for that program?
> >
> > Less than 10 min. would be impressive , but it depends on how fast the PC is
> >
> >
> It took about 8 minutes on a rather old laptop.
> The time grows exponentially with the number of people/rooms, so for 1000/1000 it is not going to be feasible even on the fastest pc.
> >
-------- The time grows [exponentially] with the number of people/rooms, (my emphasis)
> On Sunday, September 18, 2022 at 4:38:02 PM UTC-4, henh...@gmail.com wrote:
> > On Sunday, September 18, 2022 at 1:10:42 PM UTC-7, Ilan Mayer wrote:
> > > On Wednesday, September 14, 2022 at 5:42:33 PM UTC-4, henh...@gmail.com wrote:
> > > > Have you encountered this number (63.2 %) some time earlier ?
> > > > ( i may have, but if so, i had forgotten)
> > > >
> > > >
> > > >
> > > > and also ..........
> > > >
> > > >
> > > > What's the formula that gives me the expected # of ppl in the Most crowded room ( 5, 5, 22 below) ?
> > > >
> > > >
> > > > (is there a Web-page that explains it? ------ i couldn't find it in SE (StackExchange), etc.)
> > > >
> > > >
> > > >
> > > > according to the simulations i've done...
> > > >
> > > > 100 ppl are randomly assigned to 100 rooms...
> > > > ---> the Most crowded room is occupied by 5 people. (A)
> > > >
> > > > 1000 ppl are randomly assigned to 1000 rooms...
> > > > ---> the Most crowded room is occupied by 5 people. (B)
> > > >
> > > > 10000 ppl are randomly assigned to 1000 rooms...
> > > > ---> the Most crowded room is occupied by 22 people.
> > > >
> > > >
> > > > ---------------- what are the theoretical values for (A) and (B) ?
> >
> >
> >
> > > The exact number for 100 people / 100 rooms is 4.23259523879579 (found by a C# program).
> > How long is (was) the execution (run-time) for that program?
> >
> > Less than 10 min. would be impressive , but it depends on how fast the PC is
> >
> >
> It took about 8 minutes on a rather old laptop.
> The time grows exponentially with the number of people/rooms, so for 1000/1000 it is not going to be feasible even on the fastest pc.
> >
i don't want to seem Nit-picky
(but we're all Puzzle Nerds here, right ?)
where N= number of people/rooms
the relevant numbers (we're concerned about) grows proportional to N^N
is that called Super-Exponential or Supra--..... or something like that ?
z> > i don't think i can do 1000 people / 1000+ rooms on my slow home PC
Ilan Mayer
Sep 19, 2022, 9:35:06 PM9/19/22
to
Anton Shepelev
Sep 22, 2022, 6:34:17 PM9/22/22
to
HH:
> What's the formula that gives me the expected # of ppl in
> the Most crowded room
>
Observe that allocations of p people in r rooms can be
expressed as the expanded terms of a multinomial of power p
with r terms. For example:
r p
1:2 (a)^2 = a^2
E(m) = 2 = 2
2:1 (a+b)^1 = a + b
E(m) = (1 + 1)/2 = 1
2:2 (a+b)^2 = a^2 + b^2 + ab + ba =>
E(m) = ( 2 + 2 1 + 1 )/4 = 1 1/2
3:2 (a+b)^3 = a^3 + b^3 + 3b^2a + 3ab^2
E(m) =( 3 + 3 + 3 *2 + 3 * 2)/8 = 2 1/4
2:3 (a+b+c)^2 = a^2 + b^2 + c^2 + 2 a b + 2 a c + 2 b c
E(m) = ( 2 + 2 + 2 + 2 * 1 + 2 * 1 + 2 * 1)/9 = 4/3
This is regular and easily computable by sequential
generation of the terms and their corresponding multinomial
coefficient.
--
() ascii ribbon campaign - against html e-mail
/\ www.asciiribbon.org - against proprietary attachments
> What's the formula that gives me the expected # of ppl in
> the Most crowded room
>
> according to the simulations i've done...
Instead of simulation, you can compute the exact value.
Observe that allocations of p people in r rooms can be
expressed as the expanded terms of a multinomial of power p
with r terms. For example:
r p
1:2 (a)^2 = a^2
E(m) = 2 = 2
2:1 (a+b)^1 = a + b
E(m) = (1 + 1)/2 = 1
2:2 (a+b)^2 = a^2 + b^2 + ab + ba =>
E(m) = ( 2 + 2 1 + 1 )/4 = 1 1/2
3:2 (a+b)^3 = a^3 + b^3 + 3b^2a + 3ab^2
E(m) =( 3 + 3 + 3 *2 + 3 * 2)/8 = 2 1/4
2:3 (a+b+c)^2 = a^2 + b^2 + c^2 + 2 a b + 2 a c + 2 b c
E(m) = ( 2 + 2 + 2 + 2 * 1 + 2 * 1 + 2 * 1)/9 = 4/3
This is regular and easily computable by sequential
generation of the terms and their corresponding multinomial
coefficient.
--
() ascii ribbon campaign - against html e-mail
henh...@gmail.com
Sep 27, 2022, 5:54:13 PM9/27/22
to
can we get the fraction (expected value) for 10 ppl in 10 rooms this way ?
( in the very beginning, i was thinking of something like this... )
Anton Shepelev
Oct 6, 2022, 5:28:32 PM10/6/22
to
henh... to Anton Shepelev:
> > Instead of simulation, you can compute the exact value.
> > Observe that allocations of p people in r rooms can be
> > expressed as the expanded terms of a multinomial of
> > power p with r terms. For example:
> > [...]
State you doubts, if any.
> can we get the fraction (expected value) for 10 ppl in 10
> rooms this way ?
State your doubts, if any. I say we can, and my C program
reports:
1168918030 / 424490995 ~= 2.753693
Now, what is your result, if any?
> ( in the very beginning, i was thinking of something like
> this... )
And what was your conclusion, if any?
> > Instead of simulation, you can compute the exact value.
> > Observe that allocations of p people in r rooms can be
> > expressed as the expanded terms of a multinomial of
> > power p with r terms. For example:
> > This is regular and easily computable by sequential
> > generation of the terms and their corresponding
> > multinomial coefficient.
>
> really?
> > generation of the terms and their corresponding
> > multinomial coefficient.
>
State you doubts, if any.
> can we get the fraction (expected value) for 10 ppl in 10
> rooms this way ?
reports:
1168918030 / 424490995 ~= 2.753693
Now, what is your result, if any?
> ( in the very beginning, i was thinking of something like
> this... )
henh...@gmail.com
Oct 6, 2022, 5:49:16 PM10/6/22
to
On Thursday, October 6, 2022 at 2:28:32 PM UTC-7, Anton Shepelev wrote:
> henh... to Anton Shepelev:
> > > Instead of simulation, you can compute the exact value.
> > > Observe that allocations of p people in r rooms can be
> > > expressed as the expanded terms of a multinomial of
> > > power p with r terms. For example:
> > > [...]
> > > This is regular and easily computable by sequential
> > > generation of the terms and their corresponding
> > > multinomial coefficient.
> henh... to Anton Shepelev:
> > > Instead of simulation, you can compute the exact value.
> > > Observe that allocations of p people in r rooms can be
> > > expressed as the expanded terms of a multinomial of
> > > power p with r terms. For example:
> > > [...]
> > > This is regular and easily computable by sequential
> > > generation of the terms and their corresponding
> > > multinomial coefficient.
> > can we get the fraction (expected value) for 10 ppl in 10
> > rooms this way ?
> State your doubts, if any. I say we can, and my C program
> reports:
>
> 1168918030 / 424490995 ~= 2.753693
>
> Now, what is your result, if any?
on Sept 15, i posted (in this thread) ...
> > rooms this way ?
> State your doubts, if any. I say we can, and my C program
> reports:
>
> 1168918030 / 424490995 ~= 2.753693
>
> Now, what is your result, if any?
6 --------------- 2.408179012345679
8 -------------- 2.5972328186035156
10 ------------- 2.74868911 (exact number) ----
----------- i'm still wondering if there's a Really Fast way (algorithm) to compute these fractions.
Anton Shepelev
Oct 7, 2022, 8:18:33 PM10/7/22
to
Anton Shepelev to henh...:
> > can we get the fraction (expected value) for 10 ppl in
> > 10 rooms this way ?
>
> State your doubts, if any. I say we can, and my C program
> reports:
>
> 1168918030 / 424490995 ~= 2.753693
>
Thanks to the analytic values by Ilan Mayer, I have found an
error in my program and fixed it. My corrected analytic
values for n people in n rooms are:
1: 1 / 1 = 1.000000000000000
2: 6 / 4 = 1.500000000000000
3: 51 / 27 ~ 1.888888888888889
4: 544 / 256 = 2.125000000000000
5: 7145 / 3125 = 2.286400000000000
6: 112356 / 46656 ~ 2.408179012345679
7: 2066323 / 823543 ~ 2.509065100425843
8: 43574336 / 16777216 ~ 2.597232818603516
9: 1036922769 / 387420489 ~ 2.676478912296247
10: 27486891100 / 10000000000 = 2.748689110000000
11: 803137535321 / 285311670611 ~ 2.814948065745319
12: 25642631336400 / 8916100448256 ~ 2.875991750565768
13: 888148407804853 / 302875106592253 ~ 2.932391564951315
14: 33165208812574216 / 11112006825558016 ~ 2.984628189418768
That is the precision limit of my C program. Futher values
are approximate:
15: 3.033122027793592
16: 3.078246797314360
17: 3.120336673764227
18: 3.159690951821744
19: 3.196575256074798
20: 3.231235911954644
21: 3.263840995156228
22: 3.294677258703217
23: 3.323501424317847
24: 3.351204745044710
25: 3.375940763093699
26: 3.400997883301979
27: 3.420098995014796
28: 3.442852016690488
29: 3.453774951545424
30: 3.474683387544387
31: 3.476040838397223
Perhaps a big-number library or more accurate implementation
could help...
My program confirms your "exact value" for 10-by-10. How
did *you* calculate it? Have you published your solution?
> > can we get the fraction (expected value) for 10 ppl in
> > 10 rooms this way ?
>
> State your doubts, if any. I say we can, and my C program
> reports:
>
> 1168918030 / 424490995 ~= 2.753693
>
error in my program and fixed it. My corrected analytic
values for n people in n rooms are:
1: 1 / 1 = 1.000000000000000
2: 6 / 4 = 1.500000000000000
3: 51 / 27 ~ 1.888888888888889
4: 544 / 256 = 2.125000000000000
5: 7145 / 3125 = 2.286400000000000
6: 112356 / 46656 ~ 2.408179012345679
7: 2066323 / 823543 ~ 2.509065100425843
8: 43574336 / 16777216 ~ 2.597232818603516
9: 1036922769 / 387420489 ~ 2.676478912296247
10: 27486891100 / 10000000000 = 2.748689110000000
11: 803137535321 / 285311670611 ~ 2.814948065745319
12: 25642631336400 / 8916100448256 ~ 2.875991750565768
13: 888148407804853 / 302875106592253 ~ 2.932391564951315
14: 33165208812574216 / 11112006825558016 ~ 2.984628189418768
That is the precision limit of my C program. Futher values
are approximate:
15: 3.033122027793592
16: 3.078246797314360
17: 3.120336673764227
18: 3.159690951821744
19: 3.196575256074798
20: 3.231235911954644
21: 3.263840995156228
22: 3.294677258703217
23: 3.323501424317847
24: 3.351204745044710
25: 3.375940763093699
26: 3.400997883301979
27: 3.420098995014796
28: 3.442852016690488
29: 3.453774951545424
30: 3.474683387544387
31: 3.476040838397223
Perhaps a big-number library or more accurate implementation
could help...
My program confirms your "exact value" for 10-by-10. How
did *you* calculate it? Have you published your solution?
Anton Shepelev
Oct 11, 2022, 8:02:45 PM10/11/22
to
henh...:
> where N= number of people/rooms the relevant numbers
> (we're concerned about) grows proportional to N^N
N^N is the total number of terms in the expansion of:
(a_1 + ... + a_n)^n
But if you group compatible terms there will remain much
fewer summands, and then if you group terms with identical
power-sets (e.b. a^2 b and a b^2) the total number of unique
summands will futher decrease and become equal to the number
of partitions (OEIS A000041). The performance of my program
is roughly proportional to that number, but in fact a bit
worse because as the sheer numbers increase the calculation
of factorial ratios becomes harder. In the following table,
`n' is the number of rooms and people, `s' the number of
summands, `ms' calculation time in milliseconds, and `res'
the calculated answer:
n s ms s/ms res
1 1 0 0 1.000000
2 2 0 0 1.500000
3 3 0 0 1.888889
4 5 0 0 2.125000
5 7 0 0 2.286400
6 11 0 0 2.408179
7 15 0 0 2.509065
8 22 0 0 2.597233
9 30 0 0 2.676479
10 42 0 0 2.748689
.....................................
30 5604 15 373 3.492990
31 6842 32 213 3.513329
32 8349 31 269 3.532941
33 10143 47 215 3.551881
34 12310 47 261 3.570201
35 14883 62 240 3.587945
36 17977 78 230 3.605155
37 21637 94 230 3.621868
38 26015 125 208 3.638117
39 31185 141 221 3.653932
40 37338 171 218 3.669340
41 44583 204 218 3.684366
42 53174 250 212 3.699032
43 63261 328 192 3.713357
44 75175 375 200 3.727360
45 89134 453 196 3.741058
46 105558 562 187 3.754466
47 124754 641 194 3.767597
48 147273 734 200 3.780465
49 173525 907 191 3.793081
50 204226 1062 192 3.805455
51 239943 1313 182 3.817597
52 281589 1578 178 3.829517
53 329931 1797 183 3.841223
54 386155 2125 181 3.852722
55 451276 2500 180 3.864022
56 526823 2921 180 3.875129
57 614154 3500 175 3.886051
58 715220 4094 174 3.896791
59 831820 4750 175 3.907358
60 966467 5547 174 3.917754
61 1121505 6547 171 3.927986
62 1300156 7719 168 3.938057
63 1505499 9609 156 3.947973
64 1741630 10891 159 3.957737
65 2012558 12500 161 3.967353
66 2323520 15187 152 3.976826
67 2679689 16625 161 3.986158
68 3087735 19235 160 3.995353
69 3554345 22484 158 4.004414
70 4087968 25953 157 4.013345
.....................................
99 169229875 1321266 128 4.226524
100 190569292 1502828 126 4.232595
I wonder what is the sequence and formula for the number
of summands when the number of people is not equal to the
number of rooms...
> where N= number of people/rooms the relevant numbers
> (we're concerned about) grows proportional to N^N
(a_1 + ... + a_n)^n
But if you group compatible terms there will remain much
fewer summands, and then if you group terms with identical
power-sets (e.b. a^2 b and a b^2) the total number of unique
summands will futher decrease and become equal to the number
of partitions (OEIS A000041). The performance of my program
is roughly proportional to that number, but in fact a bit
worse because as the sheer numbers increase the calculation
of factorial ratios becomes harder. In the following table,
`n' is the number of rooms and people, `s' the number of
summands, `ms' calculation time in milliseconds, and `res'
the calculated answer:
n s ms s/ms res
1 1 0 0 1.000000
2 2 0 0 1.500000
3 3 0 0 1.888889
4 5 0 0 2.125000
5 7 0 0 2.286400
6 11 0 0 2.408179
7 15 0 0 2.509065
8 22 0 0 2.597233
9 30 0 0 2.676479
10 42 0 0 2.748689
.....................................
30 5604 15 373 3.492990
31 6842 32 213 3.513329
32 8349 31 269 3.532941
33 10143 47 215 3.551881
34 12310 47 261 3.570201
35 14883 62 240 3.587945
36 17977 78 230 3.605155
37 21637 94 230 3.621868
38 26015 125 208 3.638117
39 31185 141 221 3.653932
40 37338 171 218 3.669340
41 44583 204 218 3.684366
42 53174 250 212 3.699032
43 63261 328 192 3.713357
44 75175 375 200 3.727360
45 89134 453 196 3.741058
46 105558 562 187 3.754466
47 124754 641 194 3.767597
48 147273 734 200 3.780465
49 173525 907 191 3.793081
50 204226 1062 192 3.805455
51 239943 1313 182 3.817597
52 281589 1578 178 3.829517
53 329931 1797 183 3.841223
54 386155 2125 181 3.852722
55 451276 2500 180 3.864022
56 526823 2921 180 3.875129
57 614154 3500 175 3.886051
58 715220 4094 174 3.896791
59 831820 4750 175 3.907358
60 966467 5547 174 3.917754
61 1121505 6547 171 3.927986
62 1300156 7719 168 3.938057
63 1505499 9609 156 3.947973
64 1741630 10891 159 3.957737
65 2012558 12500 161 3.967353
66 2323520 15187 152 3.976826
67 2679689 16625 161 3.986158
68 3087735 19235 160 3.995353
69 3554345 22484 158 4.004414
70 4087968 25953 157 4.013345
.....................................
99 169229875 1321266 128 4.226524
100 190569292 1502828 126 4.232595
I wonder what is the sequence and formula for the number
of summands when the number of people is not equal to the
number of rooms...
henh...@gmail.com
Oct 12, 2022, 8:29:14 PM10/12/22
to
Pascal+ triangle+ (or Pyramid) for 3 rooms (or 3 variables X,Y,Z) (or trinomials (?)) looks nice.
building up a Pascal+ triangle+ from (1, 1, 1, ..., 1) (100 One's)
-- maybe this is a better way -- i'll think about it.
(The way i was doing it, (i think) it'd been hard to get Approximate values)
Reply all
Reply to author
Forward
0 new messages