tag:blogger.com,1999:blog-13646297272485578442014-10-05T11:51:21.010+11:00The Mathematical BricoleurMathematics is not some austere and perfect edifice, to be scaled only by the bravest of climbers. Mathematics is a human activity, and humans come in many kinds. This is hopefully something for us tinkerers and dabblers. I aim to collect together little trinkets and tidbits as I find or create them, but ultimately, whatever appeals to me. This is a blog about <i>stuff that works</i>.GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-1364629727248557844.post-29976030397409295092010-01-10T16:48:00.007+11:002010-01-10T17:59:58.817+11:00Creating nomograms in RThis is actually a post-in-progress, but I am publishing it before it's ready so that people on the Nomography Discussion forum can come take a sneak preview. The post will probably be updated a couple of times.<br /><br />Below is a three-scale <a href="http://en.wikipedia.org/wiki/Nomogram">nomogram</a> I generated in R. Bitmap images (like this png) don't suit the text-at-an-angle of the <I>i</i>-scale, and the angled tick-marks, but it's good enough to give the idea - it looks better as a vector-image:<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://3.bp.blogspot.com/_y8B7MKebdC4/S0lqaDS_ayI/AAAAAAAAACI/L1JTH_RUoaA/s1600-h/dif2.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 400px;" src="http://3.bp.blogspot.com/_y8B7MKebdC4/S0lqaDS_ayI/AAAAAAAAACI/L1JTH_RUoaA/s400/dif2.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5424984221938576162" /></a>(Click to obtain a slightly larger image)<br /><br />Here's a simple function to draw nomogram scales. It's a few lines longer than when I wrote about it before (I added scale labels in). I don't expect anyone to care about the details of the code, but even without taking advantage of the special aspects of R, it's worth seeing that the entire code is quite compact, and fairly easy to generalize further.<br /><br /><pre><br />curvaxis <- function(x,y,v,axlab=" ",ltick=TRUE,axlt1=TRUE,thwid=.02){<br /> lines(x,y)<br /><br /> yscale <- diff(par("yaxp"))[1]<br /> xscale <- diff(par("xaxp"))[1]<br /> yxscale <- yscale/xscale<br /><br /># compute ticks<br /> n <- length(x)<br /> tdif <- function(x,n=length(x)) c(x[2]-x[1],x[3:n]-x[1:(n-2)],x[n]-x[n-1])<br /><br /> s <- atan(-tdif(x)/tdif(y)*yxscale)<br /> xd <- cos(s)*thwid*xscale # could do this without trig functions<br /> yd <- sin(s)*thwid*yscale<br /> xd <- ifelse(tdif(y)!=0,xd,0) <br /> yd <- ifelse(tdif(y)!=0,yd,thwid*yscale) # are we scaling right? some ticks look off<br /><br /> dmul <- ifelse(ltick,-1,1) <br /> xadj <- as.integer(ltick)<br /> yadj <- 0.5<br /><br /> lines(rbind(x,x+dmul*xd,rep(NA,n)),rbind(y,y+dmul*yd,rep(NA,n))) # draw tick-marks<br /> text(x+dmul*xd*1.5,y+dmul*yd*1.5,v,adj=c(xadj,yadj),cex=0.8,srt=180/pi*mean(s))# tick labels<br /> sg <- sign(y[2]-y[1])<br /> if(axlt1) { #cludgy - this part does the scale labels<br /> text(x[1]-2*sin(s[1])*thwid*xscale,y[1]-2*sg*cos(s[1])*thwid*yscale,axlab,cex=1.33,srt=0,crt=0)<br /> }<br /> else {<br /> text(x[n]+2*sin(s[n])*thwid*xscale,y[n]+2*sg*cos(s[n])*thwid*yscale,axlab,cex=1.33,srt=0,crt=0)<br /> } <br /> }<br /></pre><br /><br />And this is the code that calls it:<br /><pre><br />#set up data<br />#variable 1<br />i <- .01*c(4:8,10,12,15,20)<br />li <- log(1+i)<br />yi <- -log(i)/(1+li)<br />xi <- li/(1+li)<br />yi <- yi-4*xi # skew the plot a bit<br /><br />#variable 2<br />n <- 4:8<br />yn <- n-4<br />xn <- rep(1,length(n))<br /><br />#variable 3<br />d <- c(1:6,8,10,15,20)<br />xd <- rep(0,length(d))<br />yd <- log(d)-4*xd<br /><br />#scale the plot<br />xmin <- min(xd,xi,xn)<br />xmax <- max(xd,xi,xn)<br />ymin <- min(yd,yi,yn)<br />ymax <- max(yd,yi,yn)<br /><br />xl <- xmin-0.02*(xmax-xmin)<br />xu <- xmax+0.02*(xmax-xmin)<br />yl <- ymin-0.02*(ymax-ymin)<br />yu <- ymax+0.02*(ymax-ymin)<br /><br />#draw the nomogram<br />par(ann=FALSE, xaxt="n",yaxt="n",bty="n")<br />plot(NULL, xlim=c(xl,xu),ylim=c(yl,yu)) #draws a blank plot<br />curvaxis(xi,yi,i,axlab="i",ltick=FALSE,axlt1=FALSE)<br />curvaxis(xn,yn,n,axlab="n")<br />curvaxis(xd,yd,d,axlab="d")<br /></pre>GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com2tag:blogger.com,1999:blog-1364629727248557844.post-57703796956057695932010-01-01T11:11:00.002+11:002010-01-01T11:15:01.035+11:002010 Mathematical CalendarRon Doerfler at <a href="http://myreckonings.com/wordpress">Dead Reckonings</a> has a 2010 "Graphical Computing" Calendar. It looks very nice.<br /><br />See this post at Ron's <a href="http://myreckonings.com/wordpress/2009/12/31/a-2010-graphical-computing-calendar/<br />">blog</a>GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com0tag:blogger.com,1999:blog-1364629727248557844.post-90679584849125963502009-09-30T13:05:00.003+10:002009-09-30T13:10:18.672+10:00User-contributed R packages on CRAN passes 2000 markThe number of user-contributed packages at for the free (in both senses) statistical package R has passed <i>2000</i>. See <a href="http://cran.r-project.org/web/packages/">http://cran.r-project.org/web/packages/</a>. <br /><br />Quite a milestone. Back in May I predicted to someone that it would hit 2000 around the start of October. Well, not too far out, but it is still September.<br /><br />If you don't have R but you do a lot of manipulation of numbers, consider getting R. It repays the investment in time very well indeed.<br /><br />(<I>I have made no posts for a good while due to major illness. Mostly okay now.</i>)GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com0tag:blogger.com,1999:blog-1364629727248557844.post-84433981701555465732009-06-23T15:38:00.004+10:002009-06-23T15:46:52.545+10:00The product of two sums of squaresI just happened upon this extra nifty little fact - the set of sums of two squares is closed under multiplication.<br /><br />That is, facts like (10<sup>2</sup> + 9<sup>2</sup>) × (1<sup>2</sup> + 1<sup>2</sup>) = 19<sup>2</sup> + 1<sup>2</sup> occur for every <br />(a<sup>2</sup> + b<sup>2</sup>) × (c<sup>2</sup> + d<sup>2</sup>).<br /><br />Take a look - simple result, I am surprised I hadn't seen it before...<br /><br />See the <a href="http://en.wikipedia.org/wiki/Brahmagupta%E2%80%93Fibonacci_identity">Brahmagupta-Fibonacci identity</a> at WikipediaGBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com0tag:blogger.com,1999:blog-1364629727248557844.post-72316520276765735682009-06-21T09:29:00.005+10:002009-06-21T10:16:41.605+10:00Trig identites and multiplicationWe're used to the idea of using logarithms to convert multiplication problems into addition problems, because of the relation:<br /><br />log(xy) = log(x) + log(y)<br /><br />So if you have a table of logarithms, to multiply x and y you can look up the logarithms of each, add them, then find the number in your tables whose logarithm is that sum. Three table-lookups and an addition. [Well, in practice you do the last lookup in a table of antilogarithms, but that's only a minor benefit, it's not actually necessary to the calculation.]<br /><br />However, there are other ways to make multiplication "simpler" than trying to directly multiply, such as this identity:<br /><br />cos x cos y = [cos (x + y) + cos (x - y)]/2<br /><br />This sort of relationship was actually used to do multiplication; it's a bit more complicated than logarithms, but it works well enough if you haven't invented logs yet, but <i>do</i> have cosine tables. It works like this.<br /><br />You want to multiply two numbers, X and Y (and let's assume that they have already been scaled to lie in a range where this will work). <br /><br />You find the numbers that they are the cosines of in your tables, X = cos x, Y = cos y. Add and difference those two numbers, giving (x+y) and (x-y). Look those numbers up in your cosine tables. Average them. That's the product. Four table lookups, an addition and a halving (and some rescaling back to the original problem, presumably, which probably just involves moving a decimal point), all much easier than general multiplication.<br /><br />So far so good.<br /><br />But here's what I am wondering. Humans came up with a nifty device to automate that multiplication via addition of logs, the slide rule. Is it possible to build a device that does mutliplication using a trig identity like the one above, perhaps some sort of "swivel rod"?<br /><br />If we do it in two parts, I think maybe we can do it with a slide rule; one side does the additions and subtraction (and halving; halving is inverse doubling, which is just addition, so it can also be done there). The other does the conversions to and from normal scale to cosine scale - but you'd be forever transferring numbers across the different scales.<br /><br />So I wonder if it can all be combined in a single, simpler system, whether it's a kind of slide rule or something more complex involving actual rotations to do the cosines (accuracy may be an issue though). <br /><br />I don't think a device was ever made that did this, but I think that it might be possible.<br /><br />If it were, I'd love to have one.GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com0tag:blogger.com,1999:blog-1364629727248557844.post-78254315630621254492009-06-15T14:24:00.003+10:002009-06-15T14:32:06.395+10:00Annoying ways to ask a question...I recently answered some mathematics questions on Yahoo Answers.<br /><br />This reminded me of some of my pet peeves when people ask for mathematical help -<br />many of which are apparently attempts to minimize the scale of your contribution<br /><br />* "Can I ask a question? It'll only take a moment."<br /> -- yes, questions rarely take long to ask - but the answer won't be nearly as fast.<br /> <br />* "This is a simple problem"<br /> -- it often isn't. If was so darn simple, you'd answer it yourself.<br /><br />* "Why are you making this so complicated? It was a simple question!"<br /> -- see question 1. Just because the question was brief doesn't mean it has a simple solution. Fermat's last theorem could be explained to a child and stated in a few lines!<br /><br /><br />Further annoyances more particular to YA include people just posting their entire homework with not the slightest indication that they've even attempted any of it, sneering responses when you don't just give them all the answers with fully worked solutions, and snarky reactions when you point out that merely typing their question <i>as is</i> into google would have got them the answer instantly.GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com0tag:blogger.com,1999:blog-1364629727248557844.post-1634296684215017822009-05-22T13:40:00.003+10:002009-05-22T13:42:48.759+10:00Total incomprehension?Sometimes, adding apples and oranges is <a href="http://img268.imageshack.us/img268/8641/sign2x.jpg">not fruitful</a>.GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com0tag:blogger.com,1999:blog-1364629727248557844.post-64799953016175217542009-05-18T17:26:00.005+10:002009-06-15T14:24:21.461+10:00Number of uniforms to sum>1<font size="-1">[Sorry - been a long time without posting. Illness has made it hard to find the impetus.]</font><br /><br /><br />Anyway, a probability problem I found interesting:<br /><br />What's the distribution of the number of random uniform[0,1) random variables that you need to generate so that the sum is greater than 1?<br /><br />There's a nifty little trick to it.<br /><br /><hr><br /><br />Update:<br /><br />Well, the trick is to compute the survivor function, 1-F(n).<br /><br />Let N be the number of uniform RVs needed to exceed 1.<br /><br />P(N>n) = P(U(1) + U(2) + ... + U(n) <= 1)<br /><br />That RHS probability is relatively easy to get in a variety of ways to be 1/n!<br /><br />From there, the probability function for N is simple...GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com0tag:blogger.com,1999:blog-1364629727248557844.post-2272363971506697142009-02-25T10:44:00.001+11:002009-02-25T12:17:51.487+11:00Calculation InformationBrendan O'Connor at, <a href="http://anyall.org/blog/">AI and Social Science</a> has looked at a number of packages with which people might do statistical and related manipulations and computations, and <a href="http://anyall.org/blog/2009/02/comparison-of-data-analysis-packages-r-matlab-scipy-excel-sas-spss-stata/">compares them</a>. Having used five of them (STATA and the items in the Python group being the exceptions, though I have had "try these out" on my agenda for some time), I agree broadly with what was said about the packages I have experience with - which suggests to me I can probably take seriously the assessment of the remainder.<br /><br />A very handy and compact comparison. If you use statistics, take a look.GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com0tag:blogger.com,1999:blog-1364629727248557844.post-27209635472313095472009-02-18T16:48:00.014+11:002009-05-22T12:45:54.191+10:00Incredibly simple ways to get rational approximations to square rootsOver at <a href="http://blog.plover.com/">The Universe of Discourse</a>, Mark Dominus talks about <a href="http://blog.plover.com/math/sqrt-3-2.html">Archimedes and the square root of three</a> pointing out that Archimedes needn't have had some mystical way of finding rational approximations to surds in order to figure that 265/153 is very close to the square root of three.<br /><br />He points out that there's a simple enough pattern that Archimedes could have spotted and soon figured it out. That is true enough, but Archimedes could have got by, while being even less clever than that.<br /><br />Let's consider a few simple facts:<br />(i) if a and b are close to the ratio √3:1 then 3b and a are also close to that ratio, with the error in the opposite direction and of similar magnitude<br />(ii) Hence (a+3b):(b+a) will be substantially closer* to √3:1 than a:b is<br /><br />*(in fact it improves the error in the approximation of 3 by a<sup>2</sup>/b<sup>2</sup> by a factor that rapidly goes to 2+√3, but Archimedes needn't have figured that fact out - he only needs to have noticed that 3b:a is also an approximation of √3:1, and (a+3b):(b+a) always seems to be a better approximation than he started with) <br /><br />If we proceed in this fashion from the very ordinary starting point of 2:1 (and eliminate common factors as they pop up), we rapidly hit on Archimedes' ratio.<br /><br /><pre><br /> 2 1 (a:b)<br /> 3 2 (3b:a)<br /><br /> 5 3 (a+3b:b+a), which becomes our new a:b<br /> 9 5<br /><br /> 7 4 (dividing out a common factor of 2 here)<br /> 12 7<br /><br /> 19 11<br /> 33 19<br /><br /> 26 15 (taking out another factor of 2)<br /> 45 26<br /><br /> 71 41<br />123 71<br /><br /> 97 56 (taking out a third factor of 2)<br />168 97<br /><br />265 153 </pre><br /><br />And you're there after maybe a couple of minutes of very simple computation, even if you're a much worse computer (in the original sense) than Archimedes doubtless was.<br /><br />Not in the least mysterious, and a bonehead like me figured it out almost immediately. I'll wager a master like Archimedes realized something like this in even less time than it took me. It's so simple, he <i>probably wouldn't have even bothered to write it down</i>.<br /><br />__________<br /><br />(<i>Later edit:</i>)<br />What I have above appears to be basically the <a href="http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method">Bablyonian Method</a>, on which Brent at <a href="http://www.mathlesstraveled.com"> The Math Less Traveled</a> writes <a href="http://www.mathlesstraveled.com/?p=323">here</a>.<br /><br />I must have seen mention of this before (at least the phrase "Babylonian Method" sounds somewhat familiar). I have no doubt Archimedes was familiar with some version of it.GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com2tag:blogger.com,1999:blog-1364629727248557844.post-81385884611483533092009-02-17T08:26:00.003+11:002009-02-17T08:35:14.974+11:00Nifty log-concave function postJohn D Cook has a nifty post up about <a href="http://www.johndcook.com/blog/2009/01/09/log-concave-functions">log-concave functions</a> (in the latest <a href="http://concretenonsense.wordpress.com/2009/01/30/welcome-to-carnival-of-mathematics-48-6/">Carnival of Mathematics</a>). These include the log-concave densities, which have been popular objects of research in statistics in the last decade or so - they're a wide class of densities that have (as you might guess from John's article) some nice properties.<br /><br />I'd like to write a longer, basic post about them sometime. The <a href="http://en.wikipedia.org/wiki/Logarithmically_concave_measure">Wikipedia page</a> doesn't really do them justice.GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com0tag:blogger.com,1999:blog-1364629727248557844.post-77396828515492622502009-01-05T19:08:00.003+11:002009-01-05T19:10:42.351+11:00What mathematicians doImagining that mathematicians spend all their times doing calculation is very like imagining that writers spend all their time spelling words.GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com0tag:blogger.com,1999:blog-1364629727248557844.post-23694090898642760402009-01-05T18:03:00.004+11:002009-01-05T18:11:20.342+11:00Some minor computer geekeryToday I managed to get <a href="http://cran.r-project.org/">R</a> running under the <a href="http://portableapps.com/">PortableApps</a> menu, with only a little fiddling. Which if you're a big computer nerd is really not much of an achievement at all, but for an old dinosaur like me, it's pretty good.<br /><br />Adding R makes that particular USB stick a lot nearer to having "all the software you need on a USB" if you're a statistician.<br /><br />I'm quite impressed with some of the portable applications, too.<br /><br />Getting R onto the USB is trivial - you can just copy an existing R (including the subdirectories) from a hard drive, and you have all your installed packages and your saved variables and everything. But making it appear in the menu was kind of nice.GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com0tag:blogger.com,1999:blog-1364629727248557844.post-86040852423212951402009-01-05T17:34:00.010+11:002009-01-06T08:55:04.099+11:00Just how small is the smallest illegal number?I've seen a number of posts recently relating to "illegal numbers", such as these ones:<br /><br /><a href="http://everything2.com/e2node/Copyrighting%2520a%2520number">Copyrighting a number</a>, and<br /><a href="http://oisteing.wordpress.com/2008/12/28/converting-pi-to-binary-dont-do-it/">Converting pi to binary</a>, which points to<br /><a href="http://www.everything2.com/index.pl?node_id=1302963">Converting Pi to binary: Don't do it!</a><br /><br />The first of these relates to the fact that files are just essentially numbers, and replicating certain numbers can be illegal (even to DMCA issues). The third (and the second which points to it) is essentially remarking on the fact that <a href="http://en.wikipedia.org/wiki/Pi">π</a> is thought to be a <a href="http://en.wikipedia.org/wiki/Normal_number">normal number</a>, so it is believed that all possible finite digit sequences occur in its expansion (and so contains all such illegal numbers).<br /><br />Let's consider the first issue: some integers are definitely illegal - it appears quite possible to get yourself into trouble posting particular integers. The post at <a href="http://everything2.com/e2node/Copyrighting%2520a%2520number">Copyrighting a number</a> suggests that the smallest such number is incomrehensibly large.<br /><br />But I suspect that this isn't necessarily the case.<br /><br />Certainly it's true that the smallest integer representing a song would be <i>huge</i>. The smallest integer representing a book would be <strike>far, far larger</strike> very large**. But it's not only entire songs or books that are subject to copyright. Indeed, it only takes a few bars before you get into copyright trouble. And it doesn't need to be a few bars of a perfomance. In fact, I could represent in a compact ASCII form just enough of a simple tune to get myself into trouble in only a small number of characters (I think with careful choice of tune, the extracted bars and the representation, I could do it in less than one line of text here). I could represent it in some <i>compressed</i> form in much less space (posting a zip file of a copyright work is just as illegal as posting an uncompressed version, and so it would be with any other compression scheme). Maybe I could get into trouble posting slightly less of a book - I can quote a tiny bit of a book in certain circumstances, but if those circumstances don't hold, how little of a book can I quote before I am in copyright violation?<br /><br />** [That "far, far larger" (now elided) looks like a dumb error if you compare the size of a high fidelity musical recording with a book recorded as, say an ascii file. But that's not comparing like with like. A book is like a score (and lyrics), not like the performance of it. If we compare a performance of a book with a performance of a song, then again, the book is larger (perfomed books typically take several CDs). But arguing about this is a distraction from the point here, so I have changed the text above to avoid the issue.]<br /><br />So, then, we are left to wonder, what is the smallest possible illegal digit sequence? <br /><br />What it the smallest possible <i>representation</i> of it? <br /><br />(Might the πth root of 237 have that digit sequence somewhere in its first ten thousand digits, thus giving me an incredibly compact way of specifying an illegal digit sequence? I doubt it.)<br /><br />Anyway, I'm inclined to think that it might be possible to get yourself into trouble with say the DMCA with some surprisingly small digit sequences.<br /><br />And wait a minute - does this post constitute an encouragement to breaking the law? <br />I've asked for people to tell me the smallest illegal number. Certainly, if someone does post such a number in the comments, it would be easy to argue that I incited it. But actually, it seems the law on that doesn't actually require the other person to <i>break</i> the law. And even if it's not enough for me just to ask what the number is, I don't want any of my readers going to jail if they do figure out the number.<br /><br /><br /><b>One less</b><br /><br />Perhaps it's better to ask what number is <i>one less than</i> the smallest illegal number. Maybe that's safer.<br /><br />But consider the RIAA - I don't expect that the RIAA would have the slightest hesitation in trying to smack me down for publishing <i>one less than the smallest illegal number</i> because that description of it implies an algorithm for producing the smallest illegal number from it... and so this very paragraph contains an algorithm for producing an illegal number, were I to later post one less than such a number. (In fact, is it illegal to describe such an algorithm already, without having a number to apply it to? The DMCA seems to be pretty broad. Have I in fact <i>already</i> broken the law merely by describing the algorithm - that "the way to produce the smallest illegal integer from the next smallest number is simply to add 1"?)<br /><br />So asking for one less than an illegal number is no good. Certainly publishing <i>that number</i> with the description ("just add one") is illegal. But if I publish a number and an algorithm for producing an illegal number from it in two different places, I believe I have still broken the law (they don't have to be in the same location, surely, or the law would be trivially circumvented). Given I've <i>already posted</i> an algorithm for producing an illegal number from one less than it, it seems that posting <i>one less than the smallest illegal number</i> anywhere must in turn be illegal.<br /><br />No doubt you've noticed the problem already.<br /><br />By that reasoning, <i>one less than</i> that number must also be illegal.<br /><br />Assuming we restrict our search to the non-negative integers, I believe I can therefore assert that the smallest illegal number I can publish to my blog is zero.<br /><br />Oops - and just I made the mistake of publishing it to my blog. <br /><br />Numbers. Every digit of every number. They're all illegal. <br /><br /><i><sub>If this blog disappears suddenly, I've probably been got by the goons at the RIAA. </i></sub>GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com5tag:blogger.com,1999:blog-1364629727248557844.post-69245835746516926992009-01-02T10:11:00.001+11:002009-01-05T17:29:29.555+11:00"Hit the target space" probabilityBack to the <a href="http://mathbric.blogspot.com/2008/12/lets-start-with-little-probability.html">problem</a> of finding the probability of hitting a desirable space when rolling a six sided die (d6). Let's look at the easy way to compute the probabilities, then we can talk about them.<br /><br />First, let's compute a couple of easy probabilities - we'll use them to check our work in a moment. If I was one space from the target, I only hit the target on a roll of 1. Any other roll takes me past it and I miss it.<br /><br />So the probability I hit the target from one space away is 1/6.<br /><br />If I was two spaces away, I hit the target with a roll of 2 (probability 1/6); but I can also hit the target by moving one space (1/6) and then hitting the target from there (times the 1/6 we already worked out a second ago). Total probability = 7/36.<br /><br />Let's say P(<i>i</i>) is the probability of hitting the target space, <i>T</i>, from space <i>i</i>.<br /><br />From the current space, <i>i</i>, the probability you hit the target is the probability you roll 1 times the probability you hit the target from one space further ahead, plus the probability you roll 2 and hit the target from 2 spaces further ahead, and so on up to 6 spaces.<br /><br />That is, we get the recursive formula<br />P(<i>i</i>) = 1/6 [P(<i>i</i>+1)+P(<i>i</i>+2)+...+P(<i>i</i>+6)].<br /><br />Let's look at that for a second. If I know the six probabilities immediately ahead of the current space, I can work out the probability from this space.<br /><br />Now, let's look at the target space, <i>T</i>. Obviously, we're there already, so P(<i>T</i>)=1.<br /><br />How would I work out the probability for the previous space?<br />P(<i>T</i>-1) = 1/6 [P(<i>T</i>) + P(<i>T</i>+1) + ... + P(<i>T</i>+5)].<br /><br />Wait. What's P(<i>T</i>+1)? Well, from <i>past</i> the space I have no chance. It's 0. Same with P(<i>T</i>+2), etc.<br /><br />P(<i>T</i>-1) = 1/6 [ 1 + 0 + 0 + 0 + 0 + 0 ] = 1/6 (checks out)<br />P(<i>T</i>-2) = 1/6 [1/6+ 1 + 0 + 0 + 0 + 0 ] = 7/36 (checks out)<br /><br />[It's not hard from this to show that, <i>for the 5 spaces immediately before the target</i>, the hit-the-target probability for the NEXT space further away is 7/6 of the probability for the current space. Consequently, for those spaces, P(<i>T</i>-<i>i</i>) = 7<sup><i>i</i>-1</sup>/6<sup><i>i</i></sup>. So from 6 spaces away, the probability is 7<sup>5</sup>/6<sup>6</sup> = 16,807/46,656. However, I'm going to take a lazier-but-more general approach for computing probabilities.]<br /><br />We can compute all the probabilities numerically, working one by one back from the target. Indeed, with a neat recursive formula like that one above, a spreadhseet is a handy tool (I happened to use Excel). Write the probabilities for P(<i>T</i>) to P(<i>T</i>+5) in a column (1 and 5 0's), and write the formula for P(<i>T</i>-1) in terms of those values:<br /><table class="MsoTableGrid" style="border-collapse: collapse;" border="0" cellpadding="0" cellspacing="0"><br /><tbody><tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i> </i><br /></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i> A</i></td> <td style="padding: 0cm 5.4pt; width: 106.85pt;" valign="top" width="142"><i> B</i></td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i>:</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><br /></td> <td style="padding: 0cm 5.4pt; width: 106.85pt;" valign="top" width="142"><br /></td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i>4</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"> T-() </td> <td style="padding: 0cm 5.4pt; width: 106.85pt;" valign="top" width="142"><span style="font-style: italic;">prob</span></td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i>5</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"> -5</td> <td style="padding: 0cm 5.4pt; width: 106.85pt;" valign="top" width="142"> 0 </td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i>6</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"> -4</td> <td style="padding: 0cm 5.4pt; width: 106.85pt;" valign="top" width="142"> 0 </td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i>7</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"> -3</td> <td style="padding: 0cm 5.4pt; width: 106.85pt;" valign="top" width="142"> 0</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i>8</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"> -2</td> <td style="padding: 0cm 5.4pt; width: 106.85pt;" valign="top" width="142"> 0</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i>9</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"> -1</td> <td style="padding: 0cm 5.4pt; width: 106.85pt;" valign="top" width="142"> 0</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i>10</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"> 0</td> <td style="padding: 0cm 5.4pt; width: 106.85pt;" valign="top" width="142"> 1</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i>11</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"> 1</td> <td style="padding: 0cm 5.4pt; width: 106.85pt;" valign="top" width="142">=AVERAGE(B5:B10)</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i>12</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"> 2</td> <td style="padding: 0cm 5.4pt; width: 106.85pt;" valign="top" width="142"><i> </i><br /></td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i>13</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><br /></td> <td style="padding: 0cm 5.4pt; width: 106.85pt;" valign="top" width="142"><i> </i><br /></td></tr><tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><i>:</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="top" width="61"><br /></td> <td style="padding: 0cm 5.4pt; width: 106.85pt;" valign="top" width="142"><i> </i><br /></td></tr></tbody></table><br />Okay, instead of 1/6*sum(B5:B10) I lazily used the average function, but you see the idea. Copy that formula and paste it down as many rows as you like.<br /><table style="border-collapse: collapse;" border="0" cellpadding="0" cellspacing="0"><br /><tbody><tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i> </i><br /></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>A</i></td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70"><i>B</i></td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>:</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><br /></td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70"><br /></td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>4</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> T-()</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70">prob </td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>5</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> -5</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70"> 0 </td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>6</i></td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> -4</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70"> 0 </td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>7</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> -3</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70"> 0</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>8</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> -2</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70"> 0</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>9</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> -1</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70"> 0</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>10</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> 0</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70"> 1</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>11</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> 1</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70">0.16667</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>12</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> 2</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70">0.19444</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>13</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> 3</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70">0.22685</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>14</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> 4</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70">0.26466</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>15</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> 5</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70">0.30877</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>16</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> 6</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70">0.36023</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>17</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> 7</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70">0.25360</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>18</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> 8</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70">0.26809</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>19</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> 9</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70">0.28037</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>20</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> 10</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70">0.28929</td> </tr> <tr> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"><i>21</i> </td> <td style="padding: 0cm 5.4pt; width: 45.8pt;" valign="bottom" width="61"> 11</td> <td style="padding: 0cm 5.4pt; width: 52.85pt;" valign="bottom" width="70">0.29339</td> </tr><br /></tbody></table>While the probability at 6 spaces away is 36%, the probability at 7 spaces away is 25%!<br /><br />At large distances, the number converges to 2/7 ~= 28.57% (if the average roll is 3.5 spaces, it's perhaps not so surprising that the average probability you hit a space is 1/3.5).<br /><br />In Excel, you can do neat plots to see what's going on:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://1.bp.blogspot.com/_y8B7MKebdC4/SV29M6NmrbI/AAAAAAAAAAU/A1QVSfU9UZs/s1600-h/rollmovegraph.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 400px; height: 282px;" src="http://1.bp.blogspot.com/_y8B7MKebdC4/SV29M6NmrbI/AAAAAAAAAAU/A1QVSfU9UZs/s400/rollmovegraph.png" alt="" id="BLOGGER_PHOTO_ID_5286589567085227442" border="0" /></a><br /><br />In short, if you have some influence on where you try to land on the target from (such as the ability to change your roll by one, for example), the best spots (in order) are 6 spaces away, 5 spaces away and 11 spaces away, and of those, 6 is by far the best. Try to avoid being fewer than 4 spaces away, and 7 isn't much good either.<br /><br />I used the approach outlined here to look at rolling two and three dice (2d6 and 3d6) as well; the direct calculation approach here adapts quite easily to these situations, yielding probabilities with a minute or so of effort.GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com2tag:blogger.com,1999:blog-1364629727248557844.post-57705821162630399502009-01-01T12:59:00.000+11:002009-01-01T17:48:56.590+11:00Let's start with a little probability intuitionImagine you're playing a board game where your pieces move according to a <a href="http://en.wikipedia.org/wiki/Dice">die roll</a>. Unless it's a very dull game, there will probably be other things that can influence your position as well, but we're ignoring them right now.<br /><br />Let's imagine that normally your move is given by a single die roll (six sided die, d6), and you pass along the spaces only once - it's a straight "race", not a circuit.<br /><br />No doubt you've seen many games where you move along spaces to some end, and a few spaces have special characteristics (such as "miss a turn" or "move ahead three spaces"). <a href="http://www.boardgamegeek.com/">BoardGameGeek</a> calls these "<a href="http://www.boardgamegeek.com/search.php3?nocategoryids%5B%5D=72&mechids%5B%5D=35&B1=Submit"><i>roll and move</i></a>" games, and appears to list more than six thousand of them. If that doesn't ring a bell, think of something a bit like <a href="http://en.wikipedia.org/wiki/Snakes_and_ladders">Snakes and Ladders</a>.<br />(However, you can apply similar ideas to a large variety of games where you accumulate some resource with varying probabilities. )<br /><br />Further, let's say there's a particularly desirable space to land on (which I'll call the target). You're currently 6 spaces away (that is, if you roll a 6 you will land on the space). You really would like to land on that space, either this turn, or next turn, or the turn after that, ... &c.<br /><br />Quick - without working it out exactly, and assuming for now that no strategy is available to change the probability, what would you guess would roughly be your chance of hitting the the target at all?<br /><br />Then, if you're so inclined, try to work out the probability. (If you're not inclined to attempt it, never fear - I will post the correct answer later. There's at least one fairly easy way to do it - and a lot of somewhat less easy ways to do it.)<br /><br />This was one case where my intuition wasn't as directly useful as I might hope. Intuition served me just fine for figuring out what the probability would be from far away, but from closer up, not so much - at least not at first.GBhttp://www.blogger.com/profile/01100913350264083875noreply@blogger.com0