Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 54 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.
Автор Сообщение
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 12:15 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Shadows писал(а):
Но мат. ожидание количества бросков у алгоритм swan намного меньше.


Для уменьшения матожидания количества бросков можно еще такую штуку придумать.
Например, при [math]n=21[/math], каждому участнику присваивается 3 числа и в итоге у нас будет [math]3\cdot 21=63 = 2^6-1[/math]. И всего за один лишний бросок в туре (6 вместо 5) мы уменьшаем вероятность следующего с 11/32 до 1/64. Для [math]n=100[/math] сразу приходит на ум на 5 умножить. Но сначала лучше на 4 поделить. Вроде так стоить поступать со всеми четными - отсеять группу до нечетного.
Желающие могут идею развить, оцифровать и оформить.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
Shadows
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 13:40 
Не в сети
Мастер
Аватара пользователя
Зарегистрирован:
31 мар 2017, 00:16
Сообщений: 206
Cпасибо сказано: 11
Спасибо получено:
76 раз в 70 сообщениях
Очков репутации: 17

Добавить очки репутацииУменьшить очки репутации
Смех в том, что точного решения может и не существовать. При нужде, доказательство можно устроить по аналогии с проблемой точности чисел с "плавающей точкой", но нужды пока нет. Даже взять желанную вероятность 1/3 - она и в десятичном представлении тянется бесконечно, и в двоичном тоже.

Но можно всё устроить более-менее прилично - если согласиться, что распределение будет не в точности равномерное, но шансы каждого участника будут отличаться от "абсолютно равномерных" не более, чем на [math]\delta[/math], которую можно выбрать сколь угодно малой.

Например, при розыгрыше среди 3 участников, можно сделать:
0,333333333333333 - вероятности выигрыша первого или второго
0,333333333333334 - вероятность выигрыша третьего

Схема, если не вдаваться в подробности, - берём монетку, кидаем её несколько раз (чем больше, тем лучше), и из нулей-единиц записываем двоичную дробь: 0.100101101101101... Получим число в интервале [0;1) . Умножаем на число участников. Возникшая целая часть будет номером победителя.

Для полноты картины сюда нужно приложить выражение "погрешности" из "разрядности дроби" и числа претендентов, но это по мере надобности.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 13:47 
Не в сети
Последняя инстанция
Зарегистрирован:
17 окт 2013, 19:46
Сообщений: 1377
Cпасибо сказано: 108
Спасибо получено:
561 раз в 447 сообщениях
Очков репутации: 155

Добавить очки репутацииУменьшить очки репутации
Конечно, интересны только нечетные n. (уменньшать вдвое до нечетного). Для [math]n=21[/math] действително уличшается умножением на 3, но всш второй пример [math]n=25[/math] умножение на 5 не дае улучшение:

(вероятность успешной игры - [math]p[/math], мат. ожидание количества игр - [math]\frac 1 p[/math])

[math]E_1=\frac{32}{25}\cdot 5[/math]

[math]E_2=\frac{128}{125}\cdot 7[/math]

[math]Е_1<Е_2[/math]

Для каждого конкретного n - как повезет.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 14:41 
Не в сети
Мастер
Аватара пользователя
Зарегистрирован:
31 мар 2017, 00:16
Сообщений: 206
Cпасибо сказано: 11
Спасибо получено:
76 раз в 70 сообщениях
Очков репутации: 17

Добавить очки репутацииУменьшить очки репутации
Shadows, я (видимо) несколько другое имел в виду. Надо было пример приложить.

Есть (скажем) 25 участников

Бросаем монетку 10 раз, записываем результат. Пусть получилось 0,1110001110.

Оно же, в десятичной форме:
[math]\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\ldots+\frac{1}{128}+\frac{1}{256}+\frac{1}{512}=0.888671875(0\ldots)[/math] (и максимальная погрешность 1/2048 < 0,0005)

Умножаем на число участников:
[math]0.888671875\cdot25=22.216796875[/math]

Округляем вверх (так удобнее, будут получаться числа от 1 до N). Получаем "23" - номер победителя.

Было бы участников 11 человек - умножали бы на 11,
[math]0.888671875\cdot11=9.775390625[/math], победитель - "10".

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 14:52 
Не в сети
Последняя инстанция
Зарегистрирован:
17 окт 2013, 19:46
Сообщений: 1377
Cпасибо сказано: 108
Спасибо получено:
561 раз в 447 сообщениях
Очков репутации: 155

Добавить очки репутацииУменьшить очки репутации
Xmas, я о другом алгоритме писал.
Равновероятность выигрыша для всех участников обязательна по условии.

Иначе ваш медод - симулировать более-менее приличный генератор случйных чисел в интервале (0;1) при помощи k битов заложен в компютерных библиотеках. Но это другая задача.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 17:11 
В сети
Последняя инстанция
Аватара пользователя
Зарегистрирован:
28 дек 2011, 15:16
Сообщений: 11671
Откуда: Дивногорск
Cпасибо сказано: 795
Спасибо получено:
1984 раз в 1822 сообщениях
Очков репутации: 314

Добавить очки репутацииУменьшить очки репутации
Генерация случайных чисел равномерного дискретного распределения для n=3 при помощи монеты. Монета бросается два раза. Перевод числа из двоичного кода в десятичный даст 4 числа: 0, 1, 2 и 3. При получении числа 0 (две решки подряд) результат аннулируется.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Talanov "Спасибо" сказали:
Shadows
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 17:50 
Не в сети
Мастер
Аватара пользователя
Зарегистрирован:
31 мар 2017, 00:16
Сообщений: 206
Cпасибо сказано: 11
Спасибо получено:
76 раз в 70 сообщениях
Очков репутации: 17

Добавить очки репутацииУменьшить очки репутации
Shadows писал(а):
Xmas, я о другом алгоритме писал.
Равновероятность выигрыша для всех участников обязательна по условии.

Иначе ваш медод - симулировать более-менее приличный генератор случйных чисел в интервале (0;1) при помощи k битов заложен в компютерных библиотеках. Но это другая задача.

Такое чувство, что Вы ищете спора, а не решения.

Вот, ув. Talanov предложил, по сути, безупречный метод. Чем не устраивает?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 19:09 
Не в сети
Последняя инстанция
Зарегистрирован:
17 окт 2013, 19:46
Сообщений: 1377
Cпасибо сказано: 108
Спасибо получено:
561 раз в 447 сообщениях
Очков репутации: 155

Добавить очки репутацииУменьшить очки репутации
Решение давно найдено, сейчас ищется оптимизация.
Против решения Таланова (последнее) ничего против не имею, я и спасибо сказал. Просто он точь в точь повторил алгоритм swan.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 19:22 
Не в сети
Мастер
Аватара пользователя
Зарегистрирован:
31 мар 2017, 00:16
Сообщений: 206
Cпасибо сказано: 11
Спасибо получено:
76 раз в 70 сообщениях
Очков репутации: 17

Добавить очки репутацииУменьшить очки репутации
Shadows писал(а):
Конечно, правильных алгоритмов можно придумать много. И все они будут иметь недостак

Shadows писал(а):
Решение давно найдено, сейчас ищется оптимизация.

Не стыкуются тезисы, батенька.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 19:34 
Не в сети
Последняя инстанция
Зарегистрирован:
17 окт 2013, 19:46
Сообщений: 1377
Cпасибо сказано: 108
Спасибо получено:
561 раз в 447 сообщениях
Очков репутации: 155

Добавить очки репутацииУменьшить очки репутации
Почему?

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Определить победителя

в форуме Теория вероятностей

forsenlol1

17

507

17 июн 2019, 13:58

2 типа выборки победителя из общего пула

в форуме Комбинаторика и Теория вероятностей

Skvozniac

1

279

21 апр 2023, 02:54

Выбор дверей

в форуме Комбинаторика и Теория вероятностей

Makstar

4

453

20 ноя 2018, 21:56

Выбор без возвращения

в форуме Теория вероятностей

mad_math

2

214

17 май 2017, 12:32

Выбор метода

в форуме Исследование операций и Задачи оптимизации

Ivann

0

285

24 окт 2015, 15:29

Выбор с возвращением

в форуме Теория вероятностей

missb

9

739

08 окт 2014, 18:02

Выбор с возвращением

в форуме Теория вероятностей

KsushaSha

1

273

15 апр 2017, 19:13

Подбрасывание монеты

в форуме Комбинаторика и Теория вероятностей

Login V

30

770

13 фев 2022, 18:39

Бросания монеты

в форуме Теория вероятностей

koka0000

6

509

01 мар 2018, 20:00

Задача. Монеты

в форуме Дискретная математика, Теория множеств и Логика

FEBUS

8

529

01 мар 2018, 22:07


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 32


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved