Случайные нули

[venco]

Если вторая, то должно быть просто. Опишите ваш метод, если не сложно. Может и ошибку найду. Или у вас, или у меня.

[voyager]

А кто-нибудь может переписать исходный код в MATLAB ?

[Valeus]

Just an idea (not a solution, as numbers do not quite match):

1. At the end A[0]==0 w.p. 1.
2. Define Z[i] as the expected number of zeroes in A[1],...,A[N-1]
at the end of i-th iteration
3. Z[0] = (1-1/N) + (1-1/N)^2
4. Z[i] = Z[i-1] + (1-Z[i-1]/(N-1))^2 (= prob. A[i] != 0, and A[A[i]] != 0)
5. Answer: Z[N-1] + 1 (+1 for the A[0])

Result of the above seems to converge to:
N/2 + 1.732...

[Valeus]

...

Можно развить эту идею: дело в том, что в уже пройденной части массива (нулевой елемент не всчет) вероятность наткнуться на 0 слегка больше, чем в еще не пройденной (речь идет о "плотности нулей"). Поэтому лучше использовать две переменные вместо одной:

Code: Select all

#!/usr/bin/perl -w
use strict;
my $N=$ARGV[0];
my $z; #estimated number of zeroes in slice (0; i)
my $Z; #estimated number of zeroes in slice [i; N-1]

#initialize to the state after iteration $i = 0
$z = 0;
$Z = (1-1/$N) + (1-1/$N)**2; #Z[0]

foreach my $i (1..($N-1)) {
    my $dz = $Z/($N-$i) + (1-$Z/($N-$i)) * 1/($N-1);
    $dz += (1-$Z/($N-$i)) * ($i-1)/($N-1) * (1-$z/($i-1))
        unless $i == 1;
    my $dZ = -$Z/($N-$i);
    $dZ += (1-$Z/($N-$i)) * ($N-1-$i)/($N-1) * (1-$Z/($N-1-$i))
        unless $i == $N-1;
    $z += $dz;
    $Z += $dZ;
}
++$z; #add a zero in a[0]

my $x = $z - $N/2;
print "$N:\t$z\t$x\n";

А вот результат, к сожалению, все еще не совсем точный:

3: 2.59533607681756 1.09533607681756
4: 3.12994319510957 1.12994319510957
5: 3.65242036081206 1.15242036081206
6: 4.16801542240006 1.16801542240006
7: 4.67939415808731 1.17939415808731
10: 6.20026164575477 1.20026164575477
100: 51.2450000423733 1.24500004237334
200: 101.247499990316 1.24749999031557
400: 201.248749996449 1.24874999644877
800: 401.249374999204 1.24937499920406
1000: 501.249499999528 1.24949999952821
2000: 1001.24974999991 1.24974999991241
10000: 5001.24995000002 1.24995000001582

[venco]

Ошибка в вашем подходе в том, что вероятности с которыми вы работаете не независимы. Поэтому неточно получается.
Я же посчитал точно, правда параметров у меня больше.

Я брал такие параметры:
Нулевой элемент - ноль или не ноль.
Количество нулей в уже пройденных элементах.
Количество обнулений попавших в ещё не пройденные элементы.

Для каждой комбинации параметров у меня хранится вероятность такой ситуации.
Потом я последовательно прохожу все элементы, и обновляю массив вероятностей.
В конце можно посчитать статистику финального распределения.
Время работы такого алгоритма - N^4, весьма медленно. Если по ходу отбрасывать маловероятные комбинации, то скорость становится между N^2 и N^3 - терпимо.
Для малых N, где можно посчитать точный результат простым перебором, результаты совпадают.
Та формула, что я привёл, основана на результатах просчитанных до N = 4000.