Formula for the average of the lowest remaining value in a sequence of multisets

90 Views Asked by At

$B_1=(b_1,b_2,\ldots,b_n)$ is a finite multiset of positive real numbers $b_i$.

To obtain $B_{i+1}$ we let
$$m_i=\min\{B_i\}\quad\quad\quad\quad k_i=\min\{j\in\mathbb{N}:(B_i)_j=m_i\}\\ B_{i+1}=\left(\underbrace{(B_{i})_1-m_i,\ \ldots\ ,(B_{i})_{{k_i}-1}-m_i}\ ,\ b_{k_i}\ ,\ \underbrace{(B_{i})_{{k_i}+1}-m_i,\ \ldots\ ,(B_{i})_n-m_i}\right)$$

In words you take the minimum of the current $B_i$, subtract it from all entries of $B_i$, and replace the leftmost zero by the value at that entry in $B_1$. I'm interested in the average of the values getting subtracted:

$$\underset{n\to\infty}{\lim}\frac{1}{n}\sum_{i=1}^n m_i$$

If all $b_i$ are integers then all $B_i$ are in a finite space, so the sequence of $B_i$s is periodic. By iterating through one period I found some averages and noticed that all of them were:

$$\frac{b_1b_2\ldots b_n}{b_1b_2\ldots b_{n-1}+b_1b_2\ldots b_{n-2}b_n+\ldots+b_2\ldots b_n}$$

Does anyone know where I can find a proof for this?

1

There are 1 best solutions below

0
On BEST ANSWER

Define $a_N = \sum_{i=1}^N m_i$, this sequence is just $\bigcup_i b_i \mathbb{Z}_+$ (after ordering from small to large and count multiplicity).

For a positive real number $x$, there are $\sum_i \lfloor \frac{x}{b_i} \rfloor =f(x)$ terms of $a_N$ that is $\le x$, hence $a_{f(x)} \le x < a_{f(x)+1}$.

The average waiting time is \begin{equation} \text{lim}_N \frac{a_N}{N} = \text{lim}_x \frac{x}{f(x)} = \frac{1}{\sum_i\frac{1}{b_i}}. \end{equation}