Возник дилетантский вопрос:
Есть числа a и b из интервала (-1, 1). d1=a-b. В цикле к числам a и b прибавляется случайно выбранное число из интервала (-1, 1). После этого считается d2=a2-b2. Вопрос заключается в следующем: будет ли с увеличением количества циклов постоянно расти расхождение между d1 и d2, или расхождение в любом случае не превзойдет определенную величину?

А>Есть числа a и b из интервала (-1, 1). d1=a-b. В цикле к числам a и b прибавляется случайно выбранное число из интервала (-1, 1). После этого считается d2=a2-b2. Вопрос заключается в следующем: будет ли с увеличением количества циклов постоянно расти расхождение между d1 и d2, или расхождение в любом случае не превзойдет определенную величину?

да, расти пропорционально квадратному корню из количества шагов.
http://en.wikipedia.org/wiki/Random_walk

Здравствуйте, dilmah, Вы писали:

D>да, расти пропорционально квадратному корню из количества шагов.
D>http://en.wikipedia.org/wiki/Random_walk

Отличные картинки в статье!

Ещё пара моментов:
1) Если вдруг потребуется моделирование, то надо учитывать, что многие стандартные генераторы ПСЧ обладают очень сильной корреляцией.
Вот классическая анимация из статьи про линейные когруэнтные генераторы:

2) Стоит обратить внимание на режим округления — в большинстве современных языков программирования по умолчанию исползуется "банкирское округление": Round(2.5) = 2 но Round(3.5) = 4, с целью как раз минимизировать погрешности:
http://en.wikipedia.org/wiki/Rounding
Кстати, в этой же статье ещё упоминается два интересных типа округления: "Stochastic rounding" и "Dithering".

Здравствуйте, andy1618, Вы писали:

A>Вот классическая анимация

Упс, ссылка неточная была.


(На всяк. случай вот оригинал этой анимации)

Здравствуйте, dilmah, Вы писали:

D>да, расти пропорционально квадратному корню из количества шагов.
D>http://en.wikipedia.org/wiki/Random_walk

Ясно. Если у меня переменные a и b имеют тип float (язык C++), какое будет фактически расхождение после n шагов (какой коэффициент в зависимости)?

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, dilmah, Вы писали:

D>>да, расти пропорционально квадратному корню из количества шагов.
D>>http://en.wikipedia.org/wiki/Random_walk

А>Ясно. Если у меня переменные a и b имеют тип float (язык C++), какое будет фактически расхождение после n шагов (какой коэффициент в зависимости)?

Это расхождение никак не связано с округлением, прочитайте статью все-таки.

Эээээ... Складывается такое ощущение, то ли я не точно выразился, то ли не правильно поняли... На каждом цикле к a и b прибавляется одно и тоже число. По этому в идеале разность меняться не должна (a+x)-(b+x)=a+x-b-x=a-b. Меня интересует расхождение связанное именно с округлением чисел.

А>Эээээ... Складывается такое ощущение, то ли я не точно выразился, то ли не правильно поняли... На каждом цикле к a и b прибавляется одно и тоже число. По этому в идеале разность меняться не должна (a+x)-(b+x)=a+x-b-x=a-b. Меня интересует расхождение связанное именно с округлением чисел.

по идее ошибку округления действительно можно представлять как случайную переменную.
Для случайной переменной равномерно распределенной на отрезке (-eps, +eps) ожидаемое отклонение от нуля после N шагов равно sqrt(N)*sqrt(2/pi)

Но, решетка флоатов имеет переменный шаг, в окрестности единицы ошибка округления одна, а в окрестности 100 ошибка округления вырастает в 100 раз.

Здравствуйте, Аноним, Вы писали:

А> ... На каждом цикле к a и b прибавляется одно и тоже число. По этому в идеале разность меняться не должна (a+x)-(b+x)=a+x-b-x=a-b. Меня интересует расхождение связанное именно с округлением чисел.

Ага, теперь понятно. Тут всё будет довольно интересно.

1. В теории, по заданным a и b (при условии a != b) можно сконструировать такую последовательность якобы "случайных" шагов x1, x2, ..., что при их добавлении к числам a и b разность между ними будет неограниченно увеличиваться. Пределом тут будет только то, что, поскольку величина шага у нас ограничена значением 1, то найдётся некоторое пороговое значение MAX (для типа float это порядка 10^7..10^8), когда прибавление к нему максимально разрешённого шага 1 его не изменит из-за ограничений разрядной сетки.
Т.е. получается, что числа a,b не смогут "выбраться" из диапазона [-MAX, MAX], что и будет ограничивать "максимальное возможное расхождение".
Это теоретический ответ на поставленный вопрос

2. На практике всё будет по-другому: во-первых, округления будут происходить не на всех итерациях. Например, если для всех пяти float-чисел: a, b, x, a+x, b+x их порядок величины (с т.з. двоичного представления) одинаковый, то сложение будет абсолютно точным и расхождение не изменится.
А, во-вторых, поскольку в данном случае тоже получаем упомянутое в посте выше "случайное блуждание" (хотя и замедленное), то рано или поздно у нас расхождение достигнет нуля и там и останется, поскольку получим a == b и все их дальнейшие изменения будут синхронными.
Таким образом, на практике получается, что расхождение будет случайно блуждать, пока не достигнет 0.

Вот пример одной из реализаций такого "блуждания":

Как видно, расхождение свелось к 0 примерно после 25 млрд. итераций.