есть вероятность, что так и задумывалось... А ты спалил тему 
Он понимает по-русски? Или ему на английском лучше изложить?
Я если че диплом когда-то защищал по моделированию физических процессов, так что если надо что-то еще учесть - давайте учтем
Topic: [NXT] Transparent Forging: ошибка в распр генерируемых блоков. (Read 1025 times)
Он понимает по-русски? Или ему на английском лучше изложить?
Я если че диплом когда-то защищал по моделированию физических процессов, так что если надо что-то еще учесть - давайте учтем
January 29, 2014, 11:19:27 AM
В реальности ничего с 1 не начинается. Даже sha256.
Действительно, проморгал этот нюанс.
January 29, 2014, 11:18:18 AM
Я говорю про мою игру.
Ты сначала правила расскажи своей игры, а потом уже решение.
А поменяется ли что-нибудь если мы рассмотрим такую игру:
Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл.
Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл.
В реальности ничего с 1 не начинается. Даже sha256.
January 29, 2014, 11:14:27 AM
В общем для того, чтобы вероятности получались правильные, надо использовать упомянутое уже выше геометрическое распределение:
выдаёт
что и ожидалось. Всем спасибо. Модератор, как тут закрыть тему?
Code:
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
elif a>b:
nb += 1
else:
nc += 1
print na/Q, nb/Q, nc/Q
print nb/na
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
elif a>b:
nb += 1
else:
nc += 1
print na/Q, nb/Q, nc/Q
print nb/na
выдаёт
Quote
0.333031 0.666969 0.0
2.00272347019
2.00272347019
что и ожидалось. Всем спасибо. Модератор, как тут закрыть тему?
January 29, 2014, 11:11:23 AM
Я говорю про мою игру.
Ты сначала правила расскажи своей игры, а потом уже решение.
А поменяется ли что-нибудь если мы рассмотрим такую игру:
Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл.
Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл.
January 29, 2014, 11:08:15 AM
Я говорю про мою игру.
Ты сначала правила расскажи своей игры, а потом уже решение.
January 29, 2014, 11:06:41 AM
Как легко понять, для произвольного M:
- вероятность выиграть для первого будет (M2-M)/4M2,
- для второго (M2 + (M2-M)/2)/2M2,
- вероятность ничьи M/(2M2).
Упрощаем, получаем то, что в первом посте.
PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб.
Как-то странно для произвольно М получается. Число граней у двух игроков разное, а в формулах только М. А где L или N которые бы про второго игрока добавляли информацию?
Quote
для одного кубика с 2M значениями, другой с M значениями
это из первого поста. Ну да, надо было наверное повториться.
January 29, 2014, 11:02:56 AM
Как легко понять, для произвольного M:
- вероятность выиграть для первого будет (M2-M)/4M2,
- для второго (M2 + (M2-M)/2)/2M2,
- вероятность ничьи M/(2M2).
Упрощаем, получаем то, что в первом посте.
PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб.
Как-то странно для произвольно М получается. Число граней у двух игроков разное, а в формулах только М. А где L или N которые бы про второго игрока добавляли информацию?
January 29, 2014, 10:56:37 AM
Ты либо забыл теорию вероятности, либо прогулял.
Здесь по горизонтали отложены значения, выпавшие у первого игрока, по вертикали - у второго. В ячейках написано, кто выиграл: A, B, или ничья(=).
Как легко понять, для произвольного M:
- вероятность выиграть для первого будет (M2-M)/4M2,
- для второго (M2 + (M2-M)/2)/2M2,
- вероятность ничьи M/(2M2).
Упрощаем, получаем то, что в первом посте.
PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб.
Code:
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
1 = B B B B B
2 A = B B B B
3 A A = B B B
B
Здесь по горизонтали отложены значения, выпавшие у первого игрока, по вертикали - у второго. В ячейках написано, кто выиграл: A, B, или ничья(=).
Как легко понять, для произвольного M:
- вероятность выиграть для первого будет (M2-M)/4M2,
- для второго (M2 + (M2-M)/2)/2M2,
- вероятность ничьи M/(2M2).
Упрощаем, получаем то, что в первом посте.
PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб.
Я говорю про мою игру. Потому что твоя не похожа на то, что происходит на самом деле.
January 29, 2014, 10:55:31 AM
Ты либо забыл теорию вероятности, либо прогулял.
Здесь по горизонтали отложены значения, выпавшие у первого игрока, по вертикали - у второго. В ячейках написано, кто выиграл: A, B, или ничья(=).
Как легко понять, для произвольного M:
- вероятность выиграть для первого будет (M2-M)/4M2,
- для второго (M2 + (M2-M)/2)/2M2,
- вероятность ничьи M/(2M2).
Упрощаем, получаем то, что в первом посте.
PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб.
Code:
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
1 = B B B B B
2 A = B B B B
3 A A = B B B
B
Здесь по горизонтали отложены значения, выпавшие у первого игрока, по вертикали - у второго. В ячейках написано, кто выиграл: A, B, или ничья(=).
Как легко понять, для произвольного M:
- вероятность выиграть для первого будет (M2-M)/4M2,
- для второго (M2 + (M2-M)/2)/2M2,
- вероятность ничьи M/(2M2).
Упрощаем, получаем то, что в первом посте.
PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб.
Пока проверил твое расчеты. Если играть в мою игру, то шансы соотносятся как 1/4. Проверь свою формулу, должно быть 1/4, а не 1/3 как ты говоришь.
Рассмотрим такую игру. Один игрок бросает кубик с цифрами 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: Вика не открывается.
Рассмотрим такую игру. Один игрок бросает кубик с цифрами 1-6, его опонент - с цифрами от 1 до 3. У кого выпало меньше - тот победил.
А поменяется ли что-нибудь если мы рассмотрим такую игру:
Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл.
Вот в этом случае если рассматриваем целые числа 1..M, то чуток по-другому выйдет - потому что с 1 начинаем считать, а не с нуля.
А если действительные от нуля до 1/N - то в точности так же.
Рассмотрим такую игру. Один игрок бросает кубик с цифрами 1-6, его опонент - с цифрами от 1 до 3. У кого выпало меньше - тот победил.
А поменяется ли что-нибудь если мы рассмотрим такую игру:
Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл.
есть вероятность, что так и задумывалось... А ты спалил тему
Ну как бы у меня не столько монет, как у отцов-основателей, мне такие изменения ни к чему. 
Если кого смущает переход от 0..1/N (где N - количество монет) к 1..M (где M - количество граней), модификация скрипта:
Code:
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
elif a>b:
nb += 1
else:
nc += 1
print na/Q, nb/Q, nc/Q
print nb/na
На выходе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
elif a>b:
nb += 1
else:
nc += 1
print na/Q, nb/Q, nc/Q
print nb/na
Quote
0.249066 0.750934 0.0
3.01500004015
3.01500004015
есть вероятность, что так и задумывалось... А ты спалил тему
Code:
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
elif a>b:
nb += 1
else:
nc += 1
print na/Q, nb/Q, nc/Q
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
elif a>b:
nb += 1
else:
nc += 1
print na/Q, nb/Q, nc/Q
Вот такая програмка на питоне моделирует эту игру. На одном кубике M сторон, на другом 2M. После Q испытаний подсчитывается количество выигрышей первого, второго и ничьих.
Затем выводится отношение выигрышей второго к выигрышам первого.
На выходе в хорошем соответствии с теорией получается
Quote
0.249153 0.749927 0.00092
3.00990556004
3.00990556004
В алгоритме 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).
С точки зрения статистики, шаги 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).
Jump to: