0
$\begingroup$

I want to compute the blocking probability \begin{align*} \operatorname{B}\left(\rho,m\right) & = \dfrac{\rho^{m}/m!} {\sum_{i= 0}^{m}\rho^{i}/i!} \\[5mm] \mbox{with}\ \left(\rho,m\right) & = \left(ka, k\left[a - 1\right]\right) \end{align*} ( Erlang $\operatorname{B}$ formula ) for 'billionaire' $k \gg a$.

  • My naïve approach is by Stirling approximation: \begin{align*} \frac{\rho^{m}}{m!} & \approx\frac{\rho^{m}}{\,\sqrt{\,2\pi m\,}\,\left(m/{\rm e}\right)^{m}}, \quad\sum_{i= 0}^{m}\frac{\rho^{i}}{i!}\approx e^{\rho} \\[2mm] & \mbox{when}\ m\ \mbox{large and}\ \rho\ \mbox{also large} \end{align*} but this seems not good enough.
  • I need your help to get a better approximation.
  • However, I googled many times about 'Approximation of blocking probability' but cannot find such an alternative approximated formula, I feel interested in understanding why.

Thanks a real lot !.

Edit: I find a better approximation for the numerator here. And I hope for an approximation of factorial sum $$ \sum_{iv= 0}^{m}\frac{\rho^{i}}{i!}\quad \mbox{as}\quad c\,{\rm e}^{\rho + o\left(1\right)} $$ sharpening the traditional exponential function ${\rm e}^{\rho}$

Edit $\bf 2$: I think Taylor's series with remainder helps here.

$\endgroup$
5
  • $\begingroup$ What happens if you substitute $\rho = ka$ and $m = k(a-1)$ in the approximations at the bottom? Incidentally, I assume the last two $p$'s are actually $\rho$'s? $\endgroup$ Commented Nov 8, 2024 at 5:15
  • $\begingroup$ @BrianTung yes, your sense is right, seems like nothing special about $\left ( \rho, m \right )= \left ( ka, k\left ( a- 1 \right ) \right )$, maybe $\operatorname{gcd}\left ( \rho, m \right )= k$ makes the problem more general. I also fixed the wrong $\rho$. Thank you so much, sir. $\endgroup$ Commented Nov 8, 2024 at 5:25
  • $\begingroup$ Some context? Where does this "blocking probability" comes from? $\endgroup$ Commented Nov 9, 2024 at 14:23
  • $\begingroup$ @leonbloy its another name is Erlang B formula, and it is also the special case of Erlang distribution. Thanks for your help. $\endgroup$ Commented Nov 10, 2024 at 1:00
  • $\begingroup$ In case this helps: dlmf.nist.gov/8.11 see 8.11.7 $\endgroup$ Commented Nov 10, 2024 at 2:58

1 Answer 1

Reset to default
3
$\begingroup$

To first order $$B\approx \frac{1}{a} \tag1$$

Proof follows (I moved to the end my original proof, much more convoluted and less reliable).

Consider $$ \frac{1}{B}=\frac{m!}{\rho ^m} \sum_{i= 0}^{m}\frac{\rho^i}{i!}= \sum_{j= 0}^{m} \rho^{-j} \frac{m!}{(m-j)!} \tag 2$$

Now, assuming $m=k(a-1)$ , $\rho = ka$, with $a>1$, $k\gg a$: $$\begin{align}\rho^{-j} \frac{m!}{(m-j)!}&= \left(\frac{m}{\rho} \right)^j \left(1-\frac{1}{m}\right)\left(1-\frac{2}{m}\right)\cdots \left(1-\frac{j-1}{m}\right) \\ &= \left(\frac{a-1}{a}\right)^j \left(1 - \frac{1+2 +\cdots +(j-1)}{m}+o(m^{-1})\right) \\ &= \alpha^j \left(1 - \frac{j (j-1)}{2m}+o(m^{-1})\right) \tag3 \\ \end{align}$$ where $\alpha = (a-1)/a$. Replacing the finite sum in $(2)$ by an infinite sum, and using $\sum_{j=0}^{\infty} \alpha^j j(j-1)=2 \alpha^2/(1-\alpha)^3$ this results in

$$ \begin{align} \frac{1}{B}\approx \frac{1}{1-\alpha} - \frac{1}{m}\frac{\alpha^2}{(1-\alpha)^3}=a - \frac{1}{k(a-1)}\frac{a^3 (a-1)^2}{a^2}=a - \frac{1}{k} a(a-1) \tag4 \end{align} $$

or

$$ B \approx \frac{1}{a - \frac{1}{k} a(a-1) } \tag 5$$

For example, for $k=50$ and $a=3.5$ ($m=125$) we get:

 B rel error exact 0.298436 aprox (1) 0.285714 4.2% aprox (5) 0.300752 -0.8%

Alternative original derivation (less reliable).

$$\begin{align} g(m,x)=\sum_{j=0}^{m-1} \frac{x^j}{j!} = e^x \frac{\Gamma(m,x)}{\Gamma(m)}\end{align} $$

Setting $m=k(a-1)$, $x=ka$, with $a>1$ fixed and $k\to \infty$, applying asympotic formula $8.11.7$ from here for the incomplete Gamma function, and Stirling approximation for the Gamma function , we get

$$\log g(m,x) \approx -\frac12\left(\alpha \,k + \log k + \beta\right)$$

with $\alpha = 2 (a-1)\left(\log(\frac{a-1}{a}) -1 \right)$ and $\beta = \log \frac{2\pi}{a-1}$

Then, doing the math...

$$ \log \frac{g(m,x)}{\frac{x^m}{m!}} \approx \log(a-1) + \frac{1}{12 (ak)^2} + o(1/k^2) $$

and finally

$$ B = \frac{1}{1+\frac{g(m,x)}{\frac{x^m}{m!}}}\approx \frac{1}{a} $$

$\endgroup$
2
  • $\begingroup$ @leonboy thank you for investing your time in my problem; your solution has made the most effective use of intentional $\left ( \rho, m \right )$. $\endgroup$ Commented Nov 11, 2024 at 1:59
  • 1
    $\begingroup$ I had made a little mistake. Fixed, I hope $\endgroup$ Commented Nov 11, 2024 at 3:07

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.