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

Se puede calcular explícitamente la derivada distribucional de una función indicadora para demostrar el teorema de la divergencia. En particular, si $1_A$ es una función indicadora en un conjunto acotado y abierto $A$, entonces $$\langle \partial_j 1_A, \varphi\rangle = \int_{\partial A} \nu_j(x) \varphi(x) \,\mathrm dS(x)$$ donde $\nu$ es la normal unitaria.

Answer 2

Prueba excesivamente complicada para la fórmula de la suma de los grados de los vértices

Tome la matriz de adyacencia $A$ de un grafo simple no dirigido $G=(V,E)$: $$A := \big[ 1_E (\{v,w\}) \big]_{v,w=1}^n.$$ Sean $x$, $y\in\mathbb R^n$. Luego, calcule $$y^{\rm T}\!Ax = \sum_{v\in V} \, \sum_{w\in V} y_v A_{v,w} x_w \tag{1}$$ y note que $$y^{\rm T}\!Ax = \sum_{v\in V} y_v \Big( \sum_{w\in V} 1_E (\{v,w\}) \, x_w \Big). \tag{2}$$ Pero también note que, dado que $A$ es simétrica y tiene hasta $2|E|$ entradas no nulas, la $(1)$ se puede reorganizar como $$y^{\rm T}\!Ax = \sum_{\{v,w\}\in E} (y_v x_w + y_w x_v). \tag{3}$$ Sustituir $y = x = \vec 1$ en $(1)$ tiene el efecto de contar cuántas entradas no nulas tiene $A$: sustituir en $(2)$ y $(3)$ y igualarlos da $$\sum_{v\in V} \color{blue}{\Big( \sum_{w\in V} 1_E (\{v,w\}) \Big)} = \color{red}{\sum_{\{v,w\}\in E} (\color{green}{1+1})}.$$ O equivalentemente, $$\sum_{v\in V} \color{blue}{\deg(v)} = \color{green}{2} \color{red}{|E|}. \tag*{$\square$}$$

---

Otra forma de expresarlo que no requiere la matriz de adyacencia

Sea $f:V\times V\to\mathbb R$, entonces la doble suma sobre los vértices se puede dividir como $$\sum_{v\in V} \sum_{w\in V} f(v,w) = \sum_{v\in V} \sum_{w\in V,\\ w Luego, note que una suma sobre las aristas se puede ver como $$\sum_{\{v,w\}\in E} g(v,w) = \sum_{v\in V} \sum_{w\in V,\\ w para un $g:V\times V\to\mathbb R$ adecuado. Aquí, $\Gamma(v) \subsetneq V$ denota el conjunto de vértices que son vecinos de $v$, pero $1_{\Gamma(v)} (w)$ también puede considerarse como $1_E (\{v,w\})$. Ahora, eligiendo $f(v,w) := 1_{\Gamma(v)} (w)$ (para que $1_{\Gamma(v)} (w) = 1_{\Gamma(w)} (v)$ y $f(v,v) = 0$) lleva a la elección de $g(v,w) = 2$ para relacionar las tres sumas: \begin{align} \sum_{v\in V} \color{blue}{ \sum_{w\in V} 1_{\Gamma(v)} (w) } &= \sum_{v\in V} \sum_{w\in V,\\ w O equivalentemente, $$\sum_{v\in V} \color{blue}{\deg(v)} = \color{green}{2} \color{red}{|E|}. \tag*{$\square$}$$

---

Edición: Oye, recordé otro más

Sea $D := \big[ \delta_{v,w} \cdot \deg(v) \big]^n_{v,w=1}$ la matriz de grados y $A := \big[ 1_E (\{v,w\}) \big]^n_{v,w=1}$ la matriz de adyacencia para un grafo simple, no dirigido $G=(V,E)$, de manera que $L:=D-A$ sea su matriz Laplaciana. Luego $$x^{\rm T}\!Lx = \sum_{\{v,w\}\in E} (x_v-x_w)^2.$$

Prueba usando funciones indicadoras

Observe que la entrada $v$-ésima de $Lx$ es \begin{align} (Lx)_v &= \deg(v) \, x_v - \sum_{w\in\Gamma(v)} x_w \\ &= \sum_{w\in\Gamma(v)} (x_v-x_w) \\ &= \sum_{w\in V} 1_{\Gamma(v)} (w) \cdot (x_v-x_w). \end{align} Entonces, \begin{align} y^{\rm T}\!Lx &= \sum_{v\in V} y_v (Lx)_v \\ &= \sum_{v\in V} \sum_{w\in V} 1_{\Gamma(v)} (w) \cdot y_v(x_v-x_w). \end{align} Elija $f(v,w) := 1_{\Gamma(v)} (w) \cdot y_v(x_v-x_w)$ de modo que $1_{\Gamma(v)} (w) = 1_{\Gamma(w)} (v) = 1_E (\{v,w\})$ y $f(v,v)=0$, luego distribuya la suma sobre la mitad de los índices: \begin{align} y^{\rm T}\!Lx &= \sum_{v\in V} \sum_{w\in V, \\ w Elija $g(v,w) = y_v(x_v-x_w) + y_w(x_w-x_v) = (y_v-y_w)(x_v-x_w)$ para relacionar la suma doble dividida con una sola suma sobre las aristas: $$y^{\rm T}\!Lx = \sum_{\{v,w\}\in E} (y_v-y_w)(x_v-x_w).$$ Al permitir que $y=x$ se obtiene el resultado. $\ \square$

Answer 3

Dado un entero $n\ge 2$, prueba que $$\lfloor \sqrt n \rfloor + \lfloor \sqrt[3]n\rfloor + \cdots +\lfloor \sqrt[n]n\rfloor = \lfloor \log_2n\rfloor + \lfloor \log_3n\rfloor + \cdots +\lfloor \log_nn\rfloor$$

Prueba: Para cualquier $0\le x\le n$, tenemos que $[x]=\sum_{i=1}^n\chi(x\ge i)$, donde $\chi(\cdot)$ es la función indicadora.

\begin{align} LHS&=\sum_{j=2}^n\sum_{i=1}^n\chi(\sqrt[j]{n}\ge i)\\ &=\sum_{i=1}^n\sum_{j=2}^n\chi(\sqrt[j]{n}\ge i)\\ &=n-1+\sum_{i=2}^n\sum_{j=2}^n\chi(n\ge i^j)\\ &=\sum_{i=2}^n\sum_{j=1}^n\chi(n\ge i^j)\\ &=\sum_{i=2}^n\sum_{j=1}^n\chi(\log_i^n\ge j)\\ &=\sum_{i=2}^n[\log_i^n]=RHS. \end{align}

Answer 4

El problema de optimización $$\min_{x \in S} f(x)$$ donde $S \subset \mathbb R^n, f : \mathbb R^n \to \mathbb R \cup \{+\infty\}$ es equivalente al problema sin restricciones $$\min_{x \in \mathbb R^n} f(x) + (1-1_S(x)) \cdot(+ \infty) $$ aquí usamos la convención $(+\infty) \cdot 0 = 0$. La reducción permite construir la teoría de la dualidad solo para problemas sin restricciones, el caso de problemas con restricciones entonces viene "gratis".

Además, aproximar el término $(1-1_S(x)) \cdot(+ \infty)$ con una familia de funciones más adecuada y factible es la idea principal de los métodos de penalización. A saber: método de penalización exterior y método de penalización interior.