jettico (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 02:29:59 PM Last edit: January 29, 2014, 02:53:07 PM by jettico |
|
В алгоритме 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 2 256, это около 10 77) при фиксированном K отношение вероятностей будет стремиться к 2K-1 (хотя правильно было бы стремиться к K).
|
|
|
|
jettico (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 02:36:45 PM |
|
import random
Q = 1000000 M = 500
na = nb = nc = 0.
for x in xrange(Q): a = random.randint(1, 2*M) b = random.randint(1, M) if a<b: na += 1 elif a>b: nb += 1 else: nc += 1
print na/Q, nb/Q, nc/Q
Вот такая програмка на питоне моделирует эту игру. На одном кубике M сторон, на другом 2M. После Q испытаний подсчитывается количество выигрышей первого, второго и ничьих. Затем выводится отношение выигрышей второго к выигрышам первого. На выходе в хорошем соответствии с теорией получается 0.249153 0.749927 0.00092 3.00990556004
|
|
|
|
fsb4000
Legendary
Offline
Activity: 1400
Merit: 1000
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 02:38:39 PM |
|
есть вероятность, что так и задумывалось... А ты спалил тему ![Grin](https://bitcointalk.org/Smileys/default/grin.gif)
|
|
|
|
jettico (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 02:40:11 PM |
|
Если кого смущает переход от 0..1/N (где N - количество монет) к 1..M (где M - количество граней), модификация скрипта: import random
Q = 1000000 M = 500
na = nb = nc = 0.
for x in xrange(Q): a = random.uniform(0, 1./M) b = random.uniform(0, 1./2/M)
if a<b: na += 1 elif a>b: nb += 1 else: nc += 1
print na/Q, nb/Q, nc/Q print nb/na На выходе 0.249066 0.750934 0.0 3.01500004015
|
|
|
|
jettico (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 02:42:53 PM |
|
есть вероятность, что так и задумывалось... А ты спалил тему ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) Ну как бы у меня не столько монет, как у отцов-основателей, мне такие изменения ни к чему. ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif)
|
|
|
|
Come-from-Beyond
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 02:51:06 PM |
|
Рассмотрим такую игру. Один игрок бросает кубик с цифрами 1-6, его опонент - с цифрами от 1 до 3. У кого выпало меньше - тот победил.
А поменяется ли что-нибудь если мы рассмотрим такую игру: Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл.
|
|
|
|
jettico (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 02:59:32 PM |
|
Рассмотрим такую игру. Один игрок бросает кубик с цифрами 1-6, его опонент - с цифрами от 1 до 3. У кого выпало меньше - тот победил.
А поменяется ли что-нибудь если мы рассмотрим такую игру: Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл. Вот в этом случае если рассматриваем целые числа 1..M, то чуток по-другому выйдет - потому что с 1 начинаем считать, а не с нуля. А если действительные от нуля до 1/N - то в точности так же.
|
|
|
|
Come-from-Beyond
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
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: Вика не открывается.
|
|
|
|
Come-from-Beyond
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 03:12:12 PM |
|
Пока проверил твое расчеты. Если играть в мою игру, то шансы соотносятся как 1/4. Проверь свою формулу, должно быть 1/4, а не 1/3 как ты говоришь.
|
|
|
|
jettico (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 03:55:31 PM |
|
Ты либо забыл теорию вероятности, либо прогулял. ![Wink](https://bitcointalk.org/Smileys/default/wink.gif) 1 2 3 4 5 6 - A 1 = B B B B B 2 A = B B B B 3 A A = B B B
B Здесь по горизонтали отложены значения, выпавшие у первого игрока, по вертикали - у второго. В ячейках написано, кто выиграл: A, B, или ничья(=). Как легко понять, для произвольного M: - вероятность выиграть для первого будет (M 2-M)/4M 2, - для второго (M 2 + (M 2-M)/2)/2M 2, - вероятность ничьи M/(2M 2). Упрощаем, получаем то, что в первом посте. PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif)
|
|
|
|
Come-from-Beyond
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 03:56:37 PM |
|
Ты либо забыл теорию вероятности, либо прогулял. ![Wink](https://bitcointalk.org/Smileys/default/wink.gif) 1 2 3 4 5 6 - A 1 = B B B B B 2 A = B B B B 3 A A = B B B
B Здесь по горизонтали отложены значения, выпавшие у первого игрока, по вертикали - у второго. В ячейках написано, кто выиграл: A, B, или ничья(=). Как легко понять, для произвольного M: - вероятность выиграть для первого будет (M 2-M)/4M 2, - для второго (M 2 + (M 2-M)/2)/2M 2, - вероятность ничьи M/(2M 2). Упрощаем, получаем то, что в первом посте. PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) Я говорю про мою игру. Потому что твоя не похожа на то, что происходит на самом деле.
|
|
|
|
Sibiryak
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 04:02:56 PM |
|
Как легко понять, для произвольного M: - вероятность выиграть для первого будет (M 2-M)/4M 2, - для второго (M 2 + (M 2-M)/2)/2M 2, - вероятность ничьи M/(2M 2). Упрощаем, получаем то, что в первом посте. PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) Как-то странно для произвольно М получается. Число граней у двух игроков разное, а в формулах только М. А где L или N которые бы про второго игрока добавляли информацию?
|
F*ck u! No, f*ck EU. BTC, 1HLVar7ymF2nkxNVLttzrUe5vwdYGFsCrk (кубышка) NVC, 4Q5z7Ryobarq5dPLwscurr262WLunu5CLU (надежда на светлое будущее)
|
|
|
jettico (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 04:06:41 PM |
|
Как легко понять, для произвольного M: - вероятность выиграть для первого будет (M 2-M)/4M 2, - для второго (M 2 + (M 2-M)/2)/2M 2, - вероятность ничьи M/(2M 2). Упрощаем, получаем то, что в первом посте. PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) Как-то странно для произвольно М получается. Число граней у двух игроков разное, а в формулах только М. А где L или N которые бы про второго игрока добавляли информацию? для одного кубика с 2M значениями, другой с M значениями это из первого поста. Ну да, надо было наверное повториться.
|
|
|
|
jettico (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 04:08:15 PM |
|
Я говорю про мою игру.
Ты сначала правила расскажи своей игры, а потом уже решение.
|
|
|
|
Come-from-Beyond
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 04:11:23 PM |
|
Я говорю про мою игру.
Ты сначала правила расскажи своей игры, а потом уже решение. А поменяется ли что-нибудь если мы рассмотрим такую игру:
Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл.
|
|
|
|
jettico (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 04:14:27 PM |
|
В общем для того, чтобы вероятности получались правильные, надо использовать упомянутое уже выше геометрическое распределение: from random import random from math import log
Q = 1000000 M = 500
na = nb = nc = 0.
for x in xrange(Q): a = log(random())/log(1-1./2/M) b = log(random())/log(1-1./M)
if a<b: na += 1 elif a>b: nb += 1 else: nc += 1
print na/Q, nb/Q, nc/Q print nb/na выдаёт 0.333031 0.666969 0.0 2.00272347019 что и ожидалось. Всем спасибо. Модератор, как тут закрыть тему?
|
|
|
|
jettico (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 04:18:18 PM |
|
Я говорю про мою игру.
Ты сначала правила расскажи своей игры, а потом уже решение. А поменяется ли что-нибудь если мы рассмотрим такую игру:
Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл.
Если тебе так понравилась аналогия с кубиками, нарисуй на них числа от 0 до 2 и от 0 до 5. Тогда можешь делить. Всё сойдётся. В реальности ничего с 1 не начинается. Даже sha256.
|
|
|
|
Come-from-Beyond
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 04:19:27 PM |
|
В реальности ничего с 1 не начинается. Даже sha256.
Действительно, проморгал этот нюанс.
|
|
|
|
jettico (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 29, 2014, 04:22:38 PM |
|
BCNext only communicates via Code from Beyond but he communicates just as recently as 2 days ago. Ты бы это, подкинул бы идею bcnext'у. Или он так и задумывал, чтобы вероятности исказились после ввода TF? Или и правда есть вероятность, что так и задумывалось... А ты спалил тему ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) Он понимает по-русски? Или ему на английском лучше изложить? Я если че диплом когда-то защищал по моделированию физических процессов, так что если надо что-то еще учесть - давайте учтем ![Wink](https://bitcointalk.org/Smileys/default/wink.gif)
|
|
|
|
|