# Calculating expected number of rounds

I am trying to find the expected number of rounds for a system to finish a process. Lets say N = 100. One process starts off the program by sending a message to another random process. The choice is made at random so a process can potentially send a message multiple times to another process.

When a process receives a message, it will also send a message to other processes. Since collision can occur (i.e. multiple processes sending a message to a same process), and this is where I am kind of confused.

If at round R - X processes have the message and Y processes don't. I am trying to find how many processes might get the message at round R + 1, and expand it to the total amount of rounds needed. Each process has a 1/100 chance of receiving a message so there is a finite possibility but I am confused on how to calculate this. Any hints?

-

1
I don't get what is random in your problem. Is it the program to whom the message is sent, or is it wether a program sends a message, or is it the amount of messages a program sends, or is it a combination of any of all three above? I think once you have figured that out and what probability you assign to each event, you'll be less confused. – Raskolnikov Sep 12 '12 at 21:04
What is random is the number of rounds required to complete a process. What is missing is the definition of completing a process. Apparently Hagen knows because he gave Paul (the OP) a satisfactory answer. – Michael Chernick Sep 12 '12 at 21:24
There has been recent interest in gossip and how a single piece of information spreads across a network. See, for example, the paper A.D. Sarwate, A.G. Dimakis, The Impact of Mobility on Gossip Algorithms, IEEE Transactions on Information Theory 58(3): pp. 1731--1742, March 2012 (the lead author is my son). – Dilip Sarwate Sep 12 '12 at 22:45

## 1 Answer

A naive estimate would say that on average a share of $\frac Xn$ of the $Y$ processes will learn the message, thus one expects the number $X$ to grow to $X+\frac{XY}n$. Thus as long as $X\ll n$, the number will grow exponentially like $2^R$; if $X\approx \frac n2$, it will grow slower, but $Y$ will decrease by about half each step; and as $Y$ gets smaller, it will decrease even faster. Therefore a rough upper bound is that you probably need at most $2\log_2 \frac n2$ rounds.

-

Ah that makes sense. I was thinking of it as not decreasing by half each step and was getting very confused. Thanks for the explanation. – Paul Sep 12 '12 at 21:15
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 10, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9460514187812805, "perplexity_flag": "head"}