politopo aleatorio

Dejar${\displaystyle \mathrm {K} }$sea ​​el conjunto de cuerpos convexos en${\displaystyle \mathbb {R} ^{d}}$. Asumir${\displaystyle K\in \mathrm {K} }$y consideremos un conjunto de puntos distribuidos uniformemente${\displaystyle x_{1},...,x_{n}}$en${\displaystyle K}$. La envoltura convexa de estos puntos,${\displaystyle K_{n}}$, se denomina politopo aleatorio inscrito en${\displaystyle K}$.${\displaystyle K_{n}=[x_{1},...,x_{n}]}$donde el conjunto${\displaystyle [S]}$representa la envoltura convexa del conjunto. ^{[ 2 ]} Definimos${\displaystyle E(k,n)}$ser el volumen esperado de${\displaystyle K-K_{n}}$Para un tamaño suficientemente grande${\displaystyle n}$y dado${\displaystyle K\in \mathbb {R} ^{n}}$.

• vol${\displaystyle K({\frac {1}{n}})\ll E(K,n)\ll }$vol${\displaystyle K({\frac {1}{n}})}$^{[ 2 ]}
  • Nota: Se puede determinar el volumen de la parte húmeda para obtener el orden de magnitud de${\displaystyle E(K,n)}$en lugar de determinar${\displaystyle E(K,n)}$. ^{[ 3 ]}
• Para la unidad de bola${\displaystyle B^{d}\in \mathbb {R} ^{d}}$, la parte mojada${\displaystyle B^{d}(v\leq t)}$es el anillo${\displaystyle {\frac {B^{d}}{(1-h)B^{d}}}}$donde h es de orden${\displaystyle t^{\frac {2}{d+1}}}$:${\displaystyle E(B^{d},n)\approx }$vol${\displaystyle B^{d}({\frac {1}{n}})\approx n^{\frac {-2}{d+1}}}$^{[ 2 ]}

Dado que tenemos${\displaystyle V=V(x_{1},...,x_{d})}$es el volumen de una tapa más pequeña cortada de${\displaystyle K}$por aff${\displaystyle (x_{1},...,x_{d})}$, y${\displaystyle F=[x_{1},...,x_{d}]}$es una faceta si y solo si${\displaystyle x_{d+1},...,x_{n}}$están todos en un lado de la afición${\displaystyle \{x_{1},...,x_{d}\}}$.

• ${\displaystyle E_{\phi }(K_{n})={{n} \choose {d}}\int _{K}...\int _{K}[(1-V)^{nd}+V^{nd}]\phi (F)dx_{1}...dx_{d}}$. ^{[ 2 ]}
  • Nota: Si${\displaystyle \phi =f_{d-1}}$(una función que devuelve la cantidad de caras de dimensión d-1), entonces${\displaystyle \phi (F)=1}$y la fórmula se puede evaluar para conjuntos convexos suaves y para polígonos en el plano.

Supongamos que se nos da una distribución de probabilidad multivariada sobre${\displaystyle (\mathbb {R} ^{d}\times \{0,1\})^{m}=(p_{1}\times i_{1},\dots ,p_{m}\times i_{m})^{m}}$eso es

1. Absolutamente continuo en${\displaystyle (p_{1},\dots ,p_{d})}$con respecto a la medida de Lebesgue .
2. Genera 0 o 1 para el${\displaystyle i}$s con probabilidad de${\displaystyle {\frac {1}{2}}}$cada.
3. Asigna una medida de 0 al conjunto de elementos en${\displaystyle (\mathbb {R} ^{d}\times \{0,1\})^{m}}$que corresponden a politopos vacíos.

Dada esta distribución y nuestras suposiciones, se cumplen las siguientes propiedades:

• Se deriva una fórmula para el número esperado de${\displaystyle k}$caras dimensionales en un politopo en${\displaystyle \mathbb {R} ^{d}}$con${\displaystyle m}$restricciones:${\displaystyle E_{k}(m)=2^{d-k}\sum _{i=d-k}^{d}{{i} \choose {d-k}}{{m} \choose {i}}/\sum _{i=0}^{d}{{m} \choose {i}}}$. (Nota:${\displaystyle \lim _{m\to \infty }E_{k}(m)={{d} \choose {d-k}}2^{d-k}}$dónde${\displaystyle m>d}$). El límite superior, o peor caso, para el número de vértices con${\displaystyle m}$Las restricciones son mucho mayores:${\displaystyle V_{max}={m-[{\frac {1}{2}}(d+1)] \choose m-d}+{m-[{\frac {1}{2}}(d+2)] \choose m-d}}$. ^{[ 1 ]}
• La probabilidad de que una nueva restricción sea redundante es:${\displaystyle \pi _{m}=1-{\frac {2\sum _{i=0}^{d-1}{{m-1} \choose i}}{\sum _{i=0}^{d}{m \choose i}}}}$. (Nota:${\displaystyle \lim _{m\to \infty }{\pi _{m}}=1}$y a medida que añadimos más restricciones, la probabilidad de que una nueva restricción sea redundante se acerca al 100%). ^{[ 1 ]}
• El número esperado de restricciones no redundantes es:${\displaystyle C_{d}(m)={\frac {2m\sum _{i=0}^{d-1}{{m-1} \choose i}}{\sum _{i=0}^{d}{{m} \choose i}}}}$. (Nota:${\displaystyle \lim _{m\to \infty }C_{d}(m)=2d}$). ^{[ 1 ]}