1
$\begingroup$

I want to construct a family of continuous functions $H$ in order to randomly partition the unit interval.

That is, consider a partition $\lambda$ of the unit interval into $n$ subintervals: $\lambda = \{[0, \frac{1}{n}), [\frac{1}{n}, \frac{2}{n}),...,[\frac{n-1}{n}, 1]\}$, I am looking for a probability distribution over functions ${h \in H}$ such that for any $x,y \in [0,1]$ which belong to distinct subintervals

$$ Pr_{h \in H}[h(x) < 0 \land h(y) < 0 \; \vert \; I_x \neq I_y] = \frac{1}{4} $$

where $I_x$ is the interval containing $x$. In other words each interval will be mapped randomly and independently to $0$ or $1$ with probability 0.5.

The setup here is very similar to that found in k-wise independent hashing (with $k=2$) ${h \in H}$, whereby we simulate "true" hash by sampling from a distribution over a hash family. The differences here are that:

  • $h$ maps from the reals and should be a continuous function or piecewise continuous.
  • I would like the function to be compact in representation. In other words, consider one possible approach which would sample a uniformly distributed value for each Interval $c(I) \sim \mathcal{U}(-1,1)$ then define $h(x) = c(I_x)$. This approach is not viable for me because $h(x)$ is effectively a (possibly very) large table and not compact.
  • $h$ should be closed form and efficiently computable in practice.

The motivation of this problem is to uniformly sample from a partition of arbitrary subsets of $\mathbb{R}^d$.

$\endgroup$
  • $\begingroup$ Do you want continuous functions or piecewise constant functions? Why do you use $w$ and not $1/n$? $\endgroup$ – Douglas Zare Jul 27 '15 at 2:32
  • $\begingroup$ Preferably continuous but compactness of representation is perhaps the biggest requirement (apologies if this is a vague concept. These functions will be used by nonlinear constraint solvers). You're correct, there's no reason to have $w$ and $n$. $\endgroup$ – zenna Jul 27 '15 at 7:47

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.