tag:blogger.com,1999:blog-38243949566727128582024-03-12T19:20:06.599-07:00Probability PuzzlesUnknownnoreply@blogger.comBlogger99125tag:blogger.com,1999:blog-3824394956672712858.post-76962132609736831632017-02-26T13:22:00.002-08:002017-02-26T13:22:38.092-08:00The Best Books for Algebraic Topology<a href="http://amzn.to/2mzRyYa" target="_blank">Algebraic Topology: A First Course</a><br />
<br />
This is a good book if you have some prior knowledge in the subject. So if you have already read a bit about the subject and want to learn more, buy it. The author appears to know how to position material to make it interesting to on board a reader but it can a bit long winded and abstract towards the end.<br />
<br />
<a href="http://amzn.to/2mA3yZr" target="_blank">A Concise Course in Algebraic Topology</a><br />
<br />
Like the above, only a basic introduction to algebraic topology is needed to get started with this book. Check for the version or edition of the book, and buy the latest one. The book has some typos which will be corrected in the latest version. The homework problems in the book can get very demanding.<br />
<br />
<a href="http://amzn.to/2mAbOIO" target="_blank">Algebraic Topology</a><br />
<br />
See this book as a go-between undergraduate and graduate levels for the subject. The book starts off well by giving an overview and introduction to topology but gets complex towards the later chapters.<br />
<br />
<a href="http://amzn.to/2mkhQBv" target="_blank">Algebraic Topology 1st Edition</a><br />
<br />
Think carefully before you buy this book, because it requires strong background knowledge in the subject before you read it. This is not an introductory book. After buying this book, you will invariably come away either liking or disliking it rather strongly.<br />
<br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-73457261855934676382017-01-26T09:29:00.002-08:002017-01-27T07:18:58.831-08:00The "Bhakshali" AlgorithmThis is a write up to describe an algorithm described in an ancient Indian manuscript. Its called the Bhakshali manuscript. The manuscript describes some mathematical assertions, methods and algorithms that has been dated to several thousands years ago.<br />
<br />
A really cool algorithm described in that manuscript is an approximation for finding the square root of a number. What I liked about this algorithm is that its handy. You could quickly approximate the square root of a real number with just some basic division and addition.<br />
<br />
This is how the algorithm works:<br />
<br />
<ol>
<li>If 'X' is the number you want to find a square root of, find the nearest whole number 'N' that approximates it. So if X = 23.2 then N = 5. </li>
<li>Find the difference between X and N*N. Call it D. In this case it works out to -1.8. This should be too tedious to work out either.</li>
<li>Now comes the magical part, divide this difference (D) by 2*N. So that's -1.8/10. Again, this shouldn't be that difficult to do in your head, -0.18.</li>
<li>The approximate value of the square root of X is simply N + D/2N = 5 - 0.18 = 4.82</li>
</ol>
<div>
<br /></div>
<div>
The true value for an approximation of the square root of 23.2 is 4.8166, very close...</div>
<div>
<br /></div>
Some good books to learn probability are listed <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html#.WIg7sHUrKbk" target="_blank">here</a>, and some good books to learn linear algebra are listed <a href="http://bayesianthink.blogspot.com/2013/09/the-best-books-for-linear-algebra.html#.WIg78XUrKbk" target="_blank">here</a><br />
<div>
</div>
<div>
<br />
A detailed write up of the algorithm and other dating techniques used can be found <a href="https://www.math10.com/en/maths-history/math-history-in-india/Bakhshali/bakshali.html" target="_blank">here</a></div>
<div>
<br /></div>
Unknownnoreply@blogger.com3tag:blogger.com,1999:blog-3824394956672712858.post-78947605838395620772017-01-16T08:00:00.000-08:002017-01-16T08:00:14.827-08:00The Bacteria Division Puzzle<style type="text/css">
pre {
background-color: #D1D1D0;
overflow: auto;
font-family: 'Monaco', monospace;
padding: 0 1em;
}
</style><br />
<br />
Q. A jar has a single cell of a bacteria. After every fixed interval of time the bacteria either splits into two with probability 2/5, does nothing with probability 2/5 or dies out with probability 1/5. What is the probability that the bacteria would continue to make a large family tree over an extended period of time?<br />
<br />
A. The situation can be described by the following visual.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjl_QXxsYEjogHI1D1COHOlxu080rJ0FQ4V4dxvYfVqfBNSqnlI-g07yoSerzs7d8dMkBRQiGDjKryGO_TJ0TiuQEhjYYfHWt7o5y0355dECG82YOtUU2LwmIwhocyvb5_OwvqeMpBHxt4/s1600/img2-1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjl_QXxsYEjogHI1D1COHOlxu080rJ0FQ4V4dxvYfVqfBNSqnlI-g07yoSerzs7d8dMkBRQiGDjKryGO_TJ0TiuQEhjYYfHWt7o5y0355dECG82YOtUU2LwmIwhocyvb5_OwvqeMpBHxt4/s1600/img2-1.png" /></a></div>
Assume that the required probability is 'p'. The term 1 - p would represent the probability that the ecosystem eventually dies out. Each of the above scenarios contributes a quantum of probability towards the ecosystem eventually dying out. Lets start off by represent 1 - p as 'x'. The probability that the bacteria die out is<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhuZUjVi_wQKeg9Jd0x3XPFgvGibvn54rLRz0CvlWANB6gZWRwCvObuoIQ2QPZW-jrmzPEKw1NELi8sQiLgYisKpOHwtgcX4RO16p-v8TYK73DARIag-u9Bs67G_bzFg_FPfRaW56JxSac/s1600/form2-1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhuZUjVi_wQKeg9Jd0x3XPFgvGibvn54rLRz0CvlWANB6gZWRwCvObuoIQ2QPZW-jrmzPEKw1NELi8sQiLgYisKpOHwtgcX4RO16p-v8TYK73DARIag-u9Bs67G_bzFg_FPfRaW56JxSac/s1600/form2-1.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjMQ5hByIjAEU2zmheTeVI4WGQLUlgEdCUdBnupKD-aZvFyT7unpRb4EHjiJVm_ye2Ofv7NI9abBamVqT0b-lsgAJdiOz507CFVupjHxGoG0WWx9N7_p_lSCEcHmVKeN-YpdeCEHF_4KEI/s1600/form2-2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjMQ5hByIjAEU2zmheTeVI4WGQLUlgEdCUdBnupKD-aZvFyT7unpRb4EHjiJVm_ye2Ofv7NI9abBamVqT0b-lsgAJdiOz507CFVupjHxGoG0WWx9N7_p_lSCEcHmVKeN-YpdeCEHF_4KEI/s1600/form2-2.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhI3jrVy1iwyAWkwhY3C1__8DJfu1HTAAef-uMs8Y4VPgugYAkSpXDnOKZM6sSHReADZCaqEeftT_iOuZpBCwuw2EbbJ3lvvFh_kZdRQdQrgMeMdD1VBxc4-ZNFJI9biANAHgej_lPB5eU/s1600/form2-3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhI3jrVy1iwyAWkwhY3C1__8DJfu1HTAAef-uMs8Y4VPgugYAkSpXDnOKZM6sSHReADZCaqEeftT_iOuZpBCwuw2EbbJ3lvvFh_kZdRQdQrgMeMdD1VBxc4-ZNFJI9biANAHgej_lPB5eU/s1600/form2-3.png" /></a></div>
<br />
The total of each of the above must add up to the probability that the bacteria eventually die out, which is 'x'. So you can phrase the problem recursively as<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhpX27bfCHA_uPH7TbfIMnkbnzcMqvsQ8W8IqZL3H2eC1VzDhWX34LiXwvfqOdRV2PtNyUmz1ai8d4zK-Rf_jzsSjNXGX_q8C2g7Rzv3oh8e8ED8GbJgGcvY_lKQwzimE1kRtyVL9YUpL0/s1600/form2-4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhpX27bfCHA_uPH7TbfIMnkbnzcMqvsQ8W8IqZL3H2eC1VzDhWX34LiXwvfqOdRV2PtNyUmz1ai8d4zK-Rf_jzsSjNXGX_q8C2g7Rzv3oh8e8ED8GbJgGcvY_lKQwzimE1kRtyVL9YUpL0/s1600/form2-4.png" /></a></div>
<br />
This simplifies to<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgPJ3ljJ-dBN8saJontPXxHHsdld7Cfj-pJoYz4qEcVP3Xsi-da0UBDbhi5SlrmmdYmmxWQR9uqOGuCjFDUFFVQNhV99NZ9lPmxkebRKgexET8p49hwCrSFfRjK5jvKhBlA9wlTTLuifFY/s1600/form2-5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgPJ3ljJ-dBN8saJontPXxHHsdld7Cfj-pJoYz4qEcVP3Xsi-da0UBDbhi5SlrmmdYmmxWQR9uqOGuCjFDUFFVQNhV99NZ9lPmxkebRKgexET8p49hwCrSFfRjK5jvKhBlA9wlTTLuifFY/s1600/form2-5.png" /></a></div>
<br />
which is a quadratic equation, yielding a solution as<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj3xdJ_muU90ztJyZ1U5hF85Xm75szkKbOJNNH5MPvGHnus3YultCPxpr6aQ0qio721xFTGPboEIP2ZELbtU9u0WlkQQuY7T2F8Rc9Dm8o0R_eqK2zAaHrGPl-rUiTrZ2sMKG1IokVG7F0/s1600/form2-6.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj3xdJ_muU90ztJyZ1U5hF85Xm75szkKbOJNNH5MPvGHnus3YultCPxpr6aQ0qio721xFTGPboEIP2ZELbtU9u0WlkQQuY7T2F8Rc9Dm8o0R_eqK2zAaHrGPl-rUiTrZ2sMKG1IokVG7F0/s1600/form2-6.png" /></a></div>
<br />
This further yields x = 1/2 or x = 1. It's easy to see why x = 1 isn't a solution because scenario 1 would rule that out immediately. This yields a probability of 50%.<br />
<br />
In order to test this out, it's also relatively easy to code it up in Python. The following code shows how to simulate this scenario.<br />
<br />
<pre>import sys
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
dist_estimates = []
for index in range(400):
counter = 0
'''
Repeating 100 times for estimating the probability
'''
for epoch in range(100):
num_bacteria = 1
'''
Looking ahead 10 steps
'''
for iter in range(20):
bacteria = np.zeros(int(num_bacteria))
'''
Step through each bacteria
'''
for nb_iter in range(int(num_bacteria)):
'''
Decide if each of the bacteria
will die/stay/split in this time slice
'''
prob = np.random.uniform(0,1)
if prob < 0.2:
''' This one dies '''
bacteria[nb_iter] = 0
elif prob >= 0.2 and prob <= 0.6:
''' This one stays as is '''
bacteria[nb_iter] = 1
else:
''' This one splits into two '''
bacteria[nb_iter] = 2
num_bacteria = np.sum(bacteria)
if np.sum(bacteria) > 0:
counter += 1
dist_estimates.append(float(counter)/100)
'''
Visualization is easy
Use matplotlib and seaborn
'''
p = sns.distplot(dist_estimates,kde=False,rug=True).get_figure()
p.savefig('t.png')
</pre>
<br />
The above code generates a plot of estimates for the said probability. This came out the following way which validates our method.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiuids7QNwdGqeuKfx7aAS3Da96h3Z1ySAjYXMoWDPn02yiglr-tS6EeAHA7SY1Pfqt8XZT0x8p23ue07xJ9U1GSpfgvaHlEgEH-TYrrZkO0rqy7QKSy9P7emuKrtBnbS7SFr6ct8BNi8k/s1600/t.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="275" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiuids7QNwdGqeuKfx7aAS3Da96h3Z1ySAjYXMoWDPn02yiglr-tS6EeAHA7SY1Pfqt8XZT0x8p23ue07xJ9U1GSpfgvaHlEgEH-TYrrZkO0rqy7QKSy9P7emuKrtBnbS7SFr6ct8BNi8k/s400/t.png" width="400" /></a></div>
<br />
If you are looking to learn probability, programming or data science related books, a good set of books are listed <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html" target="_blank">here</a><br />
<br />
<br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-83766782032637190012017-01-05T16:37:00.000-08:002017-01-05T22:21:46.354-08:00The Forgotten Geometric Mean.Often times a lot of people working with data are trying to create an index of some sort. Something that captures a set of key business metrics. If you are a site (or an app) you want to create some sort of an engagement index, which if trending up implies good things are happening, bad if it is trending down. The creators of such metrics (think analysts) tend to prefer a weighted arithmetic mean of the influencing factors. If the influencing factors are f1,f2, f3 (say) with weights w1, w2, w3 then the index would be computed as<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjhJRRxj4dZYPczKQ-0TIXGlA83mCw_8bB_14vuQjC9tQgFPTo3BUN7cE0j9YGQTcCEcIloeYGni8mqMsvoazu3qKcgMffvTG8kCPyD0RGHBWA537CKafxRNS9ixebBKvemWfvo5dhfUZc/s1600/file3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjhJRRxj4dZYPczKQ-0TIXGlA83mCw_8bB_14vuQjC9tQgFPTo3BUN7cE0j9YGQTcCEcIloeYGni8mqMsvoazu3qKcgMffvTG8kCPyD0RGHBWA537CKafxRNS9ixebBKvemWfvo5dhfUZc/s1600/file3.png" /></a></div>
<br />
However, what does not get factored in are the final consumers of the index (think product managers) and there could be many. They will invariably try to check it with something else they have handy. For example, if clicks on a site went up 20% the index may be up by just 5% (say) or vice-versa. If resources are being allocated based on the movement of such an index, it will invariably lead to contention on what is the right weighting to be given to each factor.<br />
<br />
This is meant to be a short write up on some really cool features of the geometric mean. The geometric mean is not meant to replace a simple arithmetic mean based index, but it is definitely worth the thought. To illustrate what this aspect is, lets take a look at a simple two feature index. If the features are X and Y the arithmetic mean index can be represented as<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg346S8r7Cqlaecgi3HJg0s8HCZ5ZwojZGspirqCAp0tXrkUfg3ahyyyHFL8DF9CyRsYoKMnKDQmfOdSgV-Oq8BKoSMR3d7akRRFZ7HNPxgIqyKEoT0LeKb8UAYUY0LbzEXRLCJ5b8ZtwE/s1600/file4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg346S8r7Cqlaecgi3HJg0s8HCZ5ZwojZGspirqCAp0tXrkUfg3ahyyyHFL8DF9CyRsYoKMnKDQmfOdSgV-Oq8BKoSMR3d7akRRFZ7HNPxgIqyKEoT0LeKb8UAYUY0LbzEXRLCJ5b8ZtwE/s1600/file4.png" /></a></div>
<br />
To see how it responds to changes, lets take the derivative.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2MXnQjRWwz9-wjCsdqQoFU-wk_-31CUpL3Qwg_ViptP3xaE_R2nGrANAR8g3k-ektM5kzXbqn5WZ1HXir5kkJ9L81eJHmSTqmetm-n41rgn4qdzzs1cKbLgudiYA16lkWdihgqppShes/s1600/file5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2MXnQjRWwz9-wjCsdqQoFU-wk_-31CUpL3Qwg_ViptP3xaE_R2nGrANAR8g3k-ektM5kzXbqn5WZ1HXir5kkJ9L81eJHmSTqmetm-n41rgn4qdzzs1cKbLgudiYA16lkWdihgqppShes/s1600/file5.png" /></a></div>
<br />
Clearly the derivative is dependent on the chosen weight. Lets see what happens when we choose the geometric mean.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkARO1jA_-bbJ7iZX_lDJgV4jw3ou4R6qkjJC9_b2EV8FEeAUZZahytwR7g0PF845eQVEgl_FbfaS4mVUDfNLhAAS0qENWUNGdyuA1J6upQwVVEM2e4MsUDg-1jXJU3EAGzSz6iOIMbnA/s1600/file6.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkARO1jA_-bbJ7iZX_lDJgV4jw3ou4R6qkjJC9_b2EV8FEeAUZZahytwR7g0PF845eQVEgl_FbfaS4mVUDfNLhAAS0qENWUNGdyuA1J6upQwVVEM2e4MsUDg-1jXJU3EAGzSz6iOIMbnA/s1600/file6.png" /></a></div>
<br />
Again, to see how it responds to change, lets take the derivative.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjchG0wpTVwcMSIi7x7fNkCqcOwNME9xbzRZXXRDix_BRQDTmeHaNVG09mac4qGw_mpft1C0zOoAIqsUzKGsWig1CsJCHnX1UqfwOVRfpyvbE29lY02YLD3Ogy369_KS8h3o5ZjtMIoKHA/s1600/file7.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjchG0wpTVwcMSIi7x7fNkCqcOwNME9xbzRZXXRDix_BRQDTmeHaNVG09mac4qGw_mpft1C0zOoAIqsUzKGsWig1CsJCHnX1UqfwOVRfpyvbE29lY02YLD3Ogy369_KS8h3o5ZjtMIoKHA/s1600/file7.png" /></a></div>
<br />
which can be further simplified to<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhaFJ_RLG0v0bSfFA46G3bHjnzEJHhaD5Xi6EaYmhkmTHOI5w5_aa708QnonGqC5EaJbkaFFGe41z2PhBTloOvUGougRdxPmCoq_LFXnJxLsSMXIRGjJ2ZLEbol1-_JZEL-YfcKkA8Gug0/s1600/file8.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhaFJ_RLG0v0bSfFA46G3bHjnzEJHhaD5Xi6EaYmhkmTHOI5w5_aa708QnonGqC5EaJbkaFFGe41z2PhBTloOvUGougRdxPmCoq_LFXnJxLsSMXIRGjJ2ZLEbol1-_JZEL-YfcKkA8Gug0/s1600/file8.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
The result is a useful derivable condition</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhs_0Qzl57n3AX_n4q-DESxaEXiarVvVuWxnxWgtrq8d9INBxp8160A14d-ZPbR4s21YnVR-Zl6SFzNlHnu-zU__1ncRp2FiOD-TTNLYMcYxQVA3djTG4ILRRovSzwdzNRMEzIZvS3p2zw/s1600/file9.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhs_0Qzl57n3AX_n4q-DESxaEXiarVvVuWxnxWgtrq8d9INBxp8160A14d-ZPbR4s21YnVR-Zl6SFzNlHnu-zU__1ncRp2FiOD-TTNLYMcYxQVA3djTG4ILRRovSzwdzNRMEzIZvS3p2zw/s1600/file9.png" /></a></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
i.e. the percentage change in the index is directly proportional to the percentage change in the feature.<br />
Note, there are no hand chosen weights here. A five percent change in one of the influencing factors will result in a proportional percent change in the index. Extremely useful !<br />
<br />
Yet another aspect consumers like to quantify is growth. If the index went up by x1 and x2 in consecutive years, what is the average quarterly/annual growth? If we took it as the average of x1 and x2, then the growth after two years (say) would be estimated as<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhigxyVaQ7ew6lAjnaH08cDmH_SBZ9pIT1zZ-as64DMaMUA7CWmlw-Mw2RihrhX8RFquT9N636YYiMhzgCOoQUlLrdOZNkRywFIWEyrKlRaAfWixk9rZoQB_lgnBUJIlei-0qApd-qsEb4/s1600/file10.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="23" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhigxyVaQ7ew6lAjnaH08cDmH_SBZ9pIT1zZ-as64DMaMUA7CWmlw-Mw2RihrhX8RFquT9N636YYiMhzgCOoQUlLrdOZNkRywFIWEyrKlRaAfWixk9rZoQB_lgnBUJIlei-0qApd-qsEb4/s320/file10.png" width="320" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
Contrast that to the actual growth<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjC6q5H3p5OGh3PrvL7MrmzfHRgGZZ9vt85cdb4Ox7Iga_foKQVxCKMYvDpx0qges79TqZfA4MHEzt7xfH1Fd11Og8_tYoayvxr-1kMe-q7V8DmX66qhyphenhyphenXrMulTWGIVqvW3Bth4eG8FTJs/s1600/file11.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="20" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjC6q5H3p5OGh3PrvL7MrmzfHRgGZZ9vt85cdb4Ox7Iga_foKQVxCKMYvDpx0qges79TqZfA4MHEzt7xfH1Fd11Og8_tYoayvxr-1kMe-q7V8DmX66qhyphenhyphenXrMulTWGIVqvW3Bth4eG8FTJs/s320/file11.png" width="320" /></a></div>
<br />
Clearly some terms cancel out. We are left comparing<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj6i24CTYzOuVHU8b8HyWt4C94QB8kbrAZiXPid76Tl_yUnIySuY4OE06xoiHrsJzZcitoqICQilKb8DGbKBQ_YbT0ianUNI_xrfvWywuIs1NSPyN7_Wf-u28beDcsMz6EzbW_30IapYTY/s1600/file12.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj6i24CTYzOuVHU8b8HyWt4C94QB8kbrAZiXPid76Tl_yUnIySuY4OE06xoiHrsJzZcitoqICQilKb8DGbKBQ_YbT0ianUNI_xrfvWywuIs1NSPyN7_Wf-u28beDcsMz6EzbW_30IapYTY/s1600/file12.png" /></a></div>
<br />
Notice one of them is the arithmetic mean and the other is the geometric mean. We also know from a well established theorem that the arithmetic mean is always greater than the geometric mean described <a href="https://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means" rel="nofollow" target="_blank">here</a>. So we would always end up overestimating the growth!<br />
<br />
So how would we choose a value to project as an average growth rate? We are looking for a beta in the below equation<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiCSTRn6d2lMzplJZGJH1ZUPDpF335mN1KSmPb2tXJHNB5OB9u4jJL-3UA-BP46PIxN7tRHDleh0EFgwE7rsqnYWDmsIiQLLKTdsjH7VWP52KqYLbouJWduFFasnjIiWluisLRRINusKrQ/s1600/file13.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiCSTRn6d2lMzplJZGJH1ZUPDpF335mN1KSmPb2tXJHNB5OB9u4jJL-3UA-BP46PIxN7tRHDleh0EFgwE7rsqnYWDmsIiQLLKTdsjH7VWP52KqYLbouJWduFFasnjIiWluisLRRINusKrQ/s1600/file13.png" /></a></div>
<br />
Yet again stating the average growth as the geometric mean gives the end user a handy metric to work with.<br />
<br />
If you are interested in learning probability <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html" target="_blank">here</a> are a set of good books to choose and buy from.<br />
<br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-86028737064835641052017-01-02T08:08:00.000-08:002017-01-02T08:08:50.452-08:00Colored Cards and Numbers PuzzleQ: You have a set of thirty six cards. The cards are six in color ( six each) and each color is numbered from 1 to 6. You draw two cards at random. What is probability that they are of a different color and have a different number?<br />
<br />
A: The first card can be drawn at random. It does not matter what its color or number is. To compute the probability that the second card is different in color and number from the first, it helps to visualize the situation in a simple way as shown below.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEilzpX1IF1YVHRNO-ZP0xH69r7iP8JljT63iN0xTIK11zTl98ss_UHy1uI3a0jHEHMXpRI8j1NZN3LyE3eg1gDentOSUSfevW6d7aijtuQN7CmgdrYvUqlJx-2GIVin6D2NtfB2rIWGn2k/s1600/diagram33.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="346" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEilzpX1IF1YVHRNO-ZP0xH69r7iP8JljT63iN0xTIK11zTl98ss_UHy1uI3a0jHEHMXpRI8j1NZN3LyE3eg1gDentOSUSfevW6d7aijtuQN7CmgdrYvUqlJx-2GIVin6D2NtfB2rIWGn2k/s400/diagram33.png" width="400" /></a></div>
<br />
In the figure above, assume the green dot represents the card that was picked. The marked out cards represent the cards that should not be picked to get a different color and number. Also, the act of picking a card bought down the pool of cards from 36 to 35. The remaining unmarked space represents the available set of cards to pick from. This can be computed easily as<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi90HwG4TurlsWQpVktCAdFtYNFT-jHz7Qb97Jk55s7MBEIFYvmOxEh5peFHV3y1MtpPrAOx72hMwZR993OJhyvATabnG2Kuuggg2WA4eb3HZmCuBOx1M_l2ydhgdMMFOcsZzChzh0uL3w/s1600/file2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi90HwG4TurlsWQpVktCAdFtYNFT-jHz7Qb97Jk55s7MBEIFYvmOxEh5peFHV3y1MtpPrAOx72hMwZR993OJhyvATabnG2Kuuggg2WA4eb3HZmCuBOx1M_l2ydhgdMMFOcsZzChzh0uL3w/s1600/file2.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
This yields an overall probability of<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh3A1G38vF5X1QI8PhKM2bTzzR7-LtrjEf462JWIF97rt_hsf2QRpJZ8TArgUz3dVH5nU6-ADqvRtKqXi1h929hS4cQTXDaY29LI5GcMmpVTbf8LL78EuubdEcK0WqkLf5iDqiZJI96Rd8/s1600/file1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh3A1G38vF5X1QI8PhKM2bTzzR7-LtrjEf462JWIF97rt_hsf2QRpJZ8TArgUz3dVH5nU6-ADqvRtKqXi1h929hS4cQTXDaY29LI5GcMmpVTbf8LL78EuubdEcK0WqkLf5iDqiZJI96Rd8/s1600/file1.png" /></a></div>
<br />
If you are interested in learning the art of probability, some of the best books to learn it from are listed <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html" rel="" target="_blank">here</a>.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-84258294398457673902016-10-26T21:12:00.005-07:002016-11-06T18:35:58.463-08:00The Magic of Numba and PythonPython is a great programming language. It's primary merits are readability and the numerous packages that are available online. However, being an interpreted language the speed of execution is always an issue. Here is a simple example of a piece of code written in Python that tries to add two numbers from a grid.<br />
<br />
<pre class="Python" name="code">#!/usr/bin/python
def overlap_pp(x,y):
count = 0
for i in range(x):
for j in range(y):
count += i + j
return count
for _ in range(1000):
q = overlap_pp(500,500)
</pre>If you run the above script (saved as n.py) on the command line terminal with the time command you should see some numbers like the below<br />
<br />
<pre class="Shell" name="code">time ./n.py
real 0m22.379s
user 0m22.363s
sys 0m0.407s
</pre>The process running on one processor took about 22 seconds to complete the run. Now lets do something seemingly magical. Lets add a decorator. Decorators are python speak for a mechanism to do wrapper functions. The decorator we are going to add is '@jit'. The code looks like as it is shown below<br />
<br />
<pre class="Python" name="code">#!/usr/bin/python
from numba import jit
@jit
def overlap_pp(x,y):
count = 0
for i in range(x):
for j in range(y):
count += i + j
return count
for _ in range(1000):
q = overlap_pp(500,500)
</pre>Now let's time this as before.<br />
<br />
<pre class="Shell" name="code">time ./n.py
real 0m0.420s
user 0m0.370s
sys 0m0.443s
</pre><br />
<table border="0" cellpadding="5" cellspacing="5"><tr> <td height="240 px"><iframe style="width:120px;height:240px;" marginwidth="0" marginheight="0" scrolling="no" frameborder="0" src="//ws-na.amazon-adsystem.com/widgets/q?ServiceVersion=20070822&OneJS=1&Operation=GetAdHtml&MarketPlace=US&source=ss&ref=as_ss_li_til&ad_type=product_link&tracking_id=bayesianinference-20&marketplace=amazon®ion=US&placement=B0197TWXUE&asins=B0197TWXUE&linkId=f683e5462951133c30e64181fe1a3867&show_border=true&link_opens_in_new_window=true"></iframe></td>
<td height="240px"> <iframe style="width:120px;height:240px;" marginwidth="0" marginheight="0" scrolling="no" frameborder="0" src="//ws-na.amazon-adsystem.com/widgets/q?ServiceVersion=20070822&OneJS=1&Operation=GetAdHtml&MarketPlace=US&source=ss&ref=as_ss_li_til&ad_type=product_link&tracking_id=bayesianinference-20&marketplace=amazon®ion=US&placement=B015GATPMC&asins=B015GATPMC&linkId=7b4c6dbad30bf0af79968b5e90aa0786&show_border=true&link_opens_in_new_window=true"></iframe></td>
<td height="240px"><iframe style="width:120px;height:240px;" marginwidth="0" marginheight="0" scrolling="no" frameborder="0" src="//ws-na.amazon-adsystem.com/widgets/q?ServiceVersion=20070822&OneJS=1&Operation=GetAdHtml&MarketPlace=US&source=ss&ref=as_ss_li_til&ad_type=product_link&tracking_id=bayesianinference-20&marketplace=amazon®ion=US&placement=B000G2BAB0&asins=B000G2BAB0&linkId=c588ba318f7b4471a222accec97d44f3&show_border=true&link_opens_in_new_window=true"></iframe> </td>
<td height="240px"><iframe style="width:120px;height:240px;" marginwidth="0" marginheight="0" scrolling="no" frameborder="0" src="//ws-na.amazon-adsystem.com/widgets/q?ServiceVersion=20070822&OneJS=1&Operation=GetAdHtml&MarketPlace=US&source=ss&ref=as_ss_li_til&ad_type=product_link&tracking_id=bayesianinference-20&marketplace=amazon®ion=US&placement=B00EDX8ASO&asins=B00EDX8ASO&linkId=9e564ce8c75de20822cf5541543fffd1&show_border=true&link_opens_in_new_window=true"></iframe> </td>
</tr>
</table><br />
Magic! The exact same code now runs <b>55x faster</b>! This happens because the Just-In-Time (jit) feature of the numba package compiles the function to machine code on the fly. The timing you see is almost in line with what you would expect from a similar code done in C or Fortran. In fact you will be surprised that in this particular example, the numba version runs faster than the C version! The C code is shown below.<br />
<pre class="C" name="code">#include < stdio.h >
int overlap_pp(int x,int y){
int i,j,q;
for(i=0;i<= x;i++){
for(j=0;j<= y;j++){
q += i + j;
}
}
return(q);
}
int main(int argc,char** argv){
int i,q;
for(i = 0;i<=1000;i++){
q = overlap_pp(500,500);
}
return 0;
}
</pre>The timing results after compiling the above code 'gcc t.c -o t'<br />
<br />
<pre class="Shell" name="code">time ./t
real 0m0.774s
user 0m0.774s
sys 0m0.000s
</pre>Unfortunately there isn't a clear description online on how to get Numba installed on Ubuntu 14.04. After some hacking and poking around stackoverflow the following worked for me.<br />
<br />
<b>Step 1:</b><br />
Numba uses llvm. You need to remove all llvm, llvm-config and llvmlite installations that you already have on your system. Numba needs llvm-3.8 upwards to work properly.<br />
<br />
<b>Step 2:</b><br />
Follow instructions in this stackoverflow <a href="http://stackoverflow.com/questions/28782512/getting-python-numba-working-on-ubuntu-14-10-or-fedora-21-with-python-2-7" rel="nofollow" target="_blank">thread</a>. But when you get installing do the following<br />
<span class="pln" style="background-color: #eff0f1; border: 0px; color: #303336; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;">sudo apt</span><span class="pun" style="background-color: #eff0f1; border: 0px; color: #303336; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;">-</span><span class="pln" style="background-color: #eff0f1; border: 0px; color: #303336; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;">get install zlib1g zlib1g</span><span class="pun" style="background-color: #eff0f1; border: 0px; color: #303336; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;">-</span><span class="pln" style="background-color: #eff0f1; border: 0px; color: #303336; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;">dev libedit2 libedit</span><span class="pun" style="background-color: #eff0f1; border: 0px; color: #303336; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;">-</span><span class="pln" style="background-color: #eff0f1; border: 0px; color: #303336; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;">dev llvm</span><span class="pun" style="background-color: #eff0f1; border: 0px; color: #303336; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;">-</span><span class="lit" style="background-color: #eff0f1; border: 0px; color: #7d2727; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;">3.8</span><span class="pln" style="background-color: #eff0f1; border: 0px; color: #303336; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;"> llvm</span><span class="pun" style="background-color: #eff0f1; border: 0px; color: #303336; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;">-</span><span class="lit" style="background-color: #eff0f1; border: 0px; color: #7d2727; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;">3.8</span><span class="pun" style="background-color: #eff0f1; border: 0px; color: #303336; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;">-</span><span class="pln" style="background-color: #eff0f1; border: 0px; color: #303336; font-family: "consolas" , "menlo" , "monaco" , "lucida console" , "liberation mono" , "dejavu sans mono" , "bitstream vera sans mono" , "courier new" , monospace , sans-serif; font-size: 13px; margin: 0px; padding: 0px; white-space: inherit;">dev</span><br />
Notice change in version number to 3.8.<br />
<br />
<b>Step 3:</b><br />
Next, install llvmlite. You also want to create a symbolic link on '/usr/bin/' to point to the latest 3.8 version of llvm-config.<br />
"sudo ln -s /usr/bin/llvm-config-3.8 /usr/bin/llvm-config"<br />
This step is important because the installation of numba appears to use llvm-config. After this you can install Numba directly using pip.<br />
<br />
If you are interested in learning more about python programming, data science and probability <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html" rel="nofollow" target="_blank">here</a> are a list of books that are worthwhile to buy.<br />
<br />
<br />
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-9852929659234710982016-05-15T13:27:00.000-07:002016-05-15T20:10:12.503-07:00The James-Stein Estimator<div class="separator" style="clear: both; text-align: center;">
</div>
<span style="font-family: inherit;">This write up is about an estimator. A statistical estimator, is used when you already have a model in mind, data at hand and want to estimate some parameters needed for the model. For example, you want to predict how many runs a batter would make in a game given recent history \(x_1,x_2,x_3,\ldots\) . If we assume (we are making a choice of a model now) that the scores come from a normal distribution with mean \(\mu\) and standard deviation \(\sigma\) then the probability density function for a given value \(x\) is</span><br />
<span style="font-family: inherit;"><br />
</span> <br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnI5gMMRKhk7Z7INsMmeZ7FifQXQzvDNiUWgxDss1dYFLueN8L4sEvG5R8757OrqTROEwz6NJbhfbJRxJls48WSaeAQjLZJTQlON2j4iidWyawgWHCdVsIwXxg6oFi6AzZJm5Y4xfja4A/s1600/eqa1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="55" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnI5gMMRKhk7Z7INsMmeZ7FifQXQzvDNiUWgxDss1dYFLueN8L4sEvG5R8757OrqTROEwz6NJbhfbJRxJls48WSaeAQjLZJTQlON2j4iidWyawgWHCdVsIwXxg6oFi6AzZJm5Y4xfja4A/s320/eqa1.png" width="320" /></a></div>
<span style="font-family: inherit;"><br />
</span> <span style="font-family: inherit;">The likelihood that a series of points \(x_1,x_2,x_3,\ldots\) come from such a distribution can be expressed as</span><br />
<span style="font-family: inherit;"><br />
</span> <br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEilkJcm_FoFnXdp_DISafNq1gFueek3zXfuF78uSDx2aT0omWs6OYmbek1Z589OjMEORWC8f8ZuMo0JoqfQJm2EmrOra-FLfNt-fBGi4cDe6i9MkZLfSHygx_ha9BLXIvsX4k_0hRiz0-g/s1600/eqa2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="26" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEilkJcm_FoFnXdp_DISafNq1gFueek3zXfuF78uSDx2aT0omWs6OYmbek1Z589OjMEORWC8f8ZuMo0JoqfQJm2EmrOra-FLfNt-fBGi4cDe6i9MkZLfSHygx_ha9BLXIvsX4k_0hRiz0-g/s400/eqa2.png" width="400" /></a></div>
<span style="font-family: inherit;"><br />
</span> <br />
<br />
<span style="font-family: inherit;">
</span> <span style="font-family: inherit;">Next is basic calculus. Take the logarithm on both sides, set the partial derivative w.r.t. \(\mu\) to zero yields (excluding the algebra)</span><br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj-oMWV_gCTOcW94yaPtamzo4wf7uiCCdpIojGK8elHlpxjpDZfHIdNl3WQO0JoJCKUU7PLbqdHD4-BNnZfXQboEmcxN6WUZUXc8U8fNUkjNphKGIhyphenhyphenI2ly-Frmh9Jde4KtE7BJlMc9nKw/s1600/eqa3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="80" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj-oMWV_gCTOcW94yaPtamzo4wf7uiCCdpIojGK8elHlpxjpDZfHIdNl3WQO0JoJCKUU7PLbqdHD4-BNnZfXQboEmcxN6WUZUXc8U8fNUkjNphKGIhyphenhyphenI2ly-Frmh9Jde4KtE7BJlMc9nKw/s200/eqa3.png" width="200" /></a></div>
<br />
<br />
<span style="font-family: inherit;">
</span> <span style="font-family: inherit;">To verify, you also need to check the second derivative's sign to see if its negative to ensure that it is indeed a maxima you have found.</span><br />
<span style="font-family: inherit;"><br />
</span> <span style="font-family: inherit;">So a simple estimator would be to use the average runs scored from the past \(n\) days. The average is the result of a "maximum likelihood" approach briefly described above.What if you had 5 players you wanted to estimate the average for? Intuition would tell you that you should simply compute the average for each. Wrong! The James-Stein approach provides a way to pool the data such that the overall error made in estimation is minimized.</span><br />
<span style="font-family: inherit;"><br />
</span> <span style="font-family: inherit;">Specifically, I'll demonstrate the James-Stein estimator. It is a surprising result discovered by Charles Stein and later formalized by Willard James on estimating such parameters. What makes it stunning is the rather counter intuitive result it demonstrates. James-Stein's estimator approach states that if you wanted to <u>simultaneously </u>estimate a set of independent parameters from data, the maximum likelihood approach is only optimal if you have lesser than 3 parameters to estimate from! If you have more than 3, you are better off using the James-Stein estimator. There is an obvious thought experiment you can think of. If you really wanted just one parameter, could you not simply add an unrelated set of numbers, improve efficiency in estimation and then just use the parameter you are interested in? That's a flaw. The estimator works by minimizing the overall error in estimation so it may make more errors in some of the variables, lesser on others. But overall it will be better than just doing an individual maximum likelihood estimate on each variable. So you could use it if you don't mind seeing slightly bigger errors on some variables, smaller on others but lower overall error.</span><br />
<br />
To see this work, I'll step through the actual algorithm in R. For more details you can refer the wikipedia entry <a href="https://en.wikipedia.org/wiki/James%E2%80%93Stein_estimator" target="_blank">here</a>.The general approach is the following.<br />
<br />
Let<br />
<ul>
<li>\(\hat\theta_{js}\) is the James-Stein estimate of the parameters we are interested in computing.</li>
<li>\(y\) be the set of values observed.</li>
<li>\(\hat{\sigma}^{2}\) be the estimated variance for all parameters</li>
<li>\(v\) be the mean of all parameters</li>
</ul>
then the James Stein estimator is given by<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipOdMyxjRsGZBNkLimbR-LTASLuD9D6HlksJht23RxOiX4jZwbci-rwjgQRAh5j6z-MXWaQB8fPT175PSdm9A_cOHV5Oj5_3QqNNqyMqsstRNWJ-l9mN4JqPp6yZmGDICQnvZndcESayQ/s1600/eqa4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="54" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipOdMyxjRsGZBNkLimbR-LTASLuD9D6HlksJht23RxOiX4jZwbci-rwjgQRAh5j6z-MXWaQB8fPT175PSdm9A_cOHV5Oj5_3QqNNqyMqsstRNWJ-l9mN4JqPp6yZmGDICQnvZndcESayQ/s320/eqa4.png" width="320" /></a></div>
<br />
<br />
<br />
<div style="overflow: auto;">
<div class="geshifilter">
<pre class="r geshifilter-R" style="font-family: monospace;"><span style="color: #666666; font-style: italic;">#!/usr/bin/Rscript</span>
<a href="http://inside-r.org/r-doc/base/suppressMessages"><span style="color: #003399; font-weight: bold;">suppressMessages</span></a><span style="color: #009900;">(</span><a href="http://inside-r.org/r-doc/base/library"><span style="color: #003399; font-weight: bold;">library</span></a><span style="color: #009900;">(</span><a href="http://inside-r.org/packages/cran/data.table">data.table</a><span style="color: #009900;">)</span><span style="color: #009900;">)</span>
<a href="http://inside-r.org/r-doc/base/suppressMessages"><span style="color: #003399; font-weight: bold;">suppressMessages</span></a><span style="color: #009900;">(</span><a href="http://inside-r.org/r-doc/base/library"><span style="color: #003399; font-weight: bold;">library</span></a><span style="color: #009900;">(</span><a href="http://inside-r.org/packages/cran/ggplot2">ggplot2</a><span style="color: #009900;">)</span><span style="color: #009900;">)</span>
<span style="color: #666666; font-style: italic;"># n.rows is the number of samples we have</span>
n.rows = <span style="color: #cc66cc;">100</span>
<span style="color: #666666; font-style: italic;"># n.params is the number of parameters</span>
<span style="color: #666666; font-style: italic;"># we want to estimate</span>
n.params = <span style="color: #cc66cc;">30</span>
<span style="color: #666666; font-style: italic;"># wins will hold the number of times</span>
<span style="color: #666666; font-style: italic;"># the JS estimator beats the MLE estimate</span>
wins = <a href="http://inside-r.org/r-doc/base/c"><span style="color: #003399; font-weight: bold;">c</span></a><span style="color: #009900;">(</span><span style="color: #009900;">)</span>
msejs = <a href="http://inside-r.org/r-doc/base/c"><span style="color: #003399; font-weight: bold;">c</span></a><span style="color: #009900;">(</span><span style="color: #009900;">)</span>
msemle = <a href="http://inside-r.org/r-doc/base/c"><span style="color: #003399; font-weight: bold;">c</span></a><span style="color: #009900;">(</span><span style="color: #009900;">)</span>
<span style="color: black; font-weight: bold;">for</span><span style="color: #009900;">(</span>iter <span style="color: black; font-weight: bold;">in</span> <a href="http://inside-r.org/r-doc/base/seq"><span style="color: #003399; font-weight: bold;">seq</span></a><span style="color: #009900;">(</span><span style="color: #cc66cc;">1</span>:<span style="color: #cc66cc;">1000</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span><span style="color: #009900;">{</span>
<span style="color: #666666; font-style: italic;"># Create a sample of parameters</span>
<span style="color: #666666; font-style: italic;"># They have a range of 20-25</span>
x.act = <a href="http://inside-r.org/r-doc/base/sample"><span style="color: #003399; font-weight: bold;">sample</span></a><span style="color: #009900;">(</span><span style="color: #cc66cc;">20</span>:<span style="color: #cc66cc;">25</span><span style="color: #339933;">,</span>size=n.params<span style="color: #339933;">,</span><a href="http://inside-r.org/r-doc/base/replace"><span style="color: #003399; font-weight: bold;">replace</span></a>=<span style="color: black; font-weight: bold;">TRUE</span><span style="color: #009900;">)</span>
<span style="color: #666666; font-style: italic;"># Now create a normal distribution for each of the parameters</span>
<span style="color: #666666; font-style: italic;"># uncomment below if you want to test it for a poisson distribution</span>
<span style="color: #666666; font-style: italic;"># m = mapply(rpois,mean=x.act,MoreArgs=list(n = n.rows))</span>
m = <a href="http://inside-r.org/r-doc/base/mapply"><span style="color: #003399; font-weight: bold;">mapply</span></a><span style="color: #009900;">(</span><a href="http://inside-r.org/r-doc/stats/rnorm"><span style="color: #003399; font-weight: bold;">rnorm</span></a><span style="color: #339933;">,</span><a href="http://inside-r.org/r-doc/base/mean"><span style="color: #003399; font-weight: bold;">mean</span></a>=x.act<span style="color: #339933;">,</span>MoreArgs=<a href="http://inside-r.org/r-doc/base/list"><span style="color: #003399; font-weight: bold;">list</span></a><span style="color: #009900;">(</span>n = n.rows<span style="color: #339933;">,</span><a href="http://inside-r.org/r-doc/stats/sd"><span style="color: #003399; font-weight: bold;">sd</span></a>=<span style="color: #cc66cc;">10</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span>
<span style="color: #666666; font-style: italic;"># Find the global mean</span>
mbar = <a href="http://inside-r.org/r-doc/base/mean"><span style="color: #003399; font-weight: bold;">mean</span></a><span style="color: #009900;">(</span><a href="http://inside-r.org/r-doc/base/colMeans"><span style="color: #003399; font-weight: bold;">colMeans</span></a><span style="color: #009900;">(</span>m<span style="color: #009900;">)</span><span style="color: #009900;">)</span>
<span style="color: #666666; font-style: italic;"># Find the column means</span>
mu0 = <a href="http://inside-r.org/r-doc/base/colMeans"><span style="color: #003399; font-weight: bold;">colMeans</span></a><span style="color: #009900;">(</span>m<span style="color: #009900;">)</span>
<span style="color: #666666; font-style: italic;"># Find global variance</span>
s2 = <a href="http://inside-r.org/r-doc/stats/var"><span style="color: #003399; font-weight: bold;">var</span></a><span style="color: #009900;">(</span><a href="http://inside-r.org/r-doc/base/as.vector"><span style="color: #003399; font-weight: bold;">as.vector</span></a><span style="color: #009900;">(</span>m<span style="color: #009900;">)</span><span style="color: #009900;">)</span>/<span style="color: #009900;">(</span>n.rows*n.params<span style="color: #009900;">)</span>
<span style="color: #666666; font-style: italic;"># Compute the adjustment value</span>
cval = <span style="color: #cc66cc;">1</span> - <span style="color: #009900;">(</span><span style="color: #009900;">(</span>n.params - <span style="color: #cc66cc;">2</span><span style="color: #009900;">)</span>*s2/sum<span style="color: #009900;">(</span><span style="color: #009900;">(</span>mu0 - mbar<span style="color: #009900;">)</span>^<span style="color: #cc66cc;">2</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span>
<span style="color: #666666; font-style: italic;"># Compute the JS estimate for your parameters</span>
jsest = mbar + cval *<span style="color: #009900;">(</span>mu0 - mbar<span style="color: #009900;">)</span>
z = <a href="http://inside-r.org/packages/cran/data.table">data.table</a><span style="color: #009900;">(</span>
actual = x.act<span style="color: #339933;">,</span>
mle.est = mu0<span style="color: #339933;">,</span>
js.est = jsest<span style="color: #009900;">)</span>
<span style="color: #666666; font-style: italic;"># Check to see if the JS estimate is better than MLE</span>
z<span style="color: #009900;">[</span><span style="color: #339933;">,</span>counter := <a href="http://inside-r.org/r-doc/base/ifelse"><span style="color: #003399; font-weight: bold;">ifelse</span></a><span style="color: #009900;">(</span><a href="http://inside-r.org/r-doc/base/abs"><span style="color: #003399; font-weight: bold;">abs</span></a><span style="color: #009900;">(</span>js.est - actual<span style="color: #009900;">)</span> < <a href="http://inside-r.org/r-doc/base/abs"><span style="color: #003399; font-weight: bold;">abs</span></a><span style="color: #009900;">(</span>mle.est - actual<span style="color: #009900;">)</span><span style="color: #339933;">,</span><span style="color: #cc66cc;">1</span><span style="color: #339933;">,</span><span style="color: #cc66cc;">0</span><span style="color: #009900;">)</span><span style="color: #009900;">]</span>
<span style="color: #666666; font-style: italic;"># In case you want to see what the numbers are for the</span>
<span style="color: #666666; font-style: italic;"># difference between absolute and actual estimates for</span>
<span style="color: #666666; font-style: italic;"># JS and MLE</span>
z<span style="color: #009900;">[</span><span style="color: #339933;">,</span>jserr := <a href="http://inside-r.org/r-doc/base/abs"><span style="color: #003399; font-weight: bold;">abs</span></a><span style="color: #009900;">(</span>js.est - actual<span style="color: #009900;">)</span><span style="color: #009900;">]</span>
z<span style="color: #009900;">[</span><span style="color: #339933;">,</span>mleerr := <a href="http://inside-r.org/r-doc/base/abs"><span style="color: #003399; font-weight: bold;">abs</span></a><span style="color: #009900;">(</span>mle.est - actual<span style="color: #009900;">)</span><span style="color: #009900;">]</span>
<span style="color: #666666; font-style: italic;"># Record the wins for this iteration of the simulation</span>
<span style="color: #666666; font-style: italic;"># Repeat.</span>
wins<span style="color: #009900;">[</span>iter<span style="color: #009900;">]</span> = <a href="http://inside-r.org/r-doc/base/sum"><span style="color: #003399; font-weight: bold;">sum</span></a><span style="color: #009900;">(</span>z$counter<span style="color: #009900;">)</span>
msejs<span style="color: #009900;">[</span>iter<span style="color: #009900;">]</span> = <a href="http://inside-r.org/r-doc/base/sum"><span style="color: #003399; font-weight: bold;">sum</span></a><span style="color: #009900;">(</span>z$jserr<span style="color: #009900;">)</span>
msemle<span style="color: #009900;">[</span>iter<span style="color: #009900;">]</span> = <a href="http://inside-r.org/r-doc/base/sum"><span style="color: #003399; font-weight: bold;">sum</span></a><span style="color: #009900;">(</span>z$mleerr<span style="color: #009900;">)</span>
<span style="color: #009900;">}</span>
<span style="color: #666666; font-style: italic;"># What are the mean wins? </span>
<a href="http://inside-r.org/r-doc/base/mean"><span style="color: #003399; font-weight: bold;">mean</span></a><span style="color: #009900;">(</span>wins<span style="color: #009900;">)</span>
<span style="color: #666666; font-style: italic;"># What are the distribution of the mean wins</span>
<a href="http://inside-r.org/r-doc/stats/quantile"><span style="color: #003399; font-weight: bold;">quantile</span></a><span style="color: #009900;">(</span>wins<span style="color: #339933;">,</span><a href="http://inside-r.org/packages/cran/prob">prob</a> = <a href="http://inside-r.org/r-doc/base/seq"><span style="color: #003399; font-weight: bold;">seq</span></a><span style="color: #009900;">(</span><span style="color: #cc66cc;">0.1</span><span style="color: #339933;">,</span><span style="color: #cc66cc;">0.9</span><span style="color: #339933;">,</span><a href="http://inside-r.org/r-doc/base/by"><span style="color: #003399; font-weight: bold;">by</span></a>=<span style="color: #cc66cc;">0.1</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span>
z = <a href="http://inside-r.org/r-doc/base/data.frame"><span style="color: #003399; font-weight: bold;">data.frame</span></a><span style="color: #009900;">(</span>wins = wins<span style="color: #009900;">)</span>
p = <a href="http://inside-r.org/packages/cran/ggplot">ggplot</a><span style="color: #009900;">(</span>z<span style="color: #339933;">,</span>aes<span style="color: #009900;">(</span>wins<span style="color: #009900;">)</span><span style="color: #009900;">)</span> +
geom_histogram<span style="color: #009900;">(</span>fill=<span style="color: blue;">'light blue'</span><span style="color: #009900;">)</span> +
theme_bw<span style="color: #009900;">(</span><span style="color: #009900;">)</span> +
ggtitle<span style="color: #009900;">(</span><span style="color: blue;">'Of the 30 parameters we wish to estimate:<span style="color: #000099; font-weight: bold;">\n</span> how many of them have estimates closer to the actual using the James-Stein estimator than the MLE?'</span><span style="color: #009900;">)</span> +
ylab<span style="color: #009900;">(</span><span style="color: blue;">''</span><span style="color: #009900;">)</span> +
xlab<span style="color: #009900;">(</span><span style="color: blue;">''</span><span style="color: #009900;">)</span> +
geom_vline<span style="color: #009900;">(</span>aes<span style="color: #009900;">(</span>xintercept=<a href="http://inside-r.org/r-doc/base/mean"><span style="color: #003399; font-weight: bold;">mean</span></a><span style="color: #009900;">(</span>wins<span style="color: #009900;">)</span><span style="color: #339933;">,</span>linetype=<span style="color: blue;">'longdash'</span><span style="color: #339933;">,</span>colour=<span style="color: blue;">'blue'</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span> +
annotate<span style="color: #009900;">(</span><span style="color: blue;">'text'</span><span style="color: #339933;">,</span>x=<span style="color: #cc66cc;">18</span><span style="color: #339933;">,</span>y=<span style="color: #cc66cc;">150</span><span style="color: #339933;">,</span>label=<span style="color: blue;">'Mean -->'</span><span style="color: #009900;">)</span> +
theme<span style="color: #009900;">(</span>legend.position=<span style="color: blue;">'none'</span><span style="color: #009900;">)</span>
<a href="http://inside-r.org/r-doc/grDevices/png"><span style="color: #003399; font-weight: bold;">png</span></a><span style="color: #009900;">(</span><span style="color: blue;">'xyz.png'</span><span style="color: #339933;">,</span>width=<span style="color: #cc66cc;">800</span><span style="color: #339933;">,</span>height=<span style="color: #cc66cc;">500</span><span style="color: #009900;">)</span>
<a href="http://inside-r.org/r-doc/base/print"><span style="color: #003399; font-weight: bold;">print</span></a><span style="color: #009900;">(</span>p<span style="color: #009900;">)</span>
<a href="http://inside-r.org/r-doc/grDevices/dev.off"><span style="color: #003399; font-weight: bold;">dev.off</span></a><span style="color: #009900;">(</span><span style="color: #009900;">)</span></pre>
</div>
</div>
<br />
<br />
The above R code runs a simulation of sorts. It starts by making some random parameters you would want to estimate and simulates some normally distributed data from it. Next, it uses the James Stein estimator and estimates the very parameters it started off with, using the data. Finally, it compares and records how often the James Stein estimator was better/closer that the MLE estimate. The results from the simulation are shown below.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgad98A1NFx92xIMenUI8w5use-8JkEdehxsG7ce10PRJZ0fwlEhILIsUVYi3oszPDj2VAZ-Oe2QLXrWYvVZZaHtqY8wNTqWpggFg55HS6jcD1IZGMD9yrLRHCC75iZz6Xvf7fw4loexE8/s1600/t-normal.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgad98A1NFx92xIMenUI8w5use-8JkEdehxsG7ce10PRJZ0fwlEhILIsUVYi3oszPDj2VAZ-Oe2QLXrWYvVZZaHtqY8wNTqWpggFg55HS6jcD1IZGMD9yrLRHCC75iZz6Xvf7fw4loexE8/s640/t-normal.png" width="640" /></a></div>
<br />
<br />
For kicks, you can try it for a Poisson distribution too, here is what the distribution looks like.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiWzGUujxhAB9c73JAvStGkuAoF9fHIJOcFbg4MVpNZg58cNEJEH4Ogs_yFwMjNDLMbdKryJC3Ai0hRHPyb5fYk4LGHfEYSoEGDeGBUTXHqqGuipaOran-9K8PfBaCcePPcb226eqhrzGc/s1600/t-poisson.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiWzGUujxhAB9c73JAvStGkuAoF9fHIJOcFbg4MVpNZg58cNEJEH4Ogs_yFwMjNDLMbdKryJC3Ai0hRHPyb5fYk4LGHfEYSoEGDeGBUTXHqqGuipaOran-9K8PfBaCcePPcb226eqhrzGc/s640/t-poisson.png" width="640" /></a></div>
<br />
<br />
If you are interested in learning more about probability <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html" rel="nofollow" target="_blank">here</a> are a list of books that are good to buy.<br />
<script src="httpsp://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"></script><br />Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-3824394956672712858.post-44405998559476365362014-11-28T11:14:00.000-08:002015-06-29T08:24:45.851-07:00Bayesian Cognitive BiasI chanced on this excellent puzzle on the net that tends to reveal a cognitive bias in our heads against Bayesian reasoning. The puzzle statement is quite simple<br />
<br />
You are given four cards. Each card has a letter on one side and number on the other side. You are told the statement "If there is a D on one side, there is a 5 on the other side". Which two cards would you flip over to validate the statement?<br />
<br />
<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<br />
<img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAQEAAABaCAIAAAA3sHQqAAAHFElEQVR4nO2dMWojSxCGfYM9yd5h76EDKNzEDleBAmcCg0BgBQ4sBxYYMQZhCwyyAjkRCINAAgc2KFGg7J3gvUAg9LrLo5muanX9O9VUtNjmm675urp7embP/rVmrdrtLDWANWuJmzlgrerNHLBW9WYOWKt6cx1ovf68eDzTH63Xn/7FoMCT/NDwQPw+vOvAxePZ5z+v+uPikahgKPAkPzQ8EL8Pj5oJ6DSQ/NDwQPzmgJYwB/TAo2YCOg0kPzQ8EL85oCXMAT3wqJmATgPJDw0PxG8OaAlzQA88aiag00DyQ8MD8ZsDWsIc0AOPmgnoNJD80PBA/OaAljAH9MCjZgI6DSQ/NDwQvzmgJcwBPfComYBOA8kPDQ/Ebw5oCXNADzxqJqDTQPJDwwPxmwNawhzQA4+aCeg0kPwi8G8f99m03R00ar9/7eLq7rw/bk2WvdV2ZJ1PwpsDWviZ8C/vN81OfX/rk5FN29o6Px+YjGan3h+3BOHNAS38wfCLzfDq7rz4DbTYDPV0foADu7h9vpSCL5GJxWZ4WGSLRHfQEC/EUmkoeDnNTl2W/Dv+sHtosRkeHf7FNdDgQO33Lyn4Epko29e+uPN1Fu8eKpuG4pfz9nEvhZ3DH3APrbajsKQ0O3XOqKTBgTR1gCPAIbpITeCnoTjz1d05H/gof8A91B+3fNps2j4ca+brLJu2/R+TnVKf0oGU6wFmHTi8Bg1T0lKXI14K+A7M15nv6ncdS06ZgrMQzwHZTi4IH3c9kKMBsxqcbD0QqRTwHXBG96NdutgMnYt6ml2n6vx9gDkQgD5fZ5Nl7/b50r+ruoOG7JUEp2Efbx/3JysFfAeccf3l/ebor7y83xz+iuCU2hw4jj5fZ34tLpK2E6RhH6SrkUoB3wEHr0hd9UtB8s6vkAO78Lexg2dE4g7494c/4Y66r1UW/tDY4iO6OZDYAX9lFvzkUtwBZ3q923lw/jF48lCEPwB+p8Ht82Xx1a1yB1bb0WTZ649bh0u17qCRTdtSc9HEDnx6U9LgUiDuADnkr7ajSKUgyZk5Z8GjcD2QH1d353wT0jvw6c2IJste2jR8emYeTv0jlYIkDgQso2N3fikHDku0YM8ncGCy7PEvSdYBR8vDwSZSKTi9A/5GsIbFWIADNd6mogoHnLVm2H6LYBqcGYJ/QMh5HMsch77jj+qAL4CSTbkwB2qiK8kEDvB/XTYNzpao/+TI3yDiH/c4mQOr7cgXgHmIOrYD/XHr7eN+38mLzZA87jH7ehCBr7oD/pYoeX87nvAP4p/GAfKIRAz4YH6nxmbT9nfji38tUjOIqjtAbon6IV4KTuDA7OshhgCCnb+L/Q7v0YWWyBMbc+AISU6fypaC2A6Q5z7CtuDidX5AHJ24BsBX2gH/YUWpkD2CL3gP+bPnZqceNnuO1/lhwX/EYQ78L4q/gkhG8LlLkl/qHvJPPXUHDf5hdfHODwtnqzrgLT8VDijZG80/JVokOK9ZxnCAPA0u9R69bOdzgjmAqnBAyTOy/FOiBUPwUSvzHiJP5sZ4C1Sk8znxNzig4ayEvyV64lIg64AzrNRy3ynjhznA4lByZs5ZNZaaMDgOh5UCQQf8FbDIk+x4nc8JZyIdcGgisQP+FDzV2WkHo9Q289GzFWH8YfeQswBodupSG6DxOp8TT7Nrpu0pHXDoOUWAmQanFgWMJfzpHN8B/7mp+P5PjM7fx+4Jcak5m/8tmYAFz6kdWG1H83X2NLsmP+KQ6thWzinRguGUgoCtLaYDnIq6G4w4h8D5DjhHJIoMIv6ul1QFTvNdCc4sKCwNReDzx1H+X8jnL3UPpU0B3wGy6ybLnj8pna+zt4978ktKUiuxBN8X4gsQkIaC8DlDC/8vaHNAcFOrLD/z6WSN8QoBywGpfhd5aF82DcUJ4/0FbQ4URI3hwOzrgXkXCX4g7KR1QPCZpdUBaAc+vznWWiS6g4bsSa2464Fmp377fCn4UYDgNNh6QJsDuyjy3ybsQ9c79ckj7aPKGPzQ8Ez++Tp7eb+5fb4kD/z1x62X9xupbV9zQEuYA3rgUTMBnQaSHxoeiN8c0BLmgB541ExAp4Hkh4YH4jcHtIQ5oAceNRPQaSD5oeGB+M0BLWEO6IFHzQR0Gkh+aHggfnNAS5gDeuBRMwGdBpIfGh6I3xzQEuaAHnjUTECngeSHhgfiNwe0hDmgBx41E9BpIPmh4YH4zQEtYQ7ogUfNBHQaSH5oeCB+c0BLmAN64FEzAZ0Gkh8aHojfHNAS5oAeeNRMQKeB5IeGB+I3B7SEOaAHHjUT0Gkg+aHhgfjNAS1hDuiBR80EdBpIfmh4IP7jDvx5+nHxeKY//jz98NOAAk/yQ8MD8fvwhNDWrFWqmQPWqt7MAWtVb+aAtao3c8Ba1Zs5YK3qzRywVvX2Hzqz1JOk4+v/AAAAAElFTkSuQmCC" /><br />
<br />
The original article is <a href="http://www.articlesbase.com/psychology-articles/can-you-solve-this-logic-puzzle-it-seems-incredibly-easy-but-may-reveal-a-cognitive-bias-2051369.html" target="_blank">here</a>, think hard before you click through for an answer :)<br />
<br />
Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-3824394956672712858.post-80718402109181844172014-09-02T07:02:00.000-07:002015-06-30T07:51:42.459-07:00Maximizing Chances in an Unfair Game<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table><script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
Q: You are about to play a game wherein you flip a biased coin. The coin falls heads with probability \(p\) and tails with \(1 - p\) where \(p \le \frac{1}{2}\). You are forced to play by selecting heads so the game is biased against you. For every toss you make, your opponent gets to toss too. The winner of this game is the one who wins the toss the most. You, however get to choose the number of rounds that get played. Can you ever hope to win?<br />
<br />
<a href="http://www.amazon.com/gp/product/1107422221/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=1107422221&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);" target="_blank">Machine Learning: The Art and Science of Algorithms that Make Sense of Data</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=1107422221" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
A: At a first look, it might appear that the odds are stacked against you as you are forced to play by choosing heads. You would think that your chances or winning decrease as you play more and more. But, surprisingly there is a way to choose the optimal number of tosses (remember, you get to choose the number of times this game is played). To see how, lets crank out some numbers. If you get to toss the coin \(n\) times, then the total number of coin tosses you and your opponent flips is \(2n\). Out of the \(2n\) tosses if \(y\) turns out heads, the probability that you would win is<br />
$$<br />
P(\text{y Wins}) = {2n \choose y} p^{y}(1 - p)^{2n - y}<br />
$$ <br />
In order to win, the value of \(y\) should run from \(n + 1\) to \(2n\) and the overall probability works out to<br />
$$<br />
P(\text{Win}) = \sum_{y = n + 1}^{2n}{2n \choose y} p^{y}(1 - p)^{2n - y}<br />
$$ <br />
We can work out the probability of winning by choosing various values of \(p\) and \(n\) and chart them out. Here is the R code that does it.<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhk2KgtAwcfeupzRGg3HwhUmOsJ3gv-XzxOXON4TAG1nSrcV7GzLrtidtlBo-CbbHqfk54CwNiZcBWzOKVNdIjc_zb8Q-Nx0xCOAEBytTnKsisBAUFBPEvgjOeQhD4iPQaop7KzAbSV8Zs/s1600/code1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhk2KgtAwcfeupzRGg3HwhUmOsJ3gv-XzxOXON4TAG1nSrcV7GzLrtidtlBo-CbbHqfk54CwNiZcBWzOKVNdIjc_zb8Q-Nx0xCOAEBytTnKsisBAUFBPEvgjOeQhD4iPQaop7KzAbSV8Zs/s1600/code1.png" /></a></div>The code runs pretty quickly and uses the data.table package. All the processed data is contained in variables z and z1. They are plotted using the ggplot package to generate the following charts for the strategy.<br />
<br />
The first chart shows the variation of the probability of winning by the number of games played for various probability bias values.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihMfUrmC1iTNISE9dESbFZ3kyojmL9xagRFwrCSHvqU-W1Minr79oYnqk3mzkLST7gP54rfQFYvWU7jFOJ7fWk9zV80j3uiPnVUITCEJfKe175tJEHE3DJm338gJfrFelVDrVTIJaCywI/s1600/diagram31.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihMfUrmC1iTNISE9dESbFZ3kyojmL9xagRFwrCSHvqU-W1Minr79oYnqk3mzkLST7gP54rfQFYvWU7jFOJ7fWk9zV80j3uiPnVUITCEJfKe175tJEHE3DJm338gJfrFelVDrVTIJaCywI/s1600/diagram31.png" height="400" width="400" /></a></div>The next chart shows the optimal number of games to play for a given bias probability value.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj0jjptE3yWbWk1YQVmkE2FYDl2EJQXMT4jwFjPKlmqkcgJuR6MUMp7bMyUE98m65kCskXjiEmcVlw1mpzstTvpq_8zEishdlLUGfLkc8yyYBmtVRnqpiaJE_rZoilgLhKsbd1bT29P3JY/s1600/diagram32.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj0jjptE3yWbWk1YQVmkE2FYDl2EJQXMT4jwFjPKlmqkcgJuR6MUMp7bMyUE98m65kCskXjiEmcVlw1mpzstTvpq_8zEishdlLUGfLkc8yyYBmtVRnqpiaJE_rZoilgLhKsbd1bT29P3JY/s1600/diagram32.png" height="400" width="400" /></a></div>Some good books to own for learning probability is listed <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html#.U_eV-RVx05k" target="_blank">here</a><br />
Yet another fascinating area of probability are Monte Carlo methods. <a href="http://bayesianthink.blogspot.com/2014/08/the-best-books-for-monte-carlo-methods.html#.U_eVcBVx05k" target="_blank">Here</a> are a list of good books to own to learn Monte Carlo methods.<br />
<br />
<br />
<br />
<br />
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-89205787577175939072014-08-12T16:01:00.001-07:002014-08-18T12:34:58.907-07:00The Best Books for Monte Carlo MethodsThe following are some of the best books to own to learn Monte Carlo methods for sampling and estimation problems<br />
<br />
<a href="http://www.amazon.com/ss/customer-reviews/0387212396/?_encoding=UTF8&camp=1789&creative=390957&linkCode=ur2&showViewpoints=1&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);" target="_blank">Monte Carlo Methods in Statistics (Springer)</a><img alt="" border="0" height="1" src="https://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=ur2&o=1" style="border: none !important; margin: 0px !important;" width="1" /><br />
This is a good book which discusses both Bayesian methods from a practical point of view as well as theoretical point of view with integrations. The explanations given are also fairly comprehensive. There are also a fair amount of examples in this text. Overall, this is an excellent book to own if you want to understand Monte Carlo sampling methods and algorithms at an intermediate to graduate level.<br />
<br />
<a href="http://www.amazon.com/gp/product/038787836X/ref=as_li_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=038787836X&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);" >Explorations in Monte Carlo Methods (Undergraduate Texts in Mathematics)</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=038787836X" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
This is good book to own to get you started on Monte Carlo methods. It starts with fairly simple and basic examples and illustrations. The mathematics used is also fairly basic. Buy this if you are at an undergraduate level and want to get into using Monte Carlo methods but have only a basic knowledge of statistics and probability.<br />
<br />
<a href="http://www.amazon.com/gp/product/0387004513/ref=as_li_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0387004513&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Monte Carlo Methods in Financial Engineering (Stochastic Modelling and Applied Probability) (v. 53)</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0387004513" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
Another excellent book to own if you are curious to learn about the methods of Monte Carlo in the finance industry. Some really nice areas that are covered in the book include variance reduction techniques, diffusion equations, change point detections, Option pricing methods etc. Ideal for students of financial engineering or ones wanting to break into it. The book tends to overtly rate MC methods (well its a book on MC!).<br />
<br />
<a href="http://www.amazon.com/gp/product/1452288909/ref=as_li_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=1452288909&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Monte Carlo Simulation and Resampling Methods for Social Science</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=1452288909" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
This book gives a good introduction and goes over some basic probability theory, statistics and distributions before it hops on to the Monte Carlo methods. This makes it a good introductory book for sampling methods. Recommended for undergraduates with minimal statistical background.<br />
<br />
<a href="http://www.amazon.com/ss/customer-reviews/0470177942/?_encoding=UTF8&camp=1789&creative=390957&linkCode=ur2&showViewpoints=1&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);" target="_blank">Simulation and Monte Carlo Method</a><br />
<img alt="" border="0" height="1" src="https://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=ur2&o=1" style="border: none !important; margin: 0px !important;" width="1" /><br />
An excellent book to own at the intermediate to graduate level. The text provides a good course in simulation and Monte Carlo methods. Some interesting topics covered in the text include rare-event simulation. The book assumes you have a background in statistics and probability theory. <br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-34919894443269665222014-07-06T07:21:00.000-07:002015-06-30T07:51:58.350-07:00Embarrassing Questions, German Tanks and Estimations<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table><br />
Q: You are conducting a survey and want to ask an embarrassing yes/no question to subjects. The subjects wouldn't answer that embarrassing question honestly unless they are guaranteed complete anonymity. How would you conduct the survey?<br />
<br />
<a href="http://www.amazon.com/gp/product/1107422221/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=1107422221&linkCode=as2&tag=bayesianinfer-20">Machine Learning: The Art and Science of Algorithms that Make Sense of Data</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=1107422221" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
A: One way to do this is to assign a fair coin to the subject and ask them to toss it in private. If it came out heads then answer the question truthfully else toss the coin a second time and record the result (heads = yes, tails = no). With some simple algebra you can estimate the proportion of users who have answered the question with a yes.<br />
<br />
Assume total population surveyed is \(X\). Let \(Y\) subjects have answered with a "yes". Let \(p\) be the sort after proportion. The tree diagram below shows the user flow.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://www.amazon.com/gp/product/0495391328/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0495391328&linkCode=as2&tag=bayesianinfer-1-20" imageanchor="1" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);" style="margin-left: 1em; margin-right: 1em;"><br />
<img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhaUsHEGDBGsSDM5b_H5dYHHQFwlEHf9S9wdeKTkP7bg5QQJ0Xf4FZhv5Aqy29fxUuhiMigGtoWPIG4qMYzq9OEKh5zaqpNUoDFf8cyxRDCwxiqoE2jCnhYueNoTBx6csGHySP2FoX6B4o/s1600/diagram30.png" /></a></div><br />
The total expected number of "yes" responses can be estimated as<br />
$$<br />
\frac{pX}{2} + \frac{X}{4} = Y<br />
$$<br />
which on simplification yields<br />
$$<br />
p = \big(\frac{4Y}{X} - 1\big)\frac{1}{2} <br />
$$<br />
<br />
<a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html#.Uy3bzRVx05k" target="_blank">Best Books on Probability</a><br />
<br />
Q: A bag contains unknown number of tiles numbered in serial order \(1,2,3,...,n\). You draw \(k\) tiles from the bag without replacement and find the maximum number etched on them to be \(m\). What is your estimate of the number of tiles in the bag?<br />
<br />
A: This and problems like these are called <a href="http://en.wikipedia.org/wiki/German_tank_problem" target="_blank">German War Tank</a> problems. During WW-II German tanks were numbered in sequential order when they were manufactured. Allied forces needed an estimate of how many tanks were deployed and they had a handful of captured tanks and their serial numbers painted on them. Using this, statisticians estimated the actual tanks to be far lower than what intelligence estimates had them believe. So how does it work?<br />
<br />
Let us assume we draw a sample of size \(k\). The maximum in that sample is \(m\). If we estimate the maximum of the population to be \(m\) then probability of the sample maximum to be \(m\) is<br />
$$<br />
P(\text{Sample Max} = m) = \frac{m-1 \choose k-1}{N \choose k} <br />
$$ <br />
The \(-1\) figures because the maximum is already taken out of the sample leaving behind \(m - 1\) to choose \(k -1 \) from. The expected value of the maximum using this strategy is thus<br />
$$<br />
E(\text{Maximum}) = \sum_{m=k}^{m=N}m\frac{m-1 \choose k-1}{N \choose k} <br />
$$ <br />
Note, we run the above summation from \(k\) to \(N\) as for \(m < k\) the expectation is \(0\) because the sample maximum has to be at least \(k\). After a series of algebraic manipulations <a href="http://www.r-bloggers.com/frequentist-german-tank-problem/" target="_blank">( ref )</a> the above simplifies to<br />
$$<br />
E(\text{Maximum}) = M\big( 1 + \frac{1}{k}\big) - 1 <br />
$$<br />
which is quite an ingenious and simple way to estimate population size given serial number ordering.<br />
<br />
If you are looking to buy some books on probability theory <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html#.Uy3bzRVx05k" target="_blank">here</a> is a good list.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-47579683096296582292014-06-01T07:50:00.000-07:002015-06-30T07:52:10.662-07:00The Chakravala Algorithm in R<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table><br />
A class of analysis that has piqued the interest of mathematicians across millennia are <a href="http://en.wikipedia.org/wiki/Diophantine_equation" rel="nofollow" target="_blank">Diophantine equations</a>. Diophantine equations are polynomials with multiple variables and seek integer solutions. A special case of Diophantine equations is the <a href="http://en.wikipedia.org/wiki/Pell%27s_equation" target="_blank">Pell's equation</a>. The name is a bit of a misnomer as Euler mistakenly attributed it to the mathematician John Pell. The problem seeks integer solutions to the polynomial<br />
$$<br />
x^{2} - Dy^{2} = 1<br />
$$<br />
Several ancient mathematicians have attempted to study and find generic solutions to Pell's equation. The best known algorithm is the Chakravala algorithm discovered by Bhaskara circa 1114 AD. Bhaskara implicitly credits Brahmagupta (circa 598 AD) for it initial discovery, though some credit it to Jayadeva too. Several Sanskrit words used to describe the algorithm appear to have changed in the 500 years between the two implying other contributors. The Chakravala technique is simple and implementing it in any programming language should be a breeze (credit <a href="http://cs.annauniv.edu/insight/Reading/algebra/indet/chakra.htm" target="_blank">citation</a>)<br />
<br />
<a href="http://www.amazon.com/gp/product/0125062508/ref=as_li_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0125062508&linkCode=as2&tag=bayesianinfer-20&linkId=BO2TH6KMWHHEYM6X" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Diophantine Equations (Pure & Applied Mathematics)</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0125062508" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
<br />
The method works as follows. Find a trivial solution to the equation. \(x=1,y=0\) can be used all the time. Next, initialize two parameters \([p_i,k_i]\) where \(i\) is an iteration count. \(p_i\) is updated to \(p_{i+1}\) if the following two criteria are satisfied.<br />
<ul><li>\(p_i + p_{i+1} mod k_{i} = 0\) i.e. \(p_i + p_{i+1}\) is divisible by \(k_i\)</li>
<li>\(| p_{i+1} - d |^{2}\) is minimized</li>
</ul>After updating \(p_{i+1}\) \(k_{i+1}\) is found by evaluating<br />
$$ <br />
k_{i+1} = \frac{p_{i+1}^{2} - d}{k_{i}}<br />
$$<br />
and the next pair of values for \([x,y]\) is computed as<br />
$$<br />
x_{i+1} = \frac{p_{i+1}x_i + dy_{i}}{|k_{i}|}<br />
y_{i+1} = \frac{p_{i+1}y_i + x_{i}}{|k_{i}|}<br />
$$<br />
The algorithm also has an easy way to check if the found solution is a solution. It does so by only accepting values where \(k_{i} = 1\).<br />
<br />
A screen grab of the entire algorithm done in R is shown below.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgmX4UoQaSVr7pLnBQCz4VsDOMCxSsKPpyALTnMX6363kSEjGBkJgKPQYCosa0WnYOlxX0OX4NSXyzJIxJMoAIfCiR5njbtOSkqhodM7W8Y6Sj66Ku72_NzKWYPS0KbMff3FEkKnH-O_vg/s1600/diagram29.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgmX4UoQaSVr7pLnBQCz4VsDOMCxSsKPpyALTnMX6363kSEjGBkJgKPQYCosa0WnYOlxX0OX4NSXyzJIxJMoAIfCiR5njbtOSkqhodM7W8Y6Sj66Ku72_NzKWYPS0KbMff3FEkKnH-O_vg/s1600/diagram29.png" /></a></div><br />
<b>A Related Puzzle:</b><br />
A drawer has \(x\) black socks and \(y\) white socks. You draw two socks consecutively and they are both black. You repeat this several times (by replacing the socks) and find that you get a pair of blacks with probability \(\frac{1}{2}\). You know that there are no more than 30 socks in the draw in total. How many black and white socks are there?<br />
<br />
The probability that you would draw two black socks in a row is<br />
$$<br />
P = \frac{x}{x+y}\times\frac{x - 1}{x+y - 1} = \frac{1}{2}<br />
$$<br />
Simplifying and solving for \(x\) yields<br />
$$<br />
x^{2} - (2y + 1)x + y - y^2 = 0 <br />
$$<br />
which on further simplification gives<br />
$$<br />
x = \frac{2y + 1 \pm \sqrt{(2y+1)^2 +4(y^2 - y)}}{2}<br />
$$<br />
We can ignore the root with the negative sign as it would yield a negative value for \(x\) which is impossible. The positive root of the quadratic equation yields<br />
$$<br />
x = \frac{2y + 1 + \sqrt{8y^2 + 1}}{2} <br />
$$<br />
For \(x\) to be an integer, the term \(\sqrt{8y^2 + 1}\) has to be an odd integer number \(z\) (say). We can now write it out as<br />
$$<br />
z = \sqrt{8y^2 + 1} <br />
$$<br />
or<br />
$$<br />
z^{2} - 8y^2 = 1<br />
$$<br />
This is Pell's equation (or Vargaprakriti in Sanskrit).<br />
As we know that there are no more than 30 socks in the draw, we can quickly work our way to two admissible solutions to the problem \(\{3,1\}, \{15,6\}\).<br />
If you are looking to buy books on probability theory <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html#.Uy3bzRVx05k" target="_blank">here</a> is a good list to own.<br />
If you are looking to buy books on time series analysis <a _blank="" href="http://bayesianthink.blogspot.com/2014/02/the-best-books-for-time-series-analysis.html#.U4akWxVx05k%20target=">here</a> is an excellent list to own.<br />
<br />
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-8671350675386486982014-05-07T07:57:00.000-07:002015-06-30T07:52:21.914-07:00Hopping Robots and Reinforcement Learning<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table><br />
All too often, when we deal with data the outcome needed is a strategy or an algorithm itself. To arrive at that strategy we may have historic data or some model on how entities in system respond to various situations. In this write up, I'll go over the method of reinforcement learning. The general idea behind reinforcement learning is to come up with a strategy to maximize some measurable goal. For example, if you are modelling a robot that learns to navigate around obstacles, you want the learning process to come back with a strategy that minimizes collisions (say) with other entities in the environment.<br />
<br />
<a href="http://www.amazon.com/gp/product/0387310738/ref=as_li_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0387310738&linkCode=as2&tag=bayesianinfer-20&linkId=UT7PWFCW2K2SFITH" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Pattern Recognition and Machine Learning (Information Science and Statistics)</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0387310738" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
For the sake of simplicity, lets assume the following scenario. A robot is placed (at random) on flat plank of wood which has some sticky glue in the center. To its left there is a hole which damages the robot a bit and to its right is a reward which is its destination, as shown in the figure below<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://www.amazon.com/gp/product/0495391328/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0495391328&linkCode=as2&tag=bayesianinfer-1-20" imageanchor="1" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEizMYD4SNl4dyCfO08Pkb3VDelM3lvRMMNukR2BANWT3ZbY9Ghhe6azXqizPZer0M1Cy1cbyXz5MKJHZ0k-478r9VMgB5zF7hZxxU6X5cI_NiIza-Mgon030trn0BND-rFGZgnTxqSo6_I/s1600/diagram25.png" /></a></div><br />
The robot has the following capabilities<br />
<ul><li>It can sense what state \({S_1,S_2,...,S_7}\) it is in</li>
<li>It can detect a reward or damage that happens to it while in a particular state</li>
<li>It can move one space left or right</li>
<li>It can hop a space on to the right</li>
</ul>If the robot ends up in either of the terminal states of \(S_1\) or \(S_7\) it is taken and placed in another state at random. State \(S_1\) does damage to the robot while state \(S_7\) rewards it. \(S_4\) is not exactly a damage causing state but it is an avoidable state and we want to learn that over time. All other states are neither harmful nor rewarding. The robot's goal is to "learn" to get to state \(S_7\) in as few steps as possible.<br />
<br />
In order to get reinforcement learning to work, you need to know what the reward values are for each of the states the robot can be in. In this particular example, we will assume the following reward structure for each of the states.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiHR31FcIpCaZr5fDRJueEfKKSqt9k9M_EF2K2r3Sq3aa_6_fPhrTwQSoorgsVaSFdRrIZTO5A45BnGM5Yi8GDgPRc0hSVAtP4CpTbNIA9JpjUO3vslNUKtVupXvjTZsm28KSwLo1yHvPk/s1600/diagram26.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiHR31FcIpCaZr5fDRJueEfKKSqt9k9M_EF2K2r3Sq3aa_6_fPhrTwQSoorgsVaSFdRrIZTO5A45BnGM5Yi8GDgPRc0hSVAtP4CpTbNIA9JpjUO3vslNUKtVupXvjTZsm28KSwLo1yHvPk/s1600/diagram26.png" /></a></div>Note, the numbers are fairly arbitrary. In addition to this we need a function or a table, mapping out actions/states pairs leading to new states. Given the robot's movement description above, we can use a table as follows<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiBfrfPQU31UfmcJy4KIbNoEbBe7Q3UbodfShTNZR7CC3VUG9yjnPER-_HN3vvV3P9xq153QxsYp9gprOsUlMdr2leZ8CGTZkcZ76oJunjERaVkhZNj0_Fz65iwkGUMqTeeWOqfFPaJ_qA/s1600/diagram27.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiBfrfPQU31UfmcJy4KIbNoEbBe7Q3UbodfShTNZR7CC3VUG9yjnPER-_HN3vvV3P9xq153QxsYp9gprOsUlMdr2leZ8CGTZkcZ76oJunjERaVkhZNj0_Fz65iwkGUMqTeeWOqfFPaJ_qA/s1600/diagram27.png" /></a></div>Zero is being used to designate the scenario when the robot is reset to a random state. With the above two sets of information we are good to start the learning process.<br />
<br />
Reinforcement learning works in the following way. You maintain a matrix of values for each state/action pair. This is the reward that can be attained by arriving at a particular state by taking a particular action. But the trick is to also account for what possible future state you can get to, given that you arrive at a given state. For example it may be beneficial to be in a certain state \(X\), but all downstream states from \(X\) may be bad to be in. You want to avoid such states. This way, the algorithm tries to ensure that future favourable and achievable states are taken into account. The algorithm does not immediately update itself based on whatever it learns, it preserves old values and learns gradually. The above methodology can be stated as follows.<br />
<br />
If \(Q^{*}(s_t,a_t)\) represents the pay off received by being in state then<br />
<br />
$$<br />
Q^{*}(s_t,a_t) = R(s_{t+1},s_t) + \alpha max_{a_t}Q^{*}(s_{t+1},a_{t+1})<br />
$$<br />
<br />
To slow down learning a bit, we stick with whatever prior estimate of \(Q^{*}(s_t,a_t)\) we have by a fraction of \(\beta\) as shown below<br />
<br />
$$<br />
Q^{*}_{new}(s_t,a_t) = \beta Q^{*}_{prior}(s_t,a_t) + (1 - \beta)Q^{*}(s_t,a_t)<br />
$$<br />
That's it! We now let the system take on various initial states, and let the device play around moving over to different states while we constantly update our \(Q\) matrix. After several iterations, the \(Q\) matrix will end with some values which reflect what strategy to take.<br />
<br />
To give a swirl, here is an R code that walks through the entire process for this particular example<br />
<br />
<script src="https://gist.github.com/broccolilettuce/353c3243eafff15648ba.js"></script><br />
<br />
A thing to note in the code is how the reward function is encoded. There is a penalty imposed on moving from a higher state to a lower state. This is the simple way to ensure that whatever strategy it comes up with does not involve going backwards from rightward positional gains that have been made. If you try it without the penalty, you will see cases where the strategy does not care going left or right in some states. The above code when run, creates the following output (screen grab below)<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhN86lSiH5gptMEtWi_7XnMG-qE9GeXd8WM57RAQcFhvbsKTarvl1ZWm8vLSIDryJGmFXAizfSWHsK8L9tJlgNsQY2mTEVPfRL3GEcOz7MCtK3DyQIb6K3b44ZkOCrUHahMk67GXtWqpk8/s1600/diagram28.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhN86lSiH5gptMEtWi_7XnMG-qE9GeXd8WM57RAQcFhvbsKTarvl1ZWm8vLSIDryJGmFXAizfSWHsK8L9tJlgNsQY2mTEVPfRL3GEcOz7MCtK3DyQIb6K3b44ZkOCrUHahMk67GXtWqpk8/s1600/diagram28.png" /></a></div><br />
The rows represent the states, the columns represent the three possible actions move-left, move-right and hop-right that the robot can take. Notice what it's trying to say:<br />
<ul><li>State 1, do nothing </li>
<li>State 2, move right, but don't hop</li>
<li>State 3, don't move right, hop</li>
<li>State 4, move right or hop</li>
<li>State 5, move right (small chance), hop (definitely)</li>
<li>State 6, move right, move left (small chance)</li>
</ul>This is exactly what you would expect and want! More on this subject can be read from the following books<br />
<a href="http://www.amazon.com/gp/product/364227644X/ref=as_li_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=364227644X&linkCode=as2&tag=bayesianinfer-20&linkId=LD7GC35HSG3IYQAF" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Reinforcement Learning: State-of-the-Art (Adaptation, Learning, and Optimization)</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=364227644X" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
an<br />
<a href="http://www.amazon.com/gp/product/0262193981/ref=as_li_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0262193981&linkCode=as2&tag=bayesianinfer-20&linkId=BVEEPPP5SQUOA5Z2" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Reinforcement Learning: An Introduction (Adaptive Computation and Machine Learning)</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0262193981" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
If you are looking to buy some books on probability theory <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html#.Uy3bzRVx05k" target="_blank">here</a> is a good list to own.<br />
<br />
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-87634922863901432922014-04-17T07:45:00.000-07:002015-06-30T07:52:32.076-07:00The Two Strategies<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table>Q: You are in a game where you get to toss a pair of coins once. There are two boxes (A & B) holding a pair each. Box A's coins are fair however B's coins are biased with probability of heads being \(0.6\) and \(0.4\) respectively. You are paid for the expected number of heads you will win. Which of the boxes should you pick?<br />
<br />
<a href="http://www.amazon.com/gp/product/1107422221/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=1107422221&linkCode=as2&tag=bayesianinfer-20">Machine Learning: The Art and Science of Algorithms that Make Sense of Data</a><img src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=1107422221" width="1" height="1" border="0" alt="" style="border:none !important; margin:0px !important;" /><br />
<br />
A: The expected number of heads if you chose box A is easy to calculate as<br />
$$<br />
E(\text{heads}| A) = \frac{1}{2} + \frac{1}{2} = 1<br />
$$<br />
However the expected number of heads if you chose box B is also the same<br />
$$ <br />
E(\text{heads}| B) = \frac{4}{10} + \frac{6}{10} = 1<br />
$$<br />
The average yield being the same could make one think that both boxes yield the same. However there is one difference, its the variance. The variance of a distribution of a random variable \(X\) is defined as<br />
$$<br />
Var(X) = \sum_{i=0}^{N} (x_i - \bar{x})^{2}p_i<br />
$$<br />
where \(p_i\) is the probability of \(x_i\). Given this, lets compute the variance of each strategy<br />
$$<br />
Var(X | \text{Box=A}) = (\frac{1}{2} - 1)^2 \frac{1}{2} + (\frac{1}{2} - 1)^2 \frac{1}{2} = \frac{1}{4} = 0.25 \\<br />
Var(X | \text{Box=B}) = (\frac{2}{5} - 1)^2 \frac{2}{5} + (\frac{3}{5} - 1)^2 \frac{3}{5} = \frac{6}{25} = 0.24 <br />
$$<br />
The variance for box B is slightly tighter than box A which makes choosing the coins in box B a better strategy.<br />
<br />
If you are looking to buy some books on probability theory <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html#.Uy3bzRVx05k" target="_blank">here</a> is a good list.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-64278123776142351742014-03-23T08:33:00.003-07:002015-06-30T07:52:45.497-07:00Linear Regression, Transforms and Regularization<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table>This write up is about the simple linear regression and ways to make it robust to outliers and non linearity. The linear regression method is a simple and powerful method. It is powerful because it helps compress a lot of information through a simple straight line. The complexity of the problem is vastly simplified. However being so simple comes with its set of limitations. For example, the method assumes that after a fit is made, the differences between the predicted and actual values are normally distributed. In reality, we rarely run into such ideal conditions. Almost always there is non-normality and outliers in the data that makes fitting a straight line insufficient. However there are some tricks you could do to make it better.<br />
<br />
<a href="http://www.amazon.com/gp/product/0470392223/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0470392223&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Statistics: A good book to learn statistics</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0470392223" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
As an example data set consider some dummy data shown in the table/chart below. Notice, value 33 is an outlier. When charted. you can see there is some non-linearity in the data too, for higher values of \(x\)<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhgT4Pd3fjfaQTG3GNK6LrYO0DXkYrNmKb1S2x_zaay2-8uEAPJM8eVLWMGPmyJHvPhAO3RWBoOV_gpoxH0OwPo0scks8iaehExasgnD_75VLwkw6WkZBgiNxsr1Oz9YeKr5QeABckc9ZI/s1600/diagram21.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhgT4Pd3fjfaQTG3GNK6LrYO0DXkYrNmKb1S2x_zaay2-8uEAPJM8eVLWMGPmyJHvPhAO3RWBoOV_gpoxH0OwPo0scks8iaehExasgnD_75VLwkw6WkZBgiNxsr1Oz9YeKr5QeABckc9ZI/s1600/diagram21.png" height="353" width="400" /></a></div>First lets tackle the non-linearity. The non-linearity can be managed by doing a transformation onthe y-values using the box-cox transform which is a class of power transformation. It is a useful transform to bring about normality in time series values that looks "curvy". The transform looks like<br />
$$<br />
\hat{y} = \frac{y^{\lambda} - 1}{\lambda}<br />
$$<br />
The value of lambda needs to be chosen optimally that maximizes the log likelihood that would make the time series more like it came from a normal distribution. Most statistical tools out there do it for you. In R, the function "boxcox" in the package "MASS" does it for you. The following code snippet computes the optimal value of \(\lambda\) as -0.30303<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-5A896QFvLS7OeFTABGg8xmnjAWAaiBBa5JLtqIoR8bIvFICcK4qgI9490EuwbCBpMHakrL2w3xcv4jb_SepyXXdDwhsNG04OmxwW35b1CLLvO1orixknrV8DidV77SMDBm6Z5EqCjBw/s1600/diagram22.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-5A896QFvLS7OeFTABGg8xmnjAWAaiBBa5JLtqIoR8bIvFICcK4qgI9490EuwbCBpMHakrL2w3xcv4jb_SepyXXdDwhsNG04OmxwW35b1CLLvO1orixknrV8DidV77SMDBm6Z5EqCjBw/s1600/diagram22.png" /></a></div><br />
Let's apply this transformation to the data and see how it looks on a chart.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://www.amazon.com/gp/product/0495391328/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0495391328&linkCode=as2&tag=bayesianinfer-1-20" imageanchor="1" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgGpxVs31nR6LmF_-j24wyxglCdi64qHUHgJLuP43AMy-ZkNkZc0bNo5W6MqYZ4T6HyvURfHc0V0TeZ0gg1e0wxl8oM3boCFIHbrxch5nXruVwVhhssF5FKo4sPh4XFYfsJ6hM2t7dAfsc/s1600/diagram23.png" height="358" width="400" /></a></div>You can see that it looks a lot better and more like a straight line, except for the outlier at \(x = 4\). The goodness of straight line fit is measured by the fit's \(R^2\) value. The \(R^2\) value tries to quantify the amount of variance that can be explained by the fit. If we fitted a straight line through the original data we get an \(R^2 = 0.06804 \), and the transformed data yields an \(R^2 = 0.4636\) demonstrating an improvement. Next, lets try and manage the outlier. If you try fitting a straight line \(y = \alpha_0 + \alpha_{1} x\) through a set of points that have a few outliers you will notice that the values of \(\alpha_{0}, \alpha_{1}\) tend to be slightly large. They end up being slightly large because the fit is trying to "reach out" and accommodate the outlier. In order to minimize the effect of the outlier we get back into the guts of the linear regression. A linear regression typically tries to minimize the overall error \(e\) as computed as<br />
$$<br />
e = \sum_{i=1}^{N}\frac{(y_{actual} - \alpha_{0} - \alpha_{1}x)^2}{N}<br />
$$<br />
where \(N\) is the number of points. We can tweak the above equation to minimize as follows<br />
$$<br />
e = \sum_{i=1}^{N}\frac{(y_{actual} - \alpha_{0} - \alpha_{1}x)^2}{N} + \lambda(\alpha_{0}^2 + \alpha_{1}^2)<br />
$$<br />
The tweaked error equation forces towards choices of \(\alpha_{0}, \alpha_{1}\) where they cannot take larger values. The optimal value of \(\lambda\) needs to be ascertained by tuning. A formulaic solution does not exist, so we use another tool in R, the function "optim". This function lets you do basic optimization and minimizes any function you pass it, along with required parameters. It returns parameter values that minimize this function. The actual usage of this function isn't exactly intuitive. Most examples on the internet talk of minimizing a proper well formed function. Most real life applications involve minimizing functions having lots of parameters and additional data. The funct"optim" accepts the "..." argument which is a means to pass through arguments to the function you want to minimize. So here is how you would do it in R, all of it.<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhlJC9BwQB7S4IYfk2DzgyJAqV4S5tZ2E0jyNzfSR7R3Goxd3TrpxDCCYB1UT8TAX0DEYy6vaXQKMd0wGrrLeo9olmO_lX3SUy2RiqCTN80FM59kNfU1KrVyZhb2LVJn8En3twxY2qNcxY/s1600/diagram24.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhlJC9BwQB7S4IYfk2DzgyJAqV4S5tZ2E0jyNzfSR7R3Goxd3TrpxDCCYB1UT8TAX0DEYy6vaXQKMd0wGrrLeo9olmO_lX3SUy2RiqCTN80FM59kNfU1KrVyZhb2LVJn8En3twxY2qNcxY/s1600/diagram24.png" /></a><br />
<div class="separator" style="clear: both; text-align: center;"></div><br />
<br />
The above code walks through this example by calling optim. It finally outputs the fits in original domain using all three methods<br />
<ol><li>The grey line represents the fit if you simply used "lm"</li>
<li>The red line represents the fit if you transformed the data and used "lm" in the transformed domain but without regularization. Note: you are clearly worse off.</li>
<li>The blue dotted line shows the fit if you used transformation and regularization, clearly a much better fit</li>
</ol><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnHVEIo03pIGeaIvPqqyjZ2kYEPxOgPhYVaUxgbE8POfgckcz1oGuzP7aMKcpgydcydYfgXHoenu9_IChoxRt_pKFk09SsPlFDkGOSiBCBpmHgtDAe3_UYcZ750FEBlOGhGlSvEw85TaE/s1600/t.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnHVEIo03pIGeaIvPqqyjZ2kYEPxOgPhYVaUxgbE8POfgckcz1oGuzP7aMKcpgydcydYfgXHoenu9_IChoxRt_pKFk09SsPlFDkGOSiBCBpmHgtDAe3_UYcZ750FEBlOGhGlSvEw85TaE/s1600/t.png" height="400" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhlJC9BwQB7S4IYfk2DzgyJAqV4S5tZ2E0jyNzfSR7R3Goxd3TrpxDCCYB1UT8TAX0DEYy6vaXQKMd0wGrrLeo9olmO_lX3SUy2RiqCTN80FM59kNfU1KrVyZhb2LVJn8En3twxY2qNcxY/s1600/diagram24.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><br />
</a></div><br />
<br />
The function "optim" has lots of methods that it uses for finding the minimum value of the function. Typically, you may also want to poke around with the best value of \(\lambda\) in the minimization function to get better fits.<br />
If you are looking to buy some books on time series analysis <a href="http://bayesianthink.blogspot.com/2014/02/the-best-books-for-time-series-analysis.html#.Uy3bkxVx05k" target="_blank">here</a> is a good collection. Some good books to own for probability theory are referenced <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html#.Uy3bzRVx05k" target="_blank">here</a>Unknownnoreply@blogger.com4tag:blogger.com,1999:blog-3824394956672712858.post-30928373113586021042014-03-02T07:55:00.000-08:002015-06-30T07:52:59.867-07:00The Lazy Apprentice<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table><br />
Q: A shopkeeper hires an apprentice for his store which gets one customer per minute on average uniformly randomly. The apprentice is expected to leave the shop open until at least 6 minutes have passed when no customer arrives. The shop keeper suspects that the apprentice is lazy and wants to close the shop at a shorter notice. The apprentice claims (and the shopkeeper verifies), that the shop is open for about 2.5hrs on average. How could the shopkeeper back his claim?<br />
<br />
<a href="http://www.amazon.com/gp/product/0470392223/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0470392223&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Statistics: A good book to learn statistics</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0470392223" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
A: Per the contract, at least 6 minutes should pass without a single customer showing up before the apprentice can close the shop. To solve this lets tackle a different problem first. Assume you have a biased coin with a probability \(p\) of landing heads. What is the expected number of tosses before you get \(n\) heads in a row. The expected number of tosses to get to the first head is simple enough to calculate, its \(\frac{1}{p}\). How about two heads? We can formulate this recursively. We need to get to a head first. Following this, you need to toss the coin one more time for sure. With a probability \(p\) you get the second heads or with a probability \(1 - p\) you have to start over again. The number of tosses to two heads is thus \(\frac{1}{p} + 1 + \frac{1}{p}\times(1-p)\).<br />
<br />
Extending this out to get \(n\) tosses, if you assume that \(y(n)\) is the expected number of tosses to get to \(n\) heads in a row then the following state transition diagram shows how the transitions happen.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="http://www.amazon.com/gp/product/0495391328/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0495391328&linkCode=as2&tag=bayesianinfer-1-20" imageanchor="1" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjR-e4gCbJriOKKtHPYIdf0lwX9Xyw5UdND1thdebv0euL0SX-I1Y4edyxyFFqIsQ8hB0K5EYeqVGnfr7vmqv5qp6gBToNQcyGjoqB4dxctwlh77xCng9m4kDI9wt9Vl9aQGmzW-N6M7GA/s1600/diagram19.png" /></a></div>From the state \(y_{n-1}\), with probability \(1- p\) you start over again. Stated recursively<br />
$$<br />
y_{n} = y_{n-1} + 1 + (1-p)y_{n}\\<br />
py_{n} = y_{n-1} + 1 <br />
$$<br />
Using the above expression, it is easy to derive the general expression for \(y_{n}\) as follows, keeping in mind \(y_{0} = 0\)<br />
$$<br />
y_{1} = \frac{y_{0}}{p} + \frac{1}{p} = \frac{1}{p}\\<br />
y_{2} = \frac{1}{p}(y_{1} + 1) = \frac{1}{p^{2}} + \frac{1}{p}<br />
y_{3} = \frac{1}{p}(y_{2} + 1) = \frac{1}{p^{3}} + \frac{1}{p^{2}} + \frac{1}{p}<br />
$$<br />
Being a sum of a geometric series, the \(y_{n}\) can be evaluated to<br />
$$<br />
y_{n} = \frac{1}{1-p}\big(\frac{1}{p^{n}} - 1\big)<br />
$$<br />
Now, back to the original question. Assume the apprentice waits \(k\) minutes before no customer shows up and he chooses to shut the shop. The situation is "similar" to the coin tossing and awaiting for a string of heads. (Note: Strictly speaking, it's similar only in the limiting case when the time interval is very small). In this case each "head" signifies the absence of a customer showing up in a minute. As the customers arrive uniformly at random we can assume they follow a Poisson process. The probability that \(m\) customers arrive in a one minute window if the rate parameter is \(\lambda\) (in this case \(\lambda = 1min^{-1}\)) is<br />
<br />
$$<br />
P(m,\lambda) = \frac{(\lambda)^{m}e^{-\lambda}}{m!}<br />
$$<br />
<br />
When \(m =0\) we get \(p = e^{-\lambda}\). Plugging this value back to our equation for \(y_{n}\) we get<br />
$$<br />
y_{n} = \frac{1}{1 - e^{-\lambda}}\big(e^{k\lambda} - 1\big)<br />
$$<br />
for small \(\lambda\) the denominator of the first part of the equation can be approximated as \(\frac{1}{\lambda}\) yielding<br />
$$<br />
y_{n} = \frac{1}{\lambda}\big(e^{k\lambda} - 1\big)<br />
$$<br />
<br />
Note, if you plug \(k=6\) into the above equation you get \(\approx 7\) hours whereas for \(k=5\) you get \(\approx 2.5\) hours. Due to the exponential connection between \(y_{n}\) and \(k\) the values for \(y_{n}\) are super sensitive to changes in \(k\).<br />
<br />
<div class="separator" style="clear: both; text-align: center;"></div>If you are looking to buy some books in probability <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html#.Uu3RfBVx05k" target="_blank">here</a> are some of the best books to learn the art of ProbabilityUnknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-8198767006557871072014-02-11T08:54:00.002-08:002016-03-08T07:08:43.519-08:00The Best Books for Time Series Analysis<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table>If you are looking to learn time series analysis, the following are some of the best books in time series analysis.<br />
<br />
<a href="http://www.amazon.com/gp/product/0387886974/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0387886974&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introductory Time Series with R (Use R!)</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0387886974" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
This is good book to get one started on time series. A nice aspect of this book is that it has examples in R and some of the data is part of standard R packages which makes good introductory material for learning the R language too. That said this is not exactly a graduate level book, and some of the data links in the book may not be valid.<br />
<br />
<a href="http://www.amazon.com/gp/product/0691010188/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0691010188&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Econometrics</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0691010188" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
A great book if you are in an economics stream or want to get into it. The nice thing in the book is it tries to bring out a oneness in all the methods used. Econ majors need to be up-to speed on the grounding mathematics for time series analysis to use this book. Outside of those prerequisites, this is one of the best books on econometrics and time series analysis.<br />
<br />
<a href="http://www.amazon.com/gp/product/0387310738/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0387310738&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Pattern Recognition and Machine Learning (Information Science and Statistics)</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0387310738" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
This is excellent book to own for scientists and engineers wanting to use time series methods in machine learning, forecasting and regression. Great charts and fairly readable text.<br />
<br />
<a href="http://www.amazon.com/gp/product/1441903194/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=1441903194&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Time Series: Theory and Methods (Springer Series in Statistics)</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=1441903194" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
A good book which covers a lot of theoretical aspects but with little practical applications covered. It comes with software so it doesn't really support open source alternatives like R/Python. This is all about a rigorous treatment to Time series analysis (as is the case with most Springer Series). Good for graduate students and academics.<br />
<br />
<a href="http://www.amazon.com/gp/product/0691042896/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0691042896&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Time Series Analysis</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0691042896" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
An ideal book for graduate students and it is fairly comprehensive. Lots of essential approaches are covered in this text. Typical ones include Bayesian approaches, Spectral Analysis and the newer vector auto regression. Strongly recommended for graduate students. The book does not cover real world data sets and applications in enough detail.<br />
<br />
<a href="http://www.amazon.com/gp/product/0470540648/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0470540648&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Time Series Analysis and Forecasting by Example (Wiley Series in Probability and Statistics)</a><br />
A good book to get an introduction to time series analysis. It stresses more on the signal processing aspects too like auto regressive models<img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0470540648" height="1" style="border: none !important; margin: 0px !important;" width="1" />. A drawback is the book requires software and does not use open source, likewise there aren't answers to the questions posted. All said a good book to own but do not forget the caveats.<br />
<br />
<script type="text/javascript">
amzn_assoc_placement = "adunit0";
amzn_assoc_enable_interest_ads = "true";
amzn_assoc_tracking_id = "bayesianinfer-20";
amzn_assoc_ad_mode = "auto";
amzn_assoc_ad_type = "smart";
amzn_assoc_marketplace = "amazon";
amzn_assoc_region = "US";
amzn_assoc_linkid = "35ac8aba00e4405c49345ffd6caa4074";
amzn_assoc_emphasize_categories = "2619525011,1000,15684181,2335752011,172282,228013";
amzn_assoc_fallback_mode = {"type":"search","value":"probability"};
amzn_assoc_default_category = "Collectibles";
</script><br />
<script src="//z-na.amazon-adsystem.com/widgets/onejs?MarketPlace=US"></script><br />
<br />
<br />
<br />
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-26329657622137856272014-02-02T07:03:00.001-08:002015-06-30T07:53:16.163-07:00Two Quick Puzzles<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table>The following are two puzzles which look tough at first but have quick and really elegant solutions.<br />
<br />
Q1: Ants on a wire:<br />
A large number of ants are on a wire of length \(L\). All ants start moving randomly, either right or left with a fixed velocity \(V\). If they collide they turn around and move in the opposite direction. Ants at the ends of the wire fall off. What is the time taken for all ants to fall off the wire?<br />
<br />
Q2: The Unruly Passenger:<br />
Several passengers are in a queue to board a plane. The first passenger in the queue is an unruly one and chooses a seat at random. Subsequent passengers take their allotted seat if it is unoccupied or pick a seat at random if it is occupied. What is the probability that the last passenger gets to sit on his allotted seat?<br />
<a href="http://www.amazon.com/gp/product/0470392223/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0470392223&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Statistics: A good book to learn statistics</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0470392223" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
A1: This seemingly complex problem has an elegantly simple solution. The fact that they collide and turn around is the same as if they walked through each other! See figure below<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://www.amazon.com/gp/product/0495391328/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0495391328&linkCode=as2&tag=bayesianinfer-1-20" imageanchor="1" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhvSGDP8Xv3raRERO0yNOmxZQjuhyphenhyphenM17cO5lHOUhsPm7PKY4swhH7wUZrLGxQRJCOTvCHSiFua77AH57PFz5nlcUxb8OH8vZy_8CMyxH0z5e9FM5jnrixkYHX5h_4NcAcW_7e5Kp_a7Nio/s1600/diagram18.png" height="480" width="640" /></a></div><br />
<br />
Once this is insight sinks in, the average time taken for all ants to fall off the wire can be easily calculated. It is the same as the time an ant takes to move from one end of the wire to the other end. This works out to \(\frac{L}{V}\).<br />
<br />
<a href="http://www.amazon.com/gp/product/0321356683/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0321356683&linkCode=as2&tag=bayesianinfer-1-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Effective Java (2nd Edition)</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-1-20&l=as2&o=1&a=0321356683" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
A2: You absolutely do not want to consider the various ways a large number of passengers can fill up an equally large number of seats. Bear in mind that the only unruly passenger is the first one, and what we want to know is the probability that the last passenger gets to sit on his seat. The last passenger will face exactly two scenarios, either he gets his seat or not. He will get his seat if the first passenger picks his allotted seat which happens with a probability \(\frac{1}{2}\)<br />
<br />
If you are looking to buy some books in probability <a href="http://bayesianthink.blogspot.com/2012/12/the-best-books-to-learn-probability.html#.Uu3RfBVx05k" target="_blank">here</a> are some of the best books to learn the art of ProbabilityUnknownnoreply@blogger.com4tag:blogger.com,1999:blog-3824394956672712858.post-53356617026855116072014-01-24T07:15:00.000-08:002015-06-30T07:53:27.329-07:00Three Random Numbers<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table><br />
Q: You play a game with a friend where he chooses two random numbers between 0 and 1. Next you choose a random number between 0 and 1. If your number falls between the prior two numbers you win. What is the probability that you would win?<br />
<br />
A: Consider the number line between 0 and 1 shown in figure below<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://www.amazon.com/gp/product/0495391328/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0495391328&linkCode=as2&tag=bayesianinfer-20" imageanchor="1" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgRtoWuDLfB9CU_E5LEvVMB4A0JN8q9Ai9kZ7uzT24y6iRFbDekDEIZkRJOHOMLwnS754faSQBQYFfRx6_B9gBZKKHy59SRKRgio6OF2qn-RaMwMsU0Jrf-rHwcObSxWQ-WqWhIVFMCRmA/s1600/image2.png" height="300" width="400" /></a></div><br />
<br />
Let \(x\) and \(y\) be the two numbers chosen. The probability of a win, i.e. choosing a number in the range between the two chosen numbers can be estimated as \(\frac{|y-x|}{1}\). Note, we have chosen the modulus operation because \(x\) could be greater than \(y\) or vice versa. The feasible region of numbers to be chosen to win, is the ratio of the absolute difference between \(x\) and \(y\) divided by the total possible range, which is 1. In order to estimate the probability that a third chosen number will lie between the two we integrate out (a double integral) between the ranges of \([0,1]\). This is estimated as<br />
$$<br />
P(\text{win}) = \int_{0}^{1}\int_{0}^{1}|y - x| dx dy<br />
$$<br />
To evaluate the above integral, we split the inner integral as follows<br />
$$<br />
P(\text{win}) = \int_{0}^{1}\Big[\int_{0}^{y}(y - x)dx + \int_{y}^{1}(x-y)dx\Big]dy <br />
$$<br />
The inner integral evaluates to \(y^2 - y +\frac{1}{2}\) which on further integration between the ranges of \([0,1]\) yields<br />
$$<br />
P(\text{win}) = [\frac{y^3}{3} - \frac{y^2}{2} + \frac{y}{2}]_{0}^{1} = \frac{1}{3} <br />
$$ <br />
which is the sought probability. <br />
<br />
If you are looking to buy some books in probability here are some of the best books to learn the art of Probability<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0486653552/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0486653552&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics)</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0486653552" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0262033844/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0262033844&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Algorithms</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0262033844" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
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<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/039504636X/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=039504636X&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Probability Theory</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=039504636X" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
Overall an excellent book to learn probability, well recommended for undergrads and graduate students<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0471257087/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0471257087&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd Edition</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0471257087" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
This is a two volume book and the first volume is what will likely interest a beginner because it covers discrete probability. The book tends to treat probability as a theory on its own<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0780310519/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0780310519&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">The Probability Tutoring Book: An Intuitive Course for Engineers and Scientists (and Everyone Else!)</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0780310519" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
A good book for graduate level classes: has some practice problems in them which is a good thing. But that doesn't make this book any less of buy for the beginner.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/188652923X/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=188652923X&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Probability, 2nd Edition</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=188652923X" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
A good book to own. Does not require prior knowledge of other areas, but the book is a bit low on worked out examples.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0201775786/ref=as_li_ss_tl?ie=UTF8&tag=bayesianinfer-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=0201775786" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Bundle of Algorithms in Java, Third Edition, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition) (Pts. 1-5)</a></span><img alt="" border="0" class="gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0201775786" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
An excellent resource (students, engineers and even entrepreneurs) if you are looking for some code that you can take and implement directly on the job<br />
<br />
<a href="http://www.amazon.com/gp/product/0521701724/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0521701724&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Understanding Probability: Chance Rules in Everyday Life</a><img alt="" border="0" class="nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0521701724" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
This is a great book to own. The second half of the book may require some knowledge of calculus. It appears to be the right mix for someone who wants to learn but doesn't want to be scared with the "lemmas"<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0123748569/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0123748569&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Data Mining: Practical Machine Learning Tools and Techniques, Third Edition (The Morgan Kaufmann Series in Data Management Systems)</a></span><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/1446200469/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=1446200469&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Discovering Statistics Using R</a> </span><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0121741516/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0121741516&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">A Course in Probability Theory, Third Edition</a><img alt="" border="0" class="pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0121741516" height="1" style="border: none !important; margin: 0px !important;" width="1" /></span><br />
Covered in this book are the central limit theorem and other graduate topics in probability. You will need to brush up on some mathematics before you dive in but most of that can be done online<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0321500466/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0321500466&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Probability and Statistics (4th Edition)</a><img alt="" border="0" class="pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0321500466" height="1" style="border: none !important; margin: 0px !important;" width="1" /></span>This book has been yellow-flagged with some issues: including sequencing of content that could be an issue. But otherwise its goodUnknownnoreply@blogger.com1tag:blogger.com,1999:blog-3824394956672712858.post-26067062324212430142014-01-06T08:15:00.000-08:002015-06-30T07:53:39.323-07:00The Three Magical Boxes<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg orwtcjqbiufyemylptjs" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table><br />
Q: You are playing a game wherein you are presented 3 magical boxes. Each box has a set probability of delivering a gold coin when you open it. On a single attempt, you can take the gold coin and close the box. In the next attempt you are free to either open the same box again or pick another box. You have a 100 attempts to open the boxes. You do not know what the win probability is for each of the boxes. What would be a strategy to maximize your returns?<br />
<br />
<a href="http://www.amazon.com/gp/product/0262018020/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0262018020&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Machine Learning: A Probabilistic Perspective (Adaptive Computation and Machine Learning series)</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0262018020" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
A: Problems of this type fall into a category of algorithms called "multi armed bandits". The name has its origin in casino slot machines wherein a bandit is trying to maximize his returns by pulling different arms of a slot machine by using several "arms". The dilemma he faces is similar to the game described above. Notice, the problem is a bit different from a typical estimation exercise. You could simply split your 100 attempts into 3 blocks of 33,33 & 34 for each of the boxes. But this would not be optimal. Assume that one of the boxes had just a \(1\%\) probability of yielding a golden coin. Even as you probe and explore that box you know intuitively that you have spent a fair amount of attempts to simply reinforce something you already knew. You need a strategy that adjusts according to new information that you gain from each attempt. Something that gradually transitions away from a box that yields less to a box that yields more.<br />
<br />
Assume at the beginning of the game you do not know anything about the yield probabilities. Assign a prior set of values of \(\big[\frac{1}{2}, \frac{1}{2},\frac{1}{2}\big]\). Simultaneously maintain a set of likelihoods using which you will decide which box to sample next. Initially all three values are set to 1s \(\{p_1 = 1,p_2 = 1,p_3 = 1\}\). First open the boxes in succession and use up \(n\) attempts per box. If you denote the number of successes for each box as \(\{s_1,s_2,s_3\}\), then you could update the posterior distribution of your belief in what box yields as follows<br />
$$<br />
p_1 = \frac{1 + s_1}{2 + n} \\<br />
p_2 = \frac{1 + s_2}{2 + n} \\<br />
p_3 = \frac{1 + s_3}{2 + n}<br />
$$<br />
Think of this as your initializing phase. Once you initialize your estimates, subsequent choice of boxes should be based on a re-normalized probability vector derived from \(p_1,p_2,p_3\). What this means is that the probability you would pick a box is computed as follows<br />
$$<br />
P(\text{pick box 1}) = \frac{p_1}{p_1 + p_2 + p_3} \\<br />
P(\text{pick box 2}) = \frac{p_2}{p_1 + p_2 + p_3} \\<br />
P(\text{pick box 3}) = \frac{p_3}{p_1 + p_2 + p_3}<br />
$$<br />
What ends up happening here is that you will pick the box which has the highest probability of winning based on information gleaned up to a certain point. Another benefit of this approach is you are learning in real time. If a certain box isn't yielding as much as another you don't discard opening that box all together, instead you progressively sample it less often. <br />
<br />
If you are looking to buy some books in probability here are some of the best books to own<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0486653552/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0486653552&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics)</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0486653552" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0262033844/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0262033844&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Algorithms</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0262033844" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
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<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/039504636X/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=039504636X&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Probability Theory</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=039504636X" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
Overall an excellent book to learn probability, well recommended for undergrads and graduate students<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0471257087/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0471257087&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd Edition</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0471257087" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
This is a two volume book and the first volume is what will likely interest a beginner because it covers discrete probability. The book tends to treat probability as a theory on its own<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0780310519/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0780310519&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">The Probability Tutoring Book: An Intuitive Course for Engineers and Scientists (and Everyone Else!)</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0780310519" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
A good book for graduate level classes: has some practice problems in them which is a good thing. But that doesn't make this book any less of buy for the beginner.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/188652923X/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=188652923X&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Probability, 2nd Edition</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=188652923X" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
A good book to own. Does not require prior knowledge of other areas, but the book is a bit low on worked out examples.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0201775786/ref=as_li_ss_tl?ie=UTF8&tag=bayesianinfer-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=0201775786" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Bundle of Algorithms in Java, Third Edition, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition) (Pts. 1-5)</a></span><img alt="" border="0" class="gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0201775786" height="1" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
An excellent resource (students, engineers and even entrepreneurs) if you are looking for some code that you can take and implement directly on the job<br />
<br />
<a href="http://www.amazon.com/gp/product/0521701724/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0521701724&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Understanding Probability: Chance Rules in Everyday Life</a><img alt="" border="0" class="nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0521701724" height="1" style="border: none !important; margin: 0px !important;" width="1" /><br />
This is a great book to own. The second half of the book may require some knowledge of calculus. It appears to be the right mix for someone who wants to learn but doesn't want to be scared with the "lemmas"<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0123748569/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0123748569&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Data Mining: Practical Machine Learning Tools and Techniques, Third Edition (The Morgan Kaufmann Series in Data Management Systems)</a></span><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/1446200469/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=1446200469&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Discovering Statistics Using R</a> </span><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0121741516/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0121741516&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">A Course in Probability Theory, Third Edition</a><img alt="" border="0" class="pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0121741516" height="1" style="border: none !important; margin: 0px !important;" width="1" /></span><br />
Covered in this book are the central limit theorem and other graduate topics in probability. You will need to brush up on some mathematics before you dive in but most of that can be done online<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0321500466/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0321500466&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Probability and Statistics (4th Edition)</a><img alt="" border="0" class="pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0321500466" height="1" style="border: none !important; margin: 0px !important;" width="1" /></span>This book has been yellow-flagged with some issues: including sequencing of content that could be an issue. But otherwise its goodUnknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-7146479713517420372013-12-22T07:50:00.000-08:002015-06-30T07:54:00.661-07:00Santa's Dice Game<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg orwtcjqbiufyemylptjs" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table><br />
Q: Santa offers you to play a game of dice. You get to roll a dice six times. You can stop rolling whenever you wish and you get the dollar amount shown on that roll. What is an optimal strategy to maximize your payoff?<br />
<br />
<a href="http://www.amazon.com/gp/product/0321500466/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0321500466&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Probability and Statistics (4th Edition)</a><img src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0321500466" width="1" height="1" border="0" alt="" style="border:none !important; margin:0px !important;" /><br />
<br />
<br />
A: Let us take a moment and think through this. At each point in the sequence of rolls you make, you have a decision to make. Do you keep rolling or do you stop and walk away with what is being "offered" to you? You also need to bear in mind that if you keep pushing your luck you will reach a point (the 6th roll) where you would have to be content with whatever comes out for the last roll. So lets start with the simple case of what the expected payoff is for the last roll. Lets call this \(E_{6}\). To compute it, simply take the payoff multiplied by the respective probability.<br />
$$<br />
E_{6} = \frac{1 + 2 + 3 + 4 + 5 + 6}{6} = \frac{7}{2} = 3.5<br />
$$<br />
The general strategy to be followed is to check what the expected pay off is for the next roll and accept nothing less than that. Working backwards, lets consider each of the rolls starting with the 5th roll.<br />
<br />
<b>Roll 5: </b><br />
You know that on 6th roll you get an expected payoff of 3.5. You should accept anything greater than 3.5, which means you stop rolling if you get a 4,5 or 6, put in other words anything greater than 4. The expected payoff is<br />
$$<br />
\frac{4 + 5 + 6}{6} + \frac{7}{2}\times\frac{1}{2} = \frac{17}{4}<br />
$$ <br />
<b>Roll 4:</b><br />
Looking ahead you find the expected payoff for the 5th roll is \(\frac{17}{4} = 4.25\). You stop if you get a 5 or greater for this roll. The expected payoff would be<br />
$$<br />
\frac{5+6}{6} + \frac{17}{4}\times\frac{4}{6} = \frac{14}{3}<br />
$$ <br />
<br />
<b>Roll 3:</b><br />
The expected payoff from roll 4 above is \(\frac{14}{3} = 4.66\) which means you stop if you get a 5 or above. The expected payoff for this roll is<br />
$$<br />
\frac{5 + 6}{6} + \frac{14}{3}\times\frac{4}{6} = \frac{89}{18}<br />
$$<br />
<br />
<b>Roll 2:</b><br />
The expected payoff from roll 3 above is \(\frac{89}{18}=4.94\) implying accept and stop if roll gives 5 or 6. The expected payoff for this roll is<br />
$$<br />
\frac{5 + 6}{6} + \frac{89}{18}\times\frac{4}{6} = 5.12<br />
$$<br />
<br />
<b>Roll 1:</b><br />
Being the first roll, your expected payoff from any subsequent rolls is 5.12. So you should accept nothing short of a 6 from the first roll.<br />
<br />
The optimal strategy would then be to stop at each of the first five rolls (when you have the option to stop) if you get 6,5,5,5,4 respectively. An interesting takeaway here is the expected gains from following this strategy can be computed as<br />
$$<br />
\frac{1}{6}\times 6 + \frac{5}{6}\times 5.12 = 5.26<br />
$$<br />
which is quite high for a seemingly random game!<br />
<br />
If you are looking to buy some books in probability here are some of the best books to own<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0486653552/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0486653552&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics)</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0486653552" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0262033844/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0262033844&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Algorithms</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0262033844" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
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<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/039504636X/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=039504636X&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Probability Theory</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=039504636X" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
Overall an excellent book to learn probability, well recommended for undergrads and graduate students<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0471257087/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0471257087&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd Edition</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0471257087" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
This is a two volume book and the first volume is what will likely interest a beginner because it covers discrete probability. The book tends to treat probability as a theory on its own<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0780310519/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0780310519&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">The Probability Tutoring Book: An Intuitive Course for Engineers and Scientists (and Everyone Else!)</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0780310519" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
A good book for graduate level classes: has some practice problems in them which is a good thing. But that doesn't make this book any less of buy for the beginner.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/188652923X/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=188652923X&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Probability, 2nd Edition</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=188652923X" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
A good book to own. Does not require prior knowledge of other areas, but the book is a bit low on worked out examples.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0201775786/ref=as_li_ss_tl?ie=UTF8&tag=bayesianinfer-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=0201775786" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Bundle of Algorithms in Java, Third Edition, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition) (Pts. 1-5)</a></span><img alt="" border="0" class="gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0201775786" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
An excellent resource (students, engineers and even entrepreneurs) if you are looking for some code that you can take and implement directly on the job<br />
<br />
<a href="http://www.amazon.com/gp/product/0521701724/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0521701724&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Understanding Probability: Chance Rules in Everyday Life</a><img alt="" border="0" class="nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0521701724" style="border: none !important; margin: 0px !important;" width="1" /><br />
This is a great book to own. The second half of the book may require some knowledge of calculus. It appears to be the right mix for someone who wants to learn but doesn't want to be scared with the "lemmas"<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0123748569/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0123748569&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Data Mining: Practical Machine Learning Tools and Techniques, Third Edition (The Morgan Kaufmann Series in Data Management Systems)</a></span><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/1446200469/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=1446200469&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Discovering Statistics Using R</a> </span><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0121741516/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0121741516&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">A Course in Probability Theory, Third Edition</a><img alt="" border="0" class="pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0121741516" style="border: none !important; margin: 0px !important;" width="1" /></span><br />
Covered in this book are the central limit theorem and other graduate topics in probability. You will need to brush up on some mathematics before you dive in but most of that can be done online<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0321500466/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0321500466&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Probability and Statistics (4th Edition)</a><img alt="" border="0" class="pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc srwdnvpucprahjdzkapf eckcjvjxiibaulnvingr orwtcjqbiufyemylptjs" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0321500466" style="border: none !important; margin: 0px !important;" width="1" /></span>This book has been yellow-flagged with some issues: including sequencing of content that could be an issue. But otherwise its goodUnknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-74775179034852176632013-12-11T21:37:00.000-08:002015-06-30T07:54:13.715-07:00A Box of Apples and Oranges<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nzastonxiymgukeaafez" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table><br />
Q: A box contains 6 apples and 5 oranges. You know the number of apples are 6. You pick them out one at a time. What is the probability that the box will be empty by the time you have all 6 apples out?<br />
<br />
<a href="http://www.amazon.com/gp/product/B001FVRUFQ/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=B001FVRUFQ&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">A Perfect Mathematical Christmas Gift</a><img alt="" border="0" class="nzastonxiymgukeaafez" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=B001FVRUFQ" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
A: It is tempting to say that the answer is \(50\%\), but its not, as explained further below. Let us start with the number of ways to pull all 11 out. Since you know that there are six apples, you would keep drawing until you see all six apples. The six apples can come out in any order. So there are \(\binom{11}{6}\) ways to do this.The number of favorable cases can be computed by making the following observation. If the box has to be empty when the last apple is drawn, then the finishing of the draws must end with 1, 2, 3, 4, 5 or 6 apples. These are the only scenarios. It can never end in an orange being drawn. Lets first consider the case when the last fruit drawn is an apple and the one prior is an orange. That's two down from the lot with one being an apple and the other being an orange. The number of ways this can happen is \(\binom{9}{5}\). A similar reasoning applies when the last three fruits drawn are one orange and two apples in a row. The number of ways this can happen is \(\binom{8}{4}\) and so on. Thus, the probability is the required sum of scenarios divided by the total number of ways<br />
$$<br />
P(\text{box is empty}) = \frac{\binom{9}{5} + \binom{8}{4} + \binom{7}{3} + \binom{6}{2} + \binom{5}{1} + 1 }{ \binom{11}{6}} <br />
$$<br />
Note, the final one is added to the numerator to factor the case when all six apples are drawn at the very in end in a row. The above simplifies to<br />
$$<br />
P(\text{box is empty}) = \frac{252}{462} = 54.54\%<br />
$$<br />
If you are looking to buy some books in probability here are some of the best books to learn the art of Probability<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0486653552/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0486653552&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics)</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc nzastonxiymgukeaafez" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0486653552" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0262033844/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0262033844&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Algorithms</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc nzastonxiymgukeaafez" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0262033844" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
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<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/039504636X/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=039504636X&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Probability Theory</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc nzastonxiymgukeaafez" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=039504636X" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
Overall an excellent book to learn probability, well recommended for undergrads and graduate students<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0471257087/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0471257087&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd Edition</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc nzastonxiymgukeaafez" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0471257087" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
This is a two volume book and the first volume is what will likely interest a beginner because it covers discrete probability. The book tends to treat probability as a theory on its own<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0780310519/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0780310519&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">The Probability Tutoring Book: An Intuitive Course for Engineers and Scientists (and Everyone Else!)</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc nzastonxiymgukeaafez" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0780310519" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
A good book for graduate level classes: has some practice problems in them which is a good thing. But that doesn't make this book any less of buy for the beginner.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/188652923X/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=188652923X&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Probability, 2nd Edition</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc nzastonxiymgukeaafez" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=188652923X" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
A good book to own. Does not require prior knowledge of other areas, but the book is a bit low on worked out examples.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0201775786/ref=as_li_ss_tl?ie=UTF8&tag=bayesianinfer-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=0201775786" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Bundle of Algorithms in Java, Third Edition, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition) (Pts. 1-5)</a></span><img alt="" border="0" class="gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc nzastonxiymgukeaafez" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0201775786" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
An excellent resource (students, engineers and even entrepreneurs) if you are looking for some code that you can take and implement directly on the job<br />
<br />
<a href="http://www.amazon.com/gp/product/0521701724/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0521701724&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Understanding Probability: Chance Rules in Everyday Life</a><img alt="" border="0" class="nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc nzastonxiymgukeaafez" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0521701724" style="border: none !important; margin: 0px !important;" width="1" /><br />
This is a great book to own. The second half of the book may require some knowledge of calculus. It appears to be the right mix for someone who wants to learn but doesn't want to be scared with the "lemmas"<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0123748569/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0123748569&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Data Mining: Practical Machine Learning Tools and Techniques, Third Edition (The Morgan Kaufmann Series in Data Management Systems)</a></span><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/1446200469/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=1446200469&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Discovering Statistics Using R</a> </span><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0121741516/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0121741516&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">A Course in Probability Theory, Third Edition</a><img alt="" border="0" class="pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc nzastonxiymgukeaafez" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0121741516" style="border: none !important; margin: 0px !important;" width="1" /></span><br />
Covered in this book are the central limit theorem and other graduate topics in probability. You will need to brush up on some mathematics before you dive in but most of that can be done online<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0321500466/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0321500466&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Probability and Statistics (4th Edition)</a><img alt="" border="0" class="pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc nzastonxiymgukeaafez" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0321500466" style="border: none !important; margin: 0px !important;" width="1" /></span>This book has been yellow-flagged with some issues: including sequencing of content that could be an issue. But otherwise its goodUnknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-53284262265049815942013-12-09T12:53:00.000-08:002015-06-30T07:55:02.228-07:00The Numbers on a Dice<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nzastonxiymgukeaafez" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table><br />
Q: A die is rolled and the numbers on all the visible faces is multiplied together \(=S\). How would you choose a highest number such that it is guaranteed to divide the product. <br />
<br />
A: The puzzle rests on a simple fact of prime factorization. Every number can be expressed as a product of prime numbers. For the given example, assume the face that is not visible is 1. The product of the remainder of numbers is \(6 \times 5\times\ldots \times 2\) or equivalently \(6!\). If the face that is invisible is 2, the number \(S\) is \(\frac{6!}{2}\), if it is 3 the number \(S\) is \(\frac{6!}{3}\) and so on. The number \(6!\) can be expressed as prime numbers as \(2^{4}\times3^{2}\times 5\). Let us enumerate the cases for each of the faces that is invisible, the product \(S\) expressed in terms of prime numbers are as follows<br />
<ol><li>\(2^{4}\times3^{2}\times5\)</li>
<li>\(2^{3}\times3^{2}\times5\)</li>
<li>\(2^{4}\times3^{1}\times5\) </li>
<li>\(2^{2}\times3^{2}\times5\)</li>
<li>\(2^{4}\times3^{2}\) </li>
<li>\(2^{3}\times3^{1}\times5\)</li>
</ol>Notice, the solution to our problem is the lowest exponent of each of the prime factors. This yields \(2^{2}\times3^{1}\times5^{0} = 12\).<br />
<br />
Three good books to own to learn number theory,<br />
<br />
<a href="http://www.amazon.com/gp/product/0470424133/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0470424133&linkCode=as2&tag=bayesianinfer-20">Number Theory: A Lively Introduction with Proofs, Applications, and Stories</a><img alt="" border="0" class="nzastonxiymgukeaafez" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0470424133" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
<a href="http://www.amazon.com/gp/product/0199219869/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0199219869&linkCode=as2&tag=bayesianinfer-20">An Introduction to the Theory of Numbers</a><img alt="" border="0" class="nzastonxiymgukeaafez" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0199219869" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
<a href="http://www.amazon.com/gp/product/3540761977/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=3540761977&linkCode=as2&tag=bayesianinfer-20">Elementary Number Theory (Springer Undergraduate Mathematics Series)</a><img alt="" border="0" class="nzastonxiymgukeaafez" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=3540761977" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
<a href="http://www.amazon.com/gp/product/B001FVRUFQ/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=B001FVRUFQ&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">A Perfect Mathematical Christmas Gift</a><img alt="" border="0" class="nzastonxiymgukeaafez" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=B001FVRUFQ" style="border: none !important; margin: 0px !important;" width="1" />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-1579561446120603372013-12-05T08:40:00.000-08:002015-06-30T07:55:27.709-07:00A Cow, A Monkey and a Tree<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table><br />
Q: A Cow is tethered to a tree by a rope that has half the length of the circumference of the tree's stump. A monkey with a stone in hand jumps onto the tree and starts hopping around the tree's branches which covers a circular area of radius five times that of the stump. This causes the cow to run about at random and monkey drops the stone at random. What is the probability that the cow would get hit?<br />
<br />
<a href="http://www.amazon.com/gp/product/B001FVRUFQ/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=B001FVRUFQ&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">A Perfect Mathematical Christmas Gift</a><img src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=B001FVRUFQ" width="1" height="1" border="0" alt="" style="border:none !important; margin:0px !important;" /><br />
<br />
A: The situation can be characterized by the figure shown below (not to scale)<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://www.amazon.com/gp/product/0495391328/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0495391328&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEifeLTCpPHkQ03FoFSAHlLpyczYpFFfN59JAP1UFAT-Ro_otlUMhT2MCQoYEgWIWs0GOcjH6MPsghHAehN3MZEZY6nXYDE-Z-qjyVNU3SpjkARpaHhPnz36Ko0S8bxHuz8lPnMdACa1p50/s400/diagram15.png" width="400" /></a></div><br />
The monkey can be anywhere in the light shaded orange area before it drops the stone (this of course assumes that the stump has no terrace area). The cow, can sweep a spiral as shown in the figure below along either lines (poorly drawn).<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://www.amazon.com/gp/product/0495391328/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0495391328&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgRsQi-QZ6Qawpx0cZRV0d7yTKFyrwDi1BQ5zYQoFNP6m1elp9fWCE98Q10xENxYdAaiANQHs3NfjB5OKSofS0TFSzr7RtpYZwTF6jaCF2W9m4YIsYkTO1JyYPiIFA2Rv4xKq1u8ZyMiok/s400/diagram16.png" width="400" /></a></div>To start, lets first compute the area the cow can sweep. Assume the cow moves a bit to the left, the rope would wind up along the stump of the tree. To further formalize this assume it sweeps out an angle \(\theta\) at the center as shown figure below.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://www.amazon.com/gp/product/0495391328/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0495391328&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjrj-wUkER7nn4FVju0R-iSGR_oLPHHURE7ASRbAQo6SUWjJF134wnHlrGkYK_vZAI1xBpIQHasuQheQrAtYcZEDwwxY_Gsur0DTpH2Iw_5GBI0y5T4vZlK5ZdvcwMGcpsPOIHqW5NaXfA/s400/diagram17.png" width="400" /></a></div>In the figure if the cow's rope winds up by a length AB subtending an angle \(\theta\) at the center C, and if the cow moves from D to E an incremental angle of \(d\theta \) is subtended at the centre. The length of the rope is now decreased from \(\pi r\) to \(\pi r - r\theta\). The length of DE can be computed as<br />
$$<br />
(\pi r - r\theta )d\theta<br />
$$<br />
The incremental area of triangle ADE is \(\frac{1}{2}\times DE \times AD\) which works out as<br />
$$<br />
dA = \frac{1}{2}(\pi r - r \theta)^{2}d\theta<br />
$$<br />
To compute the total area, we can integrate out with \(\theta\) running from \([0,\pi]\) and as the area is symmetric, we multiply by 2 <br />
$$<br />
A =2 \times \int_{0}^{\pi}\frac{1}{2}r^{2}(\pi - \theta)^{2}d\theta<br />
$$<br />
The above integral simplifies to<br />
$$<br />
A = \frac{r^{2}\pi^{3}}{3}<br />
$$<br />
The total area the monkey can drop the stone is easy to compute as<br />
$$<br />
A_{total} = \pi (5r)^{2} - \pi r^{2} = 24\pi r^{2}<br />
$$<br />
The sought area and probability is simply the ratio of the two areas \(\frac{A}{A_{total}} = \frac{\pi^{3}}{24\times 3} \approx 43\%\)<br />
<br />
Some of the best books to own to learn the art of probability<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0486653552/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0486653552&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics)</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0486653552" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0262033844/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0262033844&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Algorithms</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0262033844" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
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<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/039504636X/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=039504636X&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Probability Theory</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=039504636X" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
Overall an excellent book to learn probability, well recommended for undergrads and graduate students<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0471257087/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0471257087&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd Edition</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0471257087" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
This is a two volume book and the first volume is what will likely interest a beginner because it covers discrete probability. The book tends to treat probability as a theory on its own<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0780310519/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0780310519&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">The Probability Tutoring Book: An Intuitive Course for Engineers and Scientists (and Everyone Else!)</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0780310519" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
A good book for graduate level classes: has some practice problems in them which is a good thing. But that doesn't make this book any less of buy for the beginner.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/188652923X/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=188652923X&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Probability, 2nd Edition</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=188652923X" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
A good book to own. Does not require prior knowledge of other areas, but the book is a bit low on worked out examples.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0201775786/ref=as_li_ss_tl?ie=UTF8&tag=bayesianinfer-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=0201775786" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Bundle of Algorithms in Java, Third Edition, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition) (Pts. 1-5)</a></span><img alt="" border="0" class="gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0201775786" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
An excellent resource (students, engineers and even entrepreneurs) if you are looking for some code that you can take and implement directly on the job<br />
<br />
<a href="http://www.amazon.com/gp/product/0521701724/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0521701724&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Understanding Probability: Chance Rules in Everyday Life</a><img alt="" border="0" class="nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0521701724" style="border: none !important; margin: 0px !important;" width="1" /><br />
This is a great book to own. The second half of the book may require some knowledge of calculus. It appears to be the right mix for someone who wants to learn but doesn't want to be scared with the "lemmas"<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0123748569/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0123748569&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Data Mining: Practical Machine Learning Tools and Techniques, Third Edition (The Morgan Kaufmann Series in Data Management Systems)</a></span><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/1446200469/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=1446200469&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Discovering Statistics Using R</a> </span><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0121741516/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0121741516&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">A Course in Probability Theory, Third Edition</a><img alt="" border="0" class="pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0121741516" style="border: none !important; margin: 0px !important;" width="1" /></span><br />
Covered in this book are the central limit theorem and other graduate topics in probability. You will need to brush up on some mathematics before you dive in but most of that can be done online<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0321500466/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0321500466&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Probability and Statistics (4th Edition)</a><img alt="" border="0" class="pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0321500466" style="border: none !important; margin: 0px !important;" width="1" /></span>This book has been yellow-flagged with some issues: including sequencing of content that could be an issue. But otherwise its goodUnknownnoreply@blogger.com0tag:blogger.com,1999:blog-3824394956672712858.post-72012416220792815752013-11-28T08:44:00.001-08:002015-06-30T07:56:03.923-07:00The Sultan's Wine Bottles<script type="text/javascript" language="javascript" src="//c.amazon-adsystem.com/aax2/getads.js"></script><br />
<script type="text/javascript" language="javascript">
//<![CDATA[
aax_getad_mpb({
"slot_uuid":"7a68b0e5-c36f-428c-b295-c904d984ccd9"
});
//]]>
</script> <br />
<table border="0" cellpadding="1"><tbody>
<tr> <td><a class="twitter-follow-button" data-show-count="true" href="https://twitter.com/ProbabilityPuz">Follow @ProbabilityPuz</a><br />
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script> </td> <td><a href="http://www.reddit.com/submit" onclick="window.location = 'http://www.reddit.com/submit?url=' + encodeURIComponent(window.location); return false"> <img alt="submit to reddit" border="0" class="zlpbunarosdsszgrewwl jyoqqltwugeskcxifcjk qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg cqiemnhkmoosxdcmxrjc" src="http://www.reddit.com/static/spreddit7.gif" /> </a> </td> </tr>
</tbody></table><br />
Q: A Sultan has a 1000 bottles of wine. He needs to use them in 30 days time for a royal banquet. He knows that his enemies have poisoned exactly one bottle with a type of poison that takes effect in 29 days. He decides to use his soldiers to test which bottle is poisoned. Is there a strategy that minimizes the number of soldiers needed for the task?<br />
<br />
<a href="http://www.amazon.com/gp/product/0521592712/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0521592712&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Probability Theory: The Logic of Science</a><img alt="" border="0" class="cxusqthnwznhantdrfmq qcpknowctuobnxqivlfq mscpksmpxerehndvnedo disqfobbqltsingmoowg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0521592712" style="border: none !important; margin: 0px !important;" width="1" /><br />
<br />
A: The naive approach is to have one soldier per bottle. Every soldier gets a drop from each bottle and they wait for 29 days. The number of the soldier who gets affected on the 29th day shows which bottle is poisoned. However, this strategy is quite expensive in terms of the number of soldiers needed for the Sultan. A far more efficient strategy is the following.<br />
<ol><li>Label each bottle with a number.</li>
<li>Maintain a ledger which maps a number to each of the patterns 0000000000 -> 1, 0000000001 -> 2, 0000000010 -> 3, 0000000100 -> 4 and so on till you reach 1111111111 -> 1000. Note there are 10 places that can hold either 0s or 1s.</li>
<li>Assign each soldier to each of the 10 places.</li>
<li>For each bottle number, give a drop of the wine to each soldier with a number 1.</li>
</ol>What happens? On the 29th day, a certain combination of soldiers will be affected by the poison. Knowing that combination, the Sultan can trace back and find the exact bottle that contained the poison by looking up the ledger. This way the number of soldiers needed is minimized. Note, the problem solution can be extended to any number of bottles. By using the binary number encoding method the number of combinations needed can be ascertained by simply doing \(log_{2}{N}\) where \(N\) is the number of bottles.<br />
If you are looking to buy some books in probability here are some of the best books to learn the art of Probability<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0486653552/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0486653552&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics)</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0486653552" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0262033844/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0262033844&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Algorithms</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0262033844" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
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<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/039504636X/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=039504636X&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Probability Theory</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=039504636X" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
Overall an excellent book to learn probability, well recommended for undergrads and graduate students<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0471257087/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0471257087&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd Edition</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0471257087" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
This is a two volume book and the first volume is what will likely interest a beginner because it covers discrete probability. The book tends to treat probability as a theory on its own<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0780310519/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0780310519&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">The Probability Tutoring Book: An Intuitive Course for Engineers and Scientists (and Everyone Else!)</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0780310519" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
A good book for graduate level classes: has some practice problems in them which is a good thing. But that doesn't make this book any less of buy for the beginner.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/188652923X/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=188652923X&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Introduction to Probability, 2nd Edition</a></span><img alt="" border="0" class="oraisxkwsmxqoornwmlm gbzfwkxkptjlvgkladwy ovuizjyomyjoriadpkzj gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=188652923X" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
A good book to own. Does not require prior knowledge of other areas, but the book is a bit low on worked out examples.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0201775786/ref=as_li_ss_tl?ie=UTF8&tag=bayesianinfer-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=0201775786" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Bundle of Algorithms in Java, Third Edition, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition) (Pts. 1-5)</a></span><img alt="" border="0" class="gqfxvvtibbqtxxrsnvpv vovncpbreqcswuadwqcr kkjfluaharyeaiunvffx sazhqlktrntxpesgkxcx tofzjvplpoyhptpvxbic davcnqnbwbzhuuworgvv mikzufpelmhovlsnoznj lkrhfxysokesjyjtyfot pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://www.assoc-amazon.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0201775786" style="border: medium none ! important; margin: 0px ! important;" width="1" /><br />
An excellent resource (students, engineers and even entrepreneurs) if you are looking for some code that you can take and implement directly on the job<br />
<br />
<a href="http://www.amazon.com/gp/product/0521701724/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0521701724&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Understanding Probability: Chance Rules in Everyday Life</a><img alt="" border="0" class="nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0521701724" style="border: none !important; margin: 0px !important;" width="1" /><br />
This is a great book to own. The second half of the book may require some knowledge of calculus. It appears to be the right mix for someone who wants to learn but doesn't want to be scared with the "lemmas"<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0123748569/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0123748569&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Data Mining: Practical Machine Learning Tools and Techniques, Third Edition (The Morgan Kaufmann Series in Data Management Systems)</a></span><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/1446200469/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=1446200469&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Discovering Statistics Using R</a> </span><br />
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.<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0121741516/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0121741516&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">A Course in Probability Theory, Third Edition</a><img alt="" border="0" class="pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0121741516" style="border: none !important; margin: 0px !important;" width="1" /></span><br />
Covered in this book are the central limit theorem and other graduate topics in probability. You will need to brush up on some mathematics before you dive in but most of that can be done online<br />
<br />
<span style="font-size: small;"><a href="http://www.amazon.com/gp/product/0321500466/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0321500466&linkCode=as2&tag=bayesianinfer-20" onclick="_gaq.push(['_trackEvent', 'Affiliate Link', 'Amazon', 'Probability Books', 1, false]);">Probability and Statistics (4th Edition)</a><img alt="" border="0" class="pgcfjbtohselrobqrtag nrlwtfzkcfezyrxvkoxg djucguvsxgohyiovrwoc jyoqqltwugeskcxifcjk zephtniqirledkrhuuhf qfzvycqxlusjdxhyujug tdhanlmvpjdxwxsrsypg mgtduafqksnxafnjeztg nkelgfpogldyzjtmjdlf hkluvealkerngvlciiug yfyqyomcdibegdcylvox mteprfcqxjtfwhrucufk cqiemnhkmoosxdcmxrjc" height="1" src="http://ir-na.amazon-adsystem.com/e/ir?t=bayesianinfer-20&l=as2&o=1&a=0321500466" style="border: none !important; margin: 0px !important;" width="1" /></span>This book has been yellow-flagged with some issues: including sequencing of content that could be an issue. But otherwise its goodUnknownnoreply@blogger.com0