Mathematics desk
< July 23	<< Jun \| July \| Aug >>	July 25 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 24

Infinite monkey calculations

Right, based on the article infinite monkey theorem:

The odds of getting the word "banana" typed are 26^6 or 1 in 308,915,776.

say i made a program make random letters, and it stops making them when it finds "banana".

Ex:

wjkotcbanana

How then would i classify the results of this single test?

is it 6 in 12 because 6 of 12 letters make the word banana? is it 1 in 12 because out of 12 letters the word banana appears once? or is there a specific formula that i havent mentioned? Please help.

172.129.238.63 01:54, 24 July 2007 (UTC)[reply]

It depends on what you want to express. If you want to express how many letters out of those produced make up the word banana, the answer is: 6 (out of 12). If you want to state how often you found the word banana for every letter produced, it is once (on 12 times). If you want to express the odds of a certain event occurring – usually such terminology as 1 in 308,915,776 is reserved for the odds of an event occurring – you have to make clear what the event is. The probability of finding the string banana at least once in a random string of 12 letters from a 26-letter alphabet is equal to (7×26⁶−1)/26¹², which is about 7 in 308,915,776 or 1 in 44,130,825. The probability of finding the string banana exactly once in a random string of 12 letters from a 26-letter alphabet, appearing as the last 6 letters, is equal to (26⁶−1)/26¹², which is about 1 in 308,915,776. --Lambiam 03:13, 24 July 2007 (UTC)[reply]

Shirley, you mean the average number of characters typed before the word "banana" (first) appears. I would state the result as "On one run, a monkey typed a total of 12 characters when the word banana first appeared." 202.168.50.40 01:30, 25 July 2007 (UTC)[reply]

To whom is the word you meant to refer in this declaration? --Lambiam 02:47, 25 July 2007 (UTC)[reply]

It's a joke! Shirley, you would know what a joke is. 202.168.50.40 03:32, 25 July 2007 (UTC)[reply]

You edited your posting of 01:30, 25 July 2007 (UTC) after my reaction, which is cheating. Without the later addition of a second sentence, it was totally unclear that the word "average" was supposed to refer to the results of a single test. --Lambiam 03:56, 25 July 2007 (UTC)[reply]

The word "average" is not meant to refer to the result of a single run. It is meant to mean the "arithmetic mean" of many many runs. In a real run, it would be extremely unlikely that the word "banana" would appear as early as 12 characters typed. 202.168.50.40 04:31, 25 July 2007 (UTC)[reply]

I calculate the average number of typed characters when the word "banana" first appear to be an obscenely large number of 321272406 202.168.50.40 04:45, 25 July 2007 (UTC)[reply]

~~Above the correct number of 26⁶ = 308915776 has already been mentioned. --Lambiam 06:46, 25 July 2007 (UTC)~~[reply]

1 in 26^6 is just the odds of getting the word "banana" when you type 6 characters. It is not the average number of characters typed when the word "banana" first appeared. Try and consider the average number of coin toss needed before you encounter 6 heads in a row. It would not be 2^6. 211.28.119.3 08:53, 25 July 2007 (UTC)[reply]

How much is it? If not that number, perhaps something close?--Patrick 11:58, 25 July 2007 (UTC)[reply]

The average number of coin tosses needed to encounter 1 head is 2.--Patrick 12:21, 25 July 2007 (UTC)[reply]

To type the first 100 characters of the play Hamlet, requires an average of 3268647867246256383381332100041691484373976788312974266629140102414955744756908184404049903032490380904202638084876187965749304595652472251350 typed characters on the typewriter. I can't find the number for 1000 characters because my program crashed. PS. I assume the alphabet consists only of 26 unique characters. 202.168.50.40 05:00, 25 July 2007 (UTC)[reply]

Suppose we are trying to get a sequence of l correct letters from an alphabet of size s. Let

m_{k}

be the expected number of additional letters needed if the last k letters (but no more) are correct. Then we have

m_{k}=1+{\tfrac {1}{s}}m_{k+1}+{\tfrac {s-1}{s}}m_{0}

. The solution is

m_{k}={\frac {s^{l+1-k}-s}{s-1}}

. We are interested in

m_{0}

, which is equal to

{\frac {s^{l+1}-s}{s-1}}

. For

s=26,\ l=6

, this is 321272406, like 202 has mentioned. -- Meni Rosenfeld (talk) 14:23, 25 July 2007 (UTC)[reply]

For l = 1000, by the way, Mathematica is of course more than capable of finding an exact result, but the short version is "roughly

9.78\cdot 10^{1414}

". -- Meni Rosenfeld (talk) 14:28, 25 July 2007 (UTC)[reply]

There seems to be something wrong. Take e.g. the alphabet {a,b} and the sequence aa, then

m_{0}=6

seems correct, but

m_{1}=4

, not 2. And for the sequence ab, after correctly having an "a", the expected number of additional letters needed is less than for the sequence aa: if the next character is wrong we have aa, and we do not have to start from the beginning but again already the first letter is correct. I get

m_{0}=4

for this sequence.--Patrick 06:01, 26 July 2007 (UTC)[reply]

You're right, I messed up the summation of the geometric series - it should be

m_{k}={\frac {s^{l+1}-s^{k+1}}{s-1}}

(which is the same as before for k=0). You are also correct that my assumption that a wrong letter resets our position is only valid for a sequence of identical letters, where I have mistakenly assumed that it generalizes to every sequence. So the exact values depend on the structure of the desired sequence - in particular, for "banana", it will be smaller than the value I have given (which is correct only for "zzzzzz"). Sorry for those mistakes. -- Meni Rosenfeld (talk) 14:53, 26 July 2007 (UTC)[reply]

Fortunately, none of this has any bearing on your previous question regarding HHHHHH - it is still 126 (which is remarkably larger than 64). -- Meni Rosenfeld (talk) 14:59, 26 July 2007 (UTC)[reply]

Yes, and I am beginning to understand why this is: if you continue tossing the coin, 1 in 64 sequences is HHHHHH provided that HHHHHHH (7 Hs) is counted as two sequences of 6, etc.; it is 1 in 126 if overlapping sequences are not counted.--Patrick 16:22, 26 July 2007 (UTC)[reply]

Since two occurrences of "banana" cannot overlap, would not the average number of letters that has to be typed be exactly 26⁶ = 308,915,776?--Patrick 16:41, 26 July 2007 (UTC)[reply]

I can't say I am completely convinced by your argument, but solving the equations indeed gives a result of 308915776. If only we had figured this out before Lambiam has struck out his comment... :) -- Meni Rosenfeld (talk) 17:53, 26 July 2007 (UTC)[reply]

Formulating my argument a little better: on average there is 1 sequence HHHHHH for every 64 tosses, provided that HHHHHHH (7 Hs) is counted as two sequences of 6, etc.; it is 1 sequence HHHHHH for every 126 tosses if overlapping sequences are not counted. For each sequence of tosses starting after a sequence HHHHHH and ending with the next occurrence of the same, there are on average also .5 such sequences starting with the second H, .25 starting with the third, etc.--Patrick 00:02, 27 July 2007 (UTC)[reply]

Solving for Exact Value (trigonometric identities)

Excuse me, can someone please point me in the right direction for this problem (I have to look for the values of the remaining circular functions):

sinθ = -5/13, tanθ<0

Since sin=opposite/hypotenuse, I've already drawn a triangle on QIV with the sides -5, and hypotenuse=13. Through pythagorean's theorem, I found out that the last side was 12. But does it mean cosθ is 12/13?? I'm not sure what to do, please help me! --Confused Student 03:47, 24 July 2007 (UTC)

Use inverse functions. You want to find out the values of theta such that sin theta is -5/13, and that tan theta is negative. Drawing pictures of the graphs of the functions might help. Remember also that triangles do not have sides with negative length -- there's no such thing as a negative length. —The preceding unsigned comment was added by 129.78.64.106 (talk • contribs) 05:13, 24 July 2007 (UTC)[reply]

The information you were given merely means that the angle theta is located in the fourth quadrant of the unit circle. —The preceding unsigned comment was added by 124.191.116.182 (talk • contribs) 06:44, 24 July 2007 (UTC)[reply]

The best approach is to use the well-known Pythagorean trigonometric identity cos² θ + sin² θ = 1. Plug in the known value of sin θ, and solve for cos θ. This should give you two solutions. The additional information on the sign of tan θ rules out one of the two. --Lambiam 06:50, 24 July 2007 (UTC)[reply]

It may help to remember that

\tan {\theta }={\frac {\sin {\theta }}{\cos {\theta }}}

. -- Meni Rosenfeld (talk) 11:17, 24 July 2007 (UTC)[reply]

A similar example is sin θ = ²⁴⁄₂₅, tan θ < 0. This tells us that in a right triangle with hypotenuse 1, the side opposite the angle has the given length. As you already know, we can find the length of the adjacent side using the Pythagorean theorem.

{\begin{aligned}(\cos \theta )^{2}+(\sin \theta )^{2}&=1\\(\cos \theta )^{2}+\left({\frac {24}{25}}\right)^{2}&=1\\(\cos \theta )^{2}&=1-{\frac {576}{625}}\\&={\frac {49}{625}}\\\cos \theta &=\pm {\frac {7}{25}}\end{aligned}}

Because the tangent is sine divided by cosine, we conclude that the cosine must be negative.

{\begin{aligned}\sin \theta &={\frac {24}{25}}>0\\\tan \theta &={\frac {\sin \theta }{\cos \theta }}<0\\&{\text{which implies that}}\\\cos \theta &=-{\frac {7}{25}}<0\end{aligned}}

Now that we know the numeric values of the sine and cosine, we can deduce all other trigonometric values using identities. For example:

{\begin{aligned}\tan \theta &={\frac {\sin \theta }{\cos \theta }}\\&={\frac {24/25}{-7/25}}\\&=-{\frac {24}{7}}\\\sec \theta &={\frac {1}{\cos \theta }}\\&={\frac {1}{-7/25}}\\&=-{\frac {25}{7}}\end{aligned}}

There is no simple computation to give the angle itself, though we know it must lie in the third quadrant (which is where sine is positive and cosine is negative); but no matter, because the question does not ask for that. --KSmrq^T 15:59, 24 July 2007 (UTC)[reply]

Traffic Patterns

It is fairly common where I live(and I imagine wherever there are highways) for someone to shut down one of the lanes of a multi-line highway. This could be for road maintainence, crash removal, or some other reason. This is most common with the left lane. Signs are usually placed telling everyone that the lane is closed ahead, and to merge right.

In this situation you see two types of drivers: those that merge as soon as they can and those that drive down the near-empty lane until the lane closes, and then merge quickly right there. I generally think of the former as altruistic drivers and the latter as selfish(or at least hurried) drivers. So there is always a mixture of the two, but there theoretically could be all altruistic or all selfish drivers. This would be especially likely in the case of computer-controlled vehicles.

I generally assume that the situation leading to the best flow of traffic would be to have altruistic drivers driving every car on the road. However, this is not self-evident. Has anyone studied this situation in detail and looked at what ratio of selfishness-altruism leads to the optimum flow of traffic, given that drivers in the other lanes are modeled. Is there a way to figure this out mathematically, without computer simulation?

Thank You —The preceding unsigned comment was added by 76.185.102.22 (talk • contribs) 16:47, July 24, 2007 – Please sign your posts!

Imagine a 1000-mile two-lane highway. At the far end, the left lane is closed. Traffic is light on this Sunday morning, so it is not a real bottleneck. In order to allow drivers to fully exercise their altruism, a sign is put up at the beginning: "Left lane closed ahead (1000 miles). Merge right." As it happens, that Sunday morning all drivers are in a very altruistic mood, and all merge quickly as soon as they spot the sign, and so drive the next 1000 miles in a single file, soon crawling along because the slowest driver forces the pace. Clearly not optimal. If traffic is heavy enough for the lane closure to form a real bottleneck, I see no argument why traffic flow would improve by some drivers' early merging. The delays are not caused by the merging, but by the back-up at the bottleneck, which will let the same number of cars through per time unit regardless of whether they merged late or early. For optimum flow, the drivers' behaviour is important though: rather than braking at the last minute, they should gradually slow down, but not more than necessary, to give a steady flow and to allow drivers in another lane to merge gracefully. This is a general problem in doing a mathematical analysis of the effects of certain measures on traffic flow: to use a realistic model of the variety of driver behaviours, which has many more sides to it than the selfishness–altruism dimension. --Lambiam 17:25, 24 July 2007 (UTC)[reply]

It's not only the limited capacity that slows us. We generally move faster in the one lane after the compression than in the two lanes before it, because both lanes come to a dead stop as the two drivers in front of the queue play chicken or whatever to resolve who'll go first. —Tamfang 17:56, 24 July 2007 (UTC)[reply]

I'd say in this case it's best if they're all altruistic- one single file line moving at 65mph is far more efficient than two completely stopped lanes of traffic with cars trying to merge --⁪froth^t 20:33, 24 July 2007 (UTC)[reply]

Yes this has been extensively studied, Three phase traffic theory is one model, which has links to other related articles. Alas drivers take take strategies which result in slower overall movement, overtaking causes a lot of problems. There are things which can be done to encourage better flow. I believe, reducing speed limits can result in better flow. --Salix alba (talk) 21:25, 24 July 2007 (UTC)[reply]

Don't forget that there is a human element in all this, as humans are behind the wheel! Imagine that all the altruistic drivers suddenly get very annoyed at the late-mergers and choose to let them in. Clearly then there is an advantage to merging in early. Other scenarios can be imagined based on human behaviour equally well.

I can think of at least one case where altruism slows traffic. At an intersection where I'm stopped, waiting for the other person, who has the right of way, to go, only to see them waving me on, it actually takes longer than if they had just gone ahead. StuRat 06:02, 25 July 2007 (UTC)[reply]

cf. livelock. —Preceding unsigned comment added by 149.135.42.160 (talk • contribs)

Wikipedia:Reference desk/Archives/Mathematics/2007 July 24

Contents

July 24

Infinite monkey calculations

Solving for Exact Value (trigonometric identities)

Traffic Patterns