Вход через социальные сети

  • 20.11.2017, 17:33
    0 up down
    Сообщение

    А какие у Вас соображения?

  • 21.11.2017, 12:56
    0 up down
    Сообщение

    Я думал следующим образом.

    Пусть в первом ряде M+N чисел, а во втором - K+N чисел, где N - это число общих элементов двух рядов. Мы выбираем соответственно m+n чисел из первого ряда и k+n чисел из второго (где n - совпадающие числа из двух рядов, k и n - соответственно несовпадающие числа, выбранные из каждого ряда). 
    Тогда, можно вычислить по формуле гипергеометрического распределения вероятность выбрать n совпадающих чисел из первого ряда, а также со второго ряда (предположив, что есть только один вариант выбрать именно те же n чисел).

    {C_{N}}^{n} * ({C_{M}}^{m} {C_{K}}^{k} / {C_{M+N}}^{m+n} {C_{K+N}}^{k+n})

    Но тогда, мы получим вероятность, что количество совпадений будет равно n, и она будет стремиться к нулю для такого порядка чисел. Плюс, в данном случае, слишком большие числа и не получится даже вычислить биноминальные коэфициенты. 

    Мне подсказали, что, возможно, для того, чтобы определить, что число n будет меньше какого-то определенного значения (такого же порядка, что и исходные данные), можно приблизить гипергеометрическое распределение нормальным, и попробовать рассматривать функции плотности распределения. То есть, рассматривать две случайные величины (например, X и Y) - количество появлений общих чисел из первого и второго ряда соответственно. Тогда, чтобы определить вероятность, что количество совпадений будет меньше n :

    P(min(X,Y)<n)=1-P(min(X,Y)>n)=1-P(X>n)P(Y>n)=1-(1-Fx(n))(1-Fy(n))=Fx(n)+Fy(n)-Fx(n)Fy(n)

    Но, в таком случае, формула гипергеометрического распределения отличается от произведений плотностей Fx(n)Fy(n) отсутствием еще одного множителя {C_{N}}^{n}в числителе. И как это учесть...

  • 21.11.2017, 19:55
    0 up down
    Сообщение

    Так Вам нужно точно вычислить вероятность или найти её приближенную оценку?

     

    Если точно, то можно искать так.

    Пусть N_1=1000000, N_2=500000, K=100000 и n_1=200000, n_2=100000, k=50000.

    Рассмотрим n_1 чисел выбранных из N_1. Сколько среди них может быть чисел из K?

    Может быть от 0 до K. При этом вероятность того, что их там i, даётся гипергеометрическим распределением f(i;N_1,K,n_1) для каждого i.

    Если i \leq k, то вероятность события (того что совпадающих не больше 50000) будет 1 не зависимо от второй выборки.

    Отсюда P_1=\sum_{i=0}^{k}f(i;N_1,K,n_1).

    Теперь рассмотрим вторую выборку (n_2 из N_2) для k < i \leq K. Сколько в этой выборке может быть чисел из i?

    Опять может быть от 0 до i. При этом вероятность того, что их там i', даётся опять гипергеометрическим распределением f(i';N_2,i,n_2) для каждого i'.

    Вероятность события равна сумме \sum_{i'=0}^{k}f(i';N_2,i,n_2).

    Отсюда P_2=\sum_{i=k+1}^{K}\sum_{i'=0}^{k}f(i';N_2,i,n_2)\cdot f(i;N_1,k,n_1).

    Искомая вероятность равна P_1+P_2.

  • 21.11.2017, 20:55
    0 up down
    Сообщение

    Приближенную оценку можно проще найти.

    Рассмотрим произвольную пару из N_1 и N_2. Всего таких пар N_1N_2. Из них совпадающих пар только K.

    Значит вероятность совпадающей пары при равновероятном выборе будет p=K/(N_1N_2)=2\cdot10^{-7}.

    Теперь возьмём две произвольные выборки n_1 и n_2, и произвольную пару из них. Всего таких пар n_1n_2, а вероятность совпадения в произвольной паре осталась та же p.

    Приближенно можно считать, что совпадения для различных пар являются независимыми событиями (на самом деле это не так).

    Тогда среднее количество совпавших пар равно pn_1n_2=4000. Отсюда видно, что с подавляющей вероятность (очень близко к 1) количество совпадений будет не более 50000.

    При условии независимости, вероятность выпадения i совпавших пар даётся биномиальным распределением.

    Для оценки вероятности "хвоста" (более 50000 совпадений), биномиальное распределение можно приблизить распределением Пуассона (\lambda=pn_1n_2). А для оценки вероятности использовать оценку для "хвоста" P(i \geq k)\leq \frac{e^{-\lambda} (e\lambda)^k}{k^k}.

    Тогда натуральный логарифм этой оценки будет

    -\lambda+k(1+\ln\lambda)-k\ln k \approx -4000+50000(1+8.29)-50000\cdot10.82\approx -4000-50000\cdot1.53\approx -80286.

    Т.е. сама вероятность "хвоста" примерно 10^{-34870}.

  • 21.11.2017, 21:11
    0 up down
    Сообщение

    zykov в 21.11.2017, 20:55 написал(а): link
    Т.е. сама вероятность "хвоста" примерно 10^{-34870}.
    С любой практической точки зрения вероятность того что "будет не больше 50 000 совпадающих чисел" просто равна 1.

    Вот если Вы уменьшите эти 50 000 до чего-то поближе к 4 000, то уже ситуация будет другой.

  • 22.11.2017, 13:55
    0 up down
    Сообщение

    zykov, спасибо за идеи. Есть над чем поразмыслить.

    Если в общем, то у меня задача - найти некоторое соотношение. То есть, в итоге, нужно получить приблизительно следующего типа результаты:

    - С вероятностью 0,99 количество совпадений не будет превышать 50 000

    - С вероятностью 0,95 количество совпадений не будет превышать 5 000

    - С вероятностью 0,9 количество совпадений не будет превышать 1 000

    Плюс, в дальнейшем, рядов может быть от трех и больше...

  • 22.11.2017, 16:23
    0 up down
    Сообщение

    dkostetskiy в 22.11.2017, 13:55 написал(а): link
    нужно получить приблизительно следующего типа результаты
    Можете просто приблизить распределение количества совпадений нормальным распределением (\mu = 4000, \sigma = \sqrt{4000}) и сделать эти оценки.

    Оценка для нормального распределения - стандартная вещь.