Задачка от Яндекса (не сочтите за рекламу)

Логические задачи

Модераторы: Азарапетыч, Администрация

Ответить
Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Задачка от Яндекса (не сочтите за рекламу)

Сообщение Инна »

На главной странице Яндекса есть ссылка с CTR 1,5%. Ссылку изменили, и, чтобы проверить, как изменился CTR, стали показывать новую ссылку в 4% случаев. Сколько нужно показов главной страницы Яндекса, чтобы узнать об изменении CTR с точностью 5%? Почему?
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

AndrNiko
Графоман со стажем
Графоман со стажем
Сообщения: 517
Зарегистрирован: 16 апр 2005, 09:03
Пол: Мужской
Откуда: Минск

Re: Задачка от Яндекса (не сочтите за рекламу)

Сообщение AndrNiko »

Стандартная задача из курса теории вероятностей и матстатистики технического вуза. И в чём прикол? В том, что нужно ещё знать (задать) доверительную вероятность, иначе задача не имеет смысла?
С уважением Андрей Николаев.
- - -
Нам не дано предугадать, Как слово наше отзовётся... (Ф.Тютчев).

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Задачка от Яндекса (не сочтите за рекламу)

Сообщение Инна »

Ты прав, что задача не совсем соответствует предполагаемому здесь стандарту.
Лет 20 с лишним когда-то решала такие задачи, но сейчас все начисто вылетело, хочется освежить.
Но у меня возник вопрос в ее корректности, можно и это пообсуждать.
Предполагается, что задача имеет решение.
У меня возник вопрос: изменили ссылку - значит изменили дизайн ссылки или ресурс, на который ссылается?
Видимо второе.

Насчет доверительной вероятности - видимо она как-то заложена в 5%.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

AndrNiko
Графоман со стажем
Графоман со стажем
Сообщения: 517
Зарегистрирован: 16 апр 2005, 09:03
Пол: Мужской
Откуда: Минск

Re: Задачка от Яндекса (не сочтите за рекламу)

Сообщение AndrNiko »

Инна писал(а):У меня возник вопрос: изменили ссылку - значит изменили дизайн ссылки или ресурс, на который ссылается?
Очевидно, внешний вид ссылки как-то изменился, иначе с чего бы мог измениться CTR (отношение числа кликов к числу показов, если я правильно понял). Если речь идёт о реальной ситуации, то ресурс вряд ли изменился. Ведь задача исполнителя - рекламировать тот ресурс, за который им заплатили. Хотя есть нюанс: если посетитель страницы видит URL ресурса (например, в строке статуса при наведении на ссылку), то этот URL влияет на выбор посетителя (перейти по ссылке или нет) и, таким образом, тоже является элементом дизайна. Но мы ушли в дебри...
Инна писал(а):Насчет доверительной вероятности - видимо она как-то заложена в 5%.
Я не вижу, как это может быть. Это два независимых параметра. Если задача не учебная, а из реальной рабочей практики, то принимается какое-то значение исходя из здравого смысла и финансовых соображений. Я бы взял 90%, если нет особых причин брать иное значение.

А решать задачу мне совершенно не интересно. Надо вытаскивать с задней полки шкафа учебник и вспоминать, как это делается.
С уважением Андрей Николаев.
- - -
Нам не дано предугадать, Как слово наше отзовётся... (Ф.Тютчев).

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Задачка от Яндекса (не сочтите за рекламу)

Сообщение Инна »

Андрей, я поняла, что ты имел в виду, говоря про недостаточность информации.
Ведь ответ должен содержать два параметра (точность и достоверность) и выглядеть приблизительно так:
С вероятностью р% искомая величина равна с(1+-d%).
И 5% скорее всего, относятся к d, а не к р.

Но все же предположим, что задача сформулирована корректно и никаких дополнительных данных не нужно.
1. Мне в голову пришел такой вариант трактовки (это даже не из теорвера, а когда погрешность изучали что-то было).
Случайная величина имеет матожидание и дисперсию. Короче, надо найти количество измерений, чтобы квадратичное отклонение было не больше 5%.
Возможно ли такое?

2.Еще вариант трактовки, менее симпатичный.
Можно ли считать, что для узнавания изменения параметра (CTR) изначально равного 1,5% с точностью 5%, достаточно (и необходимо) измерить новый CTR с точностью 1,5%*5%= 0,075% ?
Если да, то задача становится счетной.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

AndrNiko
Графоман со стажем
Графоман со стажем
Сообщения: 517
Зарегистрирован: 16 апр 2005, 09:03
Пол: Мужской
Откуда: Минск

Re: Задачка от Яндекса (не сочтите за рекламу)

Сообщение AndrNiko »

Инна писал(а):Случайная величина имеет матожидание и дисперсию. Короче, надо найти количество измерений, чтобы квадратичное отклонение было не больше 5%.
Возможно ли такое?
Да, такая задача имеет смысл, хотя доверительная вероятность тут получается низкая, порядка 50%. И эту задачу я даже могу приблизительно решить "на пальцах", без справочника. Если событие происходит с вероятностью p, то матожидание количества событий после N испытаний будет, очевидно, N*p. А среднеквадратичное отклонение примерно равно корню квадратному из этой величины (из N*p). Это уже не совсем очевидно, но это так (давно учил и могу ошибиться на коэффициент, не очень сильно отличающийся от 1). Значит, чтобы среднеквадратичное отклонение какой-то величины было 1/20, эта величина должна быть порядка 20*20=400. Дальше простая арифметика:
ссылка с CTR 1,5% ... стали показывать новую ссылку в 4% случаев
Итого: 400 / 1.5 * 100 / 4 * 100 = 4 000 000 / 6 ~ 700 000 показов.

Для разумной доверительной вероятности значение должно быть в несколько раз больше. Ну, примерно от 3 до 10 раз. Если кто недавно это учил и не успел забыть - пусть ответит точнее.
Инна писал(а):2.Еще вариант трактовки, менее симпатичный.
Можно ли считать, что для узнавания изменения параметра (CTR) изначально равного 1,5% с точностью 5%, достаточно (и необходимо) измерить новый CTR с точностью 1,5%*5%= 0,075% ?
Мне кажется, это не вариант трактовки, а просто очевидная вещь, которая никак не меняет трактовку.
С уважением Андрей Николаев.
- - -
Нам не дано предугадать, Как слово наше отзовётся... (Ф.Тютчев).

nikita2
Читатель
Читатель
Сообщения: 1
Зарегистрирован: 03 июл 2011, 08:31

Re: Задачка от Яндекса (не сочтите за рекламу)

Сообщение nikita2 »

Здравствуйте.
Тоже недавно столкнулся с этой задачкой. Предлога рассматривать схему Бернулли: х = 1 если нажали на ссылку и х = 0 если не нажали на ссылку. Тогда ЦТР это матожидание (Е(х) = ЦТР).
То есть мы имеем случайную величину х Р(х=1)=р Р(х=0)=1-р. Из неравенства Чебышёва следует неравенство P(|(Sn)/n - p|>e) < 1/(4ne^2), где Sn -- число успехов при n испытаниях (для нас: сколько раз нажали на ссылку), р -- матожидание (для нас: CTR (который новый и мы его не знаем)).
Для того чтобы было выполнено неравенство P(|(Sn)/n - p|>e) < a (то есть вероятность отклонения от цтр более чем на е меньше а) достаточно взять n = 1/(4ae^2).
Видимо для этой задачи e = 0.05*0.015 (5% от значения предыдущего цтр), также возьмём а = 0.01 (99%).

тогда n = 1/4*(100000/75)^2*100 = 44 444 444. Поскольку показывают в 4% случаев, то 1 111 111 111.
Честно говоря, очень большое число. Причина в том, что е = 0.00075. Например, если е = 0.05, то число показов ссылки = 10 000.

Вопрос: что в этой задаче означает "с точностью 5%"?

Ответить

Вернуться в «Задачки»