1
$\begingroup$

I'm searching to devise an algorithm that finds a set of n time intervals with a random duration between min and max. On top of that, the total duration is also given (tot).

For example:

n = 15

min = 30 s

max = 90 s

tot = 15 minutes

means: "Find 15 time intervals, each of a duration between 30 and 90 seconds, which, when summed together, produce a total time interval of 15 minutes"

To check whether there is a solution to the problem I would just make sure that
min * n <= tot <= max * n.

To make sure that the total duration is equal to tot I would apply a found ratio to all the time intervals.

However, how to make sure that the min and max constrains are met even after the ratio is applied? Am I on the right track?

$\endgroup$
  • $\begingroup$ This is tricky and I don't know of a solution that is simultaneously simple, efficient, and correct. First off, this is equivalent to asking for 15 time intervals, each of duration between 0 and 60 seconds, that when summed together produce a total time interval of 7.5 minutes (just add 30 seconds to each of those, and you get a solution to your original problem). So you can without loss of generality assume that min = 0. You can also assume that max = 1 by rescaling. The problem then becomes: given $c$, sample from $x_1,\dots,x_n$ such that $0 \le x_i \le 1$ and $x_1 + \dots + x_n = c$. $\endgroup$ – D.W. May 18 '18 at 16:28
  • $\begingroup$ This is a generalization of sampling from the unit simplex (the latter is the case where $c=1$), so you might be able to use similar techniques here. See cs.stackexchange.com/q/3227/755. Alternatively, you could view this as sampling from within a convex polytope. See mathoverflow.net/q/9854/37212 and cs.stackexchange.com/q/44029/755. $\endgroup$ – D.W. May 18 '18 at 16:29
0
$\begingroup$

Let’s consider general parameters $n$, $\min$, $\max$, with $0<\min<\max$ and $tot=1$ (you can transform your problem to this form simply by considering 15 minutes as the measure unit for time). What you are trying to do is to sample from the intersection of the following two set:

  1. the set $S=\left\{(x_i)_{i=1}^{n}|\Sigma_{i=1}^{n}x_i=tot=1\right\}$, the canonical n-dimensional simplex, and
  2. the set $C=\left\{(x_i)_{i=1}^{n}|\forall i\, x_i \in [\min,\max]\right\}=[\min,\max]^n$ which is a n-dimensional hypercube in the first octant.

To see the shape of this set let’s fix $n=3$, so we now are in a $3$-dimensional space and the hypercube is an actual cube. The cube depends on the parameters $\min$ and $\max$. If you keep the radius $R=\frac{\min-\max}{2}$ constant and change the mid-point $m=\frac{\min +\max}{2}$ of the interval $[\min,\max]$ you are translating the cube with direction $\left(1,1,1\right)$. Instead if you change radius $R$ but keep the mid-point $m$ constant you get are expansion (the edge of) the cube.

The intersection of the simplex and the cube is a hexagon, whose regularity depends on the value of $R$. Moreover, it may happen that the hexagon collapses to a triangle, or to a point or to the emptyset (in these two cases you can sample only one point or none at all, so the problem is trivially solved). So, if we know how to compute the vertices of the hexagon, the problem reduces to a sampling from a hexagon.

To compute the vertices notice that they lie only on those edges of the cube such that one end-point lies “above” the simplex and the other “below”. So you could search all the couple of adjacent vertices of the cube such that one end-point satisfy the constraint $x+y+z\geq1$ and the other satisfy the constraint $x+y+z\leq1$. For all these couples $\left(e_1,e_2\right)$ you can parametrize the segment $e_1e_2$ in the form $Le_1+(1-L)e_2$ for all $L$ in $\left[0,1\right]$ and then find that particular $L$ such that the point on the segment lies on the simplex, i.e. find L such that $x_L +y_L + z_L=1$ where $(x_L,y_L,z_L)= Le_1+(1-L)e_2$.

Once you have computed the six vertices of the hexagon you should be able to decide if it is really a hexagon -if all vertices are distinct- or a triangle -if there are only three distinct vertices- or something trivial.

To sample from a triangle you can, for example, find a transformation $\varphi$ from the canonical simplex to the triangle, sample from the simplex (for example as in cs.stackexchange.com/q/3227/755 as suggested by D.W.) and then transform the sample using $\varphi$. To ensure uniformity you should sample uniformly in the simplex and normalize $\varphi$ with the norm of the determinant $d$ of its jacobian matrix (when $d\neq 0$), i.e. use the transformation $\psi =\begin{cases}\varphi & \text{if } d=0\\\frac{\varphi}{d} &\text{if } d\neq 0 \end{cases}$.

To sample from a hexagon you can divide the hexagon in six triangles drawing the edges from the vertices to an inner point of the hexagon (for example $\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)$; infact, this point is a possible sample if and only if there is at least one sample), choose randomly one of them, and then sample from that triangle. In this case to get uniformity, on top of sampling uniformly from triangles, you should choose the triangles using a probability distribution $\left(p_i\right)_1^6$ of the form $p_i =\frac{\text{area of the }i\text{-th triangle}}{\text{area of the hexagon}}$ (with this choiche you cover also the case of a collapsed hexagon). However, I suppose there are much more refined methods to sample from a triangle or from a hexagon.

Generalizing to grater values of $n$, instead of a hexagon divided in six triangles, you should get a $n-1$ dimensional convex surface whose vertices can be computed as above. This surface can be divided in some $n-1$ dimensional simplicial polytopes. So you select randomly one of these polytopes accordingly to their volume, find a transformation from the $n-1$ canonical simplex to this polytope and use it to transform a sample from the $n-1$ dimensional simplex.

$\endgroup$
  • $\begingroup$ What's the running time of your approach? On first glance it sounds like it might be exponential in $n$. Is that right? $\endgroup$ – D.W. May 24 '18 at 16:43

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.