Punto de pequeña distancia máxima a puntos arbitrarios de la $n$ $m$-cubo dimensional unidad

Question

Informalmente hablando, si $n$ personas que viven en los vértices de la $m$-dimensiones de la unidad de cubo de $C_m$ quiere tener una fiesta en el más conveniente vértice de $C_m$ (posiblemente en una de las $n$ vértices en sí), ¿cuál es el peor de los casos la distancia máxima en términos de $m$ $n$ que cualquiera de ellos puede tener para viajar en el "Manhattan" o $\ell_1$ métrica (que es: a lo largo de los bordes del cubo). Tenga en cuenta que esto se refiere a la mejor elección del lugar de la fiesta sujeto a la minimización de el viaje más largo, con la peor distribución de la gente en ese sentido

Formalmente hablando, estoy definiendo $D_{m,n} \in \mathbb{N}$ a un mínimo tal que se cumple lo siguiente: $$\forall x_1, x_2, ..., x_n \in C_m ~ \exists ~ c\in C_m ~\forall~ 1\leq i \leq n: d_1(x_i,c) \leq D_{m,n}$$ donde $(C_m,d_1)$ es la métrica subespacio $\lbrace0,1\rbrace^m$$(\mathbb{R}^m,||\cdot||_1)$.

Mis limitados progresos realizados hasta la fecha:

Por la desigualdad de triángulo, puedo ver que $D_{m,2}=\lceil\frac{m}{2}\rceil$. Puedo ver no puede ser menor en el caso de $x_1=(0,0,...,0), x_2=(1,1,...,1)$.

El ejemplo simple de $m=2$ $n=4$ cuando la $x_i$ son todos los diferentes vértices de la plaza de la muestra que $D_{2,4}=2 > D_{2,2}=1$. Por lo $D_{m,n}$ sin duda alguna manera aumenta con la $n$ si $m$ se mantiene constante. Yo simplemente no acaba de ver cómo. Por ejemplo, todavía no he conseguido construir una distribución que muestra que $D_{12,4}>6=D_{12,2}$.

Yo estaría muy agradecido por cualquier sugerencia de una manera de pensar acerca de este sistemáticamente sin carácter exhaustivo la simulación!

Answer 1

Por un Chernoff obligado, la fracción de ubicaciones dentro de $\frac m2 + k \sqrt{\frac m2}$ pasos de un asistente es de $p \le e^{-k^2/3}$. Por lo tanto, si usted tiene menos de $e^{k^2/3}$ asistentes, usted será capaz de encontrar un lugar dentro de las $\frac m2 + k\sqrt{\frac m2}$ pasos de cada uno de ellos.

También, si la ponemos abajo de $n$ de los asistentes al azar vértices del cubo, a continuación, para cada lugar, la probabilidad de que dentro de $\frac m2 + k\sqrt{\frac m2}$ pasos de cada uno de ellos es $(1-p)^n < e^{-pn}$, por lo que si establecemos $n = \frac{m \ln 2}{p}$, esta probabilidad es menor que $2^{-m}$. El esperado número de lugares en los que el trabajo es menos de $1$, por lo que hay alguna opción de $ \frac{m \ln 2}{p}$ a los asistentes para que no hay ningún lugar es esto conveniente.

Así que sea cual sea el valor real de $p$ es para un determinado$m$$k$, tenemos $$ D_{m, 1/p} \le \frac m2 + k\sqrt{\frac m2} \quad \text{y} \quad D_{m,m\ln 2/p} \ge \frac m2 + k\sqrt{\frac m2}. $$ Si fijamos $k$ y deje $m \to\infty$,$p \to \frac{1-\text{erf}(k)}{2}$, donde erf es la función de error.