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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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




Начать новую тему Ответить на тему  [ Сообщений: 54 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.
Автор Сообщение
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 13:15 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 3186
Cпасибо сказано: 55
Спасибо получено:
696 раз в 629 сообщениях
Очков репутации: 201

Добавить очки репутацииУменьшить очки репутации
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, 14:40 
Не в сети
Одарённый
Аватара пользователя
Зарегистрирован:
31 мар 2017, 01:16
Сообщений: 149
Cпасибо сказано: 8
Спасибо получено:
46 раз в 41 сообщениях
Очков репутации: 11

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

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

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

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 14:47 
Не в сети
Оракул
Зарегистрирован:
17 окт 2013, 20:46
Сообщений: 932
Cпасибо сказано: 65
Спасибо получено:
365 раз в 287 сообщениях
Очков репутации: 132

Добавить очки репутацииУменьшить очки репутации
Конечно, интересны только нечетные 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, 15:41 
Не в сети
Одарённый
Аватара пользователя
Зарегистрирован:
31 мар 2017, 01:16
Сообщений: 149
Cпасибо сказано: 8
Спасибо получено:
46 раз в 41 сообщениях
Очков репутации: 11

Добавить очки репутацииУменьшить очки репутации
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, 15:52 
Не в сети
Оракул
Зарегистрирован:
17 окт 2013, 20:46
Сообщений: 932
Cпасибо сказано: 65
Спасибо получено:
365 раз в 287 сообщениях
Очков репутации: 132

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 18:11 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
28 дек 2011, 16:16
Сообщений: 8236
Откуда: Дивногорск
Cпасибо сказано: 374
Спасибо получено:
1422 раз в 1297 сообщениях
Очков репутации: 230

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Talanov "Спасибо" сказали:
Shadows
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 18:50 
Не в сети
Одарённый
Аватара пользователя
Зарегистрирован:
31 мар 2017, 01:16
Сообщений: 149
Cпасибо сказано: 8
Спасибо получено:
46 раз в 41 сообщениях
Очков репутации: 11

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

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

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 20:09 
Не в сети
Оракул
Зарегистрирован:
17 окт 2013, 20:46
Сообщений: 932
Cпасибо сказано: 65
Спасибо получено:
365 раз в 287 сообщениях
Очков репутации: 132

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 20:22 
Не в сети
Одарённый
Аватара пользователя
Зарегистрирован:
31 мар 2017, 01:16
Сообщений: 149
Cпасибо сказано: 8
Спасибо получено:
46 раз в 41 сообщениях
Очков репутации: 11

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

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 20:34 
Не в сети
Оракул
Зарегистрирован:
17 окт 2013, 20:46
Сообщений: 932
Cпасибо сказано: 65
Спасибо получено:
365 раз в 287 сообщениях
Очков репутации: 132

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

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Выбор с возвращением

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

KsushaSha

1

56

15 апр 2017, 20:13

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

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

mad_math

2

45

17 май 2017, 13:32

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

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

Silver_Surfer

5

377

22 май 2014, 21:02

Задача про монеты

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

Andrew_

2

56

09 апр 2017, 15:17

Выбор метода

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

Ivann

0

138

24 окт 2015, 16:29

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

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

andrey546

28

733

17 окт 2013, 16:54

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

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

sonorthie

15

261

23 июн 2017, 23:44

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

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

missb

9

376

08 окт 2014, 19:02

Задача про монеты

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

Evrica

4

439

25 апр 2013, 10:30

Задача про монеты

в форуме Начала анализа и Другие разделы школьной математики

Elephant

6

369

12 ноя 2014, 14:54


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



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

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


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

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

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

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