# Randomly partitioning the unit interval with continuous functions

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$.

• Do you want continuous functions or piecewise constant functions? Why do you use $w$ and not $1/n$? – Douglas Zare Jul 27 '15 at 2:32
• 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$. – zenna Jul 27 '15 at 7:47