Бесконечная последовательность нулей и единиц

[mihaild]

vicvolf в сообщении #1501015 писал(а):

Положить номера в урну и выбирать наугад

Все натуральные номера? А как выбирать из счетного количества?

[vicvolf]

mihaild в сообщении #1501023 писал(а):

Все натуральные номера?

Я имел в виду конечную выборку номеров случайных чисел. В реальности только такая может быть.

[mihaild]

vicvolf в сообщении #1501328 писал(а):

Я имел в виду конечную выборку номеров случайных чисел

Из какого множества выбираются эти номера?
И в прошлый раз вы явно предлагали бесконечную выборку

vicvolf в сообщении #1500431 писал(а):

члены с номерами, которые выбираются случайным образом, то получим, как я понимаю, случайную подпоследовательность?

[vicvolf]

mihaild в сообщении #1501331 писал(а):

И в прошлый раз вы явно предлагали бесконечную выборку

vicvolf в сообщении #1500431 писал(а):

члены с номерами, которые выбираются случайным образом, то получим, как я понимаю, случайную подпоследовательность?

Я не писал, какая последовательность. Согласен с Вами, что в данном случае она может быть только конечной.

[geomath]

Интересно, как вы перетасуете 1, 2, ..., n? Я знаю способ Фишера и способ Дурстенфельда, больше не знаю.

[vicvolf]

geomath в сообщении #1501346 писал(а):

Интересно, как вы перетасуете 1, 2, ..., n?

А зачем тасовать? Я брошу все $n$ в урну и буду выбирать наугад.

[geomath]

vicvolf в сообщении #1501361 писал(а):

А зачем тасовать? Я брошу все $n$ в урну и буду выбирать наугад.

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

[B@R5uk]

geomath в сообщении #1501372 писал(а):

т.е. сделать два списка: один исчерпывать, а другой наполнять.

Можно же сделать всё внутри одного массива.

[ewert]

Не самый эффективный, но зато самый простой (если быстродействие не критично) способ случайной перестановки.

Сначала заполняем массив нулями. Затем для каждого $i=1..n$ разыгрываем случайное число из этого же диапазона -- до тех пор, пока не наткнёмся на ещё незаполненный (т.е. нулевой) элемент массива. И заносим в этот элемент значение $i$.

[arseniiv]

Да даже случайное [равномерно распределённое] размещение получить для практики вопрос тривиальный. А если практика ни при чём, берём равномерное распределение на всех перестановках / размещениях / чём угодно, покуда их конечное число. Совершенно незачем манипулировать элементами. Да тема только была не о том.

[B@R5uk]

ewert в сообщении #1501591 писал(а):

Не самый эффективный

Я тут сел посчитать, чтобы вам возразить, но... ВНЕЗАПНО! Этот метод имеет не экспоненциальную и даже не квадратичную временную сложность в среднем, он линеен по размеру массива! То есть, он очень даже эффективный! Может я, конечно, обсчитался...

[mihaild]

B@R5uk в сообщении #1501601 писал(а):

Этот метод имеет не экспоненциальную и даже не квадратичную временную сложность, он линеен по размеру массива!

$O(N\cdot \log N)$ он. На $k$-й элемент нужно в среднем $\frac{N}{N - k}$ попыток - после суммирование получается $N \cdot H_N$.

[B@R5uk]

mihaild в сообщении #1501607 писал(а):

На $k$-й элемент нужно в среднем $\frac{N}{N - k}$ попыток

Да, я таки обсчитался, спасибо за поправку. Но всё равно, линейно-логарифмическое время — это значительно быстрее, чем мне показалось на первый взгляд. Тут, наверное, весь подвох в длине хвоста, то бишь в дисперсии, а не в среднем числе попыток.

[ewert]

(Оффтоп)

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

Такая оптическая иллюзия была. Почему -- потому что мне это ни разу не мешало.
Бороться с квадратичностью -- себе дороже выйдет; простота алгоритма гораздо важнее.

Нет, конечно, mihaild прав -- логарифмичен он.)

[Sicker]

Someone в сообщении #1499696 писал(а):

Например, если на отрезке $[0,L]$ выбрать $n>1$ равномерно распределённых случайных чисел, то неожиданно оказывается, что математическое ожидание наименьшего интервала между ними равно $\frac L{n^2-1}$ (формулу воспроизвёл по памяти; надеюсь, не наврал)

Таки наврали У меня получилось $\frac L{(n+1)^2}$, для $n=2$ ответ широко известен $\frac{L}{9}$

Someone в сообщении #1499696 писал(а):

хотя интуитивно ожидается что-нибудь не сильно меньше $\frac L{n+1}$. Задача о днях рождения тоже это хорошо демонстрирует.

Вообще таки, нет. Это среднее расстояние, и т.к. расстояние гуляет вокруг этого среднего порядка $n$ раз, то и минимум будет где-то квадратичен