94 views

Skip to first unread message

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) ?

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]

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

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

/__ __\

||

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 !

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.)

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

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

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

Sep 17, 2022, 12:36:53 PM9/17/22

to

I didn't mean integer valued, I meant of type int.

Duncan

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 ?

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:

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:

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 ?

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 )

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.

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

Sep 19, 2022, 9:35:06 PM9/19/22

to

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

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... )

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... )

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.

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?

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...

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