Buscando usos (excesivos) de las funciones indicadoras

Question

Voy a dar una presentación sobre las funciones indicadoras, y estoy buscando algunos ejemplos interesantes para incluir. Los ejemplos pueden ser incluso una solución exagerada ya que estoy principalmente interesado en demostrar las formas creativas de usarlo.

Estaría agradecido si compartieras tus ejemplos. Se aprecia la diversidad de respuestas.

Para darte una idea, aquí están mis ejemplos. La mayoría de mis ejemplos son en probabilidad y combinatoria, por lo que ejemplos de otros campos serían aún mejores.

1. Calcular el valor esperado de una variable aleatoria usando la linealidad de las expectativas. Más famosamente el número de puntos fijos en una permutación aleatoria.

2. Mostrando cómo $|A \Delta B| = |A|+|B|-2|A \cap B|$ y $(A-B)^2 = A^2+B^2-2AB$ están relacionados.

3. Una demostración exagerada para $\sum \deg(v) = 2|E|$.

Answer 1

Si es exagerado o no es motivo de debate, pero creo que el principio de inclusión y exclusión se ve mejor a través del prisma de las funciones indicadoras.

Básicamente, la fórmula clásica es simplemente lo que se obtiene numéricamente a partir de la (clara) identidad: $$ 1 - 1_{\bigcup_{i=1}^n A_i} = 1_{\bigcap_{i=1}^n \overline A_i} = \prod_{i=1}^n (1-1_{A_i}) = \sum_{J \subseteq [\![ 1,n ]\!]} (-1)^{|J|} 1_{\bigcap_{j\in J} A_j}.$$

Answer 2

Las funciones indicadoras son a menudo muy útiles en conjunción con el teorema de Fubini.

Supongamos que quieres demostrar: $$\newcommand\dif{\mathop{}\!\mathrm{d}} \int_Y \int_{X_y} f(x, y) \dif x \dif y = \int_X \int_{Y_x} f(x,y) \dif y \dif x$$ donde los dos subconjuntos $X_y \subseteq X$ y $Y_x \subseteq Y$ describen la misma relación $x \in X_y \iff y \in Y_x$.

Debido a la variable en el dominio de la integral interna, no puedes usar Fubini de inmediato para permutar las dos sumas directamente.

Pero puedes hacerlo si usas una función indicadora para describir el conjunto $$Z = \left\{ (x,y) \in X \times Y \mid x \in X_y \right\} = \left\{ (x,y) \in X \times Y \mid y \in Y_x \right\}.$$

Finalmente: \begin{align*} \int_Y \int_{X_y} f(x, y) \dif x \dif y & = \int_Y \int_X 1_Z(x,y) f(x,y) \dif x \dif y \\ & = \int_X \int_Y 1_Z(x,y) f(x,y) \dif y \dif x \\ & = \int_X \int_{Y_x} f(x,y) \dif y \dif x. \end{align*}

Answer 3

El Epsilon de Levi-Civita y sus identidades con el Delta de Kronecker $\delta_{ij}=\mathbb{1}_{i=j}$ son frecuentemente utilizados en cálculo vectorial.

Formalmente, en $n$ dimensiones, para la $n$-tupla $\sigma= (\sigma_1,\dots,\sigma_n)$ con elementos $\sigma_i\in\{1,\dots,n\}$, definimos

$$ \epsilon_\sigma = \left\{ \begin{align} (-1)^{\text{sgn}(\sigma)} &\text{ si } \sigma\in S_n\\ 0 \quad \quad&\text{ en otro caso} \end{align} \right. $$

Por ejemplo, en $3$ dimensiones, $\epsilon_{123}=\epsilon_{231}=1$ porque $\sigma=231$ es una permutación par (y $123$ es la identidad), mientras que $\epsilon_{213}=-1$ y $\epsilon_{112}=0$.

Para dar un ejemplo de su versatilidad, en $3$ dimensiones, la simple identidad $\epsilon_{ijk}\epsilon^{pqk}=\delta_i^p\delta_j^q - \delta_i^q\delta_j^p$ puede ser utilizada para resumir $3^4=81$ identidades porque cada uno de $i,j,p,q$ puede tomar valores en $\{1,2,3\}$. (Nota: se utiliza la convención de suma de Einstein para sumar sobre $k\in \{1,2,3\}$).

Answer 4

Aquí usamos la función indicadora con una técnica introducida en la sección 3.2 Aplicaciones de Suelo/Techo de Concrete Mathematics por R. L. Graham, D. E. Knuth y O. Patashnik. Mostramos lo siguiente es válido para $n\in\mathbb{Z}, n>0$: \begin{align*} \color{blue}{\sum_{k=1}^\infty\left\lfloor\frac{n}{2^k}+\frac{1}{2}\right\rfloor=n}\tag{1} \end{align*}

Sea $n=\sum_{j=0}^Na_j2^j$ la representación binaria de $n$ con $a_j\in\{0,1\}, 0\leq j\leq N$. Obtenemos \begin{align*} \color{blue}{\sum_{k=1}^\infty}\color{blue}{\left\lfloor\frac{n}{2^k}+\frac{1}{2}\right\rfloor} &=\sum_{k=1}^\infty\sum_{m=1}^\infty m\cdot1_{\{m\}}\left(\left\lfloor\frac{n}{2^k}+\frac{1}{2}\right\rfloor\right)\tag{2}\\ &=\sum_{k=1}^\infty\sum_{m=1}^\infty m\cdot1_{[m,m+1)}\left(\frac{n}{2^k}+\frac{1}{2}\right)\\ &=\sum_{k=1}^\infty\sum_{m=1}^\infty m\cdot1_{\left[m-\frac{1}{2},m+\frac{1}{2}\right)}\left(\frac{1}{2^k}\sum_{j=0}^Na_j2^j\right)\tag{3}\\ &=\sum_{j=0}^Na_j\sum_{k=1}^{j+1}\sum_{m=1}^\infty m\cdot1_{\left[m-\frac{1}{2},m+\frac{1}{2}\right)}\left(2^{j-k}\right)\tag{4}\\ &=\sum_{j=0}^Na_j\left(\sum_{k=1}^j2^{j-k}+1\right)\tag{5}\\ &=\sum_{j=0}^N a_j\left(\sum_{k=0}^{j-1}2^k+1\right)\tag{6}\\ &=\sum_{j=0}^Na_j 2^j\tag{7}\\ &\,\,\color{blue}{=n} y se sigue la afirmación (1).

Comentario:

• En (2) introducimos una serie sumando sobre $m$ y usamos la función indicadora para deshacernos de la función de suelo.

• En (3) usamos la representación binaria de $n$.

• En (4) usamos la linealidad del operador $\sum$. También restringimos el límite superior de la segunda suma de la izquierda con $k=j+1$ ya que otros valores de $k$ no contribuyen.

• En (5) observamos que $m$ toma el valor $2^{j-k}$ si $1\leq k\leq j$ y $m=1$ si $k=j+1$.

• En (6) desplazamos el índice por uno para comenzar con $k=0$ y también cambiamos el orden de la suma $k\to j-1-k$.

• En (7) usamos la _fórmula de la serie geométrica finita $\sum\{k=0}^{j-1}2^k=2^j-1$ y obtenemos la representación binaria de $n$.

Nota: En el libro mencionado, Don Knuth prefiere el uso de _corchetes de Iverson_, que se pueden utilizar de manera conveniente en lugar de la función indicadora.

Answer 5

Este ejemplo no es realmente un exceso, pero como es un uso interesante de la función indicadora, creo que vale la pena compartirlo aquí. Aquí usaré $\chi_A$ para indicar la función indicadora del conjunto $A$.

Sea $E \subset \Bbb R^n$ un conjunto medible, y $f\colon \Bbb R^n \to \Bbb R^m$ una función suficientemente agradable (por ejemplo, Lipschitz, o simplemente continua, digamos) que mapea conjuntos medibles $\mathscr L^n$ (medibles de Lebesgue) en conjuntos medibles $\mathscr H^n$ (medibles de Hausdorff). Estamos interesados en la función $g \colon \Bbb R^m \to \Bbb N \cup \{0\}$ definida como $$ g(y) = \#\left(E \cap f^{-1}(\{y\})\right), $$ que es el número de puntos en $E$ que se mapean al punto $y \in\Bbb R^m$. Podemos pensar en $g$ como la función indicadora de $f(E)$ pero con multiplicidad (De hecho, si $f$ es inyectiva, entonces $g=\chi_{f(E)}$).

Ahora, ¿cómo demostramos que $g$ tiene propiedades agradables (por ejemplo, que es medible, o que su integral en $\Bbb R^m$ puede ser controlada por el tamaño de $\mathscr L^n(E)$, etc.)? La idea es que podemos subdividir $\Bbb R^n$ en pequeños cubos (disjuntos) de $n$ dimensiones, e inspeccionar el comportamiento de las funciones indicadoras asociadas con la imagen de esos cubos. En particular, sea $$ M^{k} := \left\{ Q | Q = (a_1,b_1] \times \cdots \times (a_n,b_n]\text{ donde } \ a_i = \frac{j}{2^k}, b_i = \frac{j+1}{2^k}; j \in \Bbb Z \right\} $$ la familia de cubos díadicos de tamaño $\frac1{2^k}$ en $\Bbb R^n$. Es fácil ver que $\Bbb R^n$ es la unión (disjunta) de los cubos en $M^k$, es decir, $$ \Bbb R^n = \bigcup_{Q \in M^k} Q. $$

Mientras que $\chi_{f(E)}(y)$ te dice si hay algún punto en $E$ que fue enviado a $y\in\Bbb R^m$ o no, no puede "ver" cuántos puntos. Sin embargo, si consideramos $$ g_k := \sum_{Q\in M^k} \chi_{f(E\cap Q)}, $$ esta función $g_k$ puede registrar si partes distintas de $E$ fueron mapeadas por $f$ al mismo punto hasta cierto punto. Puede "apilar" contribuciones de diferentes cubos, pero aún no puede decir si los puntos en el mismo cubo fueron mapeados al mismo punto en $\Bbb R^m$. Sin embargo, a medida que $k\to\infty$, los cubos en $M^k$ se vuelven más pequeños y más pequeños, por lo que el correspondiente $g_k$ nos da una "mejor resolución", por así decirlo.

No es difícil demostrar que $g_k \to g$ monótonamente a medida que $k\to\infty$, por lo tanto podemos deducir muchas propiedades de $g$ a partir de su aproximación $g_k$. El lema de Fato también se aplica muy bien, por lo que podemos "simplemente integrar". Esta estrategia de dividir nuestro conjunto en piezas más y más finas es esencial para probar muchos resultados fundamentales en teoría de la medida, como las fórmulas de área/coárea y la fórmula del cambio de variable. Esto se debe a que cuando $f$ es (aproximadamente) diferenciable, entendemos muy bien el comportamiento de $\chi_{f(E\cap Q)}$ cuando $Q$ es muy pequeño ya que $f(E\cap Q)$ es esencialmente una distorsión afín de $E \cap Q$, determinada por $\nabla f$ en ese conjunto.