7
$\begingroup$

Here's a colliding bullets problem of my own devising that's different from previous versions. Every second a gun has a 60% chance of firing a bullet in a straight line. After 10 seconds there would be a maximum possible of 10 bullets if the gun was fired every second. The gun stops possible firing after 10 seconds. If bullets collide they disappear. Bullets have a velocity randomly determined from a uniform distribution (0 to 1). What's the probability that all bullets will disappear?

$\endgroup$
12
  • $\begingroup$ Reminds me of stats.stackexchange.com/questions/204826/… $\endgroup$
    – fblundun
    Aug 17, 2023 at 14:32
  • $\begingroup$ Related: puzzling.stackexchange.com/questions/57825/… $\endgroup$
    – justhalf
    Aug 18, 2023 at 3:12
  • $\begingroup$ Do you consider the case where no bullets are fired as part of the "all bullets disappeared" case? $\endgroup$
    – acrabb3
    Aug 19, 2023 at 9:08
  • $\begingroup$ Yes, no bullets could be fired as part of the "all bullets disappeared" case. $\endgroup$
    – Bob Bixler
    Aug 19, 2023 at 11:35
  • 1
    $\begingroup$ This goes on for 10 seconds so there's a maximum possible of 10 bullets. $\endgroup$
    – Bob Bixler
    Aug 24, 2023 at 14:01

3 Answers 3

4
$\begingroup$

I believe the exact answer you're looking for is

enter image description here which is (exactly) 0.1601546044.

Explanation:

This follows from the answer to this related bullet problem (which is the product term in each of my summands). We are adding the probabilities for each case of 0, 2, 4, 6, 8, and 10 bullets fired, weighted by the probability computed via the binomial distribution of each of these cases occurring. Note that in the answer to this linked problem, the absolute speeds of the bullets do not matter but for their relative speeds compared to each other, and it does not matter that the gun in this problem may delay firing for several seconds between bullets.

This appears to corroborate Dmitry's rather than dipodomys's simulation, even if Dmitry's is flawed in design. The conclusion is at least one among the following: diopomys's simulations are flawed; my math is wrong; or my outsourced derivation is wrong, despite it being an accepted answer to the related problem. For example, to attest to the third point, I'm still not totally convinced that the inductive step of the argument for reducing n to n-2 bullets is statistically valid; see Penguino's comment in the link.

EDIT: The discrepancy has been resolved and all simulations now agree with this answer. I think it would still be nice to have a more rigorous proof for the inductive step, though.

$\endgroup$
6
  • $\begingroup$ My simulation gives .16 as well. $\endgroup$
    – Bob Bixler
    Aug 27, 2023 at 20:07
  • $\begingroup$ @BobBixler Interesting. How about for n=2, 4, 6, 8? $\endgroup$
    – Feryll
    Aug 27, 2023 at 20:46
  • 1
    $\begingroup$ @Feryll your solution does match my simulation for n =2,4,6,8 $\endgroup$
    – dipodomys
    Aug 27, 2023 at 21:51
  • $\begingroup$ n=2 .340 /// n=4 .247 /// n=6 .204 /// n=8 .179 $\endgroup$
    – Bob Bixler
    Aug 28, 2023 at 13:19
  • $\begingroup$ @BobBixler I would say that's a wrap, then. Don't forget to mark an accepted answer if you think the problem is resolved! $\endgroup$
    – Feryll
    Aug 28, 2023 at 22:02
2
$\begingroup$

Update: fixed a mistake in my code where I didn't properly account for whether the trajectory of the bullets colliding was after the bullets were fired.

I took a shot at this problem by coding up a simulation in R. I followed the first part of @Dmitry Kamenetsky's solution but took @justhalf's comment about how colliding works into account.

I'll start with an example of how we can determine when two bullets will collide. Below is an example of two bullets, one fired at 4 seconds with a speed of ~0.29 and the other fired at 6 seconds with a speed of ~0.93. They collide at ~6.9 seconds.

(Horizontal red line is the x-axis. Vertical red line is where the lines intersect) Two example bullets

We can determine when they will collide by:

time = (0.93 x 6- 0.29 x 4)/(0.93- 0.29)

Using this process, we can determine when and if each bullet collide and determine the order in which they collide. Here is my simulation process:

1. Simulate the bullets fired by drawing from a Bernoulli distribution with 10 trials and probability of 0.6. Assign a speed to each bullet (uniform distribution from 0 to 1). If there are an odd number of bullets, then stop (because then there will always be at least one bullet remaining).

2. Estimate, for all combinations of bullets, when they would collide (or not collide), ignoring all other bullets. Make sure collisions happen after both bullets are fired. (See table below for an example)

3. Determine which two bullets are the first to collide. Then, ignoring bullets we know already collided, determine which two bullets collide next.

4. Repeat step 3 until all the bullets have collided or no more bullets collide.

Here is an example of the collision table, which records when each bullet would collide: (The bottom diagonal is blank because it would just mirror the top diagonal)

Bullet 1 Bullet 2 Bullet 3 Bullet 4
Bullet 1 3.615827 10.787499
Bullet 2
Bullet 3 8.563391
Bullet 4

The first two to collide are bullets 1 and 2. Ignoring bullets 1 and 2 because they have already collided, the next to collide are bullets 3 and 4. As it turns out, bullets 1 and 3 would never collide (even without bullet 2), but bullets 1 and 4 could collide (without bullets 2 and 3).

Using this process, I performed 5,000,000 simulations. The proportion of times when there were no bullets or all the bullets disappeared was:

0.1602378

This is very close to @Feryll's answer, which I believe is correct. Splitting the simulations into 5 sets of 1,000,000, the standard deviation is

0.0007777925

@Feryll's solution is within my result plus or minus the standard deviation.

$\endgroup$
5
  • $\begingroup$ Nice simulating. For reference, a binomial distribution with n = 100,000 trials with such a mean has standard deviation ~0.0013, so the true answer should be within 1% of this estimate. $\endgroup$
    – Feryll
    Aug 26, 2023 at 21:31
  • $\begingroup$ Actually, your simulation seems to disagree with my mathematically derived value. You might like to compare my formula with your code for smaller cases (e.g. merely n=2 bullets) to see which of us is mistaken. $\endgroup$
    – Feryll
    Aug 27, 2023 at 2:09
  • $\begingroup$ Good idea. The formula and my simulation agree when n = 2, both giving 0.34. However, they disagree when n is greater than 2. At n = 4, the simulation gave 0.259, and the formula gave 0.247. I suspect that this has to do with gaps between bullets. For instance, when only 4 bullets are fired consecutively, the probability is 0.375. However, if there is a gap of 2 seconds between bullets 1 and 2, the probability (via simulation )is ~0.3858. $\endgroup$
    – dipodomys
    Aug 27, 2023 at 3:37
  • $\begingroup$ I see. I will put some effort into solving the n=4 case with rigor, and see if it agrees with the formula or your simulation. Feel free to attempt it alongside me. $\endgroup$
    – Feryll
    Aug 27, 2023 at 4:52
  • $\begingroup$ I take that back ... turns out my code was wrong when there were gaps between bullets. $\endgroup$
    – dipodomys
    Aug 27, 2023 at 21:46
0
$\begingroup$

Now that I understand what you are asking, I wrote a Java program that simulates the events.

I run 1 million simulations (can be increased for more accuracy). Each simulation generates up to 10 bullets, firing them with 60% probability and assigning them a random speed between 0 and 1. Then two neighbouring bullets are destroyed (removed from the list of bullets) if the speed of the later one is greater than the speed of the earlier one. This continues until either all bullets are destroyed or there are no more collisions left. We count the number of times that all bullets get destroyed.

Now there is a major ambiguity about the order of collisions. Suppose you have 4 consecutive bullets A (0.2), then B (0.1), then C (0.5) and then D (0.8). In one interpretation only C and D collide as D is faster than C, while B can never catch A. In another interpretation C collides with B first destroying each other, then D collides with A, so all bullets die. I used the second interpretation in my code.

The probability that all bullets die is computed as

0.16

$\endgroup$
5
  • 2
    $\begingroup$ what do you mean by "ambiguity"? Surely we can calculate whether D collide with C first before C collide with B by taking into account the time between firing and the speed? $\endgroup$
    – justhalf
    Aug 26, 2023 at 3:35
  • $\begingroup$ but we don't know how speed relates to time in seconds... $\endgroup$ Aug 26, 2023 at 5:47
  • 1
    $\begingroup$ uh, only the scale matters, no? After 1s, A travels 0.2 unit, B travels 0.1 unit, whatever that unit is. Assuming C and D is 1s apart, D hits C in 5/3s, while C hits B in X/4s, where X is the number of seconds between B and C. So D hits C first only if C is fired 7+ seconds after B. $\endgroup$
    – justhalf
    Aug 26, 2023 at 6:00
  • $\begingroup$ yeah I think you are right. I'll let someone else write the correct code. $\endgroup$ Aug 26, 2023 at 7:08
  • $\begingroup$ My simulation gives .16 also. $\endgroup$
    – Bob Bixler
    Aug 27, 2023 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.