Q: A sultan has a 100 daughters. Each of them has a fixed amount of dowry associated. Nothing is known about the distribution of dowry amounts among the princesses. You are to pick one of them. You are allowed to know the dowry amount following which you have to make a decision on whether to accept that princess or not. If you reject the princess you move on to the next princess and you cannot come back to the princess you have rejected. Your goal is to pick the princess with maximum amount of dowry. What should your optimal strategy be and what is your probability of success?
The Probability Tutoring Book: An Intuitive Course for Engineers and Scientists (And Everone Else!)
A: This one is a classic problem and there is adequate coverage around the web on how to solve this particular puzzle (which is also popularly called the secretary problem/interviewer problem etc). It is also a great introduction to one of the most interesting areas in probability (multi arm bandits/optimal stopping etc). The optimal solution has the form of sampling the first "r" princesses, taking note of the highest amount seen up until "r" and then subsequently picking an amount that is greater than this chosen maximum. To understand this, take a look at the following figure, each box being an amount, and let "n" be the number of princesses.
A first step to understand is the probability of the maximum value being on any index "i". This is simple. It is 1/n. Next, the strategy that we are adopting, would work only if the maximum amount we have seen so far (i.e. up until index i-1) lies in between the first index and "r". This happens with probability
Note, this is the probability of success from index "i". To get the total probability we sum up the above with "i" running from "r+1" to "n".
From this point on we solve this by either running a program in any computer programming language (R say) or we can make some approximations. We can let n run to infinity and replace the summation by an integral (transforming x = r/n) to yield
In order to maximize P(Success), we first differentiate it with respect to x and set it to zero (note: second derivate is negative so it must correspond to a maximum)
This yields the optimal value of x to be 1/e, which translates as
The maximum probability of success is also 1/e, which is a surprising lift this strategy provides, given that a random selection would have given a win probability of 1/n.
Some good books that deal with dynamic programming
Dynamic Programming and Optimal Control (2 Vol Set)
Introduction to Stochastic Dynamic Programming
If you are looking to buy some books in probability here are some of the best books to learn the art of Probability
Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics)
This book is a great compilation that covers quite a bit of puzzles. What I like about these puzzles are that they are all tractable and don't require too much advanced mathematics to solve.
Introduction to Algorithms
This is a book on algorithms, some of them are probabilistic. But the book is a must have for students, job candidates even full time engineers & data scientists
Introduction to Probability Theory
An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd Edition
The Probability Tutoring Book: An Intuitive Course for Engineers and Scientists (and Everyone Else!)
Introduction to Probability, 2nd Edition
The Mathematics of Poker
Good read. Overall Poker/Blackjack type card games are a good way to get introduced to probability theory
Let There Be Range!: Crushing SSNL/MSNL No-Limit Hold'em Games
Easily the most expensive book out there. So if the item above piques your interest and you want to go pro, go for it.
Quantum Poker
Well written and easy to read mathematics. For the Poker beginner.
Bundle of Algorithms in Java, Third Edition, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition) (Pts. 1-5)
An excellent resource (students/engineers/entrepreneurs) if you are looking for some code that you can take and implement directly on the job.
Understanding Probability: Chance Rules in Everyday Life A bit pricy when compared to the first one, but I like the look and feel of the text used. It is simple to read and understand which is vital especially if you are trying to get into the subject
Data Mining: Practical Machine Learning Tools and Techniques, Third Edition (The Morgan Kaufmann Series in Data Management Systems) This one is a must have if you want to learn machine learning. The book is beautifully written and ideal for the engineer/student who doesn't want to get too much into the details of a machine learned approach but wants a working knowledge of it. There are some great examples and test data in the text book too.
Discovering Statistics Using R
This is a good book if you are new to statistics & probability while simultaneously getting started with a programming language. The book supports R and is written in a casual humorous way making it an easy read. Great for beginners. Some of the data on the companion website could be missing.
The Probability Tutoring Book: An Intuitive Course for Engineers and Scientists (And Everone Else!)
A: This one is a classic problem and there is adequate coverage around the web on how to solve this particular puzzle (which is also popularly called the secretary problem/interviewer problem etc). It is also a great introduction to one of the most interesting areas in probability (multi arm bandits/optimal stopping etc). The optimal solution has the form of sampling the first "r" princesses, taking note of the highest amount seen up until "r" and then subsequently picking an amount that is greater than this chosen maximum. To understand this, take a look at the following figure, each box being an amount, and let "n" be the number of princesses.
A first step to understand is the probability of the maximum value being on any index "i". This is simple. It is 1/n. Next, the strategy that we are adopting, would work only if the maximum amount we have seen so far (i.e. up until index i-1) lies in between the first index and "r". This happens with probability
This yields the optimal value of x to be 1/e, which translates as
Some good books that deal with dynamic programming
Dynamic Programming and Optimal Control (2 Vol Set)
Introduction to Stochastic Dynamic Programming
If you are looking to buy some books in probability here are some of the best books to learn the art of Probability
Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics)
This book is a great compilation that covers quite a bit of puzzles. What I like about these puzzles are that they are all tractable and don't require too much advanced mathematics to solve.
Introduction to Algorithms
This is a book on algorithms, some of them are probabilistic. But the book is a must have for students, job candidates even full time engineers & data scientists
Introduction to Probability Theory
An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd Edition
The Probability Tutoring Book: An Intuitive Course for Engineers and Scientists (and Everyone Else!)
Introduction to Probability, 2nd Edition
The Mathematics of Poker
Good read. Overall Poker/Blackjack type card games are a good way to get introduced to probability theory
Let There Be Range!: Crushing SSNL/MSNL No-Limit Hold'em Games
Easily the most expensive book out there. So if the item above piques your interest and you want to go pro, go for it.
Quantum Poker
Well written and easy to read mathematics. For the Poker beginner.
Bundle of Algorithms in Java, Third Edition, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition) (Pts. 1-5)
An excellent resource (students/engineers/entrepreneurs) if you are looking for some code that you can take and implement directly on the job.
Understanding Probability: Chance Rules in Everyday Life A bit pricy when compared to the first one, but I like the look and feel of the text used. It is simple to read and understand which is vital especially if you are trying to get into the subject
Data Mining: Practical Machine Learning Tools and Techniques, Third Edition (The Morgan Kaufmann Series in Data Management Systems) This one is a must have if you want to learn machine learning. The book is beautifully written and ideal for the engineer/student who doesn't want to get too much into the details of a machine learned approach but wants a working knowledge of it. There are some great examples and test data in the text book too.
Discovering Statistics Using R
This is a good book if you are new to statistics & probability while simultaneously getting started with a programming language. The book supports R and is written in a casual humorous way making it an easy read. Great for beginners. Some of the data on the companion website could be missing.
Comments
Post a Comment