Составитель Борис Демешев
 Скачать 1.58 Mb.
|
|
а) Какова вероятность того, что когда-нибудь снова будет написано б) Каков (as) предел средней длины слова? Задача 5.109. Пусть 𝑆 𝑛 - симметричное случайное блуждание. Те. 𝑆 0 = 0 , 𝑆 𝑛 = 𝑆 𝑛−1 + 𝑋 𝑛 , где 𝑋 𝑛 - iid, 𝑃 (𝑋 𝑛 = 1) = 𝑃 (𝑋 𝑛 = −1) = а) Найдите lim 𝑚→∞ 𝑃 (𝑆 2𝑚 =2𝑟) 𝑃 (б) Найдите lim 𝑚→∞ 𝑃 (𝑆 2𝑚 = 2𝑟) , lim 𝑛→∞ 𝑃 (𝑆 𝑛 ≥ в) Запись 𝑘|𝑚 означает, что 𝑘 делит 𝑚 (𝑚 делится на 𝑘). Найдите lim 𝑛→∞ 𝑃 (и lim 𝑛→∞ 𝑃 (3|𝑆 𝑛 ) Задача 5.110. Пусть 𝑆 𝑛 - несимметричное случайное блуждание. Те. 𝑆 0 = 0 , 𝑆 𝑛 = 𝑆 𝑛−1 + 𝑋 𝑛 , где 𝑋 𝑛 - iid, 𝑃 (𝑋 𝑛 = 1) = 𝑝 = 1 − 𝑃 (𝑋 𝑛 = а) Найдите вероятность того, что случайное блуждание когда-нибудь вернется в исходную точку б) Пусть 𝑝 > 0.5. Найдите ожидаемое время выигрыша 𝑟 рублей. Задача 5.111. [ Steele, Корпорация стремится поддерживать курс своих акций на уровне 20$. Поэтому вероятности изменения курса выглядят таки При 𝑘 > 20: 𝑃 (𝑌 𝑛+1 = 𝑘 + 1|𝑌 𝑛 = 𝑘) = и 𝑃 (𝑌 𝑛+1 = 𝑘 − 1|𝑌 𝑛 = 𝑘) = При 𝑘 < 20: 𝑃 (𝑌 𝑛+1 = 𝑘 + 1|𝑌 𝑛 = 𝑘) = и 𝑃 (𝑌 𝑛+1 = 𝑘 − 1|𝑌 𝑛 = 𝑘) = 1/3 ТВИМС-задачник. Демешев Борис. Найдите ожидаемое время падения курса акций с 25$ до 18$. Задача 5.112. Для лотерии выпущено 10000 билетов, из них 100 билетов являются призовыми и еще 200 дают право получить еще один билет. Какова вероятность получить приз, если купить один билет? Задача 5.113. I roll 100 standard dice. I get one point for each die for which the number of dots on the top face is greater than two. What is the probability that the number of points I get is... a) Even? b) Divisible by three? c) =1 (mod 3)? source: aops, Задача sticks Take a stick and break it at a location selected with uniform density along its length. Throw away the left-hand piece and break the right-hand one at a location selected with uniform density along its length. Continue forever. What is the probability that one of the discarded left-hand pieces is more than half as long as the original stick? Source: aops, Задача and Bonnie play a game in which they take turns tossing a fair coin. The winner of a game is the first person to obtain a head. Alfred and Bonnie play this game several times with the stipulation that the loser of a game goes first in the next game. Suppose that Alfred goes first in the first game, and what is the probability that he wins the sixth game? source: aops, Задача a random walk on a fractal lattice (see attached Картинка из центра 4 направления. Далее каждое направление делится натри, потом еще натрии т.д. до бесконечности starts at origin O. At every time-step it moves in one of four directions, north south east or west, with equal probability. The north-south generator does not commute with the east-west generator – e.g. east, north <> north, east Clearly the only way the particle can revisit a particular point is by retracing its steps. Two questions: 1. What is the probability that the particle ever hits the point A? 2. What is the probability of hitting A before Задача Поисковик google рассчитывает рейтинг страницы (pagerank) последующему алгоритму предполагается, что если на странице есть 𝑛 ссылок, то пользователь с вероятностью 85% уходит на одну из этих ссылок (выбирая саму ссылку равновероятно) и с вероятностью 15% уходит на случайно выбираемую страницу. Рейтинг страницы - это вероятность того, что после длительного блуждания пользователь окажется на данной странице. Рассчитайте рейтинг для следующей сети (картинка) ссылка: википедия Задача 5.118. Выборы В выборах участвуют два кандидата. Вначале выборов каждый из них голосует сам за себя. Затем каждый из миллиона жителей по очереди голосует за одного из кандидатов. При этом если за кандидата А было подано 𝑛 голосов, аза кандидата В - 𝑚 голосов, то вероятность того, что очередной избиратель будет голосовать за А равна 𝑛 𝑛+𝑚 Какова вероятность того, что за кандидата А проголосует менее 20% жителей Prof. Vazirani’s Problems Задача 5.119. В коробке лежат 30 зеленых и 50 красных шаров. Мы извлекаем два наугад, один берем в левую ТВИМС-задачник. Демешев Борис. руку, другой - в правую. Шар в левой руке красим в цвет шара, находящегося в правой руке. Затем возвращаем шары в коробку. Снова извлекаем два наугад и т.д. до тех пор пока в коробке все шары не окрасятся в один цвета) Какова вероятность того, что шары будут окрашены в красный цвет? б) Сколько в среднем пар шаров будет извлечено? Задача 5.120. You have a black box with 𝑁 balls in it - each of a different color. Suppose you take turns as follows - randomly pick a ball in each hand, and paint the left hand ball the same color as the right hand ball. You replace both balls in the box before the next turn. How many turns do you expect before all balls are the same color? Solution: source: Ariel Landau in sci.math in September 1995 solution: Lew Mammel, Jr., Robert Задача and urns There are 𝑛 urns. Each urn has 𝑎 white balls and 𝑏 black balls. We extract at random a ball from the first urn and put it into the second one. We extract at random a ball from the second urn and put it into the third one. And so on. At the last step we extract a ball from the last urn. what is the probability of the last ball extracted to be white? source: aops, april 08 Задача 5.122. У Вас на руках 𝑛 игральных карт, часть из них черные, часть - красные. Вы выбираете одну из них наугад и заменяете на карту другого цвета. Затем снова выбираете одну наугад и снова заменяете ее на карту другого цвета. Итак далее до тех пор, пока все карты на руках не станут одноцветными. Найдите закон распределения числа замени ожидаемое число замен, если: а) изначально на руках 2 красных и 2 черных карты б) изначально на руках 3 черных и 3 красных карты Задача 5.123. Картинку в студию квадрат 𝐴𝐵𝐶𝐷, центр 𝐸. Нарисованы все стороны квадрата и все отрезки, соединяющие 𝐸 с вершинами. Жук начинает в точке 𝐸. Из 𝐸 жук равновероятно идет в любую точку (𝐴, 𝐵, 𝐶 и 𝐷). Если на ом ходу жук находится в вершине квадрата, то он с вероятностью 𝑛−1 𝑛 идет в центр и с вероятностью в каждую из двух соседних вершина) Какова вероятность того, что ровно через 𝑛 ходов он снова будет в б) Какова вероятность того, что ровно через 𝑛 ходов он впервые вернется в в) Каково математическое ожидание времени возвращения в 𝐸? source: wilmott, bt, 63190 Задача 5.124. Игральный кубик с 𝑛 гранями подбрасывают до тех пор, пока каждый следующий бросок больше предыдущего. Если какой-то результат меньше либо равен предыдущему, то подбрасывания прекращаются. Игра прекращается на первом ходу, если при первом подбрасывании выпало число меньше либо равное а) Сколько в среднем будет подбрасываний? б) Допустим 𝑘 = 0 (те. на первом броске игра никогда не заканчивается. Чему равен предел среднего числа подбрасываний при бесконечном в) Чему равно среднее значение последнего результата? г) Чему равно среднее значение суммы подбрасываний? Коммент: в и г не проверялись на компактность ответа wilmott, bt, Задача and B are to play a game. A third player, N constantly throws 2 dices. Player A wins if N rolls ’12’. ТВИМС-задачник. Демешев Борис. roah@yandex.ru 47 Player B wins if there are 2 consecutive 7 rolled by N. What is the probability that A wins? Задача 5.126. На даче у мистера А две входных двери. Сейчас у каждой двери стоит две пары ботинок. Перед каждой прогулкой он выбирает наугад одну из дверей для выхода из дома и надевает пару ботинок, стоящую у выбранной двери. Возвращаясь с прогулки мистер А случайным образом выбирает дверь, через которую он попадет в дом и снимает ботинки рядом с этой дверью. Сколько прогулок мистер А в среднем совершит, прежде чем обнаружит, что у выбранной им для выхода из дома двери не осталось ботинок? Источник: American Mathematical Monthly, problem E3043, (1984, p.310; 1987, p.79) Задача 5.127. У Мистера Х есть 𝑛 зонтиков. Зонтики мистер Х хранит дома и на работе. Каждый день утром мистер Х едет на работу, а каждый день вечером - возвращается домой. При этом каждый раз дождь идет с вероятностью 0.8 независимо от прошлого, (те. утром дождь идет с вероятностью и вечером дождь идет с вероятностью 0.8 вне зависимости оттого, что было утром. Если идет дождь и есть доступный зонтик, то мистер Х обязательно возьмет его в дорогу. Если дождя нетто мистер Х поедет без зонтика. Какой процент поездок окажется для мистера Х неудачными (те. будет идти дождь, а зонта не будет) в долгосрочном периоде? Задача 5.128. You are many squares or units away from your destination. Let n be the number of squares involved. You roll a pair of dice repeatedly until you reach (by exact count) or pass that target square. Let P(n) = the probability of landing on said target square in the process. What is the limit of P(n) as n approaches infinity? source: AMATYC I-1 by Dave Задача teams, A and B will play a series of games. The probability of A winning each game is p. The overall winner is the first team to have won two more games than the other. a) Find the propbability that team A is the overall winner b)Find the expected number of games played. source: aops, t=287021, Ross, chapter 2, Problem 49, Kent Merryfield Задача 5.130. Вася подбрасывает монетку до тех пор, пока хотя бы один раз не выпадет орел и хотя бы один раз - решка. Монетка неправильная, орел выпадает с вероятностью 𝑝. Пусть 𝑋 - требуемое число подбрасываний. Найдите 𝑃 (𝑋 = 𝑘), 𝐸(𝑋), 𝑉 𝑎𝑟(𝑋). 6 Принцип отражения и прочее про случайное блуждание Задача 6.1. За кандидата 𝐴 подано 𝑎 голосов, за кандидата 𝐵 - 𝑏 голосов, 𝑎 > 𝑏. Вовремя подсчета голосов бюллетени достают из урны по одному в случайном порядке. Какова вероятность того, что на протяжении всего подсчета голосов кандидат 𝐴 будет впереди кандидата 𝐵? Задача 6.2. Рассмотрим симметричное случайное блуждание. 𝑁 𝑘 - количество посещений точки 𝑘 до первого возвращения к 0. Заметим, что может принимать значение +∞. a) Докажите, что 𝑃 (𝑁 𝑘 > 0) = 1 2 1 𝑘 b) Докажите, что 𝑃 (𝑁 𝑘 > 𝑗 + 1|𝑁 𝑘 > 𝑗) = 1 2 + 1 2 𝑘−1 𝑘 c) Найдите 𝐸(𝑁 𝑘 ) d) Найдите 𝑃 (𝑁 𝑘 = +∞) e) Как изменятся ответы, если случайное блуждание будет несимметричным (вероятности 𝑝 и 𝑞 = 1 − 𝑝 ) Source: Steele, Задача ТВИМС-задачник. Демешев Борис. Частица движется по правильному многоугольнику из 𝑚 + 1 вершин, занумерованных от 0 до Стартует она в вершине 0. Следующая вершина выбирается равновероятно из двух соседних. Частица останавливается, когда обойдет все вершины. а) Какова вероятность того, что частица никогда не посетит вершину б) Какова вероятность того, что частица закончит свой маршрут в вершине 𝑘? Source: Ross, example 2.52 Задача 6.4. Пусть 𝑆 𝑛 - симметричное случайное блуждание, а 𝜏 - время первого посещения точки 1. С помощью принципа отражения найдите 𝑃 (𝜏 = 2𝑘 − 1). 7 Геометрическая вероятность Задача 7.1. На бумаге проведена прямая. На бумагу бросают иголку. Какова вероятность, что острый угол между прямой и иголкой будет меньше 10 градусов? Задача 7.2. Вася бегает по кругу длиной 400 метров. В случайный момент времени он останавливается. Какова вероятность того, что он будет ближе, чем в 50 мот точки старта Дальше, чем в 100 м? Задача 7.3. Внутри единичного квадрата равновероятно выбирается одна точка. Пусть 𝑋 и 𝑌 - абсцисса и ордината этой точки. Найдите 𝑃 (𝑋 < 0, 75), 𝑃 (𝑋 ≤ 𝑎) для произвольного 𝑎, 𝑃 (𝑋 > 0, 5|𝑋 + 𝑌 > 0, 5), 𝑃 (𝑋 + 𝑌 > 0, 5|𝑋 > 0, 5) , 𝑃 (𝑋 · 𝑌 > 1/3|𝑋 + 𝑌 < 2/3), 𝑃 (𝑋 > 0, 3|𝑌 < 0, 7) Задача 7.4. Внутри единичного квадрата выбирается точка наугад. Какова вероятность того, что она будет ближе к центру, чем к любой из вершин? Задача 7.5. A circle has 2006 points chosen so that the arcs between any two adjacent points are equal. Three of these points are chosen at random. a) Find the probability that the triangle is right b) Find the probability that the triangle formed is isosceles Задача 7.6. На отрезке [0;1] (равномерно и независимо друг от друга) выбираются две точки. а) Какова вероятность того, что расстояние между ними не более б) Какова вероятность, что из трех частей, на которые они разбили отрезок, можно сложить треугольник Задача7.7.На планету (окружность с центром 𝑂, НЕ круг) сели три корабля, координаты их посадки независимы и равномерно распределены по окружности. Два корабля 𝐴 и 𝐵 могут связаться друг с другом, если ∠𝐴𝑂𝐵 < а) Какова вероятность того, что между кораблями будет связь (возможно непрямая)? б) Какова вероятность того, что каждый корабль сможет добраться до базы Запаса горючего хватает, чтобы проехать расстояние равное радиусу. в) Какова вероятность того, что наименьший суммарный расход горючего, необходимый для сбора всех кораблей водной точке, будет меньше 0,25? Единицы горючего хватает, чтобы один корабль объехал всю планету. в) Решите аналогичные а-б задачи в трех измерениях. Задача 7.8. Two points on the surface of a sphere are drawn uniformly at random. a) Expected distance? b) Maximum pdf distance? Задача 7.9. На окружности наугад выбираются точки 𝐴, 𝐵, 𝐶, 𝐷, 𝐸 и 𝐹 . Какова вероятность того, что треугольники и 𝐷𝐸𝐹 не пересекаются? Задача 7.10. ТВИМС-задачник. Демешев Борис. В круге радиуса 𝑟 случайным образом (равномерно) выбирается точка. Пусть 𝑋 - расстояние от точки до центра круга. а) Найдите функцию плотности 𝑋 b) Найдите 𝐸(𝑋) c) Найдите 𝐸(𝑋 𝑛 ) Задача 7.11. В окружность радиуса 𝑟 вписан правильный угольник. Внутри него случайным образом (равномерно) выбирается точка. Пусть 𝑋 - расстояние от точки до ближайшей стороны 𝑛-угольника. а) Найдите функцию плотности 𝑋 b) Найдите 𝐸(𝑋) c) Найдите lim 𝑛 𝐸(𝑋) Задача 7.12. На окружности случайным образом выбираются 3 точки. Эти три точки являются вершинами тре- угольника. а) Какова вероятность того, что центр окружности лежит внутри построенного треугольника? б) Какова вероятность, что треугольник остроугольный? Задача 7.13. На окружности случайным образом выбираются 𝑛 точек) Какова вероятность того, что центр окружности лежит внутри многоугольника с вершинами в этих точках? б) Какова вероятность того, что эти точки можно накрыть дугой с углом 𝛼 = 2𝜋 · 𝑡, где 𝑡 ∈ [0; в) Изменится ли ответ задачи, если точки выбираются не на окружности, а на плоскости, так что все углы равновероятны и вероятность попадания в начало координат равна 0? c) In the border of a perfectly circular piece of wood we choose N points at random to place legs and make a table. What is the probability that the table will stand without falling? Задача 7.14. На окружности случайным образом выбираются точки, до тех пор пока многоугольник, образуемый точками не будет содержать центр окружности. Каково ожидаемое количество сторону такого многоугольника? Задача 7.15. На окружности случайным образом выбираются точки, до тех пор пока длина минимальной дуги их накрывающей не станет больше 2𝜋 · 𝑡, где 𝑡 ∈ [0; Каково ожидаемое количество точек? Задача 7.16. На отрезке [0; 1] случайным образом выбираются 𝑛 точек. Какова вероятность, что их можно накрыть отрезком длины 𝑡? Задача 7.17. Имеется правильный (2𝑛 + угольник. Наугад выбираются три различные точки) Какова вероятность того, что центр многоугольника лежит внутри треугольника с вершинами в выбранных точках) Чему равен предел этой вероятности? Задача 7.18. На сфере случайным образом выбираются 4 точки. Эти четыре точки являются вершинами пирамиды. Какова вероятность того, что центр сферы лежит внутри построенной пирамиды? Задача 7.19. Вася отмечает на яблоке 𝑛 точек случайным образом. Затем Петя пытается разрезать яблоко на две половинки так, чтобы все точки лежали водной половинке. Какова вероятность того, что Пете удастся это сделать Bay Area Math Meet, Test of Ingenuity 1999 - Problem 20 Задача 7.20. На окружности (не на круге) выбирается равномерным образом две точки. Каково ожидаемое рас ТВИМС-задачник. Демешев Борис. стояние между ними? Задача 7.21. Внутри единичного круга выбирается равномерным образом две точки. Каково ожидаемое расстояние между ними? Страшный интеграл или...[?] Задача 7.22. Вася хочет случайным образом равномерно выбрать точку внутри круга единичного радиуса. Для этого он использует две равномерных независимых случайных величины 𝑟 и 𝜃. Он берет в качестве координат точки 𝑥 = 𝑟𝑐𝑜𝑠(𝜃) и 𝑦 = Прав ли он Если нетто как исправить алгоритм? Задача 7.23. IBM, Ponder На плоскости взят произвольный треугольник. Внутри него равномерно и независимо друг от друга выбираются 3 точки. Эти три точки образуют новый треугольник. Каково ожидаемое отношение площади нового треугольника к площади исходного? Задача 7.24. IBM, Ponder На плоскости взят произвольный квадрат. Внутри него равномерно и независимо друг от друга выбираются 3 точки. Эти три точки образуют треугольник. Каково ожидаемое отношение площади треугольника к площади исходного квадрата? Задача 7.25. Пусть 𝑋 и 𝑌 независимы и равномерны на отрезке [0; 1]. Найдите вероятность того, что 𝑋 𝑌 будет ближе к четному числу, чем к нечетному. Подсказка: Да поможет вам святой арктангенс Putnam 1993 Задача 7.26. Св. 𝑏 распределена равномерно на отрезке [0; 1]. На плоскости проводится прямая 𝑦 = 𝑏𝑥. С какой вероятностью она отрезок с концами в точках (2; 1) и (4; 1)? Задача 7.27. Пусть 𝑋 и 𝑌 независимы и равномерны на отрезке [0; 1]. Найдите вероятность того, что в десятичной записи 𝑋 𝑌 первой ненулевой цифрой будет единица http://en.wikipedia.org/wiki/Benford’s_law Source: Задача Рассмотрим поподробнее ценники в супермаркетах. Предположим, что вероятность того, что цена начинается на цифру 𝑛 (𝑛 ∈ {1, 2, 3, ..., 9}) одинакова во всех странах и зависит только от 𝑛. Иными словами, если перевести цены из одной валюты в другую, вероятность того, что на первом месте стоит цифра 𝑛 не должна измениться. а) Найдите вероятность того, что цена начинается с цифры 1; б) Найдите вероятность того, что цена начинается с цифры 9; Comment: доработать. lim? Задача sides of a regular hexagon are chosen at random, and their midpoints are connected. Find the probability of the resulting triangle being right. Source: aops, Задача stick is broken into 𝑛 pieces. If three of these pieces are chosen at random, what is the probability that they form a Задача a stick of unit length. Break this in two pieces at random. Then break the longest piece in two pieces ТВИМС-задачник. Демешев Борис. roah@yandex.ru 51 |