That was a fun problem! I solved it using QGIS 2.18 but I don't think the tools have drastically changed in 3.0.
1. Generate the lines
I won't give much details here since you already have the lines you need. I have written a script to generate these lines, but it works only up to QGIS 2.18. Needless to say, the more lines the better your estimation.
2. Create a grid
Go to Vector > Research Tools > Vector Grid (QGIS 2.18). In QGIS 3.0, it seems that you have to open the processing toolbox (Processing > Toolbox) then look for the grid tool.
For the grid extent, choose "Use layer/canvas extent" (3 dots on the right). Choose whatever cell size you want, but be prepared to face long computation times if your grid is too thin. Choose "Output grid as polygons" in "grid type".
3. Count lines by grid cell
This is a little tricky. You first have to cut your lines so that each line is split across the cells. To achieve that, use the intersection tool (Vector > Geoprocessing Tools > Intersection in both QGIS 2.18 and 3.0). Choose the line layer as "Input layer", and the grid as "Intersection layer".
To prepare the next step, we have to add a field to the layer we just obtained. Select this layer and open the field calculator; check the "create a new field option", set 'newid' as name, keep 'numeric' as type. In the "Expression" box, write
$rownum, then click OK. You will get a new field with a unique id for each line segment.
Then, we'll use the mean coordinates tool (Vector > Analysis tools > Mean coordinates in QGIS 2.18, again in the toolbox for QGIS 3.0). Set the intersected layer (from the previous operation) in the "input layer" field, and 'newid' as "Unique ID field". This gives you a point layer, each point corresponding to a line segment.
Finally, use the "Count points in polygon tool" (in Vector > Analysis tools for both QGIS 2.18 and 3.0). Set the grid in the "Polygons" field and the newly created point layer in the "Points" field. This will create a new field in the grid with the number of line segments in each grid cell. You can divide this number by the total number of lines in the field calculator if you want, if you need an estimation of line probability.
4. Example results
Obtained with 2000 lines and a uniform point repartition inside the uncertainty regions (you might want to try a gaussian repartition too).
Same uncertainty parameters, with 5000 lines and a thinner grid (took several hours to run):