Составитель Борис Демешев
 Скачать 1.58 Mb.
|
|
возвращающихся в начало, при неограниченном времени блуждания? Задача 20.5. В киосках продается ’открытка-подарок’. На открытке есть прямоугольник размером 2 на 7. В каждом столбце в случайном порядке находятся очередная буква слова подарок и звездочка. Например, вот так: П * * АО КОД Р * Прямоугольник закрыт защитным слоем, и покупатель не видит, где буква, а где - звездочка ТВИМС-задачник. Демешев Борис. Следует стереть защитный слой водном квадратике в каждом столбце. Можно попытаться угадать любое число букв. Если открыто 𝑛 > 0 букв слова подарок и не открыто ни одной звездочки, то открытку можно обменять на 50 · рублей. Если открыта хотя бы одна звездочка, то открытка остается просто открыткой. а) Какой стратегии следует придерживаться покупателю, чтобы максимизировать ожидаемый выигрыш? б) Чему равен максимальный ожидаемый выигрыш? Подсказка: Думайте! Задача 20.6. Задача, дороги из А в Б через С, С, С3 Вопросы про вероятности Задача 20.7. In the game of Racko you have 10 slots for cards to go in. At the start, cards are dealt to each player and put in order that they were dealt starting from the «highest slot». The cards are numbered 1-60. The object is to get all of your cards in order, by means of drawing and switching in a discard pile. When all your cards are in order, you call «Racko» and the hand is over. What is the probabilty that you will be dealt a «Racko»? Source: Задача, 𝑋 2 , . . . , 𝑋𝑛 are independent random variables, uniformly distributed on [0, 1]. What is the probability that 𝑋 1 + 𝑋 2 + ...𝑋 𝑛 < 1 ? Solution: We can compose a recurrence relation for the densities of sums in [0, 1]. A simple convilution formula gives the result 𝑝 𝑛 (𝑥) = 𝑥 𝑛 /𝑛! for 𝑥 ⊂ [0, Задача break a bar of length 1 unit into 2 pieces, choosing the break point uniformly along the length. What’s the mean length of the largest piece? More general problem. Let 𝑍 𝑛 be the smallest piece arising from breaking up the unit stick into n pieces using (𝑛 − 1) uniform [0, 1] random variables, say, 𝑋 1 , 𝑋 2 , ..., 𝑋 𝑛−1 . We prove that 𝑃 (𝑍 𝑛 > 𝑐) = (1 − 𝑐𝑛) 𝑛−1 Ror any 0 < 𝑐 < 1/𝑛, because then a simple integration by parts calculation shows that 𝐸(𝑍 𝑛 ) = 1/𝑛 2 To prove this equality, it’s enough to show that 𝑃 (𝑋 1 < 𝑋 2 < · · · < 𝑋 𝑛−1 , 𝑍 𝑛 > 𝑐) = (1 − 𝑐𝑛) 𝑛−1 (𝑛 − 1)! Because then I can multiply by (𝑛 − 1)!, i.e., adding this last probability over all possible orderings of the 𝑋 𝑖 ’s, to cover all possibilities for {𝑍 𝑛 > 𝑐} . Now finally, how do I prove this last equality? Saying that 𝑋 1 < ... < 𝑋 𝑛 and 𝑍 𝑛 > 𝑐 is equivalent to saying that 𝑋 1 > 𝑐, 𝑋 2 − 𝑋 1 > 𝑐, 𝑋 3 − 𝑋 2 > 𝑐, . . . , 𝑋 𝑛−1 − 𝑋 𝑛−2 > 𝑐, 1 − 𝑋 𝑛−1 > 𝑐. which is equivalent to the following range for the 𝑋 𝑖 ’s: 𝑋 1 ∈ (𝑐, 1 − (𝑛 − 1)𝑐)𝑋 2 ∈ (𝑋 1 + 𝑐, 1 − (𝑛 − 2)𝑐) . . . 𝑋 𝑘 ∈ (𝑋 𝑘−1 + 𝑐, 1 − (𝑛 − 𝑘)𝑐) . . . 𝑋 𝑛−1 ∈ (𝑋 𝑛−2 + 𝑐, 1 − 𝑐) So now, to calculate the probability of this event, we just have to integrate 1 over this region, i.e., we have to calculate the integral ∫︁ 1−(𝑛−1)𝑐 𝑐 ∫︁ 1−(𝑛−2)𝑐 𝑥 1 +𝑐 · · · ∫︁ 1−𝑐 𝑥 𝑛−2 +𝑐 1 𝑑𝑥 𝑛−1 𝑑𝑥 𝑛−2 · · · 𝑑𝑥 1 ТВИМС-задачник. Демешев Борис. roah@yandex.ru 89 To work through the first (n-2) integrals, we note the following equality for any 2 <= k <= n-1, which is simple enough to calculate: ∫︁ 1−(𝑛−𝑘)𝑐 𝑥 𝑘−1 +𝑐 (1 − (𝑛 − 𝑘)𝑐 − 𝑥 𝑘 ) 𝑛−(𝑘+1) (𝑛 − (𝑘 + 1))! 𝑑𝑥 𝑘 = (1 − (𝑛 − (𝑘 − 1))𝑐 − 𝑥 𝑘−1 ) 𝑛−𝑘 (𝑛 − 𝑘)! Then using induction, the integral we want to calculate reduces to integrating ∫︁ 1−(𝑛−1)𝑐 𝑐 (1 − (𝑛 − 1)𝑐 − 𝑥 1 ) 𝑛−2 (𝑛 − 2)! 𝑑𝑥 1 But if we think of 𝑥 0 as equalling 0, then the integral equality above for 2 ≤ 𝑘 ≤ 𝑛 − 1 also applies when 𝑘 = 1 , which gives us the answer we want. The size of the kth largest piece is given by 1 𝑛 (︂ 1 𝑛 + · · · +Задача I draw a ball one at a time with replacement from an urn with 100 balls and there’s a unique label for each of the balls so I know which one has been drawn. Find the expected number of draws I have to make in order to get all 100 Задача are waiting for a bus. They arrive a) with rate 𝜆 = 1/10 according to a Poisson process (so we have an average time of 10𝑚𝑖𝑛 between buses). b) with time between bus arrivals distributed as 𝑈[0, 20] (the average is also 10𝑚𝑖𝑛). If you take a random time what is your average wait for a Задача 𝑌 𝑛 be the sum of n rolls of a fair 6 faced die and 0 for n=0. Determine the probability that 𝑌 𝑛 divides 13 as n approaches Задача 𝑋1, 𝑋2, . . . , 𝑋 𝑛 are independent 𝑈(0, 1) r.v.Let 𝑍 is the random variable that equals 𝑘 for which the sum 𝑆 𝑘 = (𝑋 1 + 𝑋 2 + · · · + 𝑋 𝑛 ) exceeds 1 for the first time. Find Задача throw a fair coin until you get 8 heads in a row. What’s the probability you will see 8 consecutive tails (exactly) in the sequence prior to Задача have an unfair coin. Probability of tossing a head is p. What is the expected number of tosses needed to get N consecutive Задача offer to play a card game with you using a normal deck of 52 cards. the rules of the game are that we will turn over two cards at a time. if the cards are both black, they go into my pile. if they are both red, they go into your pile. if there is one red and one black, they go into the discard pile. we repeat the two card flipping until we’ve gone through all 52 cards. whoever has more cards in their pile at the end wins. i win if there is a tie. if you win, i pay you a dollar. how much would you pay to play this Задача randomly pick three numbers on (0;1). Let’s call them a,b,c. What is the probability that there is a triangle which edges of lenghts a,b,c? Related questions are: a,b are two random numbers picked from (0,1) – non-correlated. What are the expected values of : ТВИМС-задачник. Демешев Борис. roah@yandex.ru 90 1. Min (a,b) (answer: 1/3) 2. Min(a+b,1) (answer: 5/6) 3. Min(a+b,1) - Abs(a-b) (answer: 1/2) ... This gives answer to the question below. In this case, I think the probability of being able to form an n-simplex is 1-1/n! This is because we are given n+1 "areas"for the "faces which gives us n+1 inequalities. Each inequality cuts out an n-simplex from the unit cube of volume 1/(n+1)!. These n-simplices are nonintersecting, and there are n+1 of them, so the the volume we have left is 1 - (n+1)/(n+1)! = 1 - 1/n!. Note that in 2 dimensions, this gives us the correct answer, Задача 20XX final game Brazil-Germany 8:6 Brazil scored the first goal. After that, the score follows a random sequence until it reaches 8:6. What is the probability that Brazil has been at least 1 goal ahead for the whole duration of the Задача is the probability that the lottery draw will contain two or more consecutive Задача components of a two-component system fail after receiving a shock. Shocks of three types arrive independently and in accordance with Poisson processes. Shocks of the first type arrive at a Poisson rate of ?1 and cause the first component to fail. Those of the second type arrive at a Poisson rate ?2 and cause the 2nd component to fail. The third type of shock arrives at a Poisson rate ?3 and causes both components to fail. Let X1 and X2 denote the survival times for the two components. Show that X1 and X2 both have exponential Задача throwing a fair dice and each time you add the outcome to the total (you start from 0). What is the probability that the path of this process will visit a number N? What happens when 𝑛 → Задача have a call option on coin flips - the payoff of the "security"is the number of heads that comes up after a number of flips. The strike price of the option is 2. Need to value the option for 4 coin flips. (Interest rate is zero.) Also, find the delta of this option. —————————————- Markov property - стоит взглянуть (считается интеграл с броуновским движением Puzzle - соотношение скоростей плавающего и ловящего в круглом бассейне expectation problem - складываем равномерные величины, до тех пор пока сумма не станет больше 1 Series gamble - возможно неплохая задача shrimp by the pound - возможно неплохая задача color hats puzzle - решение задачи для одновременного раздавания шляп tossing - про сходимости по вероятности - хорошая задача is full of error and round Для стохана - поиграться с какой-нибудь функцией типа реализации броуновского движения (попробовать посчитать от нее обычный интеграл, построить график Там есть пробабилити: http://www.mathematik.uni-bielefeld.de/ sillke/ ТВИМС-задачник. Демешев Борис. И досмотреть пункты 4, 6, 19 (8 возможно досмотреть) настоит посмотреть theorem and its extensions aops: 88391 97893, 88977 - максимизация ожидаемого сохраненного броска - expected number of rounds 152421 - про экспоненциальное распределение с страховые случаи - первый шаг http://home.att.net/ Общее решение задачи про взвешивания Dilemma by William Poundstone про "случайные"с т.зр. человека последовательности : //𝑤𝑤𝑤.𝑤𝑖𝑙𝑚𝑜𝑡𝑡.𝑐𝑜𝑚/𝑚𝑒𝑠𝑠𝑎𝑔𝑒𝑣𝑖𝑒𝑤.𝑐𝑓 𝑚?𝑐𝑎𝑡𝑖𝑑 = 26&𝑡ℎ𝑟𝑒𝑎𝑑𝑖𝑑 = Водной пачке 56 эмэндэмсин (50 грамм. Эмэндэмсины бывают 5 цветов (не считая синего math nerds would call 2 500 finite (Leonid Levin) topic "simple про игру вполовину от среднего и эмпирические данные) Задача 20.23. >You have a black box with N 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 Задача W(t) is a standard Wiener process, the first passage time T(x) is defined as: T(x) = inft: W(t) = x T(x) has density function |𝑥|𝐸𝑥𝑝[−𝑥 2 /(2𝑡)]/𝑆𝑞𝑟𝑡[2𝑃 𝑖𝑡 3 ] I have a problem understanding why 𝐸[𝑇 (𝑥)] is Infinity for all x > 0. Now let’s say that you don’t know the stochastic process followed by the stock price, but you are given the price at time 0 of a call with expiration at time T as a function of the strike X (that is, given any input strike from 0 to infinity, you can output the price of the call). How would you use this information to determine the risk-neutral distribution of the stock price at time T? Let f(S, T) be the terminal risk-neutral pdf for the stock - the 2nd deriv of the call price with respect to strike is the discounted value of the risk-neutral pdf: C”(K, T) = exp(-rT) f(K, T) This is the well-known Breeden-Litzenberger Задача a loop of string of unit length. Suppose we cut the string independently and at random in n places. This will divide the loop into n pieces. ТВИМС-задачник. Демешев Борис. roah@yandex.ru 92 This month’s puzzle asks 1. What is the expected (average) size of the smallest piece? 2. What is the expected (average) size of the largest Задача Volume of a Simplex The length of the unit interval is 1. The area of the triangle bounded by the x and y axes, and x+y ? 1, is 1/2. The volume bounded by the xy, xz, and yz planes, and x+y+z ? 1, is 1/6. Can we generalize this? I just got a copy of Paul & Dominic’s Guide to Getting a Quant Job, which I hope everyone reads. I say not not for your benefit in getting a job, but for my benefit in saving time and annoyance when looking to fill a job. I’m posting here because it recommends this forum for practicing for brain teaser interview questions. That’s an excellent idea. But if that’s what you’re here to do, you should also know how your answer will be scored. So here’s my take on it, I invite other opinions and comments. I ask three types of brain teaswer type questions. (1) Really easy ones. This is the equivalent to moving the mouse around at random to see if the computer is frozen. An example might be, "Suppose I flip a fair coin 10 times and pay you $1 if the first flip is heads, $2 if the second flip is heads, up to $10 if the 10th flip is heads. What is your expected payout?"I assume that anyone applying for a quant job knows how to sum the numbers from 1 to 10 (or has memorized the answer) and can divide by 2. If not, I don’t want them anyway. I score the answers as follows: 10 - Listens carefully as the problem is posed, thinks for a minute, then answers $27.50 without embellishment. 8 - Same as above, except asks for unnecessary clarification, appears suspicious of a trap, needs to use pen and paper or feels it necessary to explain the reasoning. 6 - Same as 8 or 10, but gets a wrong answer between $20 and $35, or a clearly unreasonable wrong answer but says it’s unreasonable. 4 - Same as 8 or 10, but gets a clearly unreasonable wrong answer and doesn’t mention it. 2 - Cannot understand the question, or pretends to misunderstand it to avoid giving a numerical answer. 0 - Throws out random phrases and numbers and watches my face hoping for some kind of hint, like Clever Hans, the horse that could do math. The point here is that good quants are confident of their ability to recognize and solve simple problems. Most applicants are not good quants. You can do well on exams without this skill, because problems are often set at an expected moderate level of difficulty, if it’s too easy or too hard you probably misunderstood it. Real work is not like that. If you’re too scared to give a simple answer to a simple question, you’re not going to work out. (2) Hard ones, like many of the ones you will find here. Here the scoring is: 10 - Listens carefully as the problem is posed, thinks for a minute, then says anything intelligent that indicates they understand why the problem is hard, and shows some confidence at being able to solve it. Right or wrong doesn’t matter. 8 - Answers immediately and correctly (I assume in this case they’ve heard it before). 6 - Says, "I’ve heard it before,"and answers correctly 4 - Says, "I’ve heard it before,"and answers incorrectly, or in a way that shows they don’t understand the answer, or can’t remember the answer 2 - Cannot understand the question, or pretends to misunderstand it to avoid giving an answer. 0 - Throws out random phrases and numbers and watches my face hoping for some kind of hint, like Clever Hans, the horse that could do math. There are people who expect to get the right answer, and are happy to be judged on their actual level of ТВИМС-задачник. Демешев Борис. roah@yandex.ru 93 intelligence. There are others who know in their hearts they will never get the right answer, and/or hope to mislead you into thinking they are smarter than they are. Only the first group will get considered for the job. I judge almost entirely on demeanor. Good people are eager to get these questions, bad people dread them. Good people are proud when they get it right and honest but unembarassed when they get it wrong. Bad people make excuses and complaints either way. (3) Open-ended ones, like "Give me your personal subjective 50% confidence interval for the Gross Domestic Product of Finland in USD." 10 - Without prompting comes up with a reasonable approach like, "I know it’s a small country, but it’s not so tiny I’ve never heard of it, so I’ll guess 5 million population. It’s not known as particularly poor or rich for Northern Europe, so I’ll guess $10,000 per capita income. That gives me a point estimate of $50 billion. National income and GDP are close enough to each other for this approximation. For a 50% confidence level I’d go 2 to 20 million population and $5,000 to $20,000 per capita income, that gives me $10 billion to $400 billion. Considering everything, I think that’s too big a range, I’ll go with $25 billion to $150 billion. If I had to bet, I’d be equally happy to bet the true number is inside as outside that range." 8 - Same as above but needs prompting and either uses some clearly unreasonable numbers or makes numerous math errors. 6 - Thinks for a while and comes up with a reasonable range, but can’t discuss it intelligently. 4 - Cannot understand what a 50% confidence interval is. 2 - Keeps asking for more information, or explains how they would look up the answer. 0 - Throws out random phrases and numbers and watches my face hoping for some kind of hint, like Clever Hans, the horse that could do math. Here I’m looking for ability to understand and follow instructions, some small amount of practical sense and knowledge of the world and ability to use quantitative reasoning. I retired this question when a candidate outsmarted me. I’d used it for about two years and gotten scores from 0 to 10. Then someone said "My interval is all dollar amounts that round to odd integer amounts."He turned a (3) question into a (2) one, and got the Задача are n points 1, 2, 3, ... n arranging in order on a circle. If the i th point is n, then the i+1 th point is 1. We choose a pair of adjacent points at random with equal probability of 1/(n-1). We continue to choose pairs from the points on the circle at random. If one of the points of the pair has been chosen before, we disregard this pair. The process is repeated until no new pair can be chosen and only isolated points remain. What is the mean number of isolated Задача bar in a town has 25 seats in a row. The folks in this town are antisocial, so they only take a seat of which the adjacent seats are empty, or leave. If you are the bartender, how can you seat your first guest to get more people (expected) at your bar? Задача 20.29. Найти вопрос где бы ее использовать 𝑛-odd => 0, 𝑛 - even => 2 Задача and social egalitarianism Source: Romanian TST 5 2007, Problem 2 The world-renowned Marxist theorist Joric is obsessed with both mathematics and social egalitarianism. Therefore, for any decimal representation of a positive integer 𝑛, he tries to partition its digits into two ТВИМС-задачник. Демешев Борис. roah@yandex.ru 94 groups, such that the difference between the sums of the digits in each group be as small as possible. Joric calls this difference the defect of the number n. Determine the average value of the defect (over all positive integers), that is, if we denote by 𝛿(𝑛) the defect of 𝑛, compute lim 𝑛→∞ ∑︀ 𝑛 𝑘=1 𝛿(𝑘) 𝑛 (wilmott) "вероятности"для натуральных чисел that 2 𝑛 |