Escala Logarítmica de Fatorial
A aproximação de Stirling converte um produto em uma soma, o que é o movimento fundamental que torna a matemática de grande-n manejável:
ln(n!) ≈ n·ln(n) − n + 0,5·ln(2πn)
Essa fórmula surge da aproximação da soma Σ ln(k) para k=1..n pela integral de ln(x), então aplicando a regra do trapézio para limitar o erro.
Por que Importa Geometricamente
A fórmula de volume da esfera n-dimensional envolve Γ(n/2 + 1), que para n inteiro é igual a (n/2)! ou produtos de frações inteiras. Stirling permite que estimemos esses valores para n grande sem calcular cada valor diretamente.
A aproximação de Stirling dá log(n!) ≈ n·log(n) − n·log(e) na notação base-10, útil para estimativas de ordem de grandeza.
Para n = 10: ln(10!) ≈ 10·2.303 − 10 + 0,5·ln(62,83) ≈ 23,03 − 10 + 2,08 = 15,10 (verdade: 15,104).
Para n = 100: ln(100!) ≈ 100·4,605 − 100 + 0,5·ln(628,3) ≈ 460,5 − 100 + 3,24 = 363,7 (verdade: 363,74).
Stirling em n=20
Um cálculo direto: ln(20) ≈ 2,996. ln(2π·20) = ln(125,66) ≈ 4,833.
A Fórmula de Volume
O volume de uma esfera n-dimensional de raio r:
V_n(r) = C_n · r^n onde C_n = π^(n/2) / Γ(n/2 + 1)
Os valores de C_n para pequenos n seguem um padrão usando Γ(1/2) = √π e a fórmula de redução:
- n=1: C_1 = π^(1/2)/Γ(3/2) = √π/(√π/2) = 2
- n=2: C_2 = π^1/Γ(2) = π/1 = π
- n=3: C_3 = π^(3/2)/Γ(5/2) = π^(3/2)/(3√π/4) = 4π/3
- n=4: C_4 = π²/Γ(3) = π²/2
- n=5: C_5 = π^(5/2)/Γ(7/2) = π^(5/2)/(15√π/8) = 8π²/15
Observação: C_n atinge seu pico próximo a n=5 (≈ 5.264) e depois diminui. Para grandes n, C_n → 0.
Máximo em n=5
C_5 = 8π²/15. Com π² ≈ 9.870:
C_5 = 8·9.870/15 = 78.96/15 ≈ 5.264
Para verificar que é um máximo: C_6 = π³/6 ≈ 31.006/6 ≈ 5.168. Portanto, C_6 < C_5 — o pico ocorreu em n=5.
Fração do Volume nas Esquinas
O paradoxo da esquina quantificado: qual é a fração de um n-dimensional unit hypercube [−1,1]^n que está fora da esfera inscrita de raio 1?
Fração da esquina = 1 − C_n / 2^n
| n | C_n | 2^n | Fração da esfera | Fração da esquina | |---|---|---|---|---| | 2 | 3.14 | 4 | 78.5% | 21.5% | | 3 | 4.19 | 8 | 52.4% | 47.6% | | 4 | 4.93 | 16 | 30.8% | 69.2% | | 5 | 5.26 | 32 | 16.4% | 83.6% | | 6 | 5.17 | 64 | 8.1% | 91.9% | | 10 | 2.55 | 1024 | 0.25% | 99.75% |
Implicações para Otimização
O paradoxo de cantos tem consequências diretas para a otimização em espaços de alta dimensionalidade:
Busca aleatória falha. Um ponto aleatório em um espaço de parâmetros n-dimensionais quase com certeza está em um canto - longe do origem, com valores extremos de parâmetros. Se as boas soluções se agrupam perto de valores moderados de parâmetros, a busca aleatória quase nunca as encontrar
Descida por gradiente tem sucesso. Ao seguir o gradiente local, você navega a geometria de forma sistemática em vez de amostrá-la aleatoriamente. A maldição da dimensionalidade atinge os métodos aleatórios; os métodos estruturados se adaptam
Distância se concentra. Em dimensões altas, todas as distâncias pares entre pontos aleatórios se concentram em torno do mesmo valor: todos se tornam aproximadamente √(2n/3) para pontos uniformes em [0,1]^n. Métodos de vizinho mais próximo quebram porque 'mais próximo' e 'mais distante' se tornam indistinguíveis
Prescrição de Hamming: entenda a geometria antes de confiar na sua intuição. Em espaços de alta dimensionalidade, a geometria é counterintuitive, e a matemática é a única guia confiável