[NXT] Transparent Forging: ошибка в распр генерируемых блоков.

[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²⁵⁶, это около 10⁷⁷) при фиксированном K отношение вероятностей будет стремиться к 2K-1 (хотя правильно было бы стремиться к K).

[jettico]

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<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]

есть вероятность, что так и задумывалось... А ты спалил тему  

[jettico]

Если кого смущает переход от 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<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]

есть вероятность, что так и задумывалось... А ты спалил тему  

Ну как бы у меня не столько монет, как у отцов-основателей, мне такие изменения ни к чему. 

[Come-from-Beyond]

Рассмотрим такую игру. Один игрок бросает кубик с цифрами 1-6, его опонент - с цифрами от 1 до 3. У кого выпало меньше - тот победил.

А поменяется ли что-нибудь если мы рассмотрим такую игру:

Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл.

[jettico]

Рассмотрим такую игру. Один игрок бросает кубик с цифрами 1-6, его опонент - с цифрами от 1 до 3. У кого выпало меньше - тот победил.

А поменяется ли что-нибудь если мы рассмотрим такую игру:

Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл.

Вот в этом случае если рассматриваем целые числа 1..M, то чуток по-другому выйдет - потому что с 1 начинаем считать, а не с нуля.

А если действительные от нуля до 1/N - то в точности так же.

[Come-from-Beyond]

Рассмотрим такую игру. Один игрок бросает кубик с цифрами 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]

Пока проверил твое расчеты. Если играть в мою игру, то шансы соотносятся как 1/4. Проверь свою формулу, должно быть 1/4, а не 1/3 как ты говоришь.

[jettico]

Ты либо забыл теорию вероятности, либо прогулял. 

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

Здесь по горизонтали отложены значения, выпавшие у первого игрока, по вертикали - у второго. В ячейках написано, кто выиграл: A, B, или ничья(=).

Как легко понять, для произвольного M:
  - вероятность выиграть для первого будет (M²-M)/4M²,
  - для второго (M² + (M²-M)/2)/2M²,
  - вероятность ничьи M/(2M²).

Упрощаем, получаем то, что в первом посте.

PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб. 

[Come-from-Beyond]

Ты либо забыл теорию вероятности, либо прогулял. 

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

Здесь по горизонтали отложены значения, выпавшие у первого игрока, по вертикали - у второго. В ячейках написано, кто выиграл: A, B, или ничья(=).

Как легко понять, для произвольного M:
  - вероятность выиграть для первого будет (M²-M)/4M²,
  - для второго (M² + (M²-M)/2)/2M²,
  - вероятность ничьи M/(2M²).

Упрощаем, получаем то, что в первом посте.

PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб. 

Я говорю про мою игру. Потому что твоя не похожа на то, что происходит на самом деле.

[Sibiryak]

Как легко понять, для произвольного M:
  - вероятность выиграть для первого будет (M²-M)/4M²,
  - для второго (M² + (M²-M)/2)/2M²,
  - вероятность ничьи M/(2M²).

Упрощаем, получаем то, что в первом посте.

PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб. 

Как-то странно для произвольно М получается. Число граней у двух игроков разное, а в формулах только М. А где L или N которые бы про второго игрока добавляли информацию?

[jettico]

Как легко понять, для произвольного M:
  - вероятность выиграть для первого будет (M²-M)/4M²,
  - для второго (M² + (M²-M)/2)/2M²,
  - вероятность ничьи M/(2M²).

Упрощаем, получаем то, что в первом посте.

PS Соотношения справедливы ДАЖЕ в том случае, если игроков действительно зовут Алиса и Боб. 

Как-то странно для произвольно М получается. Число граней у двух игроков разное, а в формулах только М. А где L или N которые бы про второго игрока добавляли информацию?

для одного кубика с 2M значениями, другой с M значениями

это из первого поста. Ну да, надо было наверное повториться.

[jettico]

Я говорю про мою игру.

Ты сначала правила расскажи своей игры, а потом уже решение.

[Come-from-Beyond]

Я говорю про мою игру.

Ты сначала правила расскажи своей игры, а потом уже решение.

А поменяется ли что-нибудь если мы рассмотрим такую игру:

Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл.

[jettico]

В общем для того, чтобы вероятности получались правильные, надо использовать упомянутое уже выше геометрическое распределение:

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<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]

Я говорю про мою игру.

Ты сначала правила расскажи своей игры, а потом уже решение.

А поменяется ли что-нибудь если мы рассмотрим такую игру:

Один игрок бросает кубик с цифрами 1-6, его оппонент - с цифрами от 1 до 6. Если у первого в 2 раза меньше чем у второго, то первый выиграл.

Если тебе так понравилась аналогия с кубиками, нарисуй на них числа от 0 до 2 и от 0 до 5. Тогда можешь делить. Всё сойдётся.

В реальности ничего с 1 не начинается. Даже sha256.

[Come-from-Beyond]

В реальности ничего с 1 не начинается. Даже sha256.

Действительно, проморгал этот нюанс.

[jettico]

BCNext only communicates via Code from Beyond but he communicates just as recently as 2 days ago.

Ты бы это, подкинул бы идею bcnext'у. Или он так и задумывал, чтобы вероятности исказились после ввода TF? Или и правда

есть вероятность, что так и задумывалось... А ты спалил тему  

Он понимает по-русски? Или ему на английском лучше изложить?

Я если че диплом когда-то защищал по моделированию физических процессов, так что если надо что-то еще учесть - давайте учтем