matstat-skiplistor

1. Antal noder per nivå

a)

Låt \(A=\text{första talet som når nivå }i\). Sannolikheten att \(A\) inträffar är:

\begin{equation} P(A)=1/(2^{i})\nonumber \\ \end{equation}

b)

Elementen är ordnade sekventiellt vilket medför att det är omöjligt att flytta runt dem, exempelvis räknas \(\{a,b,c,d\}\) som \(\{b,d,a,c\}\) och vice versa. Det innebär att vi har att göra med kombinationer och inte permutationer.

Alltså kan man välja \(k\) stycken tal i nivå \(i\) (gånger):

\begin{equation} \binom{n}{k}=\frac{n!}{k!(n-k)!}\nonumber \\ \end{equation}

.

c)

Sannolikheten för att det ska finnas exakt \(k\) stycken noder på nivå \(i\) är:

\begin{equation} \binom{n}{k}2^{-ik}(1-2^{-i(n-k)})\nonumber \\ \end{equation}

där \(\displaystyle 2^{-ik}\) är när man lyckas och \((1-2^{-i(n-k)})\) misslyckas. Detta enligt multiplikationsregeln där sannolikheten för att 2 oberoende händelser sker är:

\begin{equation} P(A\cap B)=P(A)P(B)\nonumber \\ \end{equation}

\(\displaystyle\binom{n}{k}\) gäller ty det inte gäller specifika element utan vi måste räkna med antalet kombinationer av \(k\) element.

2. Värsta fallet

a)

Låt \(B=\) första talet som når nivå \(i\), men ej \(i+1\).

Sannolikheten att första talet når upp till nivå \(i\) men inte högre är:

\begin{equation} P(B)=\frac{1}{2^{i+1}}\nonumber \\ \end{equation}

Detta ty: \(p=(1-p),p=\frac{1}{2}\).

b)

\(C=\) alla \(n\) talen når nivå \(i\), men ej \(i+1\).

Sannolikheten att alla tal når upp till nivå \(i\) men inte högre är:

\begin{equation} P(C)=\frac{1}{2^{i+1^{n}}}=2^{-n(i+1)}\nonumber \\ \end{equation}

Här gäller som bekant multiplikationsregeln för varje element när vi går från a) till b) och vi har \(n\) element.

c)

\(D=\) alla \(n\) talen når samma nivå \(i\).

Sannolikheten att alla tal når upp till nivå \(i\):

\begin{equation} {\displaystyle P(D)=\sum_{i=1}^{\infty}\frac{1}{2^{in}}=\sum_{i=1}^{\infty}2^{-in}}\nonumber \\ \end{equation}

Se: b) - här gäller samma sak fast för \(i\)