[Esame 20 Luglio 2021] Esercizio 2

[Elia-Belli]

[gpelisset]

Sia $E_i$ l'evento "la i-esima cella e' vuota" e Y_j la variabile aleatoria che indica l'indice della cella nella quale finisce la j-esima pallina
a)
$$P(E_i) = P\left(\bigcap_{j = 1}^n \{Y_j \ne i\}\right) \stackrel{(1)}{=} \prod_{j = 1}^n P(Y_j \ne i) =\prod_{j = 1}^n \left(1 - P(Y_j = i)\right) = \left(1 - \dfrac{1}{\mathcal{l}^2}\right)^n$$
dove (1) e' dovuto al fatto che le variabili aleatorie $Y_j$ con $j \in \{1, ..., n \}$ sono indipendenti.
b)
$$P(cellailibera) = P\left(\bigcap_{j = 1}^{2 l - 1} E_j\right) = P\left(\bigcap_{j = 1}^{2 l - 1} \bigcap_{k = 1}^n \{Y_k \ne j\}\right) = P\left(\bigcap_{k = 1}^n \{Y_k \notin \{1, ..., 2l - 1\} \}\right) = \prod_{k = 1}^n P\left(Y_k \notin \{1, ..., 2l - 1 \} \right) = \left(\dfrac{l^2 - (2l - 1)}{l^2}\right)^n$$
c) Vale
$$E[X] = E\left[\sum_{j = 1}^{l^2} 1_{E_j}\right] = \sum_{j = 1}^{l^2} E\left[1_{E_j}\right] = \sum_{j = 1}^{l^2} P(E_j) = \sum_{j = 1}^{l^2} \left(\dfrac{l^2 - (2l - 1)}{l^2}\right)^n = l^2 * \left(\dfrac{(l - 1)^2}{l^2}\right)^n = l^2 * \left(1 - \dfrac{1}{l}\right)^{2n} $$
d) Stimo
$$\left(1 - \dfrac{1}{l}\right)^{2 l \lfloor log l \rfloor} \sim e^{-2 \lfloor log l \rfloor} \sim l^{-2} $$
da cui
$$\lim_{l \to \infty} E[X] = \lim_{l \to \infty} l^2 l^{-2} = 1$$

[gpelisset]

I risultati sono stati controllati con la seguente simulazione

import random

def test(iterations, *tests):
    print(", ".join(t.__name__ + ": " + str(sum(t() for _ in range(iterations)) / iterations) for t in tests))


l = 10
l2 = l*l
n = l2

balls = [None] * n

def mix_balls():
    global balls
    for i in range(l2):
        balls[i] = random.randint(0, l2 - 1)

check_empty = lambda i: all(b != i for b in balls)
def check_free(i):
    col = i % l
    return all(check_empty(j) for j in range(i - col, i - col + l))and\
           all(check_empty(j) for j in range(col, l2, step=l))

# a)
def a():
    mix_balls()
    return check_empty(0)

# b)
def b():
    mix_balls()
#    return all(b >= 2 * l for b in balls)
    return check_free(0)

# c)
def c():
    mix_balls()
    return sum(check_free(i) for i in range(l2))

test(1000000, a, b, c)