# Expected value – Some “solutions”

(Follow-up to Expected value.)

This problem is known as the St. Petersburg paradox, and it was studied in the 18th century by Daniel Bernoulli and other mathematicians. In this post we will do a simple expected value analysis, but any kind of realistic analysis must consider the phenomenon of risk aversion.

#### Expected value

Let’s call Hi the event where a head appears at the i-th toss, and Hi the event where a tail appears at the same toss number. If we call Pn the probability that n tosses are required to get a head, we have:

$\displaystyle P_1 = P(H_1) = \frac{1}{2}$

$\displaystyle P_2 = P(T_1) P(H_2) = \frac{1}{2}\frac{1}{2} = \frac{1}{4}$

$\displaystyle P_3 = P(T_1) P(T_2) P(H_3) = \frac{1}{2}\frac{1}{2} \frac{1}{2} = \frac{1}{8}$

and, generalizing,

$\displaystyle P_n = P(T_1) P(T_2) \hdots P(T_{n-1}) P(H_n) = \left(\frac{1}{2}\right)^n = \frac{1}{2^n}$

As the bettor receives $2n from the house if n tosses are required, the expected balance is $\displaystyle E[H] = \sum_{n=1}^\infty P_n 2^n - 100 = \sum_{n=1}^\infty \frac{2^n}{2^n} - 100 = \sum_{n=1}^\infty 1 - 100 = \infty$. So it would seem a perfect bet to make: what can be better than a bet with “infinite expected value”? ðŸ˜€ #### Simulation Let’s make a simulation to check if this result is reasonable: import random N = 10000 def get_tosses_until_head(): tosses = 0 while True: coin = random.randint(0, 1) tosses += 1 if coin == 0: break return tosses def get_balance(): balance = -100 tosses = get_tosses_until_head() balance += 2 ** tosses return balance def main(): random.seed(0) min_balance = max_balance = accum_balance = get_balance() for i in xrange(1, N): balance = get_balance() if balance < min_balance: min_balance = balance if balance > max_balance: max_balance = balance accum_balance += balance print 'Statistics after %d tries:' % N print ' Minimum balance: %d' % min_balance print ' Average balance: %d' % (float(accum_balance) / N) print ' Maximum balance: %d' % max_balance if __name__ == '__main__': main()  Running the simulation we get: Statistics after 10000 tries: Minimum balance: -98 Average balance: -75 Maximum balance: 32668  The average seems quite negative, how can we reconcile this with an “infinite expected value”? The answer is the same as in the case of the martingale: low probability events with huge returns skew the expected balance. Let’s see how the normal expected value estimator works with a random variable $X$, with finite expected value $\bar{x}$ and finite variance $\sigma^2_X$: $\displaystyle \widehat{x} = \frac{1}{N}\sum_{i=0}^N X_i$ $\displaystyle E[\widehat{x}] = E[\frac{1}{N}\sum_{i=0}^N X_i]$ $\displaystyle E[\widehat{x}] = \frac{1}{N}\sum_{i=0}^N E[X_i]$ (linearity of expectation) $\displaystyle E[\widehat{x}] = \frac{1}{N}\sum_{i=0}^N \bar{x}$ ($X_i$ are identically distributed) $\displaystyle E[\widehat{x}] = \bar{x}$ (the estimator is unbiased) $\displaystyle \sigma^2(\widehat{x}) = E[\widehat{x}^2 - E[\widehat{x}]^2]$ $\displaystyle \sigma^2(\widehat{x}) = E[\widehat{x}^2 - \bar{x}^2]$ ($\bar{x}$ is an unbiased estimator) $\displaystyle \sigma^2(\widehat{x}) = E[\widehat{x}^2] - \bar{x}^2$ (linearity of expectation; $\bar{x}$ is a number) Replacing $\widehat{x}$ by its definition and focusing in $E[\widehat{x}^2]$: $\displaystyle E[\widehat{x}^2] = E\left[\left(\frac{1}{N}\sum_{i=0}^N X_i\right)^2\right]$ $\displaystyle E[\widehat{x}^2] = \frac{1}{N^2}E\left[\left(\sum_{i=0}^N X_i\right)^2\right]$ (linearity of expectation) $\displaystyle E[\widehat{x}^2] = \frac{1}{N^2}E\left[\sum_{i=0}^N\sum_{j=0}^N X_i X_j\right]$ (square of a multinomial) $\displaystyle E[\widehat{x}^2] = \frac{1}{N^2}\sum_{i=0}^N\sum_{j=0}^N E[X_i X_j]$ (linearity of expectation) $\displaystyle N^2 E[\widehat{x}^2] = \sum_i E[X_i^2] + \sum_{\substack{i, j \\ j \ne i}} E[X_i] E[X_j]$ ($X_i$ is independent of $X_j$ if $i \ne j$) $\displaystyle N^2 E[\widehat{x}^2] = N E[X_i^2] + (N^2 - N) \bar{x}^2$ ($X_i$ are identically distributed) Integrating this result in the $\sigma^2(\widehat{x})$ expression: $\displaystyle \sigma^2(\widehat{x}) = \frac{N}{N^2} E[X_i^2] + \frac{N^2 - N}{N^2} \bar{x}^2 - \bar{x}^2$ $\displaystyle \sigma^2(\widehat{x}) = \frac{N}{N^2} E[X_i^2] - \frac{N}{N^2} \bar{x}^2$ $\displaystyle \sigma^2(\widehat{x}) = \frac{1}{N} \sigma^2_X$ This guarantees the convergence of the estimator to the expected value. But in our case there is no expected value (“it’s infinite”) and, consequently, we cannot even define the variance. Then the simulation is not very useful to get the expected value, as the estimator doesn’t need to converge to the expected value. #### House without unbounded wealth One (very realistic) situation where even the expected balance is negative is when the house has reasonably bounded wealth. For example, if we are betting against an agent whose possessions are merely equal to the entire world (!), the amounts we can be paid are bounded by ~$ 200·1012, giving a very different expected value:

$\displaystyle E[H] = \sum_{n=1}^\infty P_n \min(2^n, 200\cdot10^{12}) - 100$

$\displaystyle E[H] = \sum_{n=1}^{47} \frac{2^n}{2^n} + \sum_{n=48}^\infty \frac{200\cdot10^{12}}{2^n} - 100$

$\displaystyle E[H] = 47 + \frac{200\cdot10^{12}}{2^{47}}\sum_{n=1}^\infty \frac{1}{2^n} - 100$

$\displaystyle E[H] = 47 + \frac{200\cdot10^{12}}{2^{47}} - 100 < 47 + 2 - 100 = -51$

# Expected value

(In memory of Toxie ðŸ˜€ )

Let’s suppose the following bet were proposed:

• The bettor pays $100 to the house. • An honest coin is tossed until a head appears. • The bettor receives$ 2n from the house, being n the number of coin tosses.

Is this bet worth making? Why?

An analysis will be given in the next post.

# 400 teracycles, 200 gigabytes, 7 collisions

(Follow-up to Sumando subconjuntos â€“ La respuesta.)

#### Introduction

In a previous post (and in a comment from Guille [É¡iËˆÊ’e] ðŸ˜€ ) we have seen how the pigeonhole principle implies that a set of 70 numbers in the range [1018, 1019) must have two subsets with equal sum. But this is a non-constructive proof, as it doesn’t give us the two subsets with the same sum. To rectify this omission, in this post we will see how this “sum collision” can be obtained.

#### Finding collisions: simple cases

We can start by defining the problem in a more general way: given a sequence of elements xi and a function f(), find two elements of the sequence, xj and xk, such that f(xj) = f(xk). In this way the sum collision problem can be reduced to finding a duplicate in the associated sequence of sums, f(xi).

Two common ways to get duplicates in a sequence are the following:

def find_duplicate_sort(g):
sl = sorted(g)
prev = None
for e in sl:
if e == prev:
return e
prev = e
return None

def find_duplicate_set(g):
es = set()
for e in g:
if e in es:
return e
return None


The first one has O(n log n) complexity and the second one has O(1) complexity if we use a hash-based set. As the set-based approach also has a lower constant, we will use this approach in the rest of this post.

This algorithm works well if the sequences to be inspected for duplicates can be fit entirely in RAM, but in this case we have seen that tens of billions of elements must be inspected to have a high probability of finding a collision. In the next section we will analyse how this restriction can be evaded.

#### Finding collisions in big sets

Each of the subsets to be evaluated in this problem can be encoded using 70 bits and, to allow a simple and fast sum calculation algorithm to be used, this was rounded up to 10 bytes. Then, if we want to inspect 20 billion subsets of 35 elements to get a very high probability of not wasting the calculation time, we will need 200 GB to store the whole sequence. 200 GB of data cannot be stored in the RAM of an usual machine, but it’s quite easy to store this amount of data in a hard disk nowadays.

To allow a fast hash-set based RAM collision search while keeping the bulk of the data in disk, we can take the following approach:

1. Generate in RAM a big number of random subsets and sort them by their sums.
2. Find a vector of numbers (to be called “pivots”) aplitting the sorted subsets vectors by their sums in approximately equal-sized segments. (The segment n will be composed by all the subsets whose sum is between pivot n-1 and pivot n).
3. Generate in RAM a big number of random subsets and sort them by their sums.
4. Split the sorted subset vector in segments using the previously generated pivots and append each segment to an associated segment file (for example, append segment 3 to 0003.bin).
5. Repeat steps 3 and 4 until getting enough subsets.
6. Check each segment file at a time for collisions.

If we choose enough pivots, the size of each segment file will be small enough to allow easily doing step 6 with a hash-based set (each segment file won’t have the same size, as the generated subsets are random; but the law of large numbers ensures that their sizes won’t be very different).

#### Source code & parameters

The (ugly) C code that checked for collisions can be found in the repository associated with this blog. The chosen parameters were:

• Number of subsets: 2Â·1010.
• Number of subsets in RAM: 107.
• Number of elements in each subset: 35 (constant).
• Number of segments: 1000.
• Number of slots in the hash-set: 227.

#### Results

The first stage (segment file generation) elapsed time was approximately 41 hours, somewhat over my original estimation of 36 hours, and the segment file range ranged from 194827630 bytes to 206242980 bytes. The second stage (collision detection inside each segment file) lasted for 12-18 hours.

The output of the second stage (discarding files where no collisions were found) was:

Processing file 218...  Collision between identical elements.
DONE in 40.754850s.
Processing file 363...  Collision between different elements!!!
ed940f4f5710c6351a00
a35377a5a74a03961c00
DONE in 38.585990s.
Processing file 394...  Collision between different elements!!!
9ab5dfa6312e090e2a00
6558c9c8eab667233400
DONE in 35.570039s.
Processing file 409...  Collision between different elements!!!
2429d70f6ff500ab2c00
423cf8c758740ac73b00
DONE in 34.499926s.
Processing file 434...  Collision between different elements!!!
5a8bf5a532915f213100
496ebc281e9958713e00
DONE in 32.610608s.
Processing file 475...  Collision between different elements!!!
c35d3f427a7c488c0e00
4e37132b717a287a1900
DONE in 21.971667s.
Processing file 655...  Collision between different elements!!!
4653023676ea8e5f1900
6abb914e641ba45a3900
DONE in 21.514123s.
Processing file 792...  Collision between different elements!!!
8a4a63d85de377130600
853d3d45b15e0c471e00
DONE in 21.506716s.


Each set is represented as a byte string with bit number increasing when advancing through the byte string. For example, ed940f4f5710c6351a00 represents the bit string 10110111001010011111000011110010111010100000100001100011101011000101100000000000 and, consequently, the subset with indices 0, 2, 3, 5, 6, 7, 10, 12, 15, 16, 17, 18, 19, 24, 25, 26, 27, 30, 32, 33, 34, 36, 38, 44, 49, 50, 54, 55, 56, 58, 60, 61, 65, 67, 68. Its elements are

5213588008354709077 9115813602317594993
1796745334760975384 3579709154995762145
2312952310307873817 3627590721354606439
5763055694478716846 2730952213106576953
4868653895375087301 9737387704190733086
9262565481673300485 5968266991171521006
6752113930489992229 3772194655144630358
9029836747496103755 3318990262990089104
9205546877037990475 9849598364470384044
1376783969573792128 1108556560089425769
7820574110347009988 6951628222196921724
4776591302180789869 7999940522596325715
2290598705560799669 7835010686462271800
8998470433081591390 9131522681668251869
9096632376298092495 5295758362772474604
5953431042043343946 3151838989804308537
8643312627450063997 3624820335477016277
3782849199070331143


and its sum is 203743882076389458417.

In the same way, the set a35377a5a74a03961c00 has elements

5213588008354709077 9011219417469017946
3579709154995762145 3627590721354606439
5941472576423725122 4317696052329054505
2730952213106576953 5014371167157923471
9737387704190733086 9262565481673300485
5968266991171521006 5917882775011418152
5866436908055159779 9233099989955257688
3772194655144630358 3318990262990089104
9990105869964955299 2664344232060524242
1376783969573792128 1108556560089425769
7820574110347009988 9889945707884382295
7652184907611215542 8082643935949870308
4271233363607031147 6415171202616583365
6393762352694839041 2290598705560799669
7481066850797885510 5295758362772474604
5953431042043343946 9929081270845451034
7207546018039041794 3624820335477016277
3782849199070331143


and 203743882076389458417 as its sum, the same value as the previous different subset. ðŸ˜€

#### JS puzzle

The previous post asked what happened when the JS code

(function(f){f(f)})(function(g){g(g)})


was executed. In first place we can observe that the two anonymous functions are really the same, as they only differ in the name of a dummy parameter. Let’s call this function u() and observe what happens when we apply u() over a function f():

u(f) -> f(f)


It’s clear that u() applies its argument over itself. As in this case we are applying u over itself, the result will be

u(u) -> u(u)


giving us an infinite recursion.

# PorquÃ© no se puede ganar siempre

##### Respuesta al post anterior

La tÃ©cnica mostrada en el post anterior se denomina martingala y es muy antigua. Obviamente, a pesar de lo que puedan decir algunos, no funciona. Pero porquÃ© la simulaciÃ³n anterior parecÃ­a mostrar lo contrario?

El motivo principal del fallo de la simulaciÃ³n es no limitar la cantidad de dinero del jugador disponible para apostar. Como la cantidad que se requiere apostar crece exponencialmente con la cantidad de jugadas, en una cantidad relativamente pequeÃ±a de estas se excederÃ¡n las reservas del jugador y no podrÃ¡ continuar apostando.

Otro problema de la simulaciÃ³n es que, incluso una cantidad grande de simulaciones, puede obviar acontecimientos muy improbables. Esto no es problemÃ¡tico cuando los eventos en cuestiÃ³n no tienen consecuencias excepcionales pero, cuando conducen a un impacto proporcional a su improbabilidad, puede distorsionarse mucho el valor esperado (probar la nueva simulaciÃ³n Javascript con M = 100000 para N = 1000 y N = 1000000; observar las diferencias en los valores esperados estimados).

Pero puede objetarse (con razÃ³n!) que solo demostramos el fallo de una estrategia de apuesta, no de todas las posibles. Por lo tanto, a continuaciÃ³n, demostraremos que esto se aplica a cualquier estrategia.

##### PorquÃ© los sistemas no funcionan

Como en toda demostraciÃ³n matemÃ¡tica, necesitaremos hacer ciertas suposiciones sobre el problema en cuestiÃ³n:

1. El juego consiste en una cierta serie de jugadas, cada una asociada con una variable aleatoria $X_i$. Asumimos que todas las variables $X_i$ tienen la misma distribuciÃ³n.
2. En la jugada $i$ el jugador apuesta una cantidad $m_i$ a un evento aleatorio $e_i$ (donde tomamos $e_i$ como un subconjunto de lso valores que podrÃ­a tomar $X_i$).
3. Si el evento ocurre al que el jugador apostÃ³ ocurre, este recibe el monto apostado multiplicado por una constante $k(e_i)$ dependiente del evento al que apostÃ³. En caso contrario, pierde lo apostado.
4. $k(e) P(e) \le 1$.
5. Los valores de las variables aleatorias $X_1, X_2, ..., X_{i-1}$ no aportan informaciÃ³n sobre el valor de $X_i$.

Las primeras 3 suposiciones son simplemente una descripciÃ³n general de un juego de azar, mientras que 5 nos indica que las anteriores jugadas no nos dan informaciÃ³n sobre la jugada actual. La suposiciÃ³n 4 parece mÃ¡s compleja, pero esencialmente nos indica que los factores $k$ han sido correctamente elegidos por el casino.

Para ver esto, supongamos que existe un evento $e$ tal que $k(e) P(e) > 1$. Entonces, si elegimos una estrategia de apostar $N$ veces al evento $e$ un monto unitario, nuestro balance esperado serÃ¡:

$\displaystyle E[b] = E[\sum_{i=1}^N b_i]$

$\displaystyle = \sum_{i=1}^N E[b_i]$

$\displaystyle = \sum_{i=1}^N ((k(e)-1)P(e) - (1-P(e)))$

$\displaystyle = N (k(e)P(e) - 1)$

$\displaystyle > 0$,

donde $b$ es el balance general del jugador y $b_i$ el balance de la jugada $i$.

Eso implicarÃ­a que podrÃ­amos ganar simplemente repitiendo una apuesta una y otra vez (puede demostrarse sin mucha dificultad que ni siquiera necesitarÃ­amos reservas muy grandes, solo de orden $\sqrt(N)$). Como eso claramente no ocurre en los casinos, es obvio que los multiplicadores estÃ¡n elegidos correctamente (de hecho, por ejemplo en la ruleta, estÃ¡n elegidos “a favor” del casino por la existencia del cero).

Busquemos ahora el valor esperado de una estrategia de apuestas $m_i(i, X_1, X_2, ..., X_{i-1}), e_i(i, X_1, X_2, ..., X_{i-1})$:

$\displaystyle E[b] = E[\sum_{i=1}^N b_i]$

$\displaystyle = E[\sum_{i=1}^N b_i]$

$\displaystyle = \sum_{i=1}^N E[b_i]$

$\displaystyle = \sum_{i=1}^N ((k(e_i)-1)P(e_i) - (1-P(e_i)))m_i$

$\displaystyle = \sum_{i=1}^N (k(e_i)P(e_i) - 1)m_i$

siendo $e_i$ y $m_i$ las funciones anteriormente descritas. Pero la suposiciÃ³n 5 nos dice que

$P(e_i|i,X_1=x_1, X_2=x_2, ..., X_{i-1} = x_{i-1}) = P(e_i)$,

es decir que esa informaciÃ³n no nos modifica la probabilidad de ningÃºn evento y, en particular, de $e_i$. Combinando con la suposiciÃ³n 4 llegamos a

$\displaystyle E[b] \le 0$,

siempre que $m_i$ sea positivo, como es razonable.

##### Caminos de escape

Aunque una demostraciÃ³n fuera perfecta, sus conclusiones nunca serÃ¡ mÃ¡s fuertes que sus hipÃ³tesis. En esta secciÃ³n analizaremos algunas formas en las que las hipÃ³tesis pueden ser falsas:

mi < 0: Este es esencialmente el mÃ©todo utilizado por los casinos. Suele ser bastante complejo de seguir, pero muy redituable ðŸ™‚

Fallo en la hipÃ³tesis 4: Los multiplicadores son fÃ¡ciles de determinar conociendo las probabilidades y generalmente se utilizan probabilidades “nominales” (por ejemplo, suponer equiprobables a los 37 o 38 nÃºmeros de la ruleta). Pero si algÃºn observador encuentra evidencia que lo mueva a probabilidades distintas de las nominales, puede que existan apuestas con valor esperado positivo.

Fallo en la hipÃ³tesis 5: Pueden existir correlaciones no esperadas entre las variables aleatorias. Esto es mÃ¡s comÃºn en los juegos por computadora, que suelen usar nÃºmeros pseudoaleatorios y, en algunos casos, tienen errores de implementaciÃ³n que vuelven predecibles las secuencias generadas.

# Como ganar siempre :-)

Un sistema de apuestas, muy utilizado por lo que puede verse en Google, sigue el siguiente esquema (donde lo aplicamos a una apuesta doble o nada con una moneda “justa”):

1. Empezar apostando una unidad.
2. Apostar a “cara”.
3. En caso de ganar, retirarse.
4. En caso de perder, doblar la apuesta y volver al paso 2.

Analicemos este sistema mediante un millÃ³n de simulaciones de la tÃ©cnica, utilizando 3 lenguajes de programaciÃ³n: C++ (codepad), Python (codepad, N = 1000) y Javascript.

Como puede observarse, los resultados son esencialmente idÃ©nticos:

Number of simulations: 1000000
Minimum player balance: 1
Maximum player balance: 1
Average number of rounds before winning: 2.000831

En todas las ejecuciones observamos una ganancia fija de una unidad y que se obtiene en promedio en una pequeÃ±a cantidad de tiradas.

Donde estÃ¡ el problema con este sistema? En el prÃ³ximo post la respuesta… ðŸ˜€

# Ruido blanco

Uno de los elementos fundamentales para la generaciÃ³n de contenido procedural es el ruido. Empezaremos por la forma de ruido mÃ¡s simple, el ruido blanco.

Una imagen bidimensional compuesta por ruido blanco

como oirse (bajar el volumen antes de escuchar el sonido!).

Se denomina de esta forma a una seÃ±al que posee las distintas componentes espectrales “en igual proporciÃ³n”. Dese el punto de vista de las seÃ±ales continuas es solo una idealizaciÃ³n ya que, si tuviera una potencia no nula en una banda espectral dada, tendrÃ­a que tener una potencia total infinita. Pero en las seÃ±ales discretas, al estar su frecuencia acotada superiormente, es posible tener un “espectro plano”. (TambiÃ©n es posible definir ruido blanco en una banda de frecuencias dadas para seÃ±ales continuas, pero eso no es el tema que trataremos en este post.)

Una forma comÃºn de generar ruido blanco es mediante el uso de muestras aleatorias independientes repartidas uniformemente en un intervalo. Por ejemplo, la imagen y el archivo WAV anteriormente mostrados fueron generadas mediante los siguientes scripts:

# requires PIL 1.1.6
# http://www.pythonware.com/products/pil/
import Image, random

def make_white_noise(fname, size):
im = Image.new('L', size)
for i in range(size[0]):
for j in range(size[1]):
pix[i, j] = random.randint(0, 255)
im.save(fname)

if __name__ == '__main__':
make_white_noise('white_noise.png', (256, 256))


import random, struct, wave

def make_white_noise(fname, time):
wfp = wave.open(fname, ‘w’)
wfp.setparams((1, 2, 44100, 0, ‘NONE’, None))
for i in xrange(44100*time):
wfp.writeframesraw(
struct.pack(‘h’,
random.randint(-1<<15, 1<<15-1))) wfp.close() if __name__ == '__main__': make_white_noise('white_noise.wav', 1) [/code] En lo que resta de este post analizaremos porquÃ© esto funciona…

#### Varianza y correlaciÃ³n

La varianza de una variable aleatoria es una medida de la dispersiÃ³n de sus valores y se define, para el caso de una variable aleatoria real $X$, como:

$\sigma^2(X) = E[X^2] - E[X]^2$

donde $E[.]$ representa al valor esperado. Utilizando la propiedad de linealidad del valor esperado podemos llegar a la siguiente identidad:

$\sigma^2(X + Y) = E[(X+Y)^2] - E[X+Y]^2$

$\sigma^2(X + Y) = E[(X+Y)^2] - (E[X]+E[Y])^2$

$\sigma^2(X + Y) = E[X^2+2XY+Y^2] - (E[X]^2+2E[X]E[Y]+E[Y]^2)$

$\sigma^2(X + Y) = (E[X^2]-E[X]^2)+2(E[XY]-E[X]E[Y])+(E[Y^2]-E[Y]^2)$

$\sigma^2(X + Y) = \sigma^2(X)+\sigma^2(Y)+2(E[XY]-E[X]E[Y])$.

El tÃ©rmino que aparece sumado a las varianzas se denomina (bueno, en realidad la mitad de ese tÃ©rmino se denomina…) covarianza y se anula si las variables aleatorias son independientes ya que:

$E[XY] = \int_{\mathbb{R}^2} xy h(x, y) dx dy$

$E[XY] = \int_{\mathbb{R}^2} xy f(x) g(y) dx dy$

$E[XY] = \int_{\mathbb{R}} x f(x) dx \int_{\mathbb{R}} y g(y) dy$

$E[XY] = \int_{\mathbb{R}} x f(x) dx \int_{\mathbb{R}} y g(y) dy$

$E[XY] = E[X]E[Y]$,

donde llamamos $f(x)$ a la densidad de probabilidad de $X$, $g(y)$ a la densidad de probabilidad de $Y$ y $h(x, y)$ a la densidad de probabilidad conjunta, ademÃ¡s de suponer que $X$ e $Y$ son independientes.

Por lo tanto, en caso de ser $X$ e $Y$ variables aleatorias independientes tendremos:

$\sigma^2(X + Y) = \sigma^2(X)+\sigma^2(Y)$.

#### Espectro de una seÃ±al compuesta por muestras independientes y distribuidas uniformemente

Llamemos $x_n$ a la seÃ±al compuesta por $N$ muestras independientes distribuidas uniformemente en $[-1, 1]$ y $X_k$ a su DFT. Entonces tendremos

$X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} k n}$.

Como $E[x_n]$ es nulo, cada tÃ©rmino de la suma tendrÃ¡ un valor esperado nulo y, por lo tanto, $E[X_k]$ es nulo. Pero estamos interesados en la distribuciÃ³n de potencia por intervalo espectral, por lo que debemos observar a $E[|X_k|^2]$ en lugar de a $E[X_k]$.

Aplicando directamente la definiciÃ³n y operando algebraicamente tenemos:

$E[|X_k|^2] = E\left[\left|\sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} k n}\right|^2\right]$

$E[|X_k|^2] = E\left[\left|\sum_{n=0}^{N-1} x_n \left(\cos\left(-\frac{2 \pi}{N} k n\right) + i \sin\left(-\frac{2 \pi}{N} k n\right) \right) \right|^2\right]$

$E[|X_k|^2] = E\left[\left|\sum_{n=0}^{N-1} x_n \cos\left(-\frac{2 \pi}{N} k n\right) + i \sum_{n=0}^{N-1} x_n \sin\left(-\frac{2 \pi}{N} k n\right) \right|^2\right]$

$E[|X_k|^2] = E\left[\left(\sum_{n=0}^{N-1} x_n \cos\left(-\frac{2 \pi}{N} k n\right)\right)^2 + \left(\sum_{n=0}^{N-1} x_n \sin\left(-\frac{2 \pi}{N} k n\right)\right)^2 \right]$.

Ahora, como los valores de $x_n$ son independientes, tenemos que la covarianza entre dos elementos distintos cualesquiera para cada una estas sumas serÃ¡ nula. Eso nos permite, junto con el hecho de que $E[x_n] = 0$, transformar la expresiÃ³n anterior a la siguiente:

$E[|X_k|^2] = E\left[\sum_{n=0}^{N-1} x_n^2 \cos^2\left(-\frac{2 \pi}{N} k n\right) + \sum_{n=0}^{N-1} x_n^2 \sin^2\left(-\frac{2 \pi}{N} k n\right) \right]$.

Aplicando una identidad bien conocida ðŸ™‚ y distribuyendo a $E[.]$ aprovechando su linealidad, llegamos a:

$E[|X_k|^2] = \sum_{n=0}^{N-1} E[x_n^2]$.

Aunque podrÃ­amos encontrar el valor exacto, no es de mucha importancia ya que podemos observar algo mucho mÃ¡s importante: no depende de $k$. Eso nos indica que el espectro “es plano”, el resultado que buscÃ¡bamos. (En realidad lo que es plano no es “el” espectro sino su valor esperado; pero eso es lo que suele interesar en el caso de una seÃ±al aleatoria.)

# Un problema de probabilidad

En un juego, se presentan a una persona dos sobres. Sabe que uno de ellos contiene una cantidad desconocida de dinero ‘A’, y que el otro contiene el doble de esa cantidad, pero el jugador desconoce “cuÃ¡l es cual”. Se le dice que puede llevarse solo uno de los sobres y que debe llevarse el Ãºltimo sobre que abra.

La pregunta es: despuÃ©s de haber elegido y abierto un sobre, le conviene cambiarlo por el otro?

La respuesta intuitiva es “no”, ya que ver el contenido del sobre no nos permite discriminar entre el caso en que elegimos el sobre con la cantidad A y el caso en que elegimos el sobre con al cantidad 2A. Al no tener evidencia proveniente de ver el contenido del sobre, el intercambio nos serÃ­a indiferente.

Ahora supongamos que calculamos el valor esperado del contenido del sobre no abierto, al que denominaremos “sobre 2”. Si llamamos B al contenido del sobre abierto, el sobre 2 puede tener contenido B/2 o 2B. Asumiendo la indiferencia mencionada anteriormente, el valor esperado del contenido del sobre 2 serÃ­a:

E(contenido sobre 2) = 1/2 B/2 + 1/2 2B = B/4 + B = 5/4 B

Esto implicarÃ­a que siempre nos serÃ­a conveniente realizar el intercambio!

MÃ¡s detalles sobre el problema y sus implicaciones en Wikipedia