The embedded spreadsheet below implements a Monte-Carlo solution (40,000 trials) to the frog jumping problem (diagram). Note that rand() returns a uniformly distributed real number on (0, 1). You can get the sheet to recalculate by typing a number in any blank cell and hitting return. The next to last column on the right calculates the square of the distance (d) from the origin to the landing spot of the final jump. The last column to the right of that one marks a 1 if that value is less than or equal to 1 and a 0 otherwise. The "# w/in 1 jump" cell (towards the left) adds up all the 1s in that last column and the "# of trials" cell on the far left records the total number of trials this sheet computes. Of course the "probability" cell (yellow) is the ratio.
The first jump is always taken to be at 0 degrees wrt the x-axis (so it always lands at x=1, y=0 (i.e. point (1, 0)), assuming the jump distance is always 1 and we started at the origin. The second jump is taken to be at an angle of θ and the 3rd jump is taken to be at an angle of φ. Note that the 2nd jump angle θ is uniformly distributed on (0, π) in the spreadsheet (to match my analytic solution), but it shouldn't make any difference if we make that (0, 2π) instead, because of the symmetry of the problem. Likewise we could restrict φ to be on (0, π), or add a facility to let the 1st jump take any distribution at all, rather than assume it always results in landing at (1, 0). The "1" in the expression for x₁ in the spreadsheet factors in that 1st jump.
If we take uniformly distributed angles on [0, 2π) for all three jumps, and plot the results, it looks something like this (500,000 trials, with the red circle being a one-jump radius from the starting location for the 1st jump). Of course the blue dots are the landing locations of the 3rd jump for each trial. (I didn't quite square up the plot, which is why it looks like an ellipse rather than a circle)
The solution here agrees with my analytic solution of 0.25. [UPDATE: I've added a derivation of my analytic (geometric) solution below the spreadsheet, but without use of Wolfram Alpha this time. Also it's formatted, so hopefully it's clear.]
You can download a copy of the spreadsheet using the control for that on the black bar at the bottom of the sheet (right side).
If you have access to Matlab or Octave (or perhaps SciLab will work too), then a Monte-Carlo solution is far easier to implement. Simply cut and paste these three lines into your console:
N = 1000000; % Note: this is the number of Monte Carlo trials
phi = rand(3,N)*2*pi;
length( find( abs( sum( cos(phi) + j*sin(phi) ) ) <= 1 ) ) / N
That will run 1-million Monte Carlo trials and print the answer (a single number) when it's done. If that makes your machine choke, reduce the value of N.
Analytic solution based on geometry
Figure 1 shows the key to solving the problem easily:
 |
| Figure 1: Key insight for analytic solution |
Figure 2 shows in the lower left corner the unit radius circle (in blue) around the frog's starting point at the origin. Each cyan colored circle are the set of all possible 3rd jump landing spots, given that the 1st jump landed at (1,0) and the second jump landed at different places described by the angle of the second jump direction $\theta$ with the x-axis. The red arcs are the section of each of those cyan colored circles that fall within 1-jump of the origin. Each red arc length is equal to the magnitude of the corresponding angle between the 1st and 2nd jump directions.
 |
| Figure 2: Each red arc is the set of possible 3rd jump landing spots within 1-jump of the origin, given a particular 2nd jump direction. The red arcs are equal to the magnitude of the angle $\theta$ between the 1st and 2nd jump directions, where I'm taking the 1st jump direction to always be at 0 degrees (i.e. coincident with the positive x-axis). |
Key insight in English:
If we define 1 unit of distance as 1 frog jump distance and assume the frog starts at the origin, then the absolute value of the the angle between the 1st and 2nd frog jump directions (which will be between 0 and $\pi$ radians) is equal to the length of the arc of a unit-radius circle (centered at the 2nd jump landing spot) which falls within 1 unit of distance of the origin. The full unit circle, centered at the 2nd landing spot, represents all the possible 3rd jump landing spots, given that particular 2nd jump landing spot. Now we just have to account for all possible angles between the 1st and 2nd jumps (i.e. all possible 2nd jump landing spots, relative to the 1st jump landing spot).
Here's an alternate way to state it:
If we look at the set of all possible 1st jump landing spots (a unit circle centered at the origin) and the set of all possible 3rd jump landing spots (a unit circle centered on the 2nd jump landing spot), then the length of the arc defined by these overlapping circles (the arc from either circle, since they both have unit radius = 1 jump distance) is equal to the absolute value of the angle between the 1st and 2nd jump directions. This overlapping arc length divided by the circumference of the circle (the circumference is $2\pi$ since it's a unit radius circle) represents the probability of the 3rd jump landing within 1-jump of the origin given a particular absolute value of the angle between the 1st and 2nd jump directions. Now we just have to account for all possible absolute values of the angle between the 1st and 2nd jump directions. The absolute value of this angle will be uniformly distributed on the interval [0, $\pi$], thus the overlapping arc length will be uniformly distributed on the interval [0, $\pi$].
See figures 1 and 2. A complete explanation follows:
Assume the frog starts at the origin of a plane, that is he starts at the point $\bar{x}_0 = 0,\, \bar{y}_0 = 0$, which I'll write as point $(0, 0)$. Also assume the frog's jumps are all a distance of one in length. After the frog jumps the first time, we'll define the ray from the origin passing through his 1st landing spot to be the positive $x$-axis of a new coordinate system $(x, y)$ sharing the origin with our original coordinate system. Thus we can write our frog's starting point ($p_0$) in this new coordinate system as $x_0 = \bar{x}_0 = 0$ and $y_0 = \bar{y}_0 = 0$, or $p_0 = (0, 0)$. We'll henceforth express all our measurements in this new coordinate system. Thus we can say the frog's first landing spot was at point $p_1 = (x = x_1, y = y_1) = (1,0)$.
Now how can we characterize possible 2nd jump landing spots for the frog? One way is with an angle $\theta \equiv \text{the angle of the frog's 2nd jump with respect to (wrt) the}\; x\text{-axis}$. Since all the results for negative $\theta$ angles are the same as for their positive $\theta$ counterparts, we can consider just the angles $\theta$ on $[0, \pi]$. So if the frog jumps at angle $\theta$ wrt the $x$-axis, where will he land? In other words, where is $p_2 = (x_2, y_2)$? The answer is:
$$x_2 = 1 + \cos(\theta)\tag 1$$
$$y_2 = \sin(\theta)\tag 2$$
Now if we knew the distance $d_2$ between this 2nd landing spot and the origin, we could calculate the the length of an arc defined by the section of the circle of radius = $1$ (centered at this 2nd landing spot) which lies inside a circle of radius = $1$ centered at the origin. This arc inside the unit radius circle centered at the origin represents all the possible 3rd jump landing spots which are within one jump of the origin given that $p_2$ is the 2nd landing spot. Call this arc length $\psi$ which we'll write $\psi(\theta)$ since it's a function of $\theta$. Furthermore, if we knew the ratio of this arc length ($\psi(\theta)$) to the total arc length of the circle (the total arc length is $2\pi$ in this case because the circle is unit radius) which represent all possible 3rd jump landing spots starting from $p_2$, then we'd know the conditional probability that the frog's 3rd jump will land him at a point $p_3 = (x_3, y_3)$ within one jump distance of his starting point $p_0 = (0, 0)$ given that his second landing place was $p_2$. First of all we note that the distance from the origin to this 3rd landing spot is $d_3 = \left\|p_3 - p_0\right\| = \left\|p_3\right\|$. Now we can write the conditional probability as $P(d_3 \le 1\, |\, p_2) = P(d_3 \le 1\, |\, \theta)$. So what is this conditional probability?
$$P(d_3 \le 1\, |\, \theta) = \frac{\psi(\theta)}{2\pi}\tag 3$$
And we can find the total probability $P(d_3 \le 1)$ that the frog's 3rd jump lands him within 1 jump of the origin by integrating the product of the conditional probability in $(3)$ with the probability density function for $\theta$ over relevant possible values for $\theta$:
$$P(d_3 \le 1) = \int_\limits{0}^{\pi} P(d_3 \le 1\, |\, \theta) p_{\theta}(\theta) d\theta \tag 4$$
where $p_{\theta}(\theta) \equiv$ the probability density function for $\theta$. What is $p_{\theta}(\theta)$? It's uniform on the interval $[0,\,\pi]$, thus $p_{\theta}(\theta) = \pi^{-1}$ for $\theta$ on $[0, \pi]$, and $0$ otherwise. Substituting this and $(3)$ into $(4)$ we have:
$$P(d_3 \le 1) = \int_\limits{0}^{\pi} \frac{\psi(\theta)}{2 \pi^2} d\theta \tag 5$$
Now if we can find an expression for $\psi(\theta)$ and integrate it, we'll be done. Looking at our diagram again, we can relate $\psi(\theta)$ to the distance $d_2$. We note that the line segment connecting $p_0$ to $p_2$ bisects the arc whose length is $\psi(\theta)$, and thus that $d_2/2$ is the base of a right triangle of angle $\alpha$ at the origin, and because the circles are all unit radius, we have $\alpha = \psi(\theta)/2$. Thus $\cos(\alpha) = \cos(\psi(\theta)/2) = d_2/2$, and thus we can write:
$$\psi(\theta) = 2 \cos^{-1}\left(\frac{d_2}{2}\right) \tag 6$$
Using $(1)$ and $(2)$ to find $d$ we have:
$$d_2 = \left\|p_2 - p_0\right\| = \left\|p_2\right\| = \sqrt{x_2^2 + y_2^2} = \sqrt{(1+\cos(\theta))^2 + \sin^2(\theta)}\tag 7$$
Evaluating the argument to the square root in $(7)$, we see that:
$$(1+\cos(\theta))^2 + \sin^2(\theta) = 1 + 2\cos(\theta) + \cos^2(\theta) + \sin^2(\theta) = 2 + 2\cos(\theta) = 2(1 + \cos(\theta)) = 2(2 \cos^2(\theta / 2)) = 4\cos^2\left(\frac{\theta}{2}\right)\tag 8$$
The only tricky bit there is that $1 + \cos(\theta) = 2 \cos^2(\theta / 2)$ which you can find in any table of trigonometric identities [4th half-angle formula down] or do like I do and sketch it out and it becomes obvious. Given $(8)$ we can rewrite $(7)$ as:
$$d_2 = \sqrt{4\cos^2\left(\frac{\theta}{2}\right)} = 2\cos\left(\frac{\theta}{2}\right)\tag 9$$
and thus $(6)$ becomes:
$$\psi(\theta) = 2 \cos^{-1}\left(\frac{2\cos\left(\frac{\theta}{2}\right)}{2}\right) = 2 \cos^{-1}\left(\cos\left(\frac{\theta}{2}\right)\right) = 2 \frac{\theta}{2} = \theta\tag {10}$$
Substituting $(10)$ into $(5)$ we have:
$$\bbox[yellow,border:1px solid red]{P(d_3 \le 1) = \int_\limits{0}^{\pi} \frac{\theta}{2 \pi^2} d\theta = \frac{1}{2\pi^2} \frac{\theta^2}{2}\Bigg|_0^{\pi} = \frac{1}{4\pi^2} (\pi^2 - 0^2) = \frac{1}{4}}\tag {11}$$
And we're done! ＼(^o^)／
Easy!!... right?! (+_+)
Well, what can I say? ¯\_(ツ)_/¯
... if you found this to be far too easy, then this might be more your speed. Enjoy!
-----------------------------------------------------------------------------------------------------------------------------
For extreme nerds, here's a script which should run in Matlab or Octave (free) to animate the frog jumping problem (beneath screen shots: click on to enlarge):
% Frog Jumping Problem visualizer (animation):
% Parameters: start
MarkerSize = 15; % for landing location dots
ArrowHeadSize = 0.05; % for arrows indicating jumps
LineWidth = 2; % For arrows and circles
p0 = [0 0]; % Origin or start of 1st jump
p1 = [1 0]; % Landing location for 1st jump
dtheta = pi/10; % delta between each angle (theta) between 1st & 2nd jump dirctions
Ntheta = 11; % Number of theta to examine
pause_length_sec = 3;
short_pause_length_sec = 0.5;
% Parameters: end
% Create data to draw a radius-1 circle:
N = 1000;
phi = [0:N]*2*pi/N;
circle = [cos(phi);sin(phi)];
% Plot starting location (P0) (the origin) as black dot and establish plot dimentions
figure(1),
plot(p0(1),p0(2),'k.','MarkerSize',MarkerSize);
text(p0(1)-0.25,p0(2)-0.15,'P_0 \equiv start (origin)');
axis equal;
xlim([-1.5 3.5]);
ylim([-1.5 2.5]);
pause(short_pause_length_sec);
% Plot blue cirle representing 1-jump distant from the origin (P0). Note this is
% also technically the set of all possible 1st jump landing locations, but the
% 1st jump landing location is always P1 = (1,0) in this animation.
figure(1), hold on;
plot(p0(1)+circle(1,:),p0(2)+circle(2,:),'b','Linewidth',LineWidth);
pause(short_pause_length_sec);
% Plot the 1st jump (blue arrow) and the 1st jump landing location P1 (blue dot):
jump1 = p1 - p0;
q = quiver(p0(1),p0(2),jump1(1),jump1(2),0,'MaxHeadSize',ArrowHeadSize,'Color',...
'blue','Linewidth',LineWidth);
pause(short_pause_length_sec);
plot(p1(1),p1(2),'b.','MarkerSize',MarkerSize);
text(p1(1)-0.3,p1(2)-0.15,'P_1 \equiv 1^{st} jump','Color','blue','BackgroundColor','white');
hold off;
pause(short_pause_length_sec);
% For each angle between the 1st jump direction and 2nd jump direction, plot the
% 2nd jump (cyan arrow), the 2nd jump landing location (P2) (cyan dot), the angle of this jump
% (in cyan, dashed), and finally the corresponding set of possible 3rd jump landing
% locations (green circle), and then re-color those 3rd jump landing locations red
% within 1-jump of the origin P0, and label the resulting red arc length.
for n=1:Ntheta
% Select the angle (theta) between the 1st and 2nd jump directions:
theta = dtheta*(n-1);
jump2 = [cos(theta) sin(theta)];
p2 = p1 + jump2;
% Plot the 2nd jump (cyan arrow) and the 2nd jump landing location (P2) (cyan dot):
figure(1), hold on;
q = quiver(p1(1),p1(2),jump2(1),jump2(2),0,'MaxHeadSize',ArrowHeadSize,...
'Color','cyan','Linewidth',LineWidth);
h = plot(p2(1),p2(2),'c.','MarkerSize',MarkerSize);
t1 = text(p2(1)-0.3,p2(2)+0.15,'P_2 \equiv 2^{nd} jump','Color','cyan',...
'BackgroundColor','white');
% Draw and label the angle between the 1st & 2nd jump locations (in cyan)
alpha = [0:N]*theta/N; % alpha is a vector of angles to draw the arc/angle
arc2 = [p1(1)+cos(alpha); p1(2)+sin(alpha)];
h2 = plot([0 1]+p1(1),[0 0]+p1(2),'c',arc2(1,:),arc2(2,:),'c--','Linewidth',LineWidth);
arc2_label_pos = arc2(:,floor(N/2));
t2 = text(arc2_label_pos(1)+0.01,arc2_label_pos(2)+0.08,...
['\theta = ' num2str(theta*180/pi) '^o = ' num2str(theta)],...
'Color','cyan','BackgroundColor','white');
pause(short_pause_length_sec);
% Calculate the set of points (d) within 1-jump of the 2nd landing spot (P2)
% which represents the set set of all possible 3rd jump landing locations
% and draw as a green circle:
d = p2(1)+circle(1,:) + j*(p2(2)+circle(2,:));
h3 = plot(real(d),imag(d),'g','Linewidth',2);
% Label as possible 3rd jump landing locations:
[m,k] = max(imag(d));
jump3_label_pos = d(k) - 0.3;
jump3_label = {{'Possible 3rd jump'},{'landing locations'}};
t4 = text(real(jump3_label_pos),imag(jump3_label_pos)+0.20,jump3_label{1},...
'Color','green','BackgroundColor','white');
t5 = text(real(jump3_label_pos)+0.01,imag(jump3_label_pos)+0.10,jump3_label{2},...
'Color','green','BackgroundColor','white');
pause(2*short_pause_length_sec);
% Draw over the segment of the green circle (possible 3rd jump landing
% locations) in red, to create a red arc indicating the sub-set of 3rd jump
% landing locations which fall within 1-jump distance of the origin (i.e.
% the possible 3rd jump landing locations that fall within the blue circle):
if theta ~= pi
% Normal case when theta is not equal to pi
k = find(abs(d)<=1);
else
% Take care of special case when theta = pi:
k = find(imag(d)<0);
end
% Plot the red arc (the possible 3rd jump landing locations <= 1 from origin):
h4 = plot(real(d(k)),imag(d(k)),'r','Linewidth',2);
% Label the length of this red arc:
if length(k) > 1
% Normal case when red arc consists of more than one point:
midk = k(floor(length(k)/2));
arc3_label_pos = d(midk)-0.6 - j*0.10;
else
% Special case when red arc is just one point or less:
arc3_label_pos = p1(1)-0.4 + j*(p1(2)+0.10);
end
t3 = text(real(arc3_label_pos),imag(arc3_label_pos),['arc = \theta = ' num2str(theta)],...
'Color','red','BackgroundColor','white');
hold off;
pause(pause_length_sec);
% Erase the items we drew associated with this value of theta to prepare
% for the next value of theta:
if n ~= Ntheta
delete(q);
delete(h);
delete(t1);
delete(h2);
delete(t2);
delete(h3);
delete(h4);
delete(t3);
delete(t4);
delete(t5);
end
end
-------------------------------------------------------------------
Below I present yet another Matlab/Octave script to extend the Monte Carlo solution of the Monte Carlo script listed earlier to cases with other numbers of frog jumps:
% Script to calculate extended solutions to the frog jumping problem
% Parameters: start
Nmc = 1000000; % Number of Monte Carlo trials
Njump_max = 10; % The maximum number of jumps to consider
% Parameters: end
% Without loss of generality assume the 1st jump always lands at point (1,0)
% and use complex numbers to represent the jump landing spots (jump_landing):
jump_landing = ones(1,Nmc);
% Print header:
disp(['Predicted and observed fractions of jumps landing within 1-jump of '...
'origin after ' num2str(Nmc) ' Monte-Carlo trials:']);
% Iterate through each number of jumps, calculate a result and print this
% result in comparison with a predicted fraction based on the pattern:
for jump = 2:Njump_max
phi = rand(1,Nmc)*2*pi;
jump_landing = jump_landing + cos(phi) + 1i*sin(phi);
fraction = sum( abs(jump_landing) <= 1) / Nmc;
disp(['After ' num2str(jump) ' jumps: predicted = '...
num2str(1/(jump+1)) '; observed = ' num2str(fraction)]);
end
And here's an example of the console output from the above script:
Predicted and observed fractions of jumps landing within 1-jump of origin after 1000000 Monte-Carlo trials:
After 2 jumps: predicted = 0.33333; observed = 0.33398
After 3 jumps: predicted = 0.25; observed = 0.24908
After 4 jumps: predicted = 0.2; observed = 0.20012
After 5 jumps: predicted = 0.16667; observed = 0.16663
After 6 jumps: predicted = 0.14286; observed = 0.14337
After 7 jumps: predicted = 0.125; observed = 0.12548
After 8 jumps: predicted = 0.11111; observed = 0.11109
After 9 jumps: predicted = 0.1; observed = 0.10011
After 10 jumps: predicted = 0.090909; observed = 0.091159
Notice any patterns (i.e. how well did the predictions do?)?
No comments :
Post a Comment