2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение15.01.2021, 11:33 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
vicvolf в сообщении #1501015 писал(а):
Положить номера в урну и выбирать наугад
Все натуральные номера? А как выбирать из счетного количества?

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение16.01.2021, 12:24 


23/02/12
3110
mihaild в сообщении #1501023 писал(а):
Все натуральные номера?
Я имел в виду конечную выборку номеров случайных чисел. В реальности только такая может быть.

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение16.01.2021, 12:35 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
vicvolf в сообщении #1501328 писал(а):
Я имел в виду конечную выборку номеров случайных чисел
Из какого множества выбираются эти номера?
И в прошлый раз вы явно предлагали бесконечную выборку
vicvolf в сообщении #1500431 писал(а):
члены с номерами, которые выбираются случайным образом, то получим, как я понимаю, случайную подпоследовательность?

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение16.01.2021, 13:45 


23/02/12
3110
mihaild в сообщении #1501331 писал(а):
И в прошлый раз вы явно предлагали бесконечную выборку
vicvolf в сообщении #1500431 писал(а):
члены с номерами, которые выбираются случайным образом, то получим, как я понимаю, случайную подпоследовательность?
Я не писал, какая последовательность. Согласен с Вами, что в данном случае она может быть только конечной.

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение16.01.2021, 14:22 
Аватара пользователя


15/11/06
2689
Москва Первомайская
Интересно, как вы перетасуете 1, 2, ..., n? Я знаю способ Фишера и способ Дурстенфельда, больше не знаю.

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение16.01.2021, 15:48 


23/02/12
3110
geomath в сообщении #1501346 писал(а):
Интересно, как вы перетасуете 1, 2, ..., n?
А зачем тасовать? Я брошу все $n$ в урну и буду выбирать наугад.

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение16.01.2021, 16:32 
Аватара пользователя


15/11/06
2689
Москва Первомайская
vicvolf в сообщении #1501361 писал(а):
А зачем тасовать? Я брошу все $n$ в урну и буду выбирать наугад.
Ну, вы наугад вытащите один номер, без возврата, затем другой, тоже без возврата, и т.д. - это и есть способ Фишера. :-) В смысле, если это запрограммировать для компьютера, т.е. сделать два списка: один исчерпывать, а другой наполнять.

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение17.01.2021, 17:24 
Аватара пользователя


26/05/12
1534
приходит весна?
geomath в сообщении #1501372 писал(а):
т.е. сделать два списка: один исчерпывать, а другой наполнять.
Можно же сделать всё внутри одного массива.

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение17.01.2021, 17:45 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение17.01.2021, 18:12 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение17.01.2021, 18:16 
Аватара пользователя


26/05/12
1534
приходит весна?
ewert в сообщении #1501591 писал(а):
Не самый эффективный
Я тут сел посчитать, чтобы вам возразить, но... ВНЕЗАПНО! Этот метод имеет не экспоненциальную и даже не квадратичную временную сложность в среднем, он линеен по размеру массива! То есть, он очень даже эффективный! Может я, конечно, обсчитался...

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение17.01.2021, 18:23 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
B@R5uk в сообщении #1501601 писал(а):
Этот метод имеет не экспоненциальную и даже не квадратичную временную сложность, он линеен по размеру массива!
$O(N\cdot \log N)$ он. На $k$-й элемент нужно в среднем $\frac{N}{N - k}$ попыток - после суммирование получается $N \cdot H_N$.

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение17.01.2021, 18:38 
Аватара пользователя


26/05/12
1534
приходит весна?
mihaild в сообщении #1501607 писал(а):
На $k$-й элемент нужно в среднем $\frac{N}{N - k}$ попыток
Да, я таки обсчитался, спасибо за поправку. Но всё равно, линейно-логарифмическое время — это значительно быстрее, чем мне показалось на первый взгляд. Тут, наверное, весь подвох в длине хвоста, то бишь в дисперсии, а не в среднем числе попыток.

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение17.01.2021, 21:45 
Заслуженный участник


11/05/08
32166

(Оффтоп)

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

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

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

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение09.03.2021, 08:16 
Аватара пользователя


13/08/13

4323
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$ раз, то и минимум будет где-то квадратичен

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 60 ]  На страницу Пред.  1, 2, 3, 4

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Gg322, YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group