¿Cómo puedo distribuir al azar de agua en los cubos sin los cubos desbordante?

Question

Hice esta pregunta hace una semana, pero terminó siendo cerrado por no ser lo suficientemente específico. Voy a probar y definir todo como matemáticamente como sea posible en este, así que por favor, hágamelo saber si hay algo ambigua.

¿Cómo puedo distribuir al azar W litros de agua en n vaciar los cubos sin ellos desbordante (es decir, sin poner más agua en el cubo, a continuación, puede mantener pulsado)

Hay $n$ cubos de agua con el $i^{th}$ cubeta que contiene $w_i$ litros de agua.

1) $W = w_1 + w_2 + ... + w_n =$ Total cantidad de agua

2) $w_i$ $\epsilon$ $[0, x]$ para $i = 1, 2, ..., n$ donde $x$ $\epsilon$ $\Re$

Dado un número natural $n$ y el número real valor de$x$$W$, ¿que puedo utilizar para asignar un valor aleatorio a cada una de las $w_i$, de tal manera que (1) y (2) seguir siendo fiel?

Para aclarar lo que quiero decir al azar, estoy pensando en una función que devuelve un valor en el intervalo de $[0, 1]$ similar a la de el .NextDouble() método en la clase al Azar (Y sí, sé que esto es un pseudo-aleatorios y no verdaderamente aleatorios).

Ejemplo:

Para $n$ = 3, $W$ = 1 y $x$ = 1 una posible solución es:

$w_1$ = 0.22 $w_2$ = 0.43 $w_3$ = 0.35

Desde $w_1 + w_2 + w_3 = 0.22 + 0.43 + 0.35 = 1 = W$ y $w_1$, $w_2$ y $w_3$ están en el intervalo de $[0,1]$

Answer 1

Como se aclara en los comentarios, desea uniformemente muestra el conjunto de todos los puntos de $\vec w = (w_1,\dots,w_n)$ tal que $$w_1+\dots+w_n = W,\\ 0\le w_i\le x\ \text{para todos los $i=1,\dots,n$.}$$

Aquí se abren dos posibilidades.

1. Usted puede utilizar el rechazo de muestreo: de manera Uniforme generar un punto de satisfacciones $w_1+\dots+w_n=W$, $0\le w_i\ \forall i$; si se viola la restricción de la capacidad de $w_i\le x$ cualquier $i$, rechazarlo e inténtelo de nuevo.

   El primer paso se puede hacer fácilmente mediante la generación de $n-1$ uniforme de números aleatorios entre el$0$$W$, de la clasificación por lo que se $s_1,\dots,s_{n-1}$, en orden creciente, y el establecimiento de $w_1=s_1-0$, $w_2=s_2-s_1$, . . . , $w_n = W-s_{n-1}$. Este es el palo de romper el modelo aludido por El Recuento, ya que es equivalente a la ruptura de un palo de longitud $W$ a $n$ piezas haciendo recortes en ubicaciones $s_1,\dots,s_{n-1}$.

   El rechazo de muestreo está garantizado para darle una distribución uniforme, pero el inconveniente es que puede que tengas que probar muchas, muchas veces antes de obtener una muestra válida, sobre todo si $x\ll W$.

2. Tim Seguine en MathOverflow recomienda hit-and-run de muestreo: Comienzan en un punto arbitrario $\vec w$ dentro de su conjunto; escoger una dirección $\vec d$ uniformemente al azar; encontrar el rango de valores de $t$ que $\vec w+t\vec d$ se encuentra en el conjunto; elegir un $t$ uniformemente al azar de este rango; reemplace $\vec w$ con el nuevo punto de $\vec w+t\vec d$ y repetir. (Esto es esencialmente Seguine la descripción con las variables cambiado de nombre.)

   Para la inicialización, la elección de $\vec w=(W/n,\dots,W/n)$ es tan bueno como cualquier otro. Para escoger una dirección $\vec d$ de manera uniforme, una manera sencilla es elegir $n$ números de una distribución normal estándar, restar la media, la forma en que un vector y normalizar. Para encontrar el rango de valores de $t$, calcular todos los valores críticos de $t_{i,1} = -w_i/d_i$ $t_{i,2} = (x-w_i)/d_i$ donde $\vec w+t\vec d$ cruza una restricción de límite; ya que sabemos $\vec w$ está en el conjunto, $t=0$ debe ser válido, por lo $t$ debe estar entre el mayor valor negativo y el positivo menor valor.

   Hit-and-run de muestreo converge a una distribución uniforme como repite el proceso, pero si se detiene después de un número finito de iteraciones, la distribución solo puede ser aproximadamente uniforme. No obstante, hice algunos experimentos para baja $n$ y la distribución parecía enfoque de la uniformidad con bastante rapidez. Mi totalmente desinformados conjetura es que $n$ iteraciones es, probablemente, "lo suficientemente bueno", al menos para su problema.

Ambos métodos son fáciles de implementar, así que usted debe probar ambas. Gracias por hacernos esta pregunta; yo no habría aprendido acerca de hit-and-run de muestreo de otra manera.

Answer 2

El método exacto

La fórmula $W = w_1 + w_2 + ... + w_n$ describe un $(n-1)$-dimensiones hyperplane en $\mathbb R^n.$ La intersección de esta hyperplane con el $n$-dimensiones hipercubo $[0,x]^n$ es un convexo $(n-1)$-dimensiones polytope incrustado en $\mathbb R^n.$ Encontrar que polytope y de la muestra de manera uniforme sobre él. De hecho, usted puede tomar la imagen de que polytope en $\mathbb R^{n-1}$ al quitar el $n$th coordinar, muestra la primera $n-1$ coordenadas de manera uniforme sobre la que polytope, y resolver para el $n$th de coordenadas.

Sin duda, este es solo cambiar el problema para el problema de la descripción y muestreo de la polytope para un determinado$W$$x,$, lo que también puede ser un problema complicado.

El rechazo de muestreo

Como sugiere ya en otra respuesta, puede utilizar el muestreo uniforme sobre el polytope $W = w_1 + w_2 + ... + w_n \cap [0,\infty)^n$ (es decir, donde todos los $w_i$ son no negativos).

Si $W \leq x$ es una solución completa.

Si $x < W \leq \frac12 nx,$ de la muestra uniformemente a lo largo de $W = w_1 + w_2 + ... + w_n \cap [0,\infty)^n$ , pero rechazan el resultado si no hay ningún valor de $i$ que $w_i > x$ en ese resultado.

Si $W > \frac12 nx,$ cambiar el problema a uno de forma aleatoria la distribución de $nx - W$ "espacio vacío" entre $n$ cubos, cada uno de los cuales puede contener no más de $x$ "espacio vacío". A continuación, llenar el resto de cada cubeta con agua.

Esto evita que el extremo de las tasas de rechazo que de lo contrario podría ocurrir cuando los $W$ está cerca de a $nx.$ De hecho, para $(n-1)x \leq W \leq nx$ esto da una solución con ningún rechazo.

---

Cualquiera de estos métodos puede ser adaptado para el problema más general en el que cada cubo tiene una capacidad de especificar de manera individual, es decir, donde la restricción es $0 \leq w_i \leq x_i.$

Answer 3

Creo que lo que están pidiendo es que puedo vacío W, x dada y n. Es decir, que yo inicie con $W$ y verter en cada una de las $w_i$ $i \in [1,n]$ hasta su capacidad de entre $[0,x]$ es completa. Entonces, si después de rellenar $w_n$ tenemos agua de sobra, no podemos hacerlo. Así que queremos: $$P(\sum_{i=1}^{n}w_i- W=0|w_1=x) =P(\frac Wn\le x|w_1=x)= {1, \ W\le nx \brace 0, \ W>nx}$$

Usted podría hacer más interesante por tener $w_i \in [0,x_i]$. De esa manera, al menos, de asignar un "valor aleatorio" a$w_i$, por lo que cada uno de ellos es diferente.

Lo siento si he interpretado mal tu pregunta.

Answer 4

EDIT: he tenido una respuesta diferente, pero Darq señaló que no era correcto.

Discretizar el problema, dicen que todos los valores son enteros. (Si son racionales para comenzar con, usted puede multiplicar por un común denominador.) Repetidamente hacer lo siguiente: tomar una unidad de agua y agregar al azar a cualquier no-depósito lleno.