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\) istället för \(i+1\), och att:

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

Vilket innebär att:

\begin{equation} P\left(\bigcup\limits_{i=1}^{n}A_{i}\right)=\sum_{i=1}^{n}P(A_{i})\nonumber \\ \end{equation}

.

3. Minnesutrymme

a)

Den stokastiska variabeln \(X\) kallas för: (Har distribution) Binomial-distribution. Vi är ute efter antal ”success” i en sekvens av oberoende händelser, alltså passar \(Binom\) bra.

PDF är:

\begin{equation} f_{X}(x)=\binom{n}{k}\left(\frac{1}{2^{i}}^{x}\right)\left(1-\frac{1}{2^{i}}\right)^{n-x}\nonumber \\ \end{equation}

\(X\) har parametrarna:

\begin{equation} X\sim Binom\left(2^{-i},n\right)\nonumber \\ \end{equation}

b)

Genom att utnyttja väntevärdet i binomialfördelningen kan vi få fram det förväntade antal noder på nivå i är:

\begin{equation} E\left[x\right]=n2^{-i}\nonumber \\ \end{equation}

c)

Förväntat totalantal noder i skiplistan är:

\begin{equation} \sum_{i=1}^{\infty}E[x]=\sum_{i=1}^{\infty}n2^{-i}=n\sum_{i=1}^{\infty}2^{-i}\nonumber \\ \end{equation}

\(i=n\) är inte summans slut ty det skulle kunna fortsätta med fler nivåer teoretiskt, även om det inte görs i praktiken.

Skiplistans höjd

a)

För att visa vad den stokastisk