Colliding Bullets again

Question

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?

Answer 1

I believe the exact answer you're looking for is

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.

Answer 2

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)

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.

Answer 3

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