[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

859.0. "Telephone switching: probability of a connection" by LASSIE::PETTENGILL (mulp) Fri Apr 08 1988 19:40

What is the probability of a connection when c*n*g customers attempt to call
a randomly (uniform) chosen numbers in the range of 1 to n where there are
g lines for each number (hunt group) ?

We have worked on this problem and come up with equations which fit the brute
force analysis.

The following is the closed-form solution for c=1 (in Maple format):

u1 := proc (n, g)
      1-(n-1)/n*(n*g)!/(g)!/(n*g-g)!*(1/n)**(g)*((n-1)/n)**(n*g-g) end;

(Recall that n is the number of groups and g is the group size.)

The same thing in a more `natural' form:

	    n-1    n     1 g    n-1 (n-1)*g
	1 - --- * ( ) * (-)  * (---)
	     n     g     n       n

The following is the closed-form solution for g=1 (in Maple format):

c0 := proc(n,c)1-((n-1)/n)**(n*c)end;

ditto:
	     n-1 n*c
	1 - (---)
	      n

Non closed-form solution for groups AND concentration:

u3:=proc(n,g,c)
1-sum((g-k)/g*(n*g*c)!/k!/(n*g*c-k)!*(1/n)**k*((n-1)/n)**(n*g*c-k),k=0..g-1)end;

ditto:

	    g-1 g-k    n*g*c     1 k    n-1 n*g*c-k
	1 - sum --- * (     ) * (-)  * (---)
	    k=0  g       k       n       n

Can anyone derive a closed form for the last solution ?

(My apologies if I screwed rewriting from Maple format to the more traditional
notation.)
T.RTitleUserPersonal
Name		DateLines
859.1??SSDEVO::LARYFri Apr 08 1988 23:1830
I'm confused.

> The following is the closed-form solution for g=1 (in Maple format):
>
>	     n-1 n*c
>	1 - (---)
>	      n

Given the definition of your problem, I would have thought that when g=1
it collapsed to the "birthday problem" - i.e. if there are N days in the
year, and M people in a room, what is the probability that all the people
have distinct birthdays.

The solution to the birthday problem is

		N(N-1)(N-2)...(N-M+1)
    P(N,M) =	---------------------
			 M
			N

Assuming that you wanted the probability of every caller getting connected,
I would have expected this to be the answer - it has the desired property
that when M (=c*n) > N (=n) the probability is zero. If your formula gives
the probability of some caller NOT being connected, it should then go to 1.0
when the number of callers exceeds the number of called numbers...

So - do you mean something different by "connection"?

							Richie
859.2Corrections, clarifications, detailsLASSIE::PETTENGILLmulpWed Apr 13 1988 18:2149
I was imprecise in my statement of the problem.  I should have asked for the
average expectation of all the attempted connections, or something like that.
However, with the addition of the factor c, that statement is wrong.

Let me try again, I hope I have better luck.

Given n telephone numbers, each with g lines, and n*g*c customers calling
these numbers, what is the utilization of the n*g total lines ?

Some examples:

For n=2, g=1, c=1, there are two ways that there can be 2 connections and
two ways that there can be 1 connection, for a total of 6 connections in 4
cases.  Therefore there is an average of 6/4 connections over 2 lines or
a utilization of 3/4.

For n=2, g=2, c=1, there are two ways to get 2 connections (all four callers
try to connect to the same number), 8 ways to get 3 connections, and 6 ways
to get 4 connections.  This is a total of 52 connection in 16 cases.  The
utilization in this case is 13/16.

The following table summarizes the above cases and more for n=2, c=1

				g
		1		2		3		4
N c
u o  1		2		0		0		0
m n  2		2		2		0		0
b n  3				8		2		0
e e  4				6		12		0
r c  5						30		16
  t  6						20		56
  e  7								112
  d  8								70

Total
connected	6		52		324		1768

Total cases	4		16		64		256

The following table (created by enumeration) is for c=1

			g
n \	  1		  2		  3		   4		  5
   ----------------------------------------------------------------------------
2  !	3/4		13/16		27/32		221/256		449/512
3  !	19/27		569/729		16099/19683	148987/177147
4  !	175/256		50227/65532	13529521/16777216
859.3The answer, I thinkSSDEVO::LARYMon Apr 18 1988 21:0624
This may be what you want:
	(sorry for the ugly notation, I didn't have time to prettify it)

let u (user count) = n*g*c for shorthand.

Prob of dialing a given number = 1/n

Probability of exactly m out of the u callers dialing a given number = p(m) =:

		uCm * (1/n)^m * (1-1/n)^(u-m)	The usual binomial distribution,
						xCy = # combinations of x things
						taken y at a time.

Expected value of the number of connections on a given number is:

	E = sum (m=0 thru m=u) (min(m,g)*p(m))	Since max connections = g

Expected utilization of the lines is E/g.

This formula seems to produce the same results as your table for the cases
in the table. I didn't see a way to express E in closed form.

							Richie