1
$\begingroup$

Suppose you have strings of several lengths $\ell_1, \ldots, \ell_n$. You trim them using the following procedure: you pick a number $0 \leq L \leq \sum_i \ell_i$ uniformly at random. Then you trim each string which is longer than $L$ so that it now has length $L$. Now you have strings of length $\ell_1^\prime, \ldots, \ell_n^\prime$.

Suppose you perform this procedure twice. What is the expected amount of string you have left— or, to put it another way, what is the expected amount of string you will have trimmed off?


For the first round of trimming, I can find that the expected amount trimmed off of $\ell_k$ is just $$\frac{\frac{1}{2}\ell_k^2}{\sum_i \ell_i}.$$

But because the trimming in the next round depends on the trimming in the first round, I'm not sure how to approach the join probability computation.


When all the strings have the same length $\ell$, I think (based on a geometric argument, looking at the different regions in an $n\ell\times n\ell$ square encoding the possible values of $L_1$ and $L_2$) the expected length of each string after two cuts is:

$$E[\ell^{\prime\prime}] = \left[\frac{6n^2 - 7n + 2}{3n(2n-1)}\right]\ell$$

which is more complex than I expected, but which gives the expected answers in the limiting case that $n=1$ and $n\rightarrow \infty$. It also implies that the expected length trimmed is:

$$\frac{2}{3}\frac{1}{n}\ell$$ per string, or just $\frac{2}{3}\ell$ total, independent of the number of strings.

$\endgroup$
0
$\begingroup$

It would help to solve the problem to find the distribution function for $\sum_i \ell_i'$. This is not a full reply, but maybe it can help you on your way to the final solution. First of all, the cumulative distribution of $\ell_k'=\min(\ell_i,L)$ with $L\sim U([0,\sum_i\ell_i])$ is given by

$$\mathbb{P}(\ell_k'\leq x) = \begin{cases}0 &, x<0\\ \frac{x}{\sum_i\ell_i} &, 0\leq x <\ell_k \\ 1 &, x \geq \ell_k\end{cases}.$$

Note that this distribution has a discontinuous jump at $\ell_k$, indeed, either the string is trimmed, either it is not. For the part where it is not, you have a concentrated mass distribution at $\ell_k$, for the other part, a continuous distribution.

Then, we want the distribution of the sum $\sum_i \ell_i'$. We can work out a recursion relation for the distribution

$$\mathbb{P}(\sum_{i=1}^{n} \ell_i' \leq x) = \mathbb{P}(\sum_{i=1}^{n-1} \ell_i' \leq x-\ell_n') \\ =\int_0^{\ell_n} \mathbb{P}(\sum_{i=1}^{n-1} \ell_i' \leq x-s|\ell_n'=s)\frac{1}{\sum_i\ell_i} ds + \mathbb{P}(\sum_{i=1}^{n-1} \ell_i' \leq x-\ell_n|\ell_n'=\ell_n)\left(1-\frac{\ell_n}{\sum_i\ell_i}\right) \\ =\int_0^{\ell_n} \mathbb{P}(\sum_{i=1}^{n-1} \ell_i' \leq x-s)\frac{1}{\sum_i\ell_i} ds + \mathbb{P}(\sum_{i=1}^{n-1} \ell_i' \leq x-\ell_n)\left(1-\frac{\ell_n}{\sum_i\ell_i}\right) $$

Introducing the notation $F_n(x)=\mathbb{P}(\sum_{i=1}^{n} \ell_i' \leq x)$ we have

$$F_n(x)=\int_0^{\ell_n} F_{n-1}(x-s)\frac{1}{\sum_i\ell_i} ds + F_{n-1}(x-\ell_n)\left(1-\frac{\ell_n}{\sum_i\ell_i}\right) $$

and

$$F_1(x) = \begin{cases}0 &, x<0\\ \frac{x}{\sum_i\ell_i} &, 0\leq x <\ell_1 \\ 1 &, x \geq \ell_1\end{cases}.$$

This is a recursion relation for $F_n(x)$. If we can solve it, we can go to the next step of determining $L'\sim U([0,\sum_i\ell_i'])$ for the second trimming and in the end $\mathbb{E}[\min(\ell_k',L')]$. That's how far I got for now. Maybe this is a bit too brutish an approach, but it gets us somewhere. I'll come back at you if I figure out more. Also, I think there might be an advantage to order the strings in either increasing or decreasing order of length, to work out the recursion. Just a hunch.

$\endgroup$
  • $\begingroup$ Yeah! Thanks for this. With this approach, I've been trying to solve the case where all strings are the same length since it seems that's the limiting effect of the trimming process. $\endgroup$ – user326210 Nov 5 '17 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.