New answers tagged randomized-algorithms
1
A very simple proof: I claim that if there are d integers with values between x and y, and there are n ≥ 2 elements in the array, then the probability that x and y are compared is 2 / (d + 2), independent of n.
Proof by induction: If n = 2 then clearly d = 0, so the claim is that x and y are compared with probability 2 / (0 + 2) = 1. This is also clearly ...
1
The idea of the proof is to compute, for any two elements $x,y$ in the array, the probability that they are compared in the algorithm. This probability could potentially depend on the entire array. However, it turns out that you can compute it only given the order statistics of $x,y$, that is, their relative order in the sorted array. If you know that $x$ is ...
0
You actually can use true / false to simulate a Riffle Shuffle or Faro Shuffle:
Start with the deck of cards on the middle
Move half of the deck to the left, and half to the right
Get a boolean: if true, then move the top card from the left pile back to the middle, or if false, move that top card from the right pile back to the middle
Repeat step 3 until ...
7
As Yuval has noted, this way of randomly generating recursive data structures is known to (usually) end up with an infinite expected size.
There is, however, a solution to the problem, that allows one to weigh the recursive choices in such a way that expected size lies within a certain finite interval: Boltzmann samplers. They are based on the ...
11
Your process is a textbook example of a branching process. Starting with one $E$, we have an expected $3/2$ many $F$s, $9/4$ many $T$s, and so $9/8$ many remaining $E$s in expectation. Since $9/8 > 1$, it is not surprising that your process often failed to terminate.
To gain more information, we need to know the exact distribution of the number of $E$-...
Top 50 recent answers are included
