1

This was a question that was asked in my distributed network algorithms assignment

Say I have n nodes in a distributed network and at every node I'm tossing a coin. Let $X_i$ be the independent random variables following geometric distribution, where $1 \leq i \leq n$, that denotes the number of coin tosses before a heads appear. let the parameter $ p = 1/2$. Then show with high probability that $Max\{X_i | 1 \leq i \leq n\} = O(logn)$.

Added the picture of question for more clarity:

enter image description here

This is the partial answer that I submitted.

E[x] = 1/P = 2

P($x_i = k_i$) = $(1-p)^{k_i-1}p$ where $k_i$ denotes the number of trails before heads appear in $i^{th}$ node

substituting p= 1/2, we get

P($x_i = k_i$) = $(1/2)^{k_i}$ for $ 1 \leq i \leq n$

How to procced after this ?

Hitesh Khandelwal
  • 83
  • Are you sure you've read the question correctly? You can't say $\max{X_i|1\le i \le n}=O(\log n)$, the left-hand side is random and the right-hand side is constant. – 1Rock Sep 15 '21 at 01:45
  • Yes, this was the question. I have added picture of the question as well – Hitesh Khandelwal Sep 15 '21 at 04:29
  • Thanks. The phrase "with high probability" is important. Notice how $\max{X_i|1 \le i \le n}\le c \log n$ if and only if $X_i \le c \log n$ for every $i$. Try calculating the probability that $X_i \le c \log n$. – 1Rock Sep 15 '21 at 04:49

2 Answers2

1

Here $X_i\sim\text{Geom}\left(p=\frac{1}{2}\right)$ $\forall i=1(1)n$.

Now let us turn our attention towards $\mathcal{O}$:

$$\begin{align} &\max\{X_i|1\leq i\leq n\}=\mathcal{O}\left(\log n\right)\\ \implies &\max\{X_i|1\leq i\leq n\}\leq \text{c}\cdot\log n \hspace{1em}\text{as }n\rightarrow\infty\hspace{1em}\text{where c is a positive constant}\\ \implies &X_i\leq\text{c}\cdot\log n \hspace{1em}\forall i=1(1)n \hspace{1em}\text{as }n\rightarrow\infty \end{align}$$

Now we can find the probability as $$\begin{align} P\left(X_i\leq\text{c}\cdot\log n|1\leq i\leq n\right)&=\{P\left(X_1\leq\text{c}\cdot\log n\right)\}^n\hspace{5em}\text{as all are i.i.d}\\ &=\left\{\sum_{k=1}^{\lfloor\text{c}\cdot\log n\rfloor}\left(\frac{1}{2}\right)^k\right\}^n\\ &=\left\{1-\left(\frac{1}{2}\right)^{\lfloor\text{c}\cdot\log n\rfloor}\right\}^n \end{align}$$

Now, do you understand why with high probability?

Take $\lim_{n\rightarrow\infty}$ on the above probability. Then $\left(\frac{1}{2}\right)^{\lfloor\text{c}\cdot\log n\rfloor}\rightarrow0$ [Why?].

So $1-\left(\frac{1}{2}\right)^{\lfloor\text{c}\cdot\log n\rfloor}\rightarrow1$.

The rest is trivial...

DeBARtha
  • 609
1

To add to the previous answer. Why and when does $(1-(\frac12)^{\lfloor c \log n\rfloor})^n$ converge to $1$? We can calculate $$\Big(1-\Big(\frac12\Big)^{\lfloor c \log n\rfloor}\Big)^n = \Big(1-\frac{n0.5^{\lfloor c \log n\rfloor}}{n}\Big)^n = \Big(1+\frac{-e^{\log n}0.5^{\lfloor c \log n\rfloor}}{n}\Big)^n$$ which converges to $e$ to the power of something depending on the numerator. If numerator converges to $0$ then the expression converges to $1$ and we are done. Thus, when just ignoring the floor function we need $$e 0.5^c < 1 \Leftrightarrow c\log 0.5 < \log (1/e) \Leftrightarrow c > 1/\log 2$$ and it follows that for $c>1/\log 2$ with high probability $\max_{i=1,\dots,n} X_i \leq c\log n$.
But we also get that the above probability converges to $0$ if $c< 1/\log 2$. This means that in this case with high probability $\max_{i=1,\dots,n} X_i \geq c\log n$.
To summarize: With high probability $$c_1\log n \leq \max_{i=1,\dots,n} X_i \leq c_2\log n$$ for $c_1<1/\log 2$ and $c_2>1/\log 2$.

Trailblazer
  • 357
  • and what exactly is $e$ to the power something? – DeBARtha Sep 15 '21 at 11:19
  • The $e$ function can be characterized by $e^x = \lim_{n\to\infty} (1+\frac{x}{n})^n$ and if $x$ is a sequence depending on $n$ itself and it converges the statement is still true. – Trailblazer Sep 15 '21 at 11:23