# Taking snapshots from a stream

Dominik Bojko,
<EMAIL_ADDRESS>Jacek Cichoń,
<EMAIL_ADDRESS>
Wroclaw University of Science and Technology,
Faculty of Fundamental Problems of Technology,
pl. Grunwaldzki 13, 50-377 Wroclaw, Poland

(June 2022)

###### Abstract

This work is devoted to a certain class of probabilistic snapshots for
elements of the observed data stream. We show you how one can control their
probabilistic properties and we show some potential applications. Our solution
can be used to store information from the observed history with limited
memory. It can be used for both web server applications and Ad hoc networks
and, for example, for automatic taking snapshots from video stream online of
unknown size.

##  1 Introduction

Suppose that we are observing a stream $x_{1},x_{2},\ldots$ of data. Our goal
is to keep an element from this stream with a prescribed position. For
example, we may want to keep the element $x_{i}$ with index $i$ close to
$\left\lfloor n/2\right\rfloor$ after reading first $n$ elements from the
stream. Of course this problem is trivial if we have a direct access to all
elements $x_{1},\ldots,x_{n}$. But in the case of large amount of data keeping
all information into memory is expensive or undesirable. Suppose hence that
our memory resources are limited.

In this article we investigates series of randomized procedures which allow us
to choose elements located near the required position in the stream of data.
All these procedures are based on the same schema. They only differs on a
sequence $(\alpha_{n})$ of probabilities which are used for control of changes
of stored data. In each cases we will have $\alpha_{1}=1$. We will use three
variables: $K$, $n$ and $data$. Initially we put $K=0$, $n=0$ and we set
$data$ as nil value:

    Initialization: K:= 0; n:= 0; data:= nil;

After reading an element $x$ from the stream we call the following update
procedure:

    procedure Update(x)
      n:= n+1
      if (random() <= a(n))
      begin
        K:= 1;
        data: = x
      end else begin
        K:= K+1
      end
    end

In the procedure Update we used the function random() which is high quality
pseudo-random generator of random reals from the interval $[0,1]$. The
function $a(n)$ represents the probabilities sequence $(\alpha_{n})$. We call
the variable $K$ a probabilistic snapshot from data stream.

#### Connection with reservoir sampling

This class of algorithms may be treated as a subclass of reservoir sampling
algorithms with reservoir of size 1 (see [Tillé(2006)]). Suppose that we use
this procedure with the sequence $\alpha_{n}=\frac{1}{n}$. In this case we
obtain the classical Jeffrey Vitter’s Algorithm R published in [Vitter(1985)].
Let $K_{n}$ denotes value of the random variable $K$ after reading $n$ items
from the stream. It is well known that in this case (i.e. when
$\alpha_{n}=\frac{1}{n}$) we have $\Pr[K_{n}=i]=\frac{1}{n}$ for each
$i\in\\{1,\ldots,n\\}$, i.e. that the random variable $K_{n}$ has the uniform
distribution on the set $\\{1,\ldots,n\\}$. Therefore $E[K_{n}]=(n+1)/2$.

#### Applications

Here we show some possible applications of methods discussed in Section 4:

  * •

The solution proposed in this paper may by used for storing fixed number of
snapshots from an observed movie of unknown length. For example we may want to
store short samples of the movie taken at times closed to $0$,
$\frac{1}{10}T$, $\frac{2}{10}T$ …$\frac{9}{10}T$, $T$ from a movie of length
$T$.

  * •

We may need a sample of data from times close to $n$, $n-C$, $n-2\cdot C$,…,
$n-k\cdot C$, where $n$ is an index of current item, $C$ is a fixed distance
and $k$ is a reasonably small natural number.

  * •

We may need to observe a sample from stock market in such a way that the
snapshots from the past should be less rare than snapshots from times close to
the present.

###  1.1 Mathematical notations and background

  * •

We denote by $\mathrm{E}\left[X\right]$ the expected value of the random
variable $X$.

  * •

Let us recall that a discrete random variable $X$ has geometric distribution
with parameter $p\in[0,1]$ ($X\sim\mathrm{Geo}(p)$) if $P[X=k]=(1-p)^{k-1}p$
for $k\geq 1$. If $X\sim\mathrm{Geo}(p)$ then
$\mathrm{E}\left[X\right]=\frac{1}{p}$.

  * •

A random variable $Y$ has an exponential distribution with parameter $g$
($Y\sim\mathrm{Exp}\left(\lambda\right)$) if its support is $[0,\infty)$ and
$\Pr[Y>x]=e^{-\lambda x}$ for each $x\geq 0$. If
$Y\sim\mathrm{Exp}\left(\lambda\right)$ then
$\mathrm{E}\left[Y\right]=\frac{1}{\lambda}$.

  * •

A random variable $Z$ has the Beta distribution with parameters $a,b>0$
($Z\sim\mathrm{B}(a,b)$) if its support is $[0,1]$ and its density is given by
the function $f(x)=\frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}x^{a-1}(1-x)^{b-1}$,
where $\Gamma(x)$ is the standard generalization of the factorial function. If
$Z\sim\mathrm{B}(a,b)$ then $\mathrm{E}\left[Z\right]=\frac{a}{a+b}$.

  * •

A sequence $X_{1},X_{2},\ldots$ of real-valued random variables is said to
converge in distribution if $\lim_{n\to\infty}F_{n}(x)=F(x)$, for every number
$x\in\mathbb{R}$ at which the function $F$ is continuous, where $F_{n}$ and
$F$ are the cumulative distribution functions of random variables $X_{n}$ and
$X$, respectively.

  * •

We denote by $H_{n}$ the $n$-th harmonic number, i.e.
$H_{n}=\sum_{i=1}^{n}\frac{1}{i}$. We will use the following well known
approximation $H_{n}=\ln(n)+\gamma+\mathrm{O}\left(\frac{1}{n}\right)$, where
$\gamma\approx 0.577$ is the Euler - Mascheroni constant.

  * •

We denote by $H_{n,a}$ the $n$-th harmonic number in power $a$, i.e.
$H_{n,a}=\sum_{i=1}^{n}\frac{1}{i^{a}}$. If $a\neq 1$ and positive, then the
following formula is useful:

$\displaystyle
H_{n,a}-H_{k,a}=\frac{n^{1-a}-k^{1-a}}{1-a}+f^{(a)}(k)+\mathrm{O}\left(1\right)~{},$

as $n\rightarrow\infty$, where $|f^{(a)}(k)|\leq k^{-a}$.

  * •

In this paper $\zeta$ is Riemann’s Zeta function, defined as
$\zeta(z)=\sum_{n=1}^{\infty}n^{-z}$ (for $Re(z)>1$).

  * •

By $\mathrm{Ei}(x)$ we denote Exponential Integral, defined as
$-\int_{-x}^{\infty}\frac{e^{-t}dt}{t}$. By $mathrm{E}_{1}(x)$ we denote the
First Exponential Integral, defined as $\int_{1}^{\infty}\frac{e^{-xt}dt}{t}$.
These functions have foregoing property $\mathrm{Ei}(x)=-\mathrm{E}_{1}(-x)$.

  * •

We will use the following inequalities (extension of the classical
Weierstarass product inequality):

$1-\sum_{i=1}^{n}x_{i}\leq\prod_{i=1}^{n}(1-x_{i})<1-\sum_{i=1}^{n}x_{i}+\sum_{1\leq
i<j\leq n}x_{i}x_{j}.$

which holds for any sequence $x_{1},\ldots,x_{n}$ of real numbers from the
interval $[0,1]$ (see [Klamkin and Newman(1970)]).

##  2 General Properties

Let us fix sequence $\alpha_{n}$ of reals from interval $[0,1]$ such that
$\alpha_{1}=1$. Let us consider the sequence $K_{n}$ of consecutive integers
tracing the value of the variable $K$ during the run of the Algorithm 1 with
controlling sequence $\alpha_{n}$. Clearly we have $1\leq K_{n}\leq n$ for
each $n$.

Notice that $\Pr[K_{1}=1]=1$, $\Pr[K_{n}=1]=\alpha_{n}$ and

$\Pr[K_{n+1}=k+1]=(1-\alpha_{n})\Pr[K_{n}=k]$ (1)

The following formula may be derived from the previous one

$\Pr[K_{n}=k]=\alpha_{n-k+1}\prod_{i=n-k+2}^{n}(1-\alpha_{i})~{}.$ (2)

Moreover

$\Pr[K_{n}\geq k]=\prod_{i=n-k+2}^{n}(1-\alpha_{i})$ (3)

######  Example 1.

Let us consider the case when $\alpha_{n}=\frac{1}{n}$. We claim that
$\Pr[K_{n}=k]=\frac{1}{n}$ for each $n$ and $k\in\\{1,\ldots,n\\}$. Indeed,
$\Pr[K_{1}=1]=1$. Let us assume that $\Pr[K_{n}=k]=\frac{1}{n}$ for each $k$.
Then $\Pr[K_{n+1}=1]=\frac{1}{n+1}$ and

$\Pr[K_{n+1}=k]=(1-\alpha_{n+1})\Pr[K_{n}=k-1]=\left(1-\frac{1}{n+1}\right)\frac{1}{n}=\frac{n}{n+1}\frac{1}{n}=\frac{1}{n+1}~{},$

for $k\in\\{2,\ldots,n+1\\}$. Notice that we just reconstructed the mentioned
result from [Alon et al.(1999)Alon, Matias, and Szegedy]: the random variable
$K_{n}$ in this case is uniformly distributed on the set $\\{1,\ldots,n\\}$.
Therefore $\mathrm{E}\left[K_{n}\right]=\frac{1+n}{2}$, so the expected value
of $K_{n}$ is precisely the middle of the set $\\{1,\ldots,n\\}$.

The sequence $\mathrm{E}\left[K_{n}\right]$ satisfies simple linear first
order difference equation:

######  Theorem 1.

$\mathrm{E}\left[K_{n+1}\right]=1+(1-\alpha_{n+1})\mathrm{E}\left[K_{n}\right]$

###### Proof.

Let $\beta_{n}=1-\alpha_{n}$. The proof follows directly from the recurrence
(1):

$\displaystyle\mathrm{E}\left[K_{n+1}\right]=\sum_{k=1}^{n+1}k\cdot
p^{n+1}_{k}=\alpha_{n}+\sum_{k=2}^{n+1}k\cdot
p^{n+1}_{k}=\alpha_{n}+\sum_{k=2}^{n+1}k\cdot(1-\alpha_{n+1})p^{n}_{k-1}=$
$\displaystyle\alpha_{n}+\beta_{n+1}\sum_{k=1}^{n}(k+1)\cdot
p^{n}_{k}=\alpha_{n}+\beta_{n+1}\sum_{k=1}^{n}k\cdot
p^{n}_{k}+\beta_{n+1}\sum_{k=1}^{n}\cdot p^{n}_{k}=$
$\displaystyle\alpha_{n}+\beta_{n+1}\sum_{k=1}^{n}k\cdot
p^{n}_{k}+\beta_{n+1}=1+(1-\alpha_{n+1})\mathrm{E}\left[K_{n}\right]~{}.$

∎

We shall also use the variable $L_{n}=(n+1)-K_{n}$. From formula (2) we
immediately get

$\Pr[L_{n}=k]=\alpha_{k}\prod_{i=0}^{n-k-1}(1-\alpha_{n-i})$ (4)

###  2.1 Monotonicity of expected value, related to $\alpha_{n}$

Let’s consider two sequences of probabilities of a saving of $n$-th data:
$(\alpha_{n})$ and $(\alpha^{\prime}_{n})$, one majorized by another, in
particular: $(\forall n\in\mathbb{N})\quad
0\leq\alpha_{n}\leq\alpha^{\prime}_{n}\leq 1$. Random processes
$(K_{n})_{n\in\mathbb{N}}$ and $(K^{\prime}_{n})_{n\in\mathbb{N}}$ are
corresponding to sequences $(\alpha_{n})$ and $(\alpha^{\prime}_{n})$
respectively, f.e. $P(K_{n}=1)=\alpha_{n}$ and
$P(K^{\prime}_{n}=1)=\alpha^{\prime}_{n}$. We show that then
$\mathrm{E}\left[K_{n}\right]\geq\mathrm{E}\left[K^{\prime}_{n}\right]$. The
proof is a simple induction —
$\mathrm{E}\left[K_{1}\right]=\mathrm{E}\left[K^{\prime}_{1}=1\right]$ for any
sequences of probabilities. Now, assume that
$\mathrm{E}\left[K_{n}\right]\geq\mathrm{E}\left[K^{\prime}_{n}\right]$ for
some $n\in\mathbb{N}$. Then
$\mathrm{E}\left[K_{n+1}\right]=1+(1-\alpha_{n+1})\mathrm{E}\left[K_{n}\right]\geq
1+(1-\alpha^{\prime}_{n+1})\mathrm{E}\left[K^{\prime}_{n}\right]=\mathrm{E}\left[K^{\prime}_{n+1}\right]$.

##  3 Special cases

In this section we will consider some examples of sequences $(\alpha_{n})$
which may have applications for controlling the history of a massive streams
of data. The case $\alpha_{n}=\frac{1}{n}$ was analyzed in Example 1 and the
generated pointers (i.e. the values of the random variables $K_{n}$) may be
treated as controllers of behavior of a stream at position $\frac{n}{2}$ after
reading $n$ items. In a series of four subsections we shall analyze behavior
of the random variable $K_{n}$ for sequences of the form
$\alpha_{n}=\min\\{1,\frac{g}{n^{\alpha}}\\}$ for various fixed parameters
$\alpha$. This is a summary of our results:

  * •

if $\alpha=0$ and $g\in(0,1)$ then the random variable $K_{n}$ converges in
distribution to the geometric distribution $\mathrm{Geo}(g)$, hence
$\mathrm{E}\left[K_{n}\right]\sim\frac{1}{g}$

  * •

if $\alpha\in(0,1)$ then the random variable $\frac{K_{n}}{n^{\alpha}}$
converges in distribution to exponential distribution $\mathrm{Exp}(g)$, hence
$\mathrm{E}\left[K_{n}\right]\sim\frac{n^{\alpha}}{g}$

  * •

if $\alpha=1$ then the random variable $\frac{K_{n}}{n}$ converges in
distribution to the beta distribution $\mathrm{Beta}(1,g)$, hence
$\mathrm{E}\left[K_{n}\right]\sim\frac{n}{g+1}$

  * •

if $\alpha\in(1,2)$ then
$\mathrm{E}\left[L_{n}\right]=\frac{g}{2-\alpha}n^{2-\alpha}+\mathrm{O}\left(\max\\{1,1\\!\\!1_{\\{\frac{3}{2}\\}}(\alpha)\ln{n},n^{3-2\alpha}\\}\right)$

  * •

if $\alpha=2$ then
$\mathrm{E}\left[L_{n}\right]=g\ln(n)+\mathrm{O}\left(1\right)$

  * •

if $\alpha>2$ then $\mathrm{E}\left[L_{n}\right]=\mathrm{O}\left(1\right)$.

###  3.1 Fixed value

Let us fix a real number $a>1$ and let $\alpha_{n}=\frac{1}{a}$ for each
$n>1$. In this case we have a closed formula for $E[K_{n}]$, namely, from Eq.
(2) we immediately get

$\Pr[K_{n}=k]=\begin{cases}\frac{1}{a}(1-\frac{1}{a})^{k-1}&:1\leq k<n\\\
(1-\frac{1}{a})^{n-1}&:k=n\end{cases}$

From this formula we deduce that

  1. 1.

The sequence $(K_{n})$ of random variables converges in distribution to the
geometrical distribution with parameter $\frac{1}{a}$.

  2. 2.

$E[K_{n}]=a\left(1-\left(\frac{a-1}{a}\right)^{n}\right)$

Therefore the generated pointer may be used for controlling a behavior of a
stream at a fixed position in the past.

###  3.2 Sublinear Case

In this section we consider the case when
$\alpha_{n}=\min\\{1,\frac{g}{n^{\alpha}}\\}$ for some fixed $g>0$ and
$\alpha\in(0,1)$. We shall show that the normalized random variable
$\frac{K_{n}}{n^{\alpha}}$ converges in distribution to the exponential
$\mathrm{Exp}\left(g\right)$ distribution.

######  Theorem 2.

Let $g>0$ and $\alpha\in(0,1)$. Let
$\alpha_{n}=\min\\{1,\frac{g}{n^{\alpha}}\\}$ and let $x>0$. Then

$\lim_{n\to\infty}\Pr\left[\frac{K_{n}}{n^{\alpha}}\leq
x\right]=1-e^{-gx}~{}.$

###### Proof.

Let $k=\lfloor n^{\alpha}x\rfloor$. Using formula (3) we obtain

$\displaystyle\Pr\left[\frac{K_{n}}{n^{\alpha}}>x\right]=\Pr[K_{n}>n^{\alpha}x]=\Pr[K_{n}>k]=\prod_{i=n-k+1}^{n}\left(1-\frac{g}{i^{\alpha}}\right)$

(for sufficiently large $n$). Therefore

$\displaystyle\Pr\left[\frac{K_{n}}{n^{\alpha}}>x\right]<\left(1-\frac{g}{n^{\alpha}}\right)^{k}\leq\left(1-\frac{g}{n^{\alpha}}\right)^{n^{\alpha}x-1}$

and

$\displaystyle\Pr\left[\frac{K_{n}}{n^{\alpha}}>x\right]>\left(1-\frac{g}{(n-k+1)^{\alpha}}\right)^{k}>\left(1-\frac{g}{(n-\lfloor
n^{\alpha}x\rfloor)^{\alpha}}\right)^{n^{\alpha}x}=$
$\displaystyle\left(1-\frac{g/(1-\lfloor
n^{\alpha}x\rfloor/n)}{n^{\alpha}}\right)^{n^{\alpha}x}~{},$

so we see that both bounds on $\Pr\left[\frac{K_{n}}{n^{\alpha}}>x\right]$
converges to the same limit $e^{-gx}$ when $n$ tends to infinity. ∎

######  Theorem 3.

If $g>0$, $\alpha\in(0,1)$ and $\alpha_{n}=\min\\{1,\frac{g}{n^{\alpha}}\\}$
then
$\lim_{n\to\infty}\mathrm{E}\left[\frac{K_{n}}{n^{\alpha}}\right]=\frac{1}{g}$.

###### Proof.

From Theorem 2 and Fatou’s Lemma we get
$\frac{1}{g}\leq\liminf_{n\to\infty}\mathrm{E}\left[\frac{K_{n}}{n^{\alpha}}\right]$.
On the other hand, inequality (5) bears (for sufficiently large
$n>g^{1/\alpha}$):

$\mathrm{E}\left[\frac{K_{n}}{n^{\alpha}}\right]=\int\limits_{0}^{\infty}\Pr\left[\frac{K_{n}}{n^{\alpha}}>t\right]dt\leq\int\limits_{0}^{\infty}\left(1-\frac{g}{n^{\alpha}}\right)^{n^{\alpha}t-1}dt=-\frac{1}{(n^{\alpha}-g)\ln(1-\frac{g}{n^{\alpha}})}\stackrel{{\scriptstyle
n\rightarrow\infty}}{{\longrightarrow}}\frac{1}{g}~{}.$

∎

######  Corollary 1.

If $g>0$ and $\alpha_{n}=\min\\{1,\frac{g}{n}\\}$ then
$\mathrm{E}\left[K_{n}\right]=\frac{n^{\alpha}}{g}+\mathrm{o}(n^{\alpha})$.

#### Remark

We know a more precise results in some special cases. For example, if
$\alpha_{n}=\frac{1}{\sqrt{n}}$ then
$\mathrm{E}\left[K_{n}\right]=\sqrt{n}-\frac{1}{2}+\frac{1}{2\sqrt{n}}+\frac{1}{8n}+\mathrm{O}\left(\frac{1}{n^{3/2}}\right)$.

###  3.3 Linear Case

In this section we consider the case when $\alpha_{n}=\min\\{1,\frac{g}{n}\\}$
for some fixed $g>0$. We shall show that the normalized random variable
$\frac{K_{n}}{n}$ converges in distribution to the Beta(1,g) distribution.

######  Theorem 4.

Let $g>0$. Let $\alpha_{n}=\min\\{1,\frac{g}{n}\\}$ and let $x\in(0,1)$. Then

$\lim_{n\to\infty}\Pr\left[\frac{K_{n}}{n}\leq x\right]=1-(1-x)^{g}~{}.$

###### Proof.

Let $k=\lfloor nx\rfloor$. Then we have

$\displaystyle\Pr\left[\frac{K_{n}}{n}>x\right]=\Pr[K_{n}>nx]=\Pr[K_{n}>k]=\prod_{i=n-k+1}^{n}(1-\alpha_{i})~{}.$

Therefore, for sufficiently large $n$, we have

$\displaystyle\Pr\left[\frac{K_{n}}{n}>x\right]=\prod_{i=n-k+1}^{n}\left(1-\frac{g}{i}\right)~{}.$

Hence

$\displaystyle\ln\left(\Pr\left[\frac{K_{n}}{n}>x\right]\right)=-\sum_{i=n-k+1}^{n}\ln\left(\frac{1}{1-\frac{g}{i}}\right)=-\sum_{i=n-k+1}^{n}\sum_{a\geq
1}\frac{1}{a}\left(\frac{g}{i}\right)^{a}=$
$\displaystyle-g\sum_{i=n-k+1}^{n}\frac{1}{i}-\sum_{a\geq
2}\frac{g^{a}}{a}\sum_{i=n-k+1}^{n}\frac{1}{i^{a}}~{}.$

Notice that $\sum_{i=n-k+1}^{n}\frac{1}{i}=H_{n}-H_{n-k}$, and

$-g(H_{n}-H_{n-k})=-g\left(\ln(n)-\ln(n-k)+\mathrm{O}\left(\frac{1}{n}\right)+\mathrm{O}\left(\frac{1}{n-\lfloor
nx\rfloor}\right)\right)=\ln\left(\frac{n-\lfloor
nx\rfloor}{n}\right)^{g}+O\left(\frac{1}{n}\right)$

Therefore $\lim_{n\to\infty}(-g(H_{n}-H_{n-\lfloor
nx\rfloor}))=\ln((1-x)^{g})$. Let $A_{n,k}=\sum_{a\geq
2}\frac{g^{a}}{a}\sum_{i=n-k+1}^{n}\frac{1}{i^{a}}$. Then

$\displaystyle 0<A_{n,k}<\sum_{a\geq
2}g^{a}\sum_{i=n-k+1}^{\infty}\frac{1}{i^{a}}=\sum_{i=n-k+1}^{\infty}\sum_{a\geq
2}\frac{g^{a}}{i^{a}}=\sum_{i=n-k+1}^{\infty}\frac{g^{2}}{i^{2}}\frac{1}{1-\frac{g}{i}}<2g^{2}\sum_{i=n-k+1}^{\infty}\frac{1}{i^{2}}$

(the last inequality holds for $n>\frac{2g}{1-x}$), hence

$A_{n,k}<2g^{2}\sum_{i=n-k+1}^{\infty}\frac{1}{i(i-1)}=\frac{2g^{2}}{n-k}=\frac{2g^{2}}{n-\lfloor
nx\rfloor}=\mathrm{O}\left(\frac{1}{n}\right)~{}.$

Thus

$\ln\left(\Pr\left[\frac{K_{n}}{n}>x\right]\right)=\ln\left(1-\frac{\lfloor
nx\rfloor}{n}\right)^{g}+\mathrm{O}\left(\frac{1}{n}\right).$

Therefore

$\Pr\left[\frac{K_{n}}{n}>x\right]=\left(1-\frac{\lfloor
nx\rfloor}{n}\right)^{g}e^{\mathrm{O}\left(\frac{1}{n}\right)}=\left(1-\frac{\lfloor
nx\rfloor}{n}\right)^{g}+\mathrm{O}\left(\frac{1}{n}\right)~{},$

so $\lim_{n\to\infty}\Pr\left[\frac{K_{n}}{n}>x\right]=(1-x)^{g}$. ∎

######  Corollary 2.

If $g>0$ and $\alpha_{n}=\min\\{1,\frac{g}{n}\\}$ then
$\lim_{n\to\infty}\mathrm{E}\left[\frac{K_{n}}{n}\right]=\frac{1}{g+1}$.

###### Proof.

Notice that $\frac{K_{n}}{n}\leq 1$, hence the sequence
$(\frac{K_{n}}{n})_{n\in\mathbb{N}}$ is bounded, therefore the convergence in
distribution of the sequence $(\frac{K_{n}}{n})_{n\in\mathbb{N}}$ to a random
variable $Y$ with Beta(1,g) distribution implies the convergence of moments
(see e.g. [Billingsley(2012)]), hence

$\lim_{n}\mathrm{E}\left[\frac{K_{n}}{n}\right]=\int_{0}^{1}x\frac{d}{dx}\left(1-(1-x)^{g}\right)dx=\frac{1}{1+g}~{}.$

∎

######  Corollary 3.

If $g>0$ and $\alpha_{n}=\min\\{1,\frac{g}{n}\\}$ then
$\mathrm{E}\left[K_{n}\right]=\frac{n}{g+1}+\mathrm{o}(n)$.

#### Remark

A slightly more complicated calculus shows that in the case considered in this
section we have
$\mathrm{E}\left[K_{n}\right]=\frac{n+1}{g+1}+\mathrm{O}\left(\frac{1}{n^{g}}\right)$.

###  3.4 Subquadratic Case

In this section we consider the case when
$\alpha_{n}=\min\\{1,\frac{g}{n^{\alpha}}\\}$ for some fixed $g>0$ and
$\alpha\in(1,2)$. We introduce an auxilliary random variable
$L_{n}:=n+1-K_{n}$. Let’s define $g_{0}=\left\lceil
g^{\frac{1}{a}}\right\rceil-1$. Realize that $\alpha_{k}=\frac{g}{k^{\alpha}}$
for $k\geq g_{0}+1$. Thus we briefly see that $Pr\left[L_{n}=k\right]=0$,
whenever $k\leq g_{0}$ and

$\displaystyle\Pr\left[L_{n}=k\right]=\displaystyle{\frac{g}{k^{\alpha}}\prod\limits_{i=0}^{n-k-1}\left(1-\frac{g}{(n-i)^{\alpha}}\right)}~{}$

otherwise.
In foregoing calculations let $k>g_{0}$. At commencement we approach a lower
bound, using standard Weierstrass’ product inequality (ref??):

$\displaystyle\Pr\left[L_{n}=k\right]\geq\frac{g}{k^{\alpha}}\left(1-\sum\limits_{i=k+1}^{n}\frac{g}{i^{\alpha}}\right)=\frac{g}{k^{\alpha}}\left(1-g(H_{n,\alpha}-H_{k,\alpha})\right)~{}.$
(5)

To find the upper limitation, we apply more precise extension of Weierstrass’
product inequality (ref??):

$\displaystyle\Pr\left[L_{n}=k\right]\leq\frac{g}{k^{\alpha}}\left(1-\sum\limits_{i=k+1}^{n}\frac{g}{i^{\alpha}}+\sum_{i=k+1}^{n-1}\sum_{j=i+1}^{n}\frac{g^{2}}{(ij)^{\alpha}}\right)\leq\frac{g}{k^{\alpha}}\left(1-\sum\limits_{i=k+1}^{n}\frac{g}{i^{\alpha}}+\frac{1}{2}\sum_{i=k+1}^{n}\sum_{j=k+1}^{n}\frac{g^{2}}{(ij)^{\alpha}}\right)~{}.$
(6)

Hence, by repeating the same trick as in (5) we attain:

$\displaystyle\Pr\left[L_{n}=k\right]\leq\frac{g}{k^{\alpha}}\left(1-g(H_{n,\alpha}-H_{k,\alpha})+\frac{g^{2}}{2}(H_{n,\alpha}-H_{k,\alpha})^{2}\right)~{}.$

We would like to find close confinements for an expected value of $L_{n}$.
We consider the limitation which is easier to analyze —

$\displaystyle\mathrm{E}\left[L_{n}\right]$
$\displaystyle\geq\sum_{k=g_{0}+1}^{n}\frac{g}{k^{\alpha-1}}\left(1-g(H_{n,\alpha}-H_{k,\alpha})\right)=g(H_{n,\alpha-1}-H_{g_{0},\alpha-1})-g^{2}\sum_{k=1}^{n}\frac{\frac{k^{1-\alpha}-n^{1-\alpha}}{\alpha-1}+f^{(a)}(k)+\mathrm{O}\left(1\right)}{k^{\alpha-1}}$
$\displaystyle\geq
g\frac{n^{2-\alpha}}{2-\alpha}-g^{2}\left[\frac{(H_{n,2\alpha-2}-H_{g_{0},2\alpha-2})}{\alpha-1}-\frac{n^{1-\alpha}}{\alpha-1}(H_{n,\alpha-1}-H_{g_{0},\alpha-1})\right]+\mathrm{O}\left(1\right)\geq$
$\displaystyle\geq\frac{gn^{2-\alpha}}{2-\alpha}-g^{2}\left[-\frac{n^{3-2\alpha}}{(\alpha-1)(2-\alpha)}+\frac{(H_{n,2\alpha-2}-H_{g_{0},2\alpha-2})}{\alpha-1}\right]+\mathrm{O}\left(1\right)=$
$\displaystyle=\left\\{\begin{array}[]{ll}\frac{gn^{2-\alpha}}{2-\alpha}-\frac{g^{2}n^{3-2\alpha}}{(3-2\alpha)(\alpha-1)}+\frac{g^{2}n^{3-2\alpha}}{(\alpha-1)(2-\alpha)}+\mathrm{O}\left(1\right)=\frac{gn^{2-\alpha}}{2-\alpha}-\frac{g^{2}n^{3-2\alpha}}{(3-2\alpha)(2-\alpha)}+\mathrm{O}\left(1\right)&;\quad\text{for
}\alpha<\frac{3}{2},\\\
\frac{gn^{2-\alpha}}{2-\alpha}-\frac{g^{2}H_{n}}{\alpha-1}+\mathrm{O}\left(1\right)&;\quad\text{for
}\alpha=\frac{3}{2},\\\
\frac{gn^{2-\alpha}}{2-\alpha}+\mathrm{O}\left(1\right)&;\quad\text{for
}\alpha>\frac{3}{2},\end{array}\right.$

as $n\rightarrow\infty$.
The second one can be attained the same way:

$\mathrm{E}\left[L_{n}\right]\leq\left\\{\begin{array}[]{ll}\frac{gn^{2-a}}{2-a}-\frac{g^{2}n^{3-2a}}{(3-2a)(2-a)}+\frac{g^{2}n^{4-3a}}{(4-3a)(3-2a)(2-a)}+\mathrm{O}\left(1\right)&;\quad\text{for
}a<\frac{4}{3},\\\
\frac{gn^{2-a}}{2-a}-\frac{g^{2}n^{3-2a}}{(3-2a)(2-a)}+\frac{g^{3}H_{n}}{2(a-1)^{2}}+\mathrm{O}\left(1\right)&;\quad\text{for
}a=\frac{4}{3},\\\
\frac{gn^{2-a}}{2-a}-\frac{g^{2}n^{3-2a}}{(3-2a)(2-a)}+\mathrm{O}\left(1\right)&;\quad\text{for
}\frac{4}{3}<a<\frac{3}{2},\\\
\frac{gn^{2-a}}{2-a}-\frac{g^{2}H_{n}}{a-1}+\mathrm{O}\left(1\right)&;\quad\text{for
}a=\frac{3}{2},\\\
\frac{gn^{2-a}}{2-a}+\mathrm{O}\left(1\right)&;\quad\text{for
}a>\frac{3}{2},\end{array}\right.$

as $n\rightarrow\infty$.
Resuming up all the cases, we obtain:

######  Corollary 4.

If $g>0$ is fixed, $\alpha\in(1,2)$ and
$\alpha_{n}=\min\\{1,\frac{g}{n^{\alpha}}\\}$, then

$\displaystyle\mathrm{E}\left[L_{n}\right]=\left\\{\begin{array}[]{ll}\frac{gn^{2-\alpha}}{2-\alpha}-\frac{g^{2}n^{3-2\alpha}}{(3-2\alpha)(2-\alpha)}+\mathrm{O}\left(\max\\{\ln
n,n^{4-3\alpha}\\}\right)&;\quad\text{for }\alpha<\frac{3}{2},\\\
\frac{gn^{2-\alpha}}{2-\alpha}-\frac{g^{2}H_{n}}{\alpha-1}+\mathrm{O}\left(1\right)&;\quad\text{for
}\alpha=\frac{3}{2},\\\
\frac{gn^{2-\alpha}}{2-\alpha}+\mathrm{O}\left(1\right)&;\quad\text{for
}\alpha>\frac{3}{2},\end{array}\right.$

as $n\rightarrow\infty$.

#### Remark

A better generalization of Weierstrass’ product inequality is known (ref??).
Notice that it could be helpful to get a more precise asymptotics for
$\mathrm{E}\left[L_{n}\right]$, when $1<\alpha\leq\frac{4}{3}$. Nevertheless,
it won’t be thorough due to the approximations of the generalized harmonic
numbers. Unfortunately this calculation is very unpleasant.

###  3.5 Quadratic Case

In this section we consider the case when
$\alpha_{n}=\min\\{1,\frac{g}{n^{2}}\\}$ for some fixed $g>0$. For
computational purpose let introduce some auxiliary symbols: $g_{0}:=\sqrt{g}$
and $h:=\lceil g_{0}\rceil$. We analyze random variable given by
$L_{n}:=n+1-K_{n}$. Our main goal is to achieve an approximation for its
expected value. It’s easy to realize that $\Pr\left[L_{n}\geq k\right]=1$,
when $k<h$. Otherwise, we use (3) to reach $\Pr\left[L_{n}\geq
k\right]=1-\prod\limits_{i=k}^{n}\left(1-\frac{g}{i^{2}}\right)$.

######  Theorem 5.

Let $g>0$ and $\alpha_{n}=\min\\{1,\frac{g}{n^{2}}\\}$. Then
$\mathrm{E}\left[L_{n}\right]=g\ln{n}+O(1)$.

###### Proof.

Commence with some simple facts. The first uses the formula for expected value
for non-negative discrete random variables:

$\displaystyle\mathrm{E}\left[L_{n}\right]=\sum\limits_{k=1}^{n}\Pr\left[L_{n}\geq
k\right]=h-1+\sum\limits_{k=h}^{n}\left(1-\frac{g}{k^{2}}\right)~{}.$ (7)

The next two apply standard integral inequalities to find some confinements
for sums:

$\displaystyle-((n+1)^{-1}-k^{-1})=\int\limits_{k}^{n+1}x^{-2}dx\leq\sum\limits_{i=k}^{n}k^{-2}\leq\int\limits_{k-1}^{n}x^{-2}dx=-(n^{-1}-(k-1)^{-1})~{}$
(8)

and

$\displaystyle\sum\limits_{i=k}^{n}e^{-\frac{g}{k}}\leq\int\limits_{h}^{n+1}e^{-\frac{g}{x}}dx~{}.$
(9)

In the last formula we received integral, which isn’t elementary function. In
order to use it, we need some additional properties of related known
integrals. It’s known that

$\int
e^{-\frac{1}{x}}dx=\mathrm{Ei}\left(-\frac{1}{x}\right)+xe^{-\frac{1}{x}}~{},$

so

$\displaystyle\int\limits_{h}^{n+1}e^{-\frac{g}{x}}dx=g\int\limits_{\frac{h}{g}}^{\frac{n+1}{g}}e^{-\frac{1}{x}}dx=g\left(\mathrm{Ei}\left(-\frac{1}{x}\right)+xe^{-\frac{1}{x}}\right)\bigg{|}_{\frac{h}{g}}^{\frac{n+1}{g}}~{}.$
(10)

We also adduce the series expansion of exponential integral

$\displaystyle\mathrm{E}_{1}(x)=-\gamma-\ln{x}-\sum\limits_{k=1}^{\infty}\frac{(-1)^{k}x^{k}}{k!k}~{}.$
(11)

Now, we find an upper bound for $\Pr\left[L_{n}\geq k\right]$ (for $k\geq h$),
using standard Weierstrass’ inequality and (8):

$1-\prod\limits_{i=k}^{n}\left(1-\frac{g}{i^{2}}\right)\leq
1-\left(1-\sum\limits_{i=k}^{n}\frac{g}{i^{2}}\right)\leq
g\left(\frac{1}{k-1}-\frac{1}{n}\right)~{}.$

From above formula and (7), we obtain:

$\mathrm{E}\left[L_{n}\right]\leq
h-1+g\sum\limits_{k=h}^{n}\left(\frac{1}{k-1}-\frac{1}{n}\right)=gH_{n}-gH_{h-2}+h-1-g+\mathrm{O}\left(n^{-1}\right)=g\ln
n+\mathrm{O}\left(1\right)~{}.$

The second limitation is more difficult. After removing the remainder of
Taylor’s formula for the function $e^{x}$, the inequality (8) provides:

$\Pr\left[L_{n}\geq k\right]\geq
1-\prod\limits_{i=k}^{n}\left(1-\frac{g}{i^{2}}\right)\geq
1-\prod\limits_{i=k}^{n}e^{-\frac{g}{i^{2}}}=1-e^{-g\sum\limits_{i=k}^{n}\frac{1}{i^{2}}}\geq
e^{\frac{g}{n+1}-\frac{g}{k}}~{}.$

Then we use the above part, the equality (7) once again and finally (9) to
attain:

$\mathrm{E}\left[L_{n}\right]\geq
h-1+\sum\limits_{k=h}^{n}\left(1-e^{\frac{g}{n+1}-\frac{g}{k}}\right)=n-e^{\frac{g}{n+1}}\sum\limits_{k=h}^{n}e^{-\frac{g}{k}}\geq
n-e^{\frac{g}{n+1}}\int\limits_{h}^{n+1}e^{-\frac{g}{x}}dx~{}.$

Remind that $\mathrm{Ei}(-y)=-\mathrm{E}_{1}(y)$ and by proceeding with (10)
and (11) we procure:

$\displaystyle\mathrm{E}\left[L_{n}\right]$ $\displaystyle\geq
n-ge^{\frac{g}{n+1}}\left[-\mathrm{E}_{1}\left(\frac{g}{n+1}\right)+\mathrm{E}_{1}\left(\frac{g}{h}\right)+\frac{n+1}{g}e^{-\frac{g}{n+1}}-\frac{h}{g}e^{-\frac{g}{h}}\right]$
$\displaystyle=n-ge^{\frac{g}{n+1}}\left[\ln\left(\frac{g}{n+1}\right)-\ln\left(\frac{g}{h}\right)+\frac{n+1}{g}e^{-\frac{g}{n+1}}-\frac{h}{g}e^{-\frac{g}{h}}+c_{g}+\mathrm{O}\left(\frac{1}{n}\right)\right]$
$\displaystyle=-1+g\left(1+\mathrm{O}\left(\frac{1}{n}\right)\right)(\ln(n+1)-\ln(h))-gc_{g}+he^{-\frac{g}{h}}+\mathrm{O}\left(\frac{1}{n}\right)=g\ln
n+\mathrm{O}\left(\frac{1}{n}\right)~{},$

where
$c_{g}=\sum_{k=1}^{\infty}\frac{(-1)^{k}\left(\frac{g}{h}\right)^{k}}{k!k}$. ∎

#### Remark

It’s possible to find neat limitations for $c_{g}$, because it’s the
alternating series. If we denote $n$-th partial sum of this series by $S_{n}$,
then $c_{g}$ is between $S_{r}$ and $S_{r+1}$, where $r$ is a natural number,
which satisfies $\frac{g}{h}^{r}<r!r$.

#### Remark

The case $a=2$ is recognized as some kind of exception (due to appearance of
$H_{n}$). We noticed that in fact, some pattern for expected value of $L_{n}$
extrapolates from the case, when $1<a<2$ on $a=2$.

###  3.6 Superquadratic Case

Finally, in this section we consider the case when
$\alpha_{n}=\min\\{1,\frac{g}{n^{\alpha}}\\}$ for some fixed $g>0$ and
$\alpha>2$. This case is the least interesting in our purpose, but we
concisely consider $a>2$ for completeness. Again, we apply random variable
$L_{n}:=n+1-K_{n}$. The foregoing obvious fact is fulfilled:

$\displaystyle\Pr\left[L_{n}=k\right]=\alpha_{k}\prod\limits_{i=0}^{n-k-1}(1-\alpha_{n-i})\leq\alpha_{k}=\min\left\\{1,\dfrac{g}{k^{\alpha}}\right\\}~{}.$

The foregoing formula provides an easy majorization for expected value:

$\displaystyle\mathrm{E}\left[L_{n}\right]\leq\sum_{k=1}^{\left\lfloor
g^{\frac{1}{\alpha}}\right\rfloor}k+gH_{n,\alpha-1}<\frac{g^{\frac{1}{\alpha}}+1}{2}g^{\frac{1}{\alpha}}+g\zeta(\alpha-1)<\infty~{}.$

######  Corollary 5.

If $\alpha>2$, $g>0$ and $\alpha_{n}=\min\\{1,\frac{g}{n^{\alpha}}\\}$, then
$\mathrm{E}\left[K_{n}\right]=n-\mathrm{O}\left(1\right)$.

#### Remark

$L_{n}$ is a number of update of algorithm which saved the last snapshot. We
should expect that our algorithm save only data from the very beginning. In
this case, the algorithm is redundant, so we don’t consider this case anymore.
Nevertheless this is quite interesting mathematical problem to study.

##  4 Applications

In this chapter we will discuss three examples of applications discussed in
the previous chapters of probabilistic pointers.

###  4.1 Linear sampling

Let us assume that we are observing data stream and that after reading $n$-th
item we would like to have access to elements laying near points
$\\{\frac{k}{10}\cdot n:k=0,\ldots,10\\}$. Of course, there is no problem with
the element laying near $\frac{0}{n}\cdot n$ \- it is sufficient to store the
first element from the stream. As an element laying near $\frac{10}{10}\cdot
n$ we may take the current item. So we must propose some mechanism for dealing
with remaining $9$ points.

Let us consider a series $K_{n}^{1},\ldots K_{n}^{M}$ of independent random
variables generated by the sequence $\alpha_{n}=\frac{1}{n}$. We know (see
3.3) that this is a sequence of independent random variables uniformly
distributed in the set $\\{1,\ldots,n\\}$. Let $X_{n}=\\{K_{n}^{1},\ldots
K_{n}^{M}\\}$. Let us fix some $0<\varepsilon<\frac{1}{10}$. Let
$I_{k}=\\{a\in\mathbb{N}:|\frac{a}{n}-\frac{k}{10}|<\varepsilon\\}$. Let us
observe that $\Pr[I_{k}\cap X_{n}=\emptyset]\approx(1-2\varepsilon)^{M}$. This
approximation is accurate for large $n$. So, for simplicity we shall assume
that we have an equality. Therefore

$\Pr[\bigvee_{k=1}^{9}(I_{k}\cap X_{n}=\emptyset)]\leq
9\cdot(1-2\varepsilon)^{M}~{}.$

The solution of inequality $9\cdot(1-2\varepsilon)^{M}\leq\eta$ is given by
$M\geq\frac{\log\left(\frac{\eta}{9}\right)}{\log(1-2\epsilon)}$. Putting in
this formula $\varepsilon=\frac{1}{100}$ and $\eta=10^{-10}$ we get $M\geq
1248.5$. Therefore, if we take $M=1250$ snapshots then

$\Pr[\bigwedge_{k=1}^{9}(I_{k}\cap
X_{n}\neq\emptyset)]>1-\frac{1}{10^{10}}~{}.$

Hence, with a very high probability for each $k\in\\{1,\ldots,10\\}$ we are
able to choose a point from the set $X_{n}$ which approximates $\frac{kn}{10}$
with precision $1\%$.

We perform numerical experiments with this a collection of 1250 probabilistic
snapshots $\mathcal{K}_{n}=(K_{n}^{1},\ldots K_{n}^{1250})$ evolving
independently according to the sequence $\alpha_{n}=\frac{1}{n}$. In the
experiment whose results are shown in Fig. 1 after each call to the procedure
Update we calculated the quality of set of snapshots defined as

$Q(\mathcal{K}_{n})=\frac{1}{n}\max\left\\{\min\left\\{\left|\frac{kn}{10}-K_{n}^{j}\right|:j=1,\ldots,1250\right\\}:k=1,\ldots,9\right\\}~{}.$

Figure 1: Quality of approximation of points $\frac{kn}{10}$, $k=1,\ldots,9$,
by a collection of 1250 snapshots.

We may observe in this figure several regularities which are connected with
the specific method of generation of sequences $\mathcal{K}_{n}$ (for example,
it is clear that sequences $\mathcal{K}_{n}$ and $\mathcal{K}_{n+1}$ are not
independent of each other). We can see that the predicted $1\%$ precision has
been achieved.

###  4.2 Bitcoin capitalization

Figure 2: Precision of bitcon cap approximation by 100 snapshots with
$\mathrm{Exp}\left(0.1\right)$ distribution.

We used bitcoin cap data from [quandl(2017)] to test probabilistic snapshots
concentrated at the end of the data stream. The data stream consists of 1439
records from 2013-09-30 to 2017-12-31 (one record for one day). Since the
length of this stream of data is relatively short, we decided to use only 100
probabilistic snapshots. W used the probability sequence
$\alpha_{n}=\frac{0.1}{\sqrt{n}}$. From Sec. 3.2 we know that in this case the
expected value of snapshots is close to $10\sqrt{1439}\approx 380$.

We added to generated probabilistic snapshots to points: the first one, and
the last one. The results of this experiment is shown at Fig. 2. Let us remark
that the most left points at these diagrams corresponds to data from the day
2017-12-31 and the most right point to 2013-09-30 (so we reversed the typical
order of such kind of diagrams). Note that despite the large fluctuations in
the bitcoin market at the end of 2017, using only 100 snapshots makes it
possible to reproduce the main trend of this parameter of the bitcoins market
quite faithfully.

#### Acknowledgements

The authors would like to thank Zbigniew Gołębiewski and Jakub Lemiesz for
usefull hints and comments on the proofs presented in this paper. The work is
supported by the Polish National Science Center grant number
2013/09/B/ST6/02258 .

## References

  * [Tillé(2006)] Y. Tillé.  _Sampling Algorithms_.  Springer Series in Statistics. Springer, 2006.  ISBN 9780387308142.  URL https://books.google.pl/books?id=2auW1rVAwGMC.
  * [Vitter(1985)] Jeffrey S. Vitter.  Random sampling with a reservoir.  _ACM Trans. Math. Softw._ , 11(1):37–57, March 1985.  ISSN 0098-3500.  doi: 10.1145/3147.3165.  URL http://doi.acm.org/10.1145/3147.3165.
  * [Klamkin and Newman(1970)] M. S. Klamkin and D. J. Newman.  Extensions of the weierstrass product inequalities.  _Mathematics Magazine_ , 43(3):137–141, 1970\.  ISSN 0025570X, 19300980.  URL http://www.jstor.org/stable/2688388.
  * [Alon et al.(1999)Alon, Matias, and Szegedy] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  _J. Comput. Syst. Sci._ , 58(1):137–147, February 1999.  ISSN 0022-0000.  doi: 10.1006/jcss.1997.1545.  URL http://dx.doi.org/10.1006/jcss.1997.1545.
  * [Billingsley(2012)] Patrick Billingsley.  _Probability and Measure_.  Wiley Series in Probability and Statistics. Wiley, anniversary edition, 2012.  ISBN 1118122372, 978-1118122372.
  * [quandl(2017)] quandl.  Bitcoin mining statistics.  https://www.quandl.com/data/BITCOINWATCH/MINING, 2017.