Re[2]: Девочка Таня и лохотрон - 2 - Этюды для программистов

Здравствуйте, andyJB, Вы писали:

JB>Здравствуйте, vadimcher, Вы писали:
V>>Я запутался там в формулах.
V>>С вероятностью 1/2 она достанет a, с вероятностью 1/2 -- b (a<b). Далее она говорит "другое больше" или "другое меньше" с вероятностями 1-F(x) и F(x), где x -- это то число, которое она достала, либо a, либо b. Она выиграет, если достала a и сказала, что "другое больше", или достала b и сказала, что "другое меньше". По сути это тоже самое, что сгенерить z~F() и сравнить его с тем, что она достала, т.е. с x, как Вы предлагаете. Сути это не меняет.
V>>Есть вполне законченное выражение для того, с какой вероятностью она выиграет. Оно включает a,b и F(). Оно всегда больше 1/2.
JB>Вы имеете в виду 1/2*(1-F(a)) + 1/2*F(b), которое отличается от 1\2 на 1/2*(F(b)-F(a))?

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

Здравствуйте, vadimcher, Вы писали:
V>Как мы договорились, Вова пишет два различных числа на бумажках и Таня выбирает одну из них.
V>А что если Таня сразу до того, как увидит число, написанное на одной из бумажек, придумает строго возрастающую функцию распределения F(), и, увидев одно из чисел x, скажет, что второе меньше x с вероятностью F(x), и что второе больше x с вероятностью 1-F(x)?
V>С какой вероятностью она угадает?

Если F(x) — функция распределения Вовиного генератора, то действительно, Таня выигравает в любом раунде с вероятностью max(F(x), 1-F(x)), что, очевидно >= 1/2. Однако для реализации такой стратегии и Тани должна быть априорная (о чем Вам с самого начала и говорили) информация о Вовиной функции распределения.

Более того, есть случай, когда даже такая стратегия Тани приведет к честным фифти-фифти. Если Вовина случайная величина будет равномерно распределена на интервале [a, b], где -a и b — устремлены к бесконечности, то, очевидно, для любого x F(x) будет стремиться к 1-F(x), т.е. вероятность успеха Тани даже при наличии у нее априорной информации будет стремиться к 1/2.

Здравствуйте, vadimcher, Вы писали:
V>Я запутался там в формулах.
V>С вероятностью 1/2 она достанет a, с вероятностью 1/2 -- b (a<b). Далее она говорит "другое больше" или "другое меньше" с вероятностями 1-F(x) и F(x), где x -- это то число, которое она достала, либо a, либо b. Она выиграет, если достала a и сказала, что "другое больше", или достала b и сказала, что "другое меньше". По сути это тоже самое, что сгенерить z~F() и сравнить его с тем, что она достала, т.е. с x, как Вы предлагаете. Сути это не меняет.
V>Есть вполне законченное выражение для того, с какой вероятностью она выиграет. Оно включает a,b и F(). Оно всегда больше 1/2.
Вы имеете в виду 1/2*(1-F(a)) + 1/2*F(b), которое отличается от 1\2 на 1/2*(F(b)-F(a))?

Здравствуйте, vadimcher, Вы писали:
V>Тонкий вопрос. Равномерного как такового на R нет. Но можно симулировать каким-нибудь пределом.
V>Например, пусть Вова генерит свои два числа случайно и равномерно на [-k,k]. Берем выборку из двух элементов. Какова вероятность, что разница между a и b меньше, чем x? (x/k)-(x/2k)^2. Какова вероятность, что |b-a|>sqrt(k), например. 1-(sqrt(k)-1/4)/k->1. Т.е. с вероятностью, стремящейся к единице, a и b разъезжаются, на разные бесконечности (в силу симметрии). F(b)->1, F(a)->0.
V>Вове наоборот надо стремиться назвать a и b как можно ближе.

Я Вам не поверил

и написал такую вот программу , чтобы прикинуть lim(F(b)-F(a)):

from math import fabs
from random import random, seed

def F(hi, x):
    'Функция распределения равномерно распределенной на интервале [-hi, hi] случайной величины'
    return (x + hi) / (2*hi)

if __name__ == '__main__':
    seed()
    n = 1000 #Число измерений для определения среднего |F(b)-F(a)|
    hi = 2 #Величина полуинтервала
    for i in range(200):
        s = 0
        for j in range(n):            
            a = 2 * (random() - 1) * hi
            b = 2 * (random() - 1) * hi
            s += fabs(F(hi, a) - F(hi, b))
            
        print '[-2^%d, 2^%d]: avg F(b)-F(a) = %f' % (i+1, i+1, s/n)
        hi *= 2

Результат — lim|F(b)-F(a)| ~= 0.33. Неужели так и должно быть? Может, я наглючил где?

Здравствуйте, Roman Odaisky, Вы писали:

RO>Здравствуйте, vadimcher, Вы писали:

V>>«На этот раз все по-честному», — начала Таня. — «Мы с тобой сыграем в игру „Удача-2“. Ты загадываешь ЛЮБЫЕ два различные числа. Одно из них любое называешь мне, а я отвечаю больше ли второе загаданное число или меньше. Вероятность угадать, разумеется, одна вторая. Если я угадала, ты мне рубь, если нет — я тебе».

V>>По-моему, все честно, не правда ли?

RO>Вова называет всегда 42, а другое число — равновероятный выбор из 0 и 73.
RO>50%.

Вова "работает" по-другому. Он придумывает два числа и называет одно из них случайно. Чтобы начать загадывать как-то по-другому, надо сначала понять, в чем подвох.

V>>class CTanya: public CStudent { // Tanya-student, can answer stupid questions and get cash
RO>http://www.jelovic.com/articles/stupid_naming.htm ! !! !!!

А это к чему? Кого-то раздражет обилие букв C перед именами классов? Не увидел в статье ни одного довода, почему это вредно. Не используйте C перед именами классов, так как это было сделано по ошибке? Если бы Вы знали, сколько полезных вещей в этом мире сделано по ошибке! Кроме того, это вещь весьма субъективная. "Почему у Вас телевизор круглый?" "А потому, что мне так нравится!"

[Из цикла "ДДТ или Детство Девочки Тани"]

После того, как соседский мальчик Вова, известный в школе математик-компьютерщик, раскусил ее первый лохотрон, она, не долго думая, пришла к нему снова...

"На этот раз все по-честному," -- начала Таня. -- "Мы с тобой сыграем в игру 'Удача-2'. Ты загадываешь ЛЮБЫЕ два различные числа. Одно из них любое называешь мне, а я отвечаю больше ли второе загаданное число или меньше. Вероятность угадать, разумеется, одна вторая. Если я угадала, ты мне рубь, если нет -- я тебе."

По-моему, все честно, не правда ли?

--------------------------------------------------------------------------------
Вот реализация этой игры, функция Вовы randomBig неизвестна, функцию Тани isTheOtherBigger требуется реализовать.

#include <iostream>
#include <math.h>

using namespace std;

class CStudent { // class for a student
    virtual int getGrade(void) = 0;
};

class CVova: public CStudent { // Vova-student, can produce and memorize big numbers!
private:
    BigNumber x, y;

    BigNumber randomBig(void);
public:
    virtual int getGrade(void) { return 5; }

    BigNumber guess(void) {
        x = randomBig();
        y = randomBig();
        if (rand() & 1) swap(x, y);
        return x;
    }
    BigNumber cash(bool theOtherIsBigger) {
        if ((theOtherIsBigger && y > x) || (!theOtherIsBigger && y < x)) return 1/*buck*/;
        else return -1/*buck*/;
    }
} Vova;

class CTanya: public CStudent { // Tanya-student, can answer stupid questions and get cash
private:
    BigNumber cash;
public:
    virtual int getGrade(void) { return rand()&1 ? 3 : 2; }

    bool isTheOtherBigger(BigNumber n); // TODO

    BigNumber getCash(BigNumber check) { return cash += check; }
} Tanya;

/******* MAIN *******/
void main(void) {
    BigNumber iteration = 0;
    while (1) {
        BigNumber hercash;
        cout << "Tanya's cash: "
            << (hercash = Tanya.getCash(
                    Vova.cash(
                            Tanya.isTheOtherBigger(
                                    Vova.guess()
                            )
                    )
                ))
            << " She wins with probability: " << (hercash + ++iteration) / 2. / iteration
            << '\n';
    }
}

Здравствуйте, vadimcher, Вы писали:

V>«На этот раз все по-честному», — начала Таня. — «Мы с тобой сыграем в игру „Удача-2“. Ты загадываешь ЛЮБЫЕ два различные числа. Одно из них любое называешь мне, а я отвечаю больше ли второе загаданное число или меньше. Вероятность угадать, разумеется, одна вторая. Если я угадала, ты мне рубь, если нет — я тебе».

V>По-моему, все честно, не правда ли?

Вова называет всегда 42, а другое число — равновероятный выбор из 0 и 73.

50%.

V>class CTanya: public CStudent { // Tanya-student, can answer stupid questions and get cash

http://www.jelovic.com/articles/stupid_naming.htm ! !! !!!

Здравствуйте, vadimcher, Вы писали:

RO>>Вова называет всегда 42, а другое число — равновероятный выбор из 0 и 73.
RO>>50%.

42 — наш ответ Чемберлену (на вопрос о жизни, вселенной и всём таком)

V>Вова "работает" по-другому. Он придумывает два числа и называет одно из них случайно. Чтобы начать загадывать как-то по-другому, надо сначала понять, в чем подвох.

Подвох в том, что если Вова работает с натуральными числами, то второе число с большей (с бесконечно большей) вероятностью больше первого. То же относится и к конечному множеству чисел: интервалы [min,X) vs (X,max] неравноценны, но тут уже Тане надо знать min и max, чтобы делать выводы.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, vadimcher, Вы писали:

RO>>>Вова называет всегда 42, а другое число — равновероятный выбор из 0 и 73.
RO>>>50%.

К>42 — наш ответ Чемберлену (на вопрос о жизни, вселенной и всём таком)

V>>Вова "работает" по-другому. Он придумывает два числа и называет одно из них случайно. Чтобы начать загадывать как-то по-другому, надо сначала понять, в чем подвох.

К>Подвох в том, что если Вова работает с натуральными числами, то второе число с большей (с бесконечно большей) вероятностью больше первого. То же относится и к конечному множеству чисел: интервалы [min,X) vs (X,max] неравноценны, но тут уже Тане надо знать min и max, чтобы делать выводы.

У Тани есть вполне определенная стратегия, чтобы выигрывать с вероятностью >1/2, даже если Вова придумывает любые два числа из Z или R.

Здравствуйте, vadimcher, Вы писали:

V>"На этот раз все по-честному," -- начала Таня. -- "Мы с тобой сыграем в игру 'Удача-2'. Ты загадываешь ЛЮБЫЕ два различные числа. Одно из них любое называешь мне, а я отвечаю больше ли второе загаданное число или меньше. Вероятность угадать, разумеется, одна вторая. Если я угадала, ты мне рубь, если нет -- я тебе."

По сути, Таня пытается предсказать генератор Вовы на основе "почти" случайной подпоследовательности его результатов. Если предположить, что Вова использует какой-нибудь неадаптируемый генератор, то подойдет, наверное, следующая стратегия: первый ответ — случайный, остальные ответы строятся исходя из сравнения называемого Вовой числа со средним ранее названных чисел. В простейшем случае ответ Тани равен результату сравнения. В более сложном стоит давать его с вероятностью успеха второго и последующих произведенных шагов.

Здравствуйте, andyJB, Вы писали:

JB>По сути, Таня пытается предсказать генератор Вовы на основе "почти" случайной подпоследовательности его результатов. Если предположить, что Вова использует какой-нибудь неадаптируемый генератор, то подойдет, наверное, следующая стратегия: первый ответ — случайный, остальные ответы строятся исходя из сравнения называемого Вовой числа со средним ранее названных чисел. В простейшем случае ответ Тани равен результату сравнения. В более сложном стоит давать его с вероятностью успеха второго и последующих произведенных шагов.
Тьфу, не со средним, конечно, а с числом, относительно которого одинаковое число результатов слева и справа. То есть, если Вова называл 100, 3 и три раза 1, то надо сравнивать с 2.
В общем случае, когда Вова может использовать произвольный генератор, ответ 1/2.

Здравствуйте, vadimcher, Вы писали:

RO>>>>Вова называет всегда 42, а другое число — равновероятный выбор из 0 и 73.

V>У Тани есть вполне определенная стратегия, чтобы выигрывать с вероятностью >1/2, даже если Вова придумывает любые два числа из Z или R.

И какая именно для вышеописанной стратегии Вовы?

Здравствуйте, Roman Odaisky, Вы писали:

RO>Здравствуйте, vadimcher, Вы писали:

RO>>>>>Вова называет всегда 42, а другое число — равновероятный выбор из 0 и 73.

V>>У Тани есть вполне определенная стратегия, чтобы выигрывать с вероятностью >1/2, даже если Вова придумывает любые два числа из Z или R.

RO>И какая именно для вышеописанной стратегии Вовы?

Для вышеописанной стратегии Вовы -- я думаю 1/2. Однако Вова, для того, чтобы применять что-то особенное, должен сначала понять, в чем подвох.

Хорошо, давайте так. Представьте, что ему надо загадать два числа, написать их на бумажках и отдать Тане. Она откроет одну из них (случайно) и ответит про второе число, больше ли оно, или меньше. После чего откроет вторую бумажку и проверит.

Здравствуйте, vadimcher, Вы писали:

V>[Из цикла "ДДТ или Детство Девочки Тани"]

V>После того, как соседский мальчик Вова, известный в школе математик-компьютерщик, раскусил ее первый лохотрон, она, не долго думая, пришла к нему снова...

V>"На этот раз все по-честному," -- начала Таня. -- "Мы с тобой сыграем в игру 'Удача-2'. Ты загадываешь ЛЮБЫЕ два различные числа. Одно из них любое называешь мне, а я отвечаю больше ли второе загаданное число или меньше. Вероятность угадать, разумеется, одна вторая. Если я угадала, ты мне рубь, если нет -- я тебе."

V>По-моему, все честно, не правда ли?

Давайте так.

Играют один раз. Вова пишет на двух бумажках два различных числа. Таня выбирает одну из бумажек наугад, смотрит число и говорит, больше оно или меньше другого. Проверяют. Если сказала правильно, получает рубль, иначе отдает.

Может ли Таня выиграть с вероятностью больше 1/2?

Здравствуйте, andyJB, Вы писали:

JB>Здравствуйте, vadimcher, Вы писали:

V>>Играют один раз. Вова пишет на двух бумажках два различных числа. Таня выбирает одну из бумажек наугад, смотрит число и говорит, больше оно или меньше другого. Проверяют. Если сказала правильно, получает рубль, иначе отдает.

V>>Может ли Таня выиграть с вероятностью больше 1/2?
JB>Без дополнительной информации — нет (в формуле условной вероятности все 1/2 успешно сократятся).

А поподробнее? Не в смысле, что это ответ, а просто, чтобы понять ход мысли.

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, andyJB, Вы писали:

JB>>Здравствуйте, vadimcher, Вы писали:

V>>>Играют один раз. Вова пишет на двух бумажках два различных числа. Таня выбирает одну из бумажек наугад, смотрит число и говорит, больше оно или меньше другого. Проверяют. Если сказала правильно, получает рубль, иначе отдает.

V>>>Может ли Таня выиграть с вероятностью больше 1/2?
JB>>Без дополнительной информации — нет (в формуле условной вероятности все 1/2 успешно сократятся).

V>А поподробнее? Не в смысле, что это ответ, а просто, чтобы понять ход мысли.

Поподробнее — очень просто. Если предположить, что Вова выбирает любое число из, например Z ( натуральные числа здесь не подойдут ) случайным образом с равномерным распределением и сообщает одно из двух чисел Тане, причем выбор какое из двух чисел сообщается делается случайным образом ( то есть образом, не зависящим от такого какие числа выбраны ), то это эквивалентно тому, что у Вовы есть функция rand(), возвращающая результат в Z, и Вова вызывает ее два раза и результат первого вызова сообщает Тане. Но вероятность того, что второе число больше первого равна 1/2, как вероятность того, что оно меньше первого. Таким образом Таня здесь поделать ничего не сможет. Другое дело, что в реальной жизни, Вова будет выбирать числа из конечного диапазона.

Здравствуйте, vadimcher, Вы писали:

V>А поподробнее? Не в смысле, что это ответ, а просто, чтобы понять ход мысли.

        P(x=x0|x>y)P(x>y)
P(x>y|x=x0) = -------------------------------------

P(x=x0|x>y)P(x>y)+P(x=x0|x<=y)P(x<=y)
P(x>y) = P(x<=y) = 1/2

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, vadimcher, Вы писали:

V>>А поподробнее? Не в смысле, что это ответ, а просто, чтобы понять ход мысли.
А>

        P(x=x0|x>y)P(x>y)
А>P(x>y|x=x0) = -------------------------------------
А>

P(x=x0|x>y)P(x>y)+P(x=x0|x<=y)P(x<=y)
А>P(x>y) = P(x<=y) = 1/2

Оба ответа свелись к тому, что вероятность того, что другое число больше равна 1/2.
Это так (никаких трюков с натуральными, кривыми диапазонами и т.д. я не предлагаю).

Но значит ли это, что Таня может угадать с вероятностью 1/2 только?
Если бы Таня играла в закрытую, то она бы могла сразу выбрать одну бумажку и, не открывая, сказать, "второе число больше", например. Таня видит одно число, дает ли это ей какое-то преимущество?

Здравствуйте, vadimcher, Вы писали:

V>Но значит ли это, что Таня может угадать с вероятностью 1/2 только?
V>Если бы Таня играла в закрытую, то она бы могла сразу выбрать одну бумажку и, не открывая, сказать, "второе число больше", например. Таня видит одно число, дает ли это ей какое-то преимущество?

Поскольку обсуждение пошло уже по третьему кругу, то буду отвечать кратко. При тех ограничениях, что я привел в своем посте, то, что Таня видит одно число, не дает ей никакого преимущества

V>Если бы Таня играла в закрытую, то она бы могла сразу выбрать одну бумажку и, не открывая, сказать, "второе число больше", например. Таня видит одно число, дает ли это ей какое-то преимущество?

P(x>y) = P(x<=y) = 1/2

              P(x=x0|x>y)P(x>y)
P(x>y|x=x0) = ------------------------------------- = 
               P(x=x0|x>y)P(x>y)+P(x=x0|x<=y)P(x<=y)

            P(x=x0|x>y)
= ------------------------------------- 
    P(x=x0|x>y) + P(x=x0|x<=y)

Утверждение, что P(x>y|x=x0)>1/2 соответствует тому, что P(x=x0|x>y) > P(x=x0|x<=y).

V>Но значит ли это, что Таня может угадать с вероятностью 1/2 только?
V>Если бы Таня играла в закрытую, то она бы могла сразу выбрать одну бумажку и, не открывая, сказать, "второе число больше", например. Таня видит одно число, дает ли это ей какое-то преимущество?

Если игра продолжается достаточно долго, то Таня может по получаемым числам оценивать диапазон чисел используемых Вовой, MIN..MAX, постоянно его корректируя. Тогда если названное число <= середины диапазона, то неназванное с вероятностью >= 1/2 больше.

Если же Вова догадается об этой стратегии, то его контрстратегия будет заключаться в ... В чем?

Когда же умная девочка Таня догадается о контрстратегии Вовы, то она перейдет к стратегии2. Какой?

jmp PC — 2

Здравствуйте, Аноним, Вы писали:

V>>Но значит ли это, что Таня может угадать с вероятностью 1/2 только?
V>>Если бы Таня играла в закрытую, то она бы могла сразу выбрать одну бумажку и, не открывая, сказать, "второе число больше", например. Таня видит одно число, дает ли это ей какое-то преимущество?

А>Если игра продолжается достаточно долго, то Таня может по получаемым числам оценивать диапазон чисел используемых Вовой, MIN..MAX, постоянно его корректируя. Тогда если названное число <= середины диапазона, то неназванное с вероятностью >= 1/2 больше.

А>Если же Вова догадается об этой стратегии, то его контрстратегия будет заключаться в ... В чем?

А>Когда же умная девочка Таня догадается о контрстратегии Вовы, то она перейдет к стратегии2. Какой?

А>jmp PC — 2

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

Здравствуйте, andyJB, Вы писали:

JB>Утверждение, что P(x>y|x=x0)>1/2 соответствует тому, что P(x=x0|x>y) > P(x=x0|x<=y).
Что, опять же из P(x>y) = P(x<=y), равносильно P(x=x0 & x>y) > P(x=x0 & x<=y). Откуда P(x>y) > P(x<=y)!?

Здравствуйте, andyJB, Вы писали:

JB>Здравствуйте, andyJB, Вы писали:

JB>>Утверждение, что P(x>y|x=x0)>1/2 соответствует тому, что P(x=x0|x>y) > P(x=x0|x<=y).
JB>Что, опять же из P(x>y) = P(x<=y), равносильно P(x=x0 & x>y) > P(x=x0 & x<=y). Откуда P(x>y) > P(x<=y)!?

Это верно. Вероятность каждой из гипотез одинаковая.
Однако, это не показывает, что Таня не может извлечь из знания числа определенную выгоду для себя, пусть даже маленькую.

Здравствуйте, vadimcher, Вы писали:

V>Давайте так.

V>Играют один раз. Вова пишет на двух бумажках два различных числа. Таня выбирает одну из бумажек наугад, смотрит число и говорит, больше оно или меньше другого. Проверяют. Если сказала правильно, получает рубль, иначе отдает.

V>Может ли Таня выиграть с вероятностью больше 1/2?

Подсказка.

Пусть Вова написал на бумажках числа a и b, a<b для определенности.

Таня их не знает, разумеется. Эти числа могут быть любыми в общем случае.

Открыв любое из этих чисел случайно, Таня может с некоторой вероятностью сказать, что другое число больше или меньше.
Причем эта вероятность может зависеть от того, что она увидела.

Здравствуйте, vadimcher, Вы писали:

V>Пусть Вова написал на бумажках числа a и b, a<b для определенности.
V>Таня их не знает, разумеется. Эти числа могут быть любыми в общем случае.
Вот, вот. В такой формулировке ещё более очевидно, что ответ равен 1/2. Вова показывает число (a или b с вероятностью 1/2), Тане нужно сказать, показали ей a или b. Показанное значение абсолютно никак не может помочь Тане в выборе.

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, vadimcher, Вы писали:

V>>Давайте так.

V>>Играют один раз. Вова пишет на двух бумажках два различных числа. Таня выбирает одну из бумажек наугад, смотрит число и говорит, больше оно или меньше другого. Проверяют. Если сказала правильно, получает рубль, иначе отдает.

V>>Может ли Таня выиграть с вероятностью больше 1/2?

V>Подсказка.

V>Пусть Вова написал на бумажках числа a и b, a<b для определенности.

V>Таня их не знает, разумеется. Эти числа могут быть любыми в общем случае.

V>Открыв любое из этих чисел случайно, Таня может с некоторой вероятностью сказать, что другое число больше или меньше.
V>Причем эта вероятность может зависеть от того, что она увидела.

Вероятность выигрыша Тани, зависит от го знает ли она стратегию Вовы.
Если не знает, то вероятность будет своей для каждой конкретной пары стратегий (Тани и Вовы). В общем случае ничего нельзя сказать.

Но даже если Таня будет знать стратегию Вовы, то Вова все равно может выбрать стратегию, дающею вероятность выигрыша сколь угодно близкую к 1/2.

Например:
Пусть Вова загадывает произвольное неотрицательное 100 — значное число A. Число Б (с равными вероятностями) берет А+1 или А-1.

Таня сможет сделать осознанный выбор, только если вытянет число -1, 0, 1e100 или 1е100+1.
Причем в случаях -1 и 1е100+1 вероятность ее выигрыша 100%, а в случае 0 и 1e100 вероятность ее выигрыша 2/3.
т.е. вероятность ее выигрыша < 1/2 + (10/3)*1e-100.

On Tue, 22 Jan 2008 11:46:49 +0500, baily <45452@users.rsdn.ru> wrote:

> Поподробнее — очень просто. Если предположить, что Вова выбирает любое
> число из, например Z ( натуральные числа здесь не подойдут ) случайным
> образом с равномерным распределением

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

--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Posted via RSDN NNTP Server 2.0

Здравствуйте, vadimcher, Вы писали:

V>[Из цикла "ДДТ или Детство Девочки Тани"]

V>После того, как соседский мальчик Вова, известный в школе математик-компьютерщик, раскусил ее первый лохотрон, она, не долго думая, пришла к нему снова...

V>"На этот раз все по-честному," -- начала Таня. -- "Мы с тобой сыграем в игру 'Удача-2'. Ты загадываешь ЛЮБЫЕ два различные числа. Одно из них любое называешь мне, а я отвечаю больше ли второе загаданное число или меньше. Вероятность угадать, разумеется, одна вторая. Если я угадала, ты мне рубь, если нет -- я тебе."

V>По-моему, все честно, не правда ли?

Как мы договорились, Вова пишет два различных числа на бумажках и Таня выбирает одну из них.
А что если Таня сразу до того, как увидит число, написанное на одной из бумажек, придумает строго возрастающую функцию распределения F(), и, увидев одно из чисел x, скажет, что второе меньше x с вероятностью F(x), и что второе больше x с вероятностью 1-F(x)?

С какой вероятностью она угадает?

Здравствуйте, vadimcher, Вы писали:

V>Как мы договорились, Вова пишет два различных числа на бумажках и Таня выбирает одну из них.
V>А что если Таня сразу до того, как увидит число, написанное на одной из бумажек, придумает строго возрастающую функцию распределения F(), и, увидев одно из чисел x, скажет, что второе меньше x с вероятностью F(x), и что второе больше x с вероятностью 1-F(x)?

V>С какой вероятностью она угадает?

Если Таня в своем выборе функции F будет не особо осмотрительна, то она может сильно попасть в данной игре. Приведу лишь простой пример, чтобы понять суть того, почему это произойдет. Допустим для простоты, что можно загадывать числа от 1 до 100. Допустим также, что Таня взяла следующую функцию F
F(1) = 0.901, F(2) = 0.902, F(3) = 0.903, ..., F(100) = 1. Ясно, что если Вова будет выбирать числа равновероятно, то Таня пролетит в одну калитку

Здравствуйте, baily, Вы писали:

B>Здравствуйте, vadimcher, Вы писали:

V>>Как мы договорились, Вова пишет два различных числа на бумажках и Таня выбирает одну из них.
V>>А что если Таня сразу до того, как увидит число, написанное на одной из бумажек, придумает строго возрастающую функцию распределения F(), и, увидев одно из чисел x, скажет, что второе меньше x с вероятностью F(x), и что второе больше x с вероятностью 1-F(x)?

V>>С какой вероятностью она угадает?

B>Если Таня в своем выборе функции F будет не особо осмотрительна, то она может сильно попасть в данной игре. Приведу лишь простой пример, чтобы понять суть того, почему это произойдет. Допустим для простоты, что можно загадывать числа от 1 до 100. Допустим также, что Таня взяла следующую функцию F
B>F(1) = 0.901, F(2) = 0.902, F(3) = 0.903, ..., F(100) = 1. Ясно, что если Вова будет выбирать числа равновероятно, то Таня пролетит в одну калитку

В какую калитку она пролетит? Хотите сказать, что будет угадывать в вероятностью <1/2?
Вопрос был поставлен конкретный про вероятность. F строго монотонная (возрастающая, естественно) на R.

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, baily, Вы писали:

B>>Здравствуйте, vadimcher, Вы писали:

V>>>Как мы договорились, Вова пишет два различных числа на бумажках и Таня выбирает одну из них.
V>>>А что если Таня сразу до того, как увидит число, написанное на одной из бумажек, придумает строго возрастающую функцию распределения F(), и, увидев одно из чисел x, скажет, что второе меньше x с вероятностью F(x), и что второе больше x с вероятностью 1-F(x)?

V>>>С какой вероятностью она угадает?

B>>Если Таня в своем выборе функции F будет не особо осмотрительна, то она может сильно попасть в данной игре. Приведу лишь простой пример, чтобы понять суть того, почему это произойдет. Допустим для простоты, что можно загадывать числа от 1 до 100. Допустим также, что Таня взяла следующую функцию F
B>>F(1) = 0.901, F(2) = 0.902, F(3) = 0.903, ..., F(100) = 1. Ясно, что если Вова будет выбирать числа равновероятно, то Таня пролетит в одну калитку

V>В какую калитку она пролетит? Хотите сказать, что будет угадывать в вероятностью <1/2?
Да, причем значительно

V>Вопрос был поставлен конкретный про вероятность. F строго монотонная (возрастающая, естественно) на R.
Я выше привел пример, показывающий в чем засада. Привел именно его, потому, что он проще для понимания. Но, как я вижу, либо вы его не читали, либо, прочли по диагонали. Теперь просите меня привести пример, когда F на R. Я опасаюсь, что вы и его читать не будете. Но попробую еще раз.

Итак пусть Таня берет строго монотонную возрастающую функцию распределения F на R. То есть F(x) стремится к 1 при x стремящемуся к плюс бесконечности,
и F(x) стремится к 0 при x стремящемуся к минус бесконечности. Так как вы в своем выборе не накладываете на F никаких ограничений, то я могу добавить свое условие — F(0) = 0,999999999999999999999999999999, больше никакого условия я не ставлю. Так вот, если Таня возьмет такую F, а Петя свои числа в R будет генерить, с помощью случайной величины, задаваемой другой функцией распределения G(x), такой, что G(0) = 0.0000000000000000000000001, то тем, что Таня будет иногда выигрывать, можно пренебречь

Здравствуйте, Mr.Cat, Вы писали:

MC>Здравствуйте, vadimcher, Вы писали:
V>>Как мы договорились, Вова пишет два различных числа на бумажках и Таня выбирает одну из них.
V>>А что если Таня сразу до того, как увидит число, написанное на одной из бумажек, придумает строго возрастающую функцию распределения F(), и, увидев одно из чисел x, скажет, что второе меньше x с вероятностью F(x), и что второе больше x с вероятностью 1-F(x)?
V>>С какой вероятностью она угадает?

MC>Если F(x) — функция распределения Вовиного генератора, то действительно, Таня выигравает в любом раунде с вероятностью max(F(x), 1-F(x)), что, очевидно >= 1/2. Однако для реализации такой стратегии и Тани должна быть априорная (о чем Вам с самого начала и говорили) информация о Вовиной функции распределения.

Еще раз. Таня ничего не знает о Вовином генераторе. Тот написал два числа (чем он пользовался, когда писал их -- его трудности), она выбирает одно из них и говорит, больше ли другое, или нет.

MC>Более того, есть случай, когда даже такая стратегия Тани приведет к честным фифти-фифти. Если Вовина случайная величина будет равномерно распределена на интервале [a, b], где -a и b — устремлены к бесконечности, то, очевидно, для любого x F(x) будет стремиться к 1-F(x), т.е. вероятность успеха Тани даже при наличии у нее априорной информации будет стремиться к 1/2.

А причем тут F(x) и 1-F(x)?

Здравствуйте, baily, Вы писали:

B>Итак пусть Таня берет строго монотонную возрастающую функцию распределения F на R. То есть F(x) стремится к 1 при x стремящемуся к плюс бесконечности,
B>и F(x) стремится к 0 при x стремящемуся к минус бесконечности. Так как вы в своем выборе не накладываете на F никаких ограничений, то я могу добавить свое условие — F(0) = 0,999999999999999999999999999999, больше никакого условия я не ставлю. Так вот, если Таня возьмет такую F, а Петя свои числа в R будет генерить, с помощью случайной величины, задаваемой другой функцией распределения G(x), такой, что G(0) = 0.0000000000000000000000001, то тем, что Таня будет иногда выигрывать, можно пренебречь

До этого Вы, кстати, утверждали всегда, что вероятность равна 1/2. Вполне понятная интуиция. После этого стали утверждать, что она "пролетит". А теперь про какие-то сверх малые...

Изначально вопрос был поставлен качественно "честная ли игра", а не колличественно.
Утверждение следующее: как бы Вова не старался, Таня всегда угадывает с вероятностью больше 1/2. Сам факт, что перед ней уже лежат два написанные числа, которые она еще не видит дает ей вероятность угадать >1/2! И неважно, собственно, как Вова получил эти два числа. Другое дело, что эта вероятность может быть лишь на чуть-чуть больше, чем 1/2, но она всегда больше! Задача Вовы сделать эту вероятность как можно ближе к 1/2.

Если Вас интересует количественная сторона, то все сильно зависит от того, как Вова генерит свои числа, как меняет функцию распределения и т.п.

Был предложен вариант с "равномерным" распределением на Z. Это только на руку Тане, ибо она будет выигрывать с вероятностью, стремящейся к 1!
Вове наоборот, надо называть числа как можно более близкие друг к другу.

Здравствуйте, Mr.Cat, Вы писали:

MC>Здравствуйте, vadimcher, Вы писали:
V>>Как мы договорились, Вова пишет два различных числа на бумажках и Таня выбирает одну из них.
V>>А что если Таня сразу до того, как увидит число, написанное на одной из бумажек, придумает строго возрастающую функцию распределения F(), и, увидев одно из чисел x, скажет, что второе меньше x с вероятностью F(x), и что второе больше x с вероятностью 1-F(x)?
V>>С какой вероятностью она угадает?

MC>Если F(x) — функция распределения Вовиного генератора, то действительно, Таня выигравает в любом раунде с вероятностью max(F(x), 1-F(x)), что, очевидно >= 1/2. Однако для реализации такой стратегии и Тани должна быть априорная (о чем Вам с самого начала и говорили) информация о Вовиной функции распределения.

Это неверно.

MC>Более того, есть случай, когда даже такая стратегия Тани приведет к честным фифти-фифти. Если Вовина случайная величина будет равномерно распределена на интервале [a, b], где -a и b — устремлены к бесконечности, то, очевидно, для любого x F(x) будет стремиться к 1-F(x), т.е. вероятность успеха Тани даже при наличии у нее априорной информации будет стремиться к 1/2.

Это тоже неверно.

Здравствуйте, vadimcher, Вы писали:

V>До этого Вы, кстати, утверждали всегда, что вероятность равна 1/2. Вполне понятная интуиция. После этого стали утверждать, что она "пролетит". А теперь про какие-то сверх малые...

Не передергивайте. Вы уже в течение этого топика несколько раз изменили условие задачи. Там, где я утверждал про 1/2, на стратегию Тани не было
никаких ограничений.

V>Изначально вопрос был поставлен качественно "честная ли игра", а не колличественно.
V>Утверждение следующее: как бы Вова не старался, Таня всегда угадывает с вероятностью больше 1/2. Сам факт, что перед ней уже лежат два написанные числа, которые она еще не видит дает ей вероятность угадать >1/2! И неважно, собственно, как Вова получил эти два числа. Другое дело, что эта вероятность может быть лишь на чуть-чуть больше, чем 1/2, но она всегда больше! Задача Вовы сделать эту вероятность как можно ближе к 1/2.

Вам привели уже несколько доказательств, что это не так. Такое впечатление, что вы их вообще не читаете. Если это будет продолжаться и далее, то вести с вами дискуссию не имеет смысла. Давайте так: либо приведите свое доказательство, либо раскритикуйте приведенные вам доказательства, указав, где в них вы видите ошибку.

V>Был предложен вариант с "равномерным" распределением на Z. Это только на руку Тане, ибо она будет выигрывать с вероятностью, стремящейся к 1!
V>Вове наоборот, надо называть числа как можно более близкие друг к другу.

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

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, Mr.Cat, Вы писали:

V>А причем тут F(x) и 1-F(x)?

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

Здравствуйте, vadimcher, Вы писали:
V>Как мы договорились, Вова пишет два различных числа на бумажках и Таня выбирает одну из них.
V>А что если Таня сразу до того, как увидит число, написанное на одной из бумажек, придумает строго возрастающую функцию распределения F(), и, увидев одно из чисел x, скажет, что второе меньше x с вероятностью F(x), и что второе больше x с вероятностью 1-F(x)?
Эта стратегия соответствует тому, что Таня просто генерирует случайное число, используя распределение F и сравнивает названное Вовой с ним. Собственно, Таня может заранее сгенерировать число z. Если x<y и x<z — независимы и P(x<y) = P(x>y), то очевидно, что P(x<y & x<z) + P(x>y & x>z) = P(x<y & x>z) + P(x>y & x<z). Я так понял, что вы утверждаете, что P(x<y & x<z) + P(x>y & x>z) > P(x<y & x>z) + P(x>y & x<z), то есть, x<y и x<z зависимы?

Здравствуйте, baily, Вы писали:

B>Здравствуйте, vadimcher, Вы писали:

V>>До этого Вы, кстати, утверждали всегда, что вероятность равна 1/2. Вполне понятная интуиция. После этого стали утверждать, что она "пролетит". А теперь про какие-то сверх малые...

B>

Не передергивайте. Вы уже в течение этого топика несколько раз изменили условие задачи. Там, где я утверждал про 1/2, на стратегию Тани не было
B>никаких ограничений.

Не правда. Условие все тоже. Вова пишет два числа. Таня выбирает одно наугад и говорит, больше ли второе, или меньше. Все, что написано про F() -- это и есть стратегия Тани как она ведет себя в этом случае.

V>>Изначально вопрос был поставлен качественно "честная ли игра", а не колличественно.
V>>Утверждение следующее: как бы Вова не старался, Таня всегда угадывает с вероятностью больше 1/2. Сам факт, что перед ней уже лежат два написанные числа, которые она еще не видит дает ей вероятность угадать >1/2! И неважно, собственно, как Вова получил эти два числа. Другое дело, что эта вероятность может быть лишь на чуть-чуть больше, чем 1/2, но она всегда больше! Задача Вовы сделать эту вероятность как можно ближе к 1/2.

B>Вам привели уже несколько доказательств, что это не так. Такое впечатление, что вы их вообще не читаете. Если это будет продолжаться и далее, то вести с вами дискуссию не имеет смысла. Давайте так: либо приведите свое доказательство, либо раскритикуйте приведенные вам доказательства, указав, где в них вы видите ошибку.

Да в том-то и дело, что никто пока не написал чему равна вероятность угадывания, если она воспользуется этой стратегией. Т.е. пусть Вова написал два числа a и b, a < b. Она их не знает. Но использует следующцю стратегию: если она открывает число x, то с вероятностью F(x) она говорит, что второе число меньше, а с вероятностью 1-F(x) -- больше.

V>>Был предложен вариант с "равномерным" распределением на Z. Это только на руку Тане, ибо она будет выигрывать с вероятностью, стремящейся к 1!
V>>Вове наоборот, надо называть числа как можно более близкие друг к другу.

B>Для начала докажите это ваше утверждение. Приведите стратегию Тани, когда она будет выигрывать с вероятностью 1 в этом случае.

Здравствуйте, baily, Вы писали:

B>Здравствуйте, vadimcher, Вы писали:

V>>Здравствуйте, Mr.Cat, Вы писали:

V>>А причем тут F(x) и 1-F(x)?

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

Где там новое условие задачи? Там то же самое условие. Это скорее уже ответ...

на вопрос, для которого у Вас ответ был 1/2.

Здравствуйте, andyJB, Вы писали:

JB>Здравствуйте, vadimcher, Вы писали:
V>>Как мы договорились, Вова пишет два различных числа на бумажках и Таня выбирает одну из них.
V>>А что если Таня сразу до того, как увидит число, написанное на одной из бумажек, придумает строго возрастающую функцию распределения F(), и, увидев одно из чисел x, скажет, что второе меньше x с вероятностью F(x), и что второе больше x с вероятностью 1-F(x)?
JB>Эта стратегия соответствует тому, что Таня просто генерирует случайное число, используя распределение F и сравнивает названное Вовой с ним. Собственно, Таня может заранее сгенерировать число z. Если x<y и x<z — независимы и P(x<y) = P(x>y), то очевидно, что P(x<y & x<z) + P(x>y & x>z) = P(x<y & x>z) + P(x>y & x<z). Я так понял, что вы утверждаете, что P(x<y & x<z) + P(x>y & x>z) > P(x<y & x>z) + P(x>y & x<z), то есть, x<y и x<z зависимы?

Нет, не так. Пусть Вова написал два числа a и b, которые Таня не знает. Таня смотрит одно число, видит x (x это либо a, либо b, но Таня не знает, большее ли оно, или меньшее), а далее с вероятностью F(x) говорит, что второе число меньше, и с веротяностью 1-F(x), что больше.

Извините, если не очень аккуратно выразился, описывая стратению Тани. Она НЕ может говорить "оно больше с вероятностью ...", но она может посмотрев на число "подбросить монетку" и сказать "больше" с некоторой вероятностью, или "меньше" с некоторой вероятностью. Т.е. ответ однозначный, но с какой вероятностью она дает тот или иной ответ -- личное дело Тани.

Здравствуйте, vadimcher, Вы писали:

V>Где там новое условие задачи? Там то же самое условие. Это скорее уже ответ...

на вопрос, для которого у Вас ответ был 1/2.

Ну чтож. Не затрудните ли себя доказательством, что эта ваша стратегия дает ответ? А то вы пока ничего своего так и не привели. То есть вы считаете, что от F ничего не зависит и она может быть любой? Если так, то давайте я предложу вам конкретную F и мы с вами сыграем на деньги, пользуясь данной стратегией? Скажем в каждом туре ставка 100 рублей, пока кто-то не проиграет 10000?

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, baily, Вы писали:

B>>Здравствуйте, vadimcher, Вы писали:

V>>>До этого Вы, кстати, утверждали всегда, что вероятность равна 1/2. Вполне понятная интуиция. После этого стали утверждать, что она "пролетит". А теперь про какие-то сверх малые...

B>>

Не передергивайте. Вы уже в течение этого топика несколько раз изменили условие задачи. Там, где я утверждал про 1/2, на стратегию Тани не было
B>>никаких ограничений.

V>Не правда. Условие все тоже. Вова пишет два числа. Таня выбирает одно наугад и говорит, больше ли второе, или меньше. Все, что написано про F() -- это и есть стратегия Тани как она ведет себя в этом случае.

Мдя! То есть вы полагаете, что от F ничего не зависит? И это есть ваше "решение"? Не затруднит ли вас доказать его корректность? Вы упорно избегаете конкретики.

Здравствуйте, baily, Вы писали:

B>Здравствуйте, vadimcher, Вы писали:

V>>Здравствуйте, baily, Вы писали:

B>>>Здравствуйте, vadimcher, Вы писали:

V>>>>До этого Вы, кстати, утверждали всегда, что вероятность равна 1/2. Вполне понятная интуиция. После этого стали утверждать, что она "пролетит". А теперь про какие-то сверх малые...

B>>>

Не передергивайте. Вы уже в течение этого топика несколько раз изменили условие задачи. Там, где я утверждал про 1/2, на стратегию Тани не было
B>>>никаких ограничений.

V>>Не правда. Условие все тоже. Вова пишет два числа. Таня выбирает одно наугад и говорит, больше ли второе, или меньше. Все, что написано про F() -- это и есть стратегия Тани как она ведет себя в этом случае.

B>Мдя! То есть вы полагаете, что от F ничего не зависит? И это есть ваше "решение"? Не затруднит ли вас доказать его корректность? Вы упорно избегаете конкретики.

От F() зависит то, с какой вероятностью она выигрывает, естественно. Это вопрос колличественный. Вова может называть числа близкие друг к другу, уменьшая вероятность выигрыша.
Качественно же, вероятность выигрыша всегда больше 1/2.
Ну а формулы, я подожду, ибо это простая формула полной вероятности.

Здравствуйте, baily, Вы писали:

B>Здравствуйте, vadimcher, Вы писали:

V>>Где там новое условие задачи? Там то же самое условие. Это скорее уже ответ...

на вопрос, для которого у Вас ответ был 1/2.

B>Ну чтож. Не затрудните ли себя доказательством, что эта ваша стратегия дает ответ? А то вы пока ничего своего так и не привели. То есть вы считаете, что от F ничего не зависит и она может быть любой? Если так, то давайте я предложу вам конкретную F и мы с вами сыграем на деньги, пользуясь данной стратегией? Скажем в каждом туре ставка 100 рублей, пока кто-то не проиграет 10000?

Нет уж, увольте.
По двум причинам.
Первая, нематематическая. Не люблю играть на деньги. Меня больше интересуют качественные результаты, а не количественные.
Вторая, математическая. Допустим, что моя вероятность выигрыша ровно 1/2. По сути, в этом случае то, что я выиграю, это random walk. С вероятностью 1/2 в каждом туре я получаю +1, с вероятностью 1/2 -- -1. Random walk такая хитрая штука, что она запросто уходит на бесконечность, а потому любой границы (например, 10000) достигает без проблем. Так вот, даже если вероятность выигрыша в каждом туре немного больше, чем 1/2, вероятность достижения -10000 по-прежнему очень близка к 1/2. Такая вот особенность random walk. Пусть уж Таня радуется по этому поводу. Я отношусь более скептично.

Я лучше с Вами пивка попью и в гусарика поиграю... на "спички".

Здравствуйте, vadimcher, Вы писали:

B>>Мдя! То есть вы полагаете, что от F ничего не зависит? И это есть ваше "решение"? Не затруднит ли вас доказать его корректность? Вы упорно избегаете конкретики.

V>От F() зависит то, с какой вероятностью она выигрывает, естественно. Это вопрос колличественный. Вова может называть числа близкие друг к другу, уменьшая вероятность выигрыша.
V>Качественно же, вероятность выигрыша всегда больше 1/2.
V>Ну а формулы, я подожду, ибо это простая формула полной вероятности.

Дайте определение, что вы подразумеваете под

количественными

качественными

вероятностями. Я не слышал о таком. Я веду речь о вероятности выигрыша в данном конкретном розыгрыше.

Здравствуйте, baily, Вы писали:

B>Здравствуйте, vadimcher, Вы писали:

B>>>Мдя! То есть вы полагаете, что от F ничего не зависит? И это есть ваше "решение"? Не затруднит ли вас доказать его корректность? Вы упорно избегаете конкретики.

V>>От F() зависит то, с какой вероятностью она выигрывает, естественно. Это вопрос колличественный. Вова может называть числа близкие друг к другу, уменьшая вероятность выигрыша.
V>>Качественно же, вероятность выигрыша всегда больше 1/2.
V>>Ну а формулы, я подожду, ибо это простая формула полной вероятности.

B>Дайте определение, что вы подразумеваете под

количественными

качественными

вероятностями. Я не слышал о таком. Я веду речь о вероятности выигрыша в данном конкретном розыгрыше.

A-a-a-a-a! Я говорю о количественном или качественном результате, а не о вероятностях.
Результат "вероятность > 1/2 " качественный
Результат "вероятность = 0.753" количественный

Вопрос о том, "честная ли игра" качественный. Вопрос о том, например, в какой степени она честная может быть количественным.

Вот Вам два вопроса и два ответа на них.
1) Зависит ли вероятность выигрыша Тани от того, какие числа написал Вова и от ее функции F()? Ответ: да.
2) Всегда ли она больше 1/2? Ответ: да.

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, baily, Вы писали:

B>>Здравствуйте, vadimcher, Вы писали:

V>A-a-a-a-a! Я говорю о количественном или качественном результате, а не о вероятностях.
V>Результат "вероятность > 1/2 " качественный
V>Результат "вероятность = 0.753" количественный

V>Вопрос о том, "честная ли игра" качественный. Вопрос о том, например, в какой степени она честная может быть количественным.

V>Вот Вам два вопроса и два ответа на них.
V>1) Зависит ли вероятность выигрыша Тани от того, какие числа написал Вова и от ее функции F()? Ответ: да.
Согласен

V>2) Всегда ли она больше 1/2? Ответ: да.

Не согласен. В приведенном мной примере, данная вероятность близка к 0, что на "качественном" уровне очевидно

Здравствуйте, baily, Вы писали:

V>>Вот Вам два вопроса и два ответа на них.
V>>1) Зависит ли вероятность выигрыша Тани от того, какие числа написал Вова и от ее функции F()? Ответ: да.
B>Согласен

V>>2) Всегда ли она больше 1/2? Ответ: да.

B>Не согласен. В приведенном мной примере, данная вероятность близка к 0, что на "качественном" уровне очевидно

Нет, она там близка к одной второй, причем больше ее.

Давайте так.
Вова написал два числа a и b.
Вы вытаскиваете одну из бумажек случайно. Видите x, который на самом деле либо a, либо b.
"Бросаете монетку" и с вероятностью F(x) говорите "другое число меньше", а с вероятностью 1-F(x) говорите, "другое число больше".
Какова вероятность того, что Вы угадаете?

Здравствуйте, vadimcher, Вы писали:

V>Извините, если не очень аккуратно выразился, описывая стратению Тани. Она НЕ может говорить "оно больше с вероятностью ...", но она может посмотрев на число "подбросить монетку" и сказать "больше" с некоторой вероятностью, или "меньше" с некоторой вероятностью. Т.е. ответ однозначный, но с какой вероятностью она дает тот или иной ответ -- личное дело Тани.
Понятно, что в вероятностной стратегии ответ однозначный. В такой стратегии:
— сгенерировать число z по распределению F,
— в ответ на вопрос Вовы ответить "больше", если z>x и "меньше", в противном случае
ответ тоже однозначный. Более того — это в точности та самая стратегия, которую предлагаете вы. Просто "подбрасывание монетки" эмулируется генерацией случайного числа.
Так каков ваш ответ на вопросы предыдущего поста?

Здравствуйте, andyJB, Вы писали:

JB>Здравствуйте, vadimcher, Вы писали:

V>>Извините, если не очень аккуратно выразился, описывая стратению Тани. Она НЕ может говорить "оно больше с вероятностью ...", но она может посмотрев на число "подбросить монетку" и сказать "больше" с некоторой вероятностью, или "меньше" с некоторой вероятностью. Т.е. ответ однозначный, но с какой вероятностью она дает тот или иной ответ -- личное дело Тани.
JB>Понятно, что в вероятностной стратегии ответ однозначный. В такой стратегии:
JB> — сгенерировать число z по распределению F,
JB> — в ответ на вопрос Вовы ответить "больше", если z>x и "меньше", в противном случае
JB>ответ тоже однозначный. Более того — это в точности та самая стратегия, которую предлагаете вы. Просто "подбрасывание монетки" эмулируется генерацией случайного числа.
JB>Так каков ваш ответ на вопросы предыдущего поста?

Я запутался там в формулах.
С вероятностью 1/2 она достанет a, с вероятностью 1/2 -- b (a<b). Далее она говорит "другое больше" или "другое меньше" с вероятностями 1-F(x) и F(x), где x -- это то число, которое она достала, либо a, либо b. Она выиграет, если достала a и сказала, что "другое больше", или достала b и сказала, что "другое меньше". По сути это тоже самое, что сгенерить z~F() и сравнить его с тем, что она достала, т.е. с x, как Вы предлагаете. Сути это не меняет.
Есть вполне законченное выражение для того, с какой вероятностью она выиграет. Оно включает a,b и F(). Оно всегда больше 1/2.

Здравствуйте, vadimcher, Вы писали:

V>>>Есть вполне законченное выражение для того, с какой вероятностью она выиграет. Оно включает a,b и F(). Оно всегда больше 1/2.
JB>>Вы имеете в виду 1/2*(1-F(a)) + 1/2*F(b), которое отличается от 1\2 на 1/2*(F(b)-F(a))?

V>Да, именно это и имелось в виду. Честно говоря, я полагал, что это известная задачка, а потому труда не вызовет. Я нашел ее в сборнике "классических вероятностных приколов". Видимо, не такой уж классический сборник был.

Посыпаю голову пеплом

Что то интуиция меня подвела. Действительно, так и есть и все просто. При конкретных числах, полученных у Вовы, имеем вероятность выигрыша Тани S(a,b) = 1/2*(1-F(a)) + 1/2*F(b). Пусть теперь Вова генерит числа случайной функцией, с распределением G. Пусть P(a,b) — вероятность того, что было сгенерированы числа (a,b). Тогда вероятность выигрыша Тани до того моммента, как Вова сгенерил числа равна

P = сумма по всем (a,b) чисел S(a,b)*P(a,b)

Но, так как S(a,b) >= 1/2 для всех (a,b), то

P >= 1/2*(сумма по всем (a,b) P(a,b)) = 1/2

Интересно подумать только, как Вова и Таня должны выбирать свои функции F и G, чтобы улучшить свою ситуацию. Ясно, что худший вариант для Тани, если F тождественна равна 0 или 1, то есть когда она говорит всегда ответ меньше или больше, независимо от того, какое число она видит при открытии. И даже в этом случае у нее вероятность выигрыша 1/2!

Здравствуйте, baily, Вы писали:

B>Здравствуйте, vadimcher, Вы писали:

V>>>>Есть вполне законченное выражение для того, с какой вероятностью она выиграет. Оно включает a,b и F(). Оно всегда больше 1/2.
JB>>>Вы имеете в виду 1/2*(1-F(a)) + 1/2*F(b), которое отличается от 1\2 на 1/2*(F(b)-F(a))?

V>>Да, именно это и имелось в виду. Честно говоря, я полагал, что это известная задачка, а потому труда не вызовет. Я нашел ее в сборнике "классических вероятностных приколов". Видимо, не такой уж классический сборник был.

B>Посыпаю голову пеплом

А результат действительно странный, если так подумать.
Два различых числа, с равной вероятностью выбираем любое из них, ситуация абсолютно симметричная. Но при этом, больше ли второе число угадываем почему-то с вероятностью больше 1/2.

Здравствуйте, vadimcher, Вы писали:
V>Да, именно это и имелось в виду. Честно говоря, я полагал, что это известная задачка, а потому труда не вызовет. Я нашел ее в сборнике "классических вероятностных приколов". Видимо, не такой уж классический сборник был.

Спасибо за задачу. Весьма интересная. Тем не менее, я не согласен с Вашим мнением, что если Вовины случайные числа распределены "псевдоравномерно" на Z или R, вероятность выигрыша Тани стремится к 1. Наоборот, для такого распределения разность F(b)-F(a) (a<b) для любых a и b будет стремиться к нулю, а вероятность выигрыша Тани — к 1/2.

Здравствуйте, Mr.Cat, Вы писали:

MC>Здравствуйте, vadimcher, Вы писали:
V>>Да, именно это и имелось в виду. Честно говоря, я полагал, что это известная задачка, а потому труда не вызовет. Я нашел ее в сборнике "классических вероятностных приколов". Видимо, не такой уж классический сборник был.

MC>Спасибо за задачу. Весьма интересная. Тем не менее, я не согласен с Вашим мнением, что если Вовины случайные числа распределены "псевдоравномерно" на Z или R, вероятность выигрыша Тани стремится к 1. Наоборот, для такого распределения разность F(b)-F(a) (a<b) для любых a и b будет стремиться к нулю, а вероятность выигрыша Тани — к 1/2.

Тонкий вопрос. Равномерного как такового на R нет. Но можно симулировать каким-нибудь пределом.

Например, пусть Вова генерит свои два числа случайно и равномерно на [-k,k]. Берем выборку из двух элементов. Какова вероятность, что разница между a и b меньше, чем x? (x/k)-(x/2k)^2. Какова вероятность, что |b-a|>sqrt(k), например. 1-(sqrt(k)-1/4)/k->1. Т.е. с вероятностью, стремящейся к единице, a и b разъезжаются, на разные бесконечности (в силу симметрии). F(b)->1, F(a)->0.

Вове наоборот надо стремиться назвать a и b как можно ближе.

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, Mr.Cat, Вы писали:

V>Тонкий вопрос. Равномерного как такового на R нет. Но можно симулировать каким-нибудь пределом.

V>Например, пусть Вова генерит свои два числа случайно и равномерно на [-k,k]. Берем выборку из двух элементов. Какова вероятность, что разница между a и b меньше, чем x? (x/k)-(x/2k)^2. Какова вероятность, что |b-a|>sqrt(k), например. 1-(sqrt(k)-1/4)/k->1. Т.е. с вероятностью, стремящейся к единице, a и b разъезжаются, на разные бесконечности (в силу симметрии). F(b)->1, F(a)->0.

V>Вове наоборот надо стремиться назвать a и b как можно ближе.
Если у Тани F фиксирована, то Вове можно стремиться либо ближе, либо дальше, чтобы минимизировать вероятность своего проигрыша до 1/2

Вопрос действительно тонкий. Обозначим через R(k) — функцию равномерного распределения на [-k,k]
Пусть Вова генерит числа с функцией распределения G, а Таня использует F. Обозначим P(F,G) вероятность выигрыша Тани при таком раскладе
Получаем следующие факты
1) Равномерного распределения на R нет. R(k) не сходятся при k стремящемся к бесконечности
2) Если у Тани фиксирована функция F, Вова использует G = R(k) и устремит k либо к бесконечности, либо к 0, то шансы его проигрыша устремляются к 1/2.
3) Если Таня, тоже будет использовать F = R(k), а у Вова фиксированная G, то существует k, такое что P(R(k), G) достигает максимума

Получаем на мой взгляд интересную задачу. Ясно, что inf( P(F,G) ) = 1/2, где inf берется по всем F и G — это мы уже показали. Но у меня родилась гипотеза, что sup( P(F,G) ) < 1. Иными словами, как бы плохо Вова не выбирал свою функцию распределения, а Таня не выбирала хорошо, то не получится так, что Таня выигрывает с вероятностью, сколь угодно близкой к 1. Было бы интересно найти этот sup.

Здравствуйте, baily, Вы писали:
B>Получаем на мой взгляд интересную задачу. Ясно, что inf( P(F,G) ) = 1/2, где inf берется по всем F и G — это мы уже показали. Но у меня родилась гипотеза, что sup( P(F,G) ) < 1. Иными словами, как бы плохо Вова не выбирал свою функцию распределения, а Таня не выбирала хорошо, то не получится так, что Таня выигрывает с вероятностью, сколь угодно близкой к 1. Было бы интересно найти этот sup.
Почему бы Тане не использовать R(-1,1), а Вове загадывать всегда -1 и 1 (т.е. функция распределения — две ступеньки)? Тогда Таня будет выигрывать с вероятностью 1.

Здравствуйте, andyJB, Вы писали:

JB>Здравствуйте, baily, Вы писали:
B>>Получаем на мой взгляд интересную задачу. Ясно, что inf( P(F,G) ) = 1/2, где inf берется по всем F и G — это мы уже показали. Но у меня родилась гипотеза, что sup( P(F,G) ) < 1. Иными словами, как бы плохо Вова не выбирал свою функцию распределения, а Таня не выбирала хорошо, то не получится так, что Таня выигрывает с вероятностью, сколь угодно близкой к 1. Было бы интересно найти этот sup.
JB>Почему бы Тане не использовать R(-1,1), а Вове загадывать всегда -1 и 1 (т.е. функция распределения — две ступеньки)? Тогда Таня будет выигрывать с вероятностью 1.

Наложим дополнительное условие, что функция G не должна иметь разрывов, или, даже , что она всюду дифференциреума на R, то есть имеется функция плотности

Здравствуйте, Mr.Cat, Вы писали:

MC>Здравствуйте, vadimcher, Вы писали:
V>>Тонкий вопрос. Равномерного как такового на R нет. Но можно симулировать каким-нибудь пределом.
V>>Например, пусть Вова генерит свои два числа случайно и равномерно на [-k,k]. Берем выборку из двух элементов. Какова вероятность, что разница между a и b меньше, чем x? (x/k)-(x/2k)^2. Какова вероятность, что |b-a|>sqrt(k), например. 1-(sqrt(k)-1/4)/k->1. Т.е. с вероятностью, стремящейся к единице, a и b разъезжаются, на разные бесконечности (в силу симметрии). F(b)->1, F(a)->0.
V>>Вове наоборот надо стремиться назвать a и b как можно ближе.

MC>Я Вам не поверил

и написал такую вот программу , чтобы прикинуть lim(F(b)-F(a)):
MC>

MC>from math import fabs
MC>from random import random, seed

MC>def F(hi, x):
MC>    'Функция распределения равномерно распределенной на интервале [-hi, hi] случайной величины'
MC>    return (x + hi) / (2*hi)

MC>if __name__ == '__main__':
MC>    seed()
MC>    n = 1000 #Число измерений для определения среднего |F(b)-F(a)|
MC>    hi = 2 #Величина полуинтервала
MC>    for i in range(200):
MC>        s = 0
MC>        for j in range(n):            
MC>            a = 2 * (random() - 1) * hi
MC>            b = 2 * (random() - 1) * hi
MC>            s += fabs(F(hi, a) - F(hi, b))
            
MC>        print '[-2^%d, 2^%d]: avg F(b)-F(a) = %f' % (i+1, i+1, s/n)
MC>        hi *= 2
MC>

MC>Результат — lim|F(b)-F(a)| ~= 0.33. Неужели так и должно быть? Может, я наглючил где?

И правильно сделали. А я сам себе не поверил, и вот почему: я сделал "прыжок" в рассуждениях, я пока лишь показал, что вероятность того, что |b-a|>sqrt(k) стремится к 1. Однако, может так случиться, что многие, например, половина, из этих a и b, отстоящих более, чем на sqrt(k), лежат по одну сторону, например, от 0, т.е. F(b)-F(a) будет для них заведомо меньше 1/2.

Надо сразу говорить о распределении (F(a),F(b)).
Чтобы было проще, посмотрим на рапределение F(x2)-F(x1), а не |F(b)-F(a)|. Ясно, что распределение F(x2)-F(x1) симметрично относительно 0, а потому распределение модуля легко получить из распределения без модуля (для положительных значений плотность умножим на 2, а для отрицательных она станет 0).

Зафиксируем x1. Тогда Pr{F(x2)-F(x1)<s}=Pr{F(x2)<F(x1)+s}=Pr{x2<Finv(F(x1)+s)}=(Finv(F(x1)+s)+k)/2k для F(-k)-F(x1) < s < F(k)-F(x1).
Теперь, если не фиксировать x1, s>0, то Pr{F(x2)-F(x1)<s} = int[x1=-k,Finv(F(k)-s)]{Finv(F(x1)+s)+k}/2kdx1/2k+int[x1=Finv(F(k)-s),k]{1}dx1/2k = int[x1=-k,Finv(F(k)-s)]{Finv(F(x1)+s)+k}dx1/2k+(k-Finv(F(k)-s))/2k

Допустим, что Таня не фиксирует F, а для простоты рассуждений пользуется также функцией равномерного распределения на [-k,k] (так интеграл легче брать, можно, конечно, какую-нибудь фиксированную функцию распределения взять, но влом нелинейные интегралы считать).
F(x) = (x+k)/2k для -k<x<k
Finv(y) = 2ky-k

Pr{F(x2)-F(x1)<s} = (1+2s-s^2)/2.

Не зависит от k!

Т.е. в этом случае ничто никуда не стремится! Это было для положительных s. Поэтому получилось Pr{F(x2)-F(x1)<0} = 1/2.

Плотность этого распределения равна 1-s, при s>0, т.е. треугольная! Соответственно если мы теперь посмотрим на плотность распределения для |F(x1)-F(x2)|, то она равна 2-2s на [0,1].

Какую среднюю "надбавку" в вероятности над 1/2 следует ожидать Тане? int[s=0,1]{s*(2-2s)}ds=1/3!

Так что, похоже, Ваша программа вполне правильно это показала! Т.е. она в среднем выигрывает с вероятностью 5/6 внезависимости от того, какого размера интервал (однако мы предположили, что она знает его размер и использует F() -- функцию равномерного распределения на [-k,k]).

Здравствуйте, vadimcher, Вы писали:

V>Играют один раз. Вова пишет на двух бумажках два различных числа. Таня выбирает одну из бумажек наугад, смотрит число и говорит, больше оно или меньше другого. Проверяют. Если сказала правильно, получает рубль, иначе отдает.

V>Может ли Таня выиграть с вероятностью больше 1/2?

Мы выяснили, что у Тани есть стратегия: увидев число x, она с вероятностью F(x) говорит, что другое число меньше, и с вероятностью 1-F(x) -- больше.

Вопрос: допустим, Вова загадывает два случайных числа, используя равновмерное распределение на [-k,k]. Какая оптимальная функция F() для Тани?

Если, например, F() = { 1,x>0, 0,x<0 }, т.е. z~F() z=0 с вероятностью 1, то она угадывает с вероятностью 3/4 (если оба загаданных Вовой числа разных знаков, то она точно угадает -- вер.1/2, а если одинаковых, то угадает с вероятностью 1/2 -- если вытащит нужное из пары, т.е. вероятность 1/2*1+1/2*1/2).

Если, например, F() -- функция равномерного на [-k,k] распределения, то, вроде бы, как установили, с вероятностью 5/6.

Какая оптимальная?

	От:	vadimcher
	Дата:	07.02.08 13:17
	Оценка:	21 (2)

	От:	Mr.Cat
	Дата:	05.02.08 20:44
	Оценка:	8 (1) -1

	От:	andyJB
	Дата:	07.02.08 11:56
	Оценка:	10 (1)

	От:	Mr.Cat
	Дата:	08.02.08 19:30
	Оценка:	10 (1)

	От:	vadimcher
	Дата:	19.01.08 18:27
	Оценка:	1 (1)

	От:	Кодт
	Дата:	20.01.08 11:20
	Оценка:

	От:	Аноним
	Дата:	22.01.08 14:35
	Оценка:

	От:	Аноним
	Дата:	22.01.08 15:54
	Оценка:

	От:	Chorkov
	Дата:	24.01.08 16:06
	Оценка: