Probability of decreasing random structures

Question

Given that we have $N$ consecutive structures that can have a maximum height of $H$, where the individual height $h_i$ depends on random coin flips (for each structure, an additional height has a probability of 0.5. The probability is given by $p(h_i=x) = 0.5^{x + 1}$, except when $x=H$, then we get $p(h_i=x)=0.5^H$

Now I want to know, given $H$, what is the probability of having a random set of $N$ structures, where each structure is followed by another structure with the same height or less?

Visual Representation

Probabilities and possible structures

              +---+  +---+  +---+       +---+
0.5^x     H   |   |  |   |  |   |  ...  |   |
              +---+  +---+  +---+       +---+
               ...    ...    ...         ...
              +---+  +---+  +---+       +---+
0.0625    3   |   |  |   |  |   |  ...  |   |
              +---+  +---+  +---+       +---+
0.125     2   |   |  |   |  |   |  ...  |   |
              +---+  +---+  +---+       +---+
0.25      1   |   |  |   |  |   |  ...  |   |
              +---+  +---+  +---+       +---+
0.5       0   |   |  |   |  |   |  ...  |   |
              +---+  +---+  +---+       +---+
p(h_i=x)  h_i   1      2      3    ...    N

Structures that satisfy the search criteria

with N = 3, H = 2 (the zero height-level is always present)

(1)

+---+  +---+  +---+
|   |  |   |  |   |
+---+  +---+  +---+
|   |  |   |  |   |
+---+  +---+  +---+
|   |  |   |  |   |
+---+  +---+  +---+

(2)

+---+
|   |
+---+  +---+
|   |  |   |
+---+  +---+  +---+
|   |  |   |  |   |
+---+  +---+  +---+

(3)

+---+
|   |
+---+
|   |
+---+  +---+  +---+
|   |  |   |  |   |
+---+  +---+  +---+

(4)

+---+  +---+  +---+
|   |  |   |  |   |
+---+  +---+  +---+

...

Structures that do not satisfy the search criteria

N = 3, H = 2 (again, the zero-level is present for all structures)

(1)

+---+         +---+
|   |         |   |
+---+  +---+  +---+
|   |  |   |  |   |
+---+  +---+  +---+
|   |  |   |  |   |
+---+  +---+  +---+

(2)

+---+
|   |
+---+         +---+
|   |         |   |
+---+  +---+  +---+
|   |  |   |  |   |
+---+  +---+  +---+

(3)

+---+
|   |
+---+         +---+
|   |         |   |
+---+  +---+  +---+
|   |  |   |  |   |
+---+  +---+  +---+

(4)

              +---+
              |   |
+---+  +---+  +---+
|   |  |   |  |   |
+---+  +---+  +---+

...

Partial Solution

To my understanding (not a math-major), the first part (all structures having the same height-level) can be calculated by

$$ p(\mbox{all same level}) = \sum_{i=1}^H 0.5^{i*n} $$

But I fail to see a possibility to calculate the second part (structures with decreasing levels). Any help is greatly appreciated.

Background

The solution to this problem finds the probability of having a Skip List with the worst setup, resulting in a search-time of $O(n)$ instead of $O(log(n))$ (and thus also an insertion- and deletion time of $O(n)$).

Edit/Addition: Building the levels of the Structures

As there are some discussions in the comments, I wanted to elaborate on the process that determines the height of each structure.

The general idea is to toss a coin multiple times. If we get heads (1) that means we add a level, if we get tails (0) that means we leave the structure at the current level and move to the next structure.

In pseudo-code, we would express the algorithm like this

lvl = 0
while coin_flip() == heads:
    lvl = lvl + 1

Addition 2: Sampled probabilities

Inspired by Jens code, I wrote my own c++-function that runs 1mil. simulations per setting and computes the probabilities. You can run the code and experiment with it here: http://cpp.sh/5vtpl (alternative link at GitHub Gist).

So far I have gotten the following results

Running 1000000 simulations each:
-----------------------------------
N =   2 & H =  3 | chance = 0.671773
N =   3 & H =  3 | chance = 0.387352
N =   4 & H =  3 | chance = 0.208013
N =   5 & H =  3 | chance = 0.107015
N =   6 & H =  3 | chance = 0.054868
N =   7 & H =  3 | chance = 0.027476
N =   8 & H =  3 | chance = 0.013878
N =   9 & H =  3 | chance = 0.006773
N =  10 & H =  3 | chance = 0.003364
N =  11 & H =  3 | chance = 0.001791
N =  12 & H =  3 | chance = 0.000869
N =  13 & H =  3 | chance = 0.000439
N =  14 & H =  3 | chance = 0.000218
N =  15 & H =  3 | chance = 0.000139
N =  16 & H =  3 | chance = 0.000047
N =  17 & H =  3 | chance = 0.000022
N =  18 & H =  3 | chance = 0.000013
N =  19 & H =  3 | chance = 0.000009

Regarding your initial probabilities, the probability that the height is $0$ is $0.5$, not $1$. The first coin throw determines this. In general, $p(h_i=x)=0.5^{x+1}$, except when $x=H$, where $p(h_i=H)=0.5^{H}$. — Jens, Mar 26 '17 at 15:27
@daniel Let a coin toss be either 0 or 1. My understanding of the question is that for the 2x2 problem, I would then have the following 6 solutions, i.e. coin tosses: (1,1,1,1), (1,1,1,0), (1,1,0), (1,0,1,0), (1,0,0) and (0,0). Not sure I follow your "1,2,1,4,2,1 ways" description. — Jens, Mar 26 '17 at 20:17
@daniel Understood. You are assuming there are H tosses for each structure. I assume one stops tossing when one gets a 0 or when the max (H) is reached. Would be good to get this clarified. — Jens, Mar 26 '17 at 20:43
@Jens, you are right. If I get (1,1,0) that means two levels for the structure. That is, the first tails (or 0) limits the height of the structure. But you would repeat the tossing process for each structure. — David, Mar 26 '17 at 20:51
@David: Thanks for the clarification. May I suggest you also edit your initial probabilities? — Jens, Mar 26 '17 at 21:03
@Jens, does that clarify things? Also, I greatly appreciate your (and @daniel's) comments so far, thank you for helping. — David, Mar 26 '17 at 21:08

Jens · Answer 1 · 2017-03-27T18:32:07.250

4

I'm still looking for a closed form for the probability, but in the mean time, the following recursive Visual Basic code computes the probability:

Function PS(H As Integer, N As Integer, hs As Integer) As Double
Dim i As Integer
  PS = 0
  For i = 0 To hs
    If N = 1 Then
      PS = PS + PH(H, i)
    Else
      PS = PS + PH(H, i) * PS(H, N - 1, i)
    End If
  Next i
End Function

Function PH(H As Integer, h1 As Integer) As Double
  If h1 < H Then
    PH = 0.5 ^ (h1 + 1)
  Else
    PH = 0.5 ^ h1
  End If
End Function

To find the probability of a given $H$ and $N$ just use

Call PS(H,N,H)

The algorithm above is based on the symmetry of the solutions. In the following I will use $H=3$ as an example. If we write the solutions for $N=1$ to $N=3$ (I know $N=1$ shouldn't really be included, but bear with me), we get:

The colors to the right of each solution set show the parts of that solution set which are reused in the solution set for $N+1$. Thus, the solution set for $N=2$ reuses bits from the solution set of $N=1$, namely $(3,2,1,0)$ (yellow), and $(2,1,0)$ (orange) and $(1,0)$ (green) and $(0)$ (blue). I haven't included the solution set for $N=4$, but the colors to the right of $N=3$ show what would have been reused for that solution set.

In the algorithm, the function PS(H,N,hs) returns the summed probability of the heights represented by a color, with hs being the largest height. Thus, PS(3,1,2) would be the summed probability of structures of heights $2$, $1$ and $0$, corresponding to the orange part to the right of $N=1$. PS(3,2,2) would be the summed probability of structures represented by the orange part to the right of $N=2$.

The function PH simply calculates the probability of a structure having a given height.

Using the algorithm, here are some exact probabilities:

N = 2 & H = 3 | chance = $\frac{43}{64}$

N = 3 & H = 3 | chance = $\frac{198}{512}$

N = 4 & H = 3 | chance = $\frac{849}{4096}$

N = 5 & H = 3 | chance = $\frac{3516}{32768}$

N = 6 & H = 3 | chance = $\frac{14311}{262144}$

edited Mar 27 '17 at 18:32

answered Mar 26 '17 at 23:31

Jens

5,686
2
20
38

Very nice code. Thanks for the hint. Now you've outrun me. I wanted to post something similar as well (see edit to the question). – David Mar 27 '17 at 06:09
I checked N=H=3 and got the same result. Would be interested in seeing closed form for (say) N=H, but doesn't look very easy. +1 – daniel Mar 27 '17 at 19:20
@David: Thanks! And nice to see that your statistical numbers align nicely with the exact probabilities from my algorithm. – Jens Mar 27 '17 at 20:24
@daniel: Thanks for the +1! I feel that a closed form is just beyond my fingertips. Here's hoping that one of the really "heavy-hitters" will show up and make us kick ourselves for the simplicity of their answer. :-) – Jens Mar 27 '17 at 20:30
1

@Jens, thank you for the explanation and most of all, for your time. On a side note, its interesting to see, that for larger $H$, the recursive function takes a lot of time to compute (the simulation is faster in this area...), but for cases with $H>3$ the values differentiate only a tiny bit. Nonetheless very helpful! If its okay with you, I would leave the bounty for roughly two more days, if no one can find a better solution, I will reward it to you. – David Mar 28 '17 at 06:30
For H=N = 2,3,4,5, FIW I get the following probabilities: 11/ 16, 99/ 256, 13377/ 65536, 880757/ 8388608. If these are correct maybe someone can see a pattern (not me). – daniel Mar 28 '17 at 18:24
@David: You're welcome. Your question was a puzzle and I like solving puzzles. In regard to the bounty, I suggest you let it run it's course (all 7 days). There is often a flurry of activity as a bounty deadline is about to close and I would really like to see if a closed form solution is possible (since I can't seem to find one myself). – Jens Mar 28 '17 at 22:09
1

@daniel: FYI, the algorithm gives the same probabilities. – Jens Mar 28 '17 at 22:13

score 1 · Answer 2 · answered Mar 30 '17 at 19:35

An alternative way of viewing things:

Initially, we start with all buildings at height $0$. Then we flip a coin for each building. The ones that come up tails, we stop their growth. The ones that come up heads, we grow by $1$ and flip another coin. We continue this process for $H$ steps.

Let $f(n,H)$ be the probability that in this process we finish with all the buildings in non-increasing order of height. For this to happen, what we need is that at each step the subset of coins which comes up heads is $\{1,\dots,s\}$ for some $s$. Considering all possible values of $s$, this leads to the recursion $$f(n,H)=2^{-n} \sum_{s=0}^n f(s,H-1)$$ Our base cases are $$f(n,0)=f(0,H)=f(1,H)=1$$ There's a few special cases where this lets us get a closed form pretty straightforwardly:

Small, fixed $n$. For example, for $n=2$ the recursion simplifies down to $$f(2,H)=\frac{1}{4}\left(f(0,H-1)+f(1,H-1)+f(2,H-1)\right) = \frac{1}{2} + \frac{1}{4} f(2,H-1)$$ Using our base case $f(2,0)=0$ and solving the recursion gives $$f(2,H)=\frac{2}{3}+\left(\frac{1}{3}\right)\left(\frac{1}{4}\right)^{H}$$ Similarly, for $n=3$ the recursion becomes \begin{eqnarray*} f(3,H)&=&\frac{1}{8}\left(f(0,H-1)+f(1,H-1)+f(2,H-1)+f(3,H-1)\right) \\ &=& \frac{1}{3} + \left(\frac{1}{24}\right)\left(\frac{1}{4}\right)^{H-1}+\frac{1}{8}f(3,H-1) \end{eqnarray*} Solving this recursion gives $$f(3,H)=\frac{8}{21}+\frac{1}{3}\left(\frac{1}{4}\right)^H+\frac{2}{7}\left(\frac{1}{8}\right)^H$$
Asymptotically as $H \rightarrow \infty$. If we let $$g(n)=\lim_{H \rightarrow \infty} f(n,H)$$ (which exists, since $f(n,H)$ is decreasing in $H$), then the above recursion implies that $$g(n) = 2^{-n} \sum_{s=0}^n g(s), \, \, \, \, \, \, \, g(1)=1$$ The solution to this recursion seems to be $$g(n)=\frac{2^{n(n-1)/2}}{\prod_{s=1}^n (2^{s}-1) }.$$ (I've only checked this for numerical examples, not verified it formally).