If you have a situation A_B and you attempt to place a domino into the gap, then the following things may occur:

* with probability Pl, the placed domino will fall left, taking out not only itself but the entire group A
* with probability Pr, the placed domino will fall right, taking out not only itself but the entire group B
* with probability 1 - Pl - Pr, the placed domino will stand, and so will A and B

The term 'expected' is used here in it's technical probability theory sense. The expected value of some discrete random variable X is the sum {over all possible values of X } of P(X == x) * x.

In other words, you have some strategy for placing dominoes, which may be contingent on which dominoes fall (it's like a potentially infinite game tree, for a game played between you and 'nature' which makes random moves). The expected number of dominoes you need to place is the sum { over all the leaves (successful completion of an N-domino block) of your strategy } (distance to leaf * probability of path to leaf).

There are lots of introductions to basic probability theory on the net or in textbooks.




Postby marian on Fri Oct 31, 2003 11:36 pm
Are there any probability theorems that could be directly applied here? I have solved this problem, but I wonder whether it could be solved more elegantly. My approach is as follows:

I compute expected value for n=1. This is infinite sum (1+2(Pl+Pr)+3(Pl+Pr)^2+4(Pl+Pr)^3+...) which is not difficult to compute.

Then I compute expected value for n>1 assuming I have expected values for every lower n. I try to put n-th domino between two blocks of length l and r (r=n-l-1). (For every l) Expected value for such situation is: (1-(Pl+Pr))*((1+E[l]+E[r])+Pl*(2+2E[l]+E[r])+Pr*(2+2E[r]+E[l])+Pl*Pl*(3+3E[l]+E[r])+
Pl*Pr*(3+2E[l]+2E[r])+Pr*Pl*(3+2E[l]+2E[r])+Pr*Pr(3+E[l]+3E[r])+Pl*Pl*Pl(4+4E[l]+E[r])+....
Where E[l] and E[r] are expected values for n=l and n=r, respectively.

So I had to manually (on paper) compute that two infinite sums.

Is there an easier way compute that?

PS: My probability knowledge (and math in general :)) is quite poor, so I'm sorry if I'm absolutely missing the point.