Title: [NXT] Transparent Forging: ошибка в распр генерируемых блоков. Post by: jettico on January 29, 2014, 02:29:59 PM В алгоритме Transparent Forging, описанном в вики http://wiki.nxtcrypto.org/wiki/Transparent_Forging нарушается имеющееся сейчас правило: способность генерировать блоки для каждого nxt-коина одинаковая. Например, если в одном кошельке два раза больше монет, чем в другом, то вероятность сгенерировать блок у первого выше не в 2, а в 3 раза.
С точки зрения статистики, шаги 3-6 из вики эквивалентны сравнению двух величин, равномерно распределенных на промежутке от 0 до 1/N, где N - количество монет в кошельке (нормализующий коэффициент для всех кошельков одинаков, опустим) Рассмотрим такую игру. Один игрок бросает кубик с цифрами 1-6, его опонент - с цифрами от 1 до 3. У кого выпало меньше - тот победил. В половине случаев первый игрок выбрасывает 4-6 и проигрывает во второй половине случаев их шансы выиграть равны. В результате шансы выиграть у второго 1/2 + 1/4 = 0.75, у первого 0.25. Что в 3 раза меньше. А не в 2, как ожидалось. Если учитывать orphan block'и, то для одного кубика с 2M значениями, другой с M значениями вероятности будут такие: - первого 3/4 - 1/4M - второго 1/4 - 1/4M - ничья 1/2M - отношение второго к первому (3-1/M)/(1-1/M) = (3M-1)/(M-1) То есть при увеличении количества "граней" значение стремится к 3, а количество коллизий стремится к 0. Для произвольного соотношения K между суммами в кошельках при увеличении количества граней (а количество граней для sha256 2256, это около 1077) при фиксированном K отношение вероятностей будет стремиться к 2K-1 (хотя правильно было бы стремиться к K). Title: Re: [NXT] Transparent Forging: ошибка в распределении сгенерирова Post by: jettico on January 29, 2014, 02:36:45 PM Code: import random Вот такая програмка на питоне моделирует эту игру. На одном кубике M сторон, на другом 2M. После Q испытаний подсчитывается количество выигрышей первого, второго и ничьих. Затем выводится отношение выигрышей второго к выигрышам первого. На выходе в хорошем соответствии с теорией получается Quote 0.249153 0.749927 0.00092 3.00990556004 Title: Re: [NXT] Transparent Forging: ошибка в распределении сгенерирова Post by: fsb4000 on January 29, 2014, 02:38:39 PM есть вероятность, что так и задумывалось... А ты спалил тему ;D
Title: Re: [NXT] Transparent Forging: ошибка в распределении сгенерирова Post by: jettico on January 29, 2014, 02:40:11 PM Если кого смущает переход от 0..1/N (где N - количество монет) к 1..M (где M - количество граней), модификация скрипта:
Code: import random Quote 0.249066 0.750934 0.0 3.01500004015 Title: Re: [NXT] Transparent Forging: ошибка в распределении сгенерирова Post by: jettico on January 29, 2014, 02:42:53 PM есть вероятность, что так и задумывалось... А ты спалил тему ;D Ну как бы у меня не столько монет, как у отцов-основателей, мне такие изменения ни к чему. :)Title: Re: [NXT] Transparent Forging: ошибка в распр сгенерированных блок Post by: Come-from-Beyond on January 29, 2014, 02:51:06 PM Рассмотрим такую игру. Один игрок бросает кубик с цифрами 1-6, его опонент - с цифрами от 1 до 3. У кого выпало меньше - тот победил. А поменяется ли что-нибудь если мы рассмотрим такую игру: Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл. Title: Re: [NXT] Transparent Forging: ошибка в распр сгенерированных блок Post by: jettico on January 29, 2014, 02:59:32 PM Рассмотрим такую игру. Один игрок бросает кубик с цифрами 1-6, его опонент - с цифрами от 1 до 3. У кого выпало меньше - тот победил. А поменяется ли что-нибудь если мы рассмотрим такую игру: Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл. Вот в этом случае если рассматриваем целые числа 1..M, то чуток по-другому выйдет - потому что с 1 начинаем считать, а не с нуля. А если действительные от нуля до 1/N - то в точности так же. Title: Re: [NXT] Transparent Forging: ошибка в распр сгенерированных блок Post by: Come-from-Beyond on January 29, 2014, 03:05:05 PM Рассмотрим такую игру. Один игрок бросает кубик с цифрами 1-6, его опонент - с цифрами от 1 до 3. У кого выпало меньше - тот победил. А поменяется ли что-нибудь если мы рассмотрим такую игру: Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл. Вот в этом случае если рассматриваем целые числа 1..M, то чуток по-другому выйдет - потому что с 1 начинаем считать, а не с нуля. А если действительные от нуля до 1/N - то в точности так же. Шанс что у Алисы выпадет от 1 или 2 == 2/6. Шанс что у Боба выпадет 1, 2, 3 или 4 = 4/6. Шанс Алисы делить на шанс Боба == 2/6 делить на 4/6 = 1/2. Что-то ты напутал... Надо перепроверить описание в Вики. Ты второй чел, который спрашивает. Edit: Вика не открывается. Title: Re: [NXT] Transparent Forging: ошибка в распр генерируемых блоков. Post by: Come-from-Beyond on January 29, 2014, 03:12:12 PM Пока проверил твое расчеты. Если играть в мою игру, то шансы соотносятся как 1/4. Проверь свою формулу, должно быть 1/4, а не 1/3 как ты говоришь.
Title: Re: [NXT] Transparent Forging: ошибка в распр генерируемых блоков. Post by: jettico on January 29, 2014, 03:55:31 PM Ты либо забыл теорию вероятности, либо прогулял. ;)
Code: 1 2 3 4 5 6 - A Здесь по горизонтали отложены значения, выпавшие у первого игрока, по вертикали - у второго. В ячейках написано, кто выиграл: A, B, или ничья(=). Как легко понять, для произвольного M: - вероятность выиграть для первого будет (M2-M)/4M2, - для второго (M2 + (M2-M)/2)/2M2, - вероятность ничьи M/(2M2). Упрощаем, получаем то, что в первом посте. PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб. ;D Title: Re: [NXT] Transparent Forging: ошибка в распр генерируемых блоков. Post by: Come-from-Beyond on January 29, 2014, 03:56:37 PM Ты либо забыл теорию вероятности, либо прогулял. ;) Code: 1 2 3 4 5 6 - A Здесь по горизонтали отложены значения, выпавшие у первого игрока, по вертикали - у второго. В ячейках написано, кто выиграл: A, B, или ничья(=). Как легко понять, для произвольного M: - вероятность выиграть для первого будет (M2-M)/4M2, - для второго (M2 + (M2-M)/2)/2M2, - вероятность ничьи M/(2M2). Упрощаем, получаем то, что в первом посте. PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб. ;D Я говорю про мою игру. Потому что твоя не похожа на то, что происходит на самом деле. Title: Re: [NXT] Transparent Forging: ошибка в распр генерируемых блоков. Post by: Sibiryak on January 29, 2014, 04:02:56 PM Как легко понять, для произвольного M: - вероятность выиграть для первого будет (M2-M)/4M2, - для второго (M2 + (M2-M)/2)/2M2, - вероятность ничьи M/(2M2). Упрощаем, получаем то, что в первом посте. PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб. ;D Как-то странно для произвольно М получается. Число граней у двух игроков разное, а в формулах только М. А где L или N которые бы про второго игрока добавляли информацию? Title: Re: [NXT] Transparent Forging: ошибка в распр генерируемых блоков. Post by: jettico on January 29, 2014, 04:06:41 PM Как легко понять, для произвольного M: - вероятность выиграть для первого будет (M2-M)/4M2, - для второго (M2 + (M2-M)/2)/2M2, - вероятность ничьи M/(2M2). Упрощаем, получаем то, что в первом посте. PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб. ;D Как-то странно для произвольно М получается. Число граней у двух игроков разное, а в формулах только М. А где L или N которые бы про второго игрока добавляли информацию? Quote для одного кубика с 2M значениями, другой с M значениями это из первого поста. Ну да, надо было наверное повториться. Title: Re: [NXT] Transparent Forging: ошибка в распр генерируемых блоков. Post by: jettico on January 29, 2014, 04:08:15 PM Я говорю про мою игру. Ты сначала правила расскажи своей игры, а потом уже решение. Title: Re: [NXT] Transparent Forging: ошибка в распр генерируемых блоков. Post by: Come-from-Beyond on January 29, 2014, 04:11:23 PM Я говорю про мою игру. Ты сначала правила расскажи своей игры, а потом уже решение. А поменяется ли что-нибудь если мы рассмотрим такую игру: Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл. Title: Re: [NXT] Transparent Forging: ошибка в распр генерируемых блоков. Post by: jettico on January 29, 2014, 04:14:27 PM В общем для того, чтобы вероятности получались правильные, надо использовать упомянутое уже выше геометрическое распределение:
Code: from random import random выдаёт Quote 0.333031 0.666969 0.0 2.00272347019 что и ожидалось. Всем спасибо. Модератор, как тут закрыть тему? Title: Re: [NXT] Transparent Forging: ошибка в распр генерируемых блоков. Post by: jettico on January 29, 2014, 04:18:18 PM Я говорю про мою игру. Ты сначала правила расскажи своей игры, а потом уже решение. А поменяется ли что-нибудь если мы рассмотрим такую игру: Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл. В реальности ничего с 1 не начинается. Даже sha256. Title: Re: [NXT] Transparent Forging: ошибка в распр генерируемых блоков. Post by: Come-from-Beyond on January 29, 2014, 04:19:27 PM В реальности ничего с 1 не начинается. Даже sha256. Действительно, проморгал этот нюанс. Title: Re: [NXT] Transparent Forging: ошибка в распр генерируемых блоков. Post by: jettico on January 29, 2014, 04:22:38 PM Quote BCNext only communicates via Code from Beyond but he communicates just as recently as 2 days ago. Ты бы это, подкинул бы идею bcnext'у. Или он так и задумывал, чтобы вероятности исказились после ввода TF? Или и правда есть вероятность, что так и задумывалось... А ты спалил тему ;D Он понимает по-русски? Или ему на английском лучше изложить? Я если че диплом когда-то защищал по моделированию физических процессов, так что если надо что-то еще учесть - давайте учтем ;) |