\section{Introduction}
Networks are an important natural phenomenon, and much efforts have been devoted to study their properties. In this article, we mainly consider social networks joined by different people, and we will pay particular attention to the social networks formed in online social networking services. For general social networks, the reader can refer to Wasserman and Faust (1994), which provides a comprehensive list of their properties. To obtain knowledge of these properties requires sampling from the networks, which have long aroused the interest of researchers, and some early work can be traced back to snowball sampling (Goodman, 1961). Generally, the sampling schemes for social networks can be very different from independent sampling, as it is very difficult to obtain independent samples from the networks and it is often necessary to reach one person from another. Indeed, many approaches of this kind ({\it chain-referral} or {\it crawling} methods) have been proposed for sampling social networks, such as BFS sampling, DFS sampling and random walk, just to name a few. Section 2 will be devoted to providing a list of common sampling methods for SNSs and noting the possible issues for consideration for each method.

As is mentioned, the network samples may not be independently distributed and to adjust the bias, one should apply weighted estimators such as the Hansen-Hurwitz estimator in Section 4.1 (Hansen and Hurwitz, 1943). Even then, for sampling methods without replacement, the sampling probabilities need to be estimated to obtain the numerical values of weighted estimators, which will be discussed in Section 3. Given these estimations, comparisons between different network sampling methods, especially variations of RDS methods, are feasible, which will be the main topic of Section 4, including comparisons between one-node-at-a-time (RW type) and multiple-nodes-at-a-time (RDS type) sampling, with-replacement and without-replacement ({\it traversal}) sampling and coverage probabilities for different confidence intervals for the attributes of sampled social networks, together with a new confidence interval which has similar performance with previous ones and lower computational costs. The effect of population size on network sampling and the homogeneity/heterogeneity between networks with the same properties will also be briefly discussed. The simulated networks will be based on the commonly used exponential random graph models (ERGMs) (Snijders, 2002). Section 5 discusses the works in the related literature and concludes the article.

\section{Current Network Sampling Methods}

\subsection{Node-based Network Sampling}
In certain situations, sampling independently from the nodes in a network is possible, and then we can apply simple node-based sampling, i.e. to randomly collect information from a group of people on SNSs and keep the links between them. Although this method generally preserves the topological structures of a social network (Lee et al., 2006), it is not easy to implement under many circumstances. While some available SNS datasets such as complete data sets for Facebook users in Harvard (Lewis et al., 2008) and Caltech (Traud et al., 2008) make this kind of sampling possible, online social networks are highly dynamic, and typical SNSs such as Facebook can only generate a small sample each time for a given group of people, which make the node-based sampling method difficult for SNSs. Moreover, such complete data sets also trigger privacy concerns.

Apart from that, there is an easier way to acquire a uniform random sample across giant online social networks, which is to generate random user IDs uniformly and then reject the IDs that do not match any user. It can be easily proved that this kind of rejection sampling generates the same results as uniform random sampling without replacements (Gjoka et al., 2010). This approach was previously available for Facebook; yet now, Facebook has stopped using number IDs, and this approach appears be less practical.

\subsection{Link-based Network Sampling}
Apart from node-based sampling, it is also possible to randomly sample from the links inside the networks and keep the nodes attached to them. The difference between node-based sampling and link-based sampling is illustrated as follows:
\newpage
\begin{figure}[h]
\begin{center}
    \includegraphics[width=2.5in,height=1in]{Figure1.pdf}
\end{center}
\caption[]{Node-based network sampling and link-based network sampling}
\end{figure}
The link-based method is the most suitable when investigating certain characteristics of links in social network services. Nevertheless, it is shown that the link-based sampling method just preserves some of the topological structures of a social network (Lee et al., 2006). Besides, it shares the same weakness with node-based sampling, as random sampling on links in online social networks is often not an easy task.

\subsection{Traversal Network Sampling}
When conducting sampling on a social network, it is convenient to use the property that the nodes are connected with each other. Therefore, we can refer from one node to another repeatedly using the existing links between them, which can accelerate the speed of sampling on SNSs. Methods of this type are generally called chain-referral methods, almost all of which are biased towards nodes with higher degree. While the bias for chain-referral sampling with replacement is known asymptotically, the bias for chain-referral sampling without replacement, i.e. traversal sampling, has no direct formula, approximations of which will be provided in Section 3. The following provides an account for common traversal network sampling methods.

The Breadth-First-Search (BFS) sampling, i.e. the snowball sampling method, starts with a certain node in a social network and then samples all its network neighbors, and then all the neighbors of its network neighbors, etc. until the total number of nodes reach a certain amount. The BFS sampling is arguably the fastest method of all, and it is also feasible in current online social networks. However, evidence has shown that the BFS sampling tends to distort the topological features of a network, and it also suffers from other problems such as low convergence rates and very high bias towards high-degree nodes. The traversal sampling methods below share similar properties with BFS (Kurant et al., 2011b).

The Depth-First-Search (DFS) sampling starts with a certain node and goes along a random route until it reaches a terminal. Then it retreats to the nearest visited node joining another branch and goes along this branch randomly until it reaches a terminal again, and so force until a whole connected component of a social network is visited. This method aims at visiting a whole network or one connected component, and when it is carried out incompletely, it also introduces an unknown bias towards high-degree nodes.

Forest Fire sampling is a modification of the BFS sampling. In Forest Fire sampling, we start with a certain node, then sample each of its neighbors with probability $p$ and then sample each of the neighbors of its sampled neighbors with probability $p$, etc. until we have collected a certain number of samples. Forest Fire sampling reduces to BFS when $p=1$.

An alternative of snowball sampling, simply referred to as snowball sampling in some texts (not to be confused with the BFS method), is another modification of the BFS method. Instead of sampling all neighbors of a node, we now just sample $n$ neighbors of a node at each step, and then reject the neighbors that we have already sampled. The reader can refer to Illenberger et al. (2009) for a crude estimation of the sampling probabilities for this approach which can be applied for bias correction.
\begin{figure}[h]
\begin{center}
    \includegraphics[width=3in,height=1in]{Figure2.pdf}
\end{center}
\caption[]{A comparison between BFS sampling and DFS sampling}
\end{figure}

\subsection{Random Walk Network Sampling}
Random walk (RW) sampling means one-node-at-a-time chain-referral sampling on an SNS with replacements. It possesses many desirable properties such as fast convergence and known asymptotic sampling probabilities, although it might not be useful in terms of non-local graph properties like the graph diameter and the average shortest path length (Gjoka et al., 2010). Moreover, from the further analysis in Section 4, in terms of sampling error, random walk may not work as well as traversal methods as the former samples nodes repetitively. The sampling results should be re-weighted with the Hansen-Hurwitz estimator in Section 4.1 or the like. The variations of random walk sampling are listed as follows:

Simple random walk visits at each step one of the neighbors of the previous node with the same probability. If the network is connected and aperiodic, the sampling probability of a particular node $v$ converges to the stationary distribution: $\pi(v)=\deg(v)/2{\rm vol}(V)$, $V$ being the whole network.

Metropolis-Hastings random walk visits at each step the neighbor $v$ of the last node $u$ with the same probability and sample the new node with probability $\min(1,\deg(u)/\deg(v))$. Otherwise, we sample the node $u$ again. Then the sampling probability of each node is the same: $1/|V|$.

Weighted random walk places weight $w(u,v)$ on each link $(u,v)$ of a network so that the desired nodes incur more weight. Then we visit at each step the neighbor $v$ of the last node $u$ with probability $w(u,v)/(\sum_{v\in N(u)}w(u,v))$, $N(u)$ being the neighborhood of $u$. The sampling probability of a node $v$ is then $\pi(v)=w(v)/(\sum_{u\in V}w(u))$, $w(v)=\sum_{v'\in N(v)}w(v,v')$. For sampling on a network with disproportionate groups, the reader can refer to Kurant et al. (2011a) for an intricate algorithm for calculating the weights in order to acquire proportionate sample volumes for each group.

\subsection{Respondent-driven Network Sampling}
Respondent-driven sampling (RDS) was first invented as a chain-referral sampling method to detect hidden populations (Heckathorn 1997) and nowadays it generally refers to chain-referral sampling methods which sample $n$ nodes from one node at a time. Both with-replacement and traversal sampling are included and RDS may also comprise multiple starts, which lead to multiple chains of samples. When $n = 1$, RDS with replacements reduces to simple random walk and when RDS is performed without replacements, it can be viewed as the alternative of snowball sampling above. Even without replacements, the sampling probabilities of RDS can be considered as proportional to the node degree. Still, this approximation is too crude and two ways to improve it are explained below.

\section{Estimation of the Sampling Probabilities}
As is mentioned above, for with-replacement chain-referral methods, we know that the sampling probability $\pi(v)\doteq\deg(v)/2{\rm vol}(V)$. For traversal sampling, Kurant et al. (2011b) provide a direct estimation of the sampling probabilities. They view traversal sampling as a process randomly connecting the ``stubs'' inside a network, a degree-$k$ node with $k$ stubs. They assign each stub with an index $\stackrel{{\rm iid}}{\sim} U(0,1)$, and assume that there is a time process from $t=0$ to $t=1$. A node is connected when $t$ reaches the smallest index of its stubs. Then given fixed time $t$, $\pi(v)\propto 1-(1-t)^{\deg(v)}$, and the sampling proportion $f \approx Ef = 1-\sum_k p(k)(1-t)^k$, which we denote as $g(t)$, $p(k)$ being the proportion of degree-$k$ nodes. Therefore $\pi(v) \propto 1-(1-g^{-1}(f))^{\deg(v)}$.

The node degree distribution $p(k)$ as above needs estimation, and Kurant et al. (2011b) have provided a number of approaches, the most direct of which is to run a random walk on the network and estimate $p(k)$. This approach will be adopted below, and the author also proposes to further estimate $g(t)$ as $1-(1-t)^{\sum p(k)k} = 1-(1-t)^{\bar{d}}$, $\bar{d}$ being the average node degree. Taking traversal sampling as with-replacement sampling, $\bar{d}$ should be the harmonic average node degree applying the Hansen-Hurwitz estimator below. It was discovered during simulation that the arithmetic average node degree resulted in little difference, which was eventually applied for simplicity. The whole proposal might be bold, yet later it will be shown that the proposal is reasonable most of the time, and it mitigates the computational burden as well.

Gile (2011a) provides a successive sampling (SS) estimation for the problem based on bootstrapping. It is first assumed that $\pi_0(v)\propto\deg(v)$, as in sampling with replacements. Given an estimation of sampling probability $\pi_{i-1}(v)$, the number of degree-$k$ nodes in the population $V_k^i \approx |V|\frac{v_k}{\pi_{i-1}(v)}/ \sum\frac{v_k}{\pi_{i-1}(v)}$, $v_k$ being the number of degree-$k$ nodes in the sample. We generate a random network with volume $|V|$ and number of degree-$k$ nodes $V_k^i$, and then draw $M$ successive samples with original sample size from it. The estimation of sampling probability can be updated as $\pi_i(v)=(U_k+1)/(MV_k^i+1)$, $U_k$ being the total number of degree-$k$ nodes in the $M$ samples. This procedure is repeated till a satisfactory $\pi_r(v)$ is reached. It should be noticed that the prior knowledge of the population size is required. It has shown in the original paper that this estimation outperforms with-replacement RDS. In the next section the author will reconfirm the result while providing a more detailed comparison of network sampling techniques.

\section{Statistical Inference for Sampling SNSs}
In this section, we will discuss statistical inference for sampling social networking services. Regarding what should be estimated, we simulate networks with population size $1000$ and randomly assign each node with category A or B. The proportion of category A could be controlled to be, say, $0.3$ in the following examples. Then variations of RDS will be applied to estimate the proportion of category A in terms of point estimation discussed in Section 4.1 and confidence interval estimation discussed in Section 4.2. Due to the scarcity of real data, all simulation results are based on ERGMs (Snijders, 2002) and averaged over $100$ random networks with population size $1000$ and $100$ samples on each network without further specification.

\subsection{Point Estimation of Node Properties}
Because RDS methods are all biased towards higher-degree nodes, we cannot use the category proportions of the sample to replace the category proportions of the total population. The Hansen-Hurwitz (or generalized Horvitz-Thompson, Volz-Heckathorn) estimator (Hansen and Hurwitz, 1943; Gile and Handcock, 2010) estimates population total as $\hat{x}_{total}=\frac{1}{n}\sum_{v\in V}\frac{x(v)}{\pi(v)}$, and population mean as $\bar{x}=\sum_{v\in V} \frac{x(v)}{\pi(v)}/\sum_{v\in V}\frac{1}{\pi(v)}$; $x(v)$ is the node characteristic and $\pi(v)$ is the sampling probability. This estimator is asymptotically unbiased and is applied for RDS in most situations. For an alternative, the reader can apply the classic Horvitz-Thompson estimator $\bar{x}=\sum_{v\in V} \frac{x(v)}{\pi(v)}/(|V|n)$, $n$ being the sample size. We need only make $x(v)$ an indicator function to estimate the category proportions of the total population.

\subsubsection{Sampling with Replacements}
Now we investigate the accuracy of random walk and RDS with replacements and estimate the proportion of category A of social networks. We use the relative mean error as an indicator which is calculated from a sample of volume $n$ on a quadratic mean basis: $\hat{e}_r=\hat{e}/p$, $\hat{e} =\sqrt{\sum e_i^2/n}$, $e_i$ being each absolute error and $p$ being the category proportion. The relative mean errors are plotted below against the sampling proportions to show how many samples we should collect in order to obtain a reliable estimation. There are comparisons between random walk and RDS when $n=3$.

To identify the influence of network structure on sampling results, we control two parameters, namely the homophily ratio and the activity ratio. The former indicates the tendency of nodes to be connected within the categories, and is calculated by dividing the expected number of ties between category A and category B in networks with the same average node degree by the actual number of ties between category A and category B. The activity ratio is defined to be the ratio between the average node degree of category A and the average node degree of category B. The figures below in the upper row are produced from networks with homophily ratio 1, which indicates normal networks; those in the lower row are produced from networks with homophily ratio 2, indicating more ties within categories. From the left to the right, the activity ratio is 0.5, 1 and 2. The figures are presented below:

\begin{figure}[h]
\begin{center}
    \includegraphics[width=6in,height=3.6in]{Figure3.pdf}
\end{center}
\caption[]{The relative mean errors of with-replacement RW and RDS (n=3) against sampling proportion on different social networks. From left to right: activity ratio = 0.5, 1, 2; from top to bottom: homophily ratio = 1, 2}
\end{figure}

All social networks of different activity ratios and homophily ratios indicate that the mean error generally decreases with more sampled nodes, though fast at first and quite slow later. Also, the patterns of RW and RDS curves are highly similar so they almost coincide and no one seems to clearly outperform another when there is no homophily. However, when the homophily ratio is large, RW tends to outperform RDS to a large extent, and all errors tend to be much larger. The sampling error decreases with an increase in activity ratio, which is consistent with the fact that a network with dense ties is easier to sample than one with fewer ties. Meanwhile, there is a tendency that the mean error does not decrease rapidly with an increase in sample volume. In contrast, they seem to die down to a certain positive number (in these examples, around 0.05 and 0.10) with the sample volume increasing, though they will eventually go to zero. Moreover, sampling proportions larger than one are particularly undesirable.

It was also found in simulation that when the homophily ratio is high, there are some outliers which significantly increase the mean error. This is likely to be caused by the fact that the sampler is trapped in a small group of people with dense ties. This phenomenon should be avoided in both theory and practice, and the most natural solution seems to be avoiding with-replacement sampling if possible.

It is reasonable to hypothesize that the mean error does not quickly converge to zero as sample size increases because the sampler picks up some nodes with extreme properties, which increases the sample variation of the node characteristic estimation to a large extent. The following simulation results, with sampling errors decomposed into sample bias and sample standard deviation, largely prove this hypothesis, which are shown as follows:

\begin{figure}[h]
\begin{center}
    \includegraphics[width=6in,height=1.8in]{Figure4.pdf}
\end{center}
\caption[]{The relative sample biases and sample standard deviations of with-replacement RW and RDS (n=3) against sampling proportion on different social networks. From left to right: homo. ratio = 1, act. ratio = 0.5; homo. ratio = 1, act. ratio = 1; homo. ratio = 2, act. ratio = 2.}
\end{figure}

We can observe from the figures above that the sampling bias is almost zero, and the main contributor to the error is the standard deviation. The standard deviation decreases rather slowly as the sampling proportion increases, which explains the slow convergence of with-replacement sampling on a social network. Meanwhile, the convergence of the traversal sampling is guaranteed as the sampling proportion tends to one. We will compare the results above with the results from traversal sampling below.

\subsubsection{Traversal Sampling}
The following figures exhibit the relative mean errors of category proportion estimated by with-replacement sampling and traversal sampling. The sampling probabilities of traversal sampling are estimated by both methods in Section 3.

\begin{figure}[h]
\begin{center}
    \includegraphics[width=6in,height=1.8in]{Figure5.pdf}
\end{center}
\caption[]{The relative mean errors against sampling proportion on different social networks. Left: homo. ratio = 1, act. ratio = 0.5, RDS(n=3); middle: homo. ratio = 1, act. ratio = 1, RW; right: homo. ratio = 2, act. ratio = 2, RDS(n=3). R: with-replacement sampling; K: Kurant et al.'s direct estimation; SK: Kurant et al.'s direct estimation (simplified); G: Gile's successive sampling (SS) estimation. Other cases in Figure 3 have identical patterns with any of the above cases and are not listed.}
\end{figure}

It can be referred from the results that all estimates from traversal sampling consistently have smaller average errors than with-replacement estimates, which shows more applicability of traversal sampling. In the traversal estimates, Gile's SS estimates consistently perform better, but the difference is only significant when the sampled proportion is large (above 0.4) and the activity ratio is far from one, which is not very common in real practice. Considering the fact that Kurant et al.'s direct estimates are much easier to calculate than Gile's SS estimates, it is acceptable to apply the direct estimates under ``normal'' circumstances, where the sampling proportion and the requirement for accuracy are not too high. Also, it is shown that the simplified direct estimates almost have the same results as original direct estimates.

Further investigation can be made into the similarity between the Gile's SS estimates and the direct estimates. The correlation factors between the two estimates under all different circumstances in Figure 3 have been calculated and the numbers are all above 0.95 for sampling proportion $\le$ 0.7. When the sampling proportion > 0.7 and activity ratio is far from 1, the correlation factors drop below 0.95 but still are greater than 0.5. Therefore, the two estimates are also interchangeable under ``normal'' circumstances.

A temporary conclusion is that traversal methods work better with approximate bias corrections, while with-replacement sampling generally yields larger errors. It is an interesting question why the mean errors of Gile's SS estimates and Kurant et al.'s direct estimates often coincide, although they are computed in totally different ways. Once we identify the reason we may be able to maintain the accuracy of Gile's SS estimates with simpler computations.

\subsubsection{Relationship Between Error and Population Size}
Because online social networks are often of very large size, it is beneficial to discuss the change of the error when the population size increases. We can see from below that the errors are quite stable when the population size increases and the sample size keeps the same. The following table indicates the relative standard errors for the category proportion estimated by traversal RDS ($n=3$) with simplified Kurant et al.'s direct method and Gile's SS method when the population size equals 500, 700, 1000, 1300, 1700, 2000 and the sample size remains 100:

\begin{table}[h]
  \centering
$$
\begin{array}{|c|c|c|c|c|c|c|}
  \hline
  {\rm Population} & 500 & 700 & 1000 & 1300 & 1700 & 2000 \\ \hline
  {\rm Gile's\ SS} & 14.1\% & 14.6\% & 15.0\% & 15.1\% & 15.2\% & 15.3\% \\ \hline
  {\rm Kurant} & 14.1\% & 14.6\% & 15.0\% & 15.1\% & 15.2\% & 15.35\% \\ \hline
\end{array}
$$
  \caption{Sampling errors under different population sizes; homo. ratio = act. ratio = 1}
\end{table}

From these results, we can observe that the sampling errors increase quite slowly with population size increasing, and the increasing trend tend to diminish as population increases. Therefore, the results obtained are quite stable, which provide some evidence that the earlier results will still hold for networks with larger sizes as well. Still, considering the very complicated structure of networks, there is still much to be investigated in this area.

\subsection{Confidence Interval Estimation of Node Properties}
Constructing confidence intervals for node properties from network samples should be another issue for consideration. While ``naive'' confidence intervals\footnote{The ``naive'' confidence interval is the confidence interval with formula $[\bar{x}-t_{\alpha/2,n-1}\hat{s}/\sqrt{n}, \bar{x}+t_{\alpha/2,n-1}\hat{s}/\sqrt{n}]$.} generally do not perform satisfactorily according to Salganik (2006), there are currently two types of bootstrap confidence intervals for node properties which are acceptable for respondent-driven sampling on networks.

\subsubsection{Available Confidence Intervals}
The first type is Salganik's bootstrap confidence interval (2006). We first gather a sample from a network with RDS and then resample on the sample with replacements for $N$ times. The resampling procedure is that if the last resampled node is of category $A$, we resample the next node from all sampled nodes referred by category $A$, and so forth. Then we calculate the estimations of the node attributes $\hat{x}_1, \ldots, \hat{x}_n$ from e.g., the Hansen-Hurwitz estimator for each of the resampled samples and construct the confidence interval using $[\bar{x}-z_{\alpha/2}\hat{s}_e, \bar{x}+z_{\alpha/2}\hat{s}_e]$; $\bar{x}=\sum\hat{x}_i/N$ and $\hat{s}_e=\sqrt{\sum(\hat{x}_i-\bar{x})^2/(N-1)}$.

The second type is Gile's successive sampling confidence interval (2011b) which takes the homophily ratio and the activity ratio into account. In this method, we first estimate the node degree distribution of the network and simulate a network with same population and estimated node degree distribution. Then we denote the current number of nodes with category $i$ and degree $k$ as $\bar{N}_{i,k}$ and the number of links from category $i$ to category $j$ as $H_0(i,j)$. The number of links within and between categories are estimated as $H_0(A,A)=\bar{d}_A\sum_k\hat{N}_{A,k}\hat{r}_A$, $H_0(B,B)=\bar{d}_B\sum_k\hat{N}_{B,k}(1-\hat{r}_B)$ and $H_0(A,B)=H_0(B,A)=[\bar{d}_A\sum_k \hat{N}_{A,k}(1-\hat{r}_A)+\bar{d}_B\sum_k\hat{N}_{B,k}\hat{r}_B]/2$; $\bar{d}_i=\sum_k\hat{N}_{i,k}k/\sum_k\hat{N}_{i,k}$ and $\hat{r}_i$ is the sample proportion of links from $i$ to $A$ in all links from $i$. We sample from the simulated network just as sampling from the original network with the following difference: from a category-$i$ node, we first choose category $j$ with weight $H(i,j)=H_0(i,j)\cdot$proportion of unsampled category-$j$ nodes and then sample from {\it all} category-$j$ nodes with weights proportional to the node degrees. The sampling procedure is repeated $N$ times and the confidence interval can be constructed similarly to the last paragraph.

\subsubsection{The Homogeneity Between Different Networks}
In the above, Gile (2011b) has applied the method of simulating one network for standard deviation calculation instead of taking an average on different networks. To know whether the main variance of estimates comes from within the networks or between the networks, we perform an ANOVA analysis on category proportion estimation of $20$ networks with size $1000$ and $25$ RDS ($n=3$) samples with size $100$ on each network, and estimate the category proportions from the gathered samples with the same assumptions as before. The result shows that the right-tail probability of the $F$ statistic is $0.3725$. Therefore, it is reasonable to hypothesize that there is not a significant structural difference for sampling between different networks, and Gile's approach is reasonable and could be continued.

\subsubsection{A Faster Confidence Interval}
While the above confidence intervals aim at imitating the process of sampling a network with certain attributes, the proposed confidence interval intends to simulate a network with certain attributes and then sample on it. To achieve this goal, we simulate a network with given average node degree, homophily ratio and activity ratio, which could be estimated as follows.

For the average node degree $\bar{d}$, we can apply the Hansen-Hurwitz estimator and direct estimates or Gile's SS estimates as illustrated before. To estimate the homophily ratio, we assume that each link is sampled with the same probability, which is asymptotically true for with-replacement sampling. The estimated proportion of links between categories is then $C_{b}/C$, $C$ being the number of sampled links and $C_{b}$ being the number of sampled links between categories. The average proportion of links between categories for a general network is $\frac{n_An_B}{|V|(|V|-1)/2}$, and therefore we can estimate the homophily ratio as $\hat{h} = \frac{Cn_An_B}{C_b|V|(|V|-1)/2}$. The estimated activity ratio is $\hat{a}=\bar{d}_A/\bar{d}_B$, $\bar{d}_A$ and $\bar{d}_B$ being the estimated average node degrees of of category A and B using direct estimates or Gile's SS estimates.

From these results, we can now construct a faster confidence interval for respondent-driven sampling with the following steps:

(1) Simulate a network with the same sample size and population, estimated mean degree $\bar{d}$, homophily ratio $\hat{h}$ and activity ratio $\hat{a}$;

(2) Sample from the network $N$ times with the same sampling method and create $N$ samples of the estimated category proportion or some other node attribute;

(3) Compute the sample variance using the values of the estimates and hence construct the desired confidence interval as before.

To investigate on the performance of different confidence intervals, their coverage probabilities ({\it CP}s) are potentially useful. Moreover, to provide more information, the estimated standard deviations ({\it SD}s), which are related to the interval lengths, are also presented. The following is the performance of different kinds of $95\%$ bootstrap confidence intervals using traversal RDS ($n=3$), based on an average of the results from simulated networks. For case A, homophily ratio = 1, activity ratio = 1, sampling proportion = 0.1; for case B, homophily ratio = 1, activity ratio = 2, sampling proportion = 0.2; for case C: homophily ratio = 2, activity ratio = 2, sampling proportion = 0.3. Kurant et al.'s directed estimates (simplified) are applied for the new confidence intervals.
\begin{table}[h]
  \centering
$$
\begin{array}{|c|c|c|c|c|c|c|}
\hline
{\rm Case} & CP {(\rm Salganik's)} & SD {(\rm Salganik's)} & CP {(\rm Gile's\ SS)} & SD {(\rm Gile's\ SS)} & CP {(\rm new)} & SD {(\rm new)} \\ \hline
{\rm A} & 94.8\% & 0.046 & 94.0\% & 0.045 & 95.0\% & 0.046 \\ \hline
{\rm B} & 96.1\% & 0.032 & 94.2\% & 0.030 & 94.4\% & 0.028 \\ \hline
{\rm C} & 91.3\% & 0.041 & 93.2\% & 0.043 & 89.2\% & 0.042 \\ \hline
\end{array}
$$
  \caption{Performance of different kinds of $95\%$ bootstrap confidence intervals}
\end{table}

It can be observed that when the characteristics of networks such as activity ratio and homophily are not significant, the new confidence intervals tend to outperform the original ones. However, when such properties are significant, especially homophily, the new confidence intervals tend to be more inaccurate. The fluctuations in the coverage probabilities indicate the complexity of this problem. Still, the three sets of confidence intervals do not differ by a great amount in terms of coverage probabilities. Therefore, the new confidence intervals can be applied when the sampled network does not have specific characteristics, or the requirement for accuracy is not high and faster computational speed is desired.

Moreover, it would also be beneficial to investigate the change in the performance of confidence intervals with adjustments in calculation, where a number of questions could be raised. For instance, we have assumed that each link with sampled with equal probability, which is only true for with-replacement sampling. This could be one point for improvement. Meanwhile, it is also unknown whether it is better to sample across the whole network as in Salganik's and Gile's confidence intervals, or apply traversal sampling as in the new ones. It is probable that the latter results in larger sample standard deviation and more conservative estimates, although they are not reflected in the table above. Apart from that, to which extent we should replicate the network exactly as the original one is also a question, as more complicated replication does not necessarily result in better results, as is illustrated in case B. The new confidence interval is admittedly subject to much improvement, but because of computational burden, the author is regretful for being unable to present further results, which can be left to the reader to explore.

The confidence intervals above are potentially useful for academic researchers in online surveying, where RDS-type sampling methods are very likely to be suitable. It would not be difficult to apply these results on popular social networking services, e.g. Facebook and Twitter, to investigate the proportion of a certain group in a population. The author is also regretful that such an example is unavailable here, which might be constructed by readers in need.

\section{Discussion and Related Works}
There have been numerous articles on social network analysis, and many of them have been devoted to social network sampling. For traversal sampling, Kurant et al. (2011b) provide a comprehensive list of sampling techniques and an approach to correct the bias as is mentioned before. For random walk methods, Gjoka et al. (2010) provide a comparison between simple random walk and Metropolis-Hastings random walk, and Kurant et al. (2011a) provide a stratified sampling technique for sampling disproportionate categories. The reader may also refer to Stutzbach et al. (2006) for a modified MHRW technique for sampling dynamic networks. In terms of respondent-driven sampling, the reader can refer to Heckathorn (1997; 2002) and Salganik and Heckathorn (2004) for some early discussion on RDS and the RDS-I type estimator. The RDS-I type estimator has become outdated as its performance is relatively inferior to the RDS-II type estimator (Volz and Heckathorn, 2008), which is basically the Hansen-Hurwitz estimator. Gile and Handcock (2010) provide an examination of the RDS techniques as are mentioned above. Wejnert and Heckathorn (2008) provide a example of RDS for online social networks, and Rasti et al. (2009) show an example of RDS for sampling dynamic networks. While a vast number of methods have been proposed for social network sampling and related estimation, new methods with higher efficiency may still be invented in the future.

To evaluate the performance of chain-referral sampling methods, there has been much discussion on the mixing time of the Markov chain. Sinclair (1992) provides theoretical evidence that the mixing time is bounded by the second largest eigenvalue of the transition matrix of the Markov chain. For empirical evidence, the reader can refer to Mohaisen et al. (2010) which shows that the mixing time of many chains is higher than expected. Mohaisen et al. (2012) provide a comprehensive empirical analysis of the mixing speed of BFS, RW and MHRW with examples of sampling online social networks. To accelerate the mixing speed of the Markov chain, there have been a number of proposed techniques, such as uniform restarts (Avrachenkov et al., 2010), multiple starts (Ribeiro and Towsley, 2010) and a fastest mixing algorithm based on the network structure (Boyd et al., 2004). On the other hand, there has been relatively limited literature on the performance of estimates from chain-referral sampling methods, some of which can be found in Gile and Handcock (2010) and Gile (2011a), and improving the performance of the estimates constitutes another question. The article above has provided some new evidence on the performance of sampling social networking services and has also proposed some new methods to improve the related estimates. Meanwhile, much still remains to be done.

\section*{References}
\begin{biblist}
\item Konstantin Avrachenkov, Bruno Ribeiro, and Don Towsley. Improving random walk estimation accuracy with uniform restarts. In {\it 17th Workshop on Algorithms and Models for the Web Graph}, 2010.
\item Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest mixing Markov chain on a graph. {\it SIAM review}, 46(4):667-689, 2004.
\item Krista J. Gile. Improved inference for respondent-driven sampling data with application to HIV prevalence estimation. {\it Journal of the American Statistical Association}, 106, 135-146, 2011a.
\item Krista J. Gile. Supplemental materials: Improved inference for respondent-driven sampling data with application to HIV prevalence estimation. {\it Journal of the American Statistical Association}, 106, 2011b.
\item Krista J. Gile and Mark S. Handcock. Respondent-driven sampling: An assessment of current methodology. {\it Sociological Methodology}, 40, 285-327, 2010.
\item Minas Gjoka, Maciej Kurant, Carter T. Butts, and Athina Markopoulou. Walking in Facebook: A case study of unbiased sampling of OSNs. In {\it INFOCOM}, 2010.
\item Leo A. Goodman. Snowball sampling. {\it Annals of Mathematical Statistics}, 32:148-170, 1961.
\item Mark S. Handcock, Krista J. Gile, and William W. Neely. {\it RDSdevelopment}: Development package for respondent-driven sampling. Version 0.1, 2012.
\item Morris H. Hansen and William N. Hurwitz. On the theory of sampling from finite populations. {\it Annals of Mathematical Statistics}, 14(3), 1943.
\item Douglas D. Heckathorn. Respondent-driven sampling: A new approach to the study of hidden populations. {\it Social Problems}, vol. 44, p. 174-199, 1997.
\item Douglas D. Heckathorn. Respondent-driven sampling II: Deriving valid population estimates from chain-referral samples of hidden populations. {\it Social Problems}, vol. 49, p. 11-34, 2002.
\item Johannes Illenberger, Gunnar Fl\"{o}tter\"{o}d, and Kai Nagel. An approach to correct bias induced by snowball sampling. In {\it Sunbelt Social Networks Conference}, 2009.
\item Maciej Kurant, Minas Gjoka, Carter T. Butts, and Athina Markopoulou. Walking on a graph with a magnifying glass: Stratified sampling via weighted random walks. In {\it Sigmetrics}, 2011a.
\item Maciej Kurant, Athina Markopoulou, and Patrick Thiran. Towards unbiased BFS sampling. {\it IEEE JSAC} 29 (9):1799-1809, 2011b.
\item Sang H. Lee, Pan-Jun Kim, and Hawoong Jeong. Statistical properties of sampled networks. {\it Phys. Rev. E}, 73:16102, 2006.
\item Kevin Lewis, Jason Kaufman, Marco Gonzalez, Andreas Wimmer, and Nicholas Christakis. Tastes, ties, and time: A new social network dataset using Facebook.com. {\it Social Networks}, 2008.
\item Abedelaziz Mohaisen, Aaram Yun, and Yongdae Kim. Measuring the mixing time of social graphs. In {\it IMC}, 2010.
\item Abedelaziz Mohaisen, Pengkui Luo, Yanhua Li, Yongdae Kim, Zhi-Li Zhang. Measuring bias in the mixing time of social graphs due to graph sampling. In {\it MILCOM}, 2012.
\item Amir H. Rasti, Mojtaba Torkjazi, Reza Rejaie, Nick Duffield, Walter Willinger, and Daniel Stutzbach. Respondent-driven sampling for characterizing unstructured overlays. In {\it Infocom Mini-conference}, p. 2701-2705, 2009.
\item Bruno Ribeiro and Don Towsley. Estimating and sampling graphs with multidimensional random walks. In {\it IMC}, 2010.
\item Matthew J. Salganik. Variance estimation, design effects, and sample size calculations for \linebreak respondent-driven sampling. {\it Journal of Urban Health}, 83:98-111, 2006.
\item Matthew J. Salganik and Douglas Heckathorn. Sampling and estimation in hidden populations using respondent-driven sampling. {\it Sociological Methodology}, vol. 34, p. 193-239, 2004.
\item Alistair Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. {\it Combinatorics, Probability $\&$ Computing}, 1:351-370, 1992.
\item Tom A. B. Snijders. Markov chain Monte Carlo estimation of exponential random graph models. {\it Journal of Social Structure} 3, 2002.
\item Daniel Stutzbach, Reza Rejaie, Nick Duffield, Subhabrata Sen, and Walter Willinger. On unbiased sampling for unstructured peer-to-peer networks. In {\it IMC}, 2006.
\item Amanda L. Traud, Eric D. Kelsic, Peter J. Mucha, and Mason A. Porter. Community structure in online collegiate social networks. {\it arXiv}: 0809.0960, 2008.
\item Erik Volz and Douglas D. Heckathorn. Probability based estimation theory for respondent-driven sampling. {\it Journal of Official Statistics}, Vol. 24, p. 79-97, 2008.
\item Stanley Wasserman and Katherine Faust. {\it Social Network Analysis: Methods and Applications}. Cambridge University Press, Cambridge, 1994.
\item Cyprian Wejnert, Douglas D. Heckathorn. Web-based network sampling: Efficiency and efficacy of respondent-driven sampling for online research. {\it Sociological Methods and Research}, Vol. 37, p. 105-134. 2008.
\end{biblist}

\end{document}


\section{Introduction} \label{introduction:sec}

Faraday Rotation Measures (RM) is one of the very few
 methods to probe extragalactic magnetic fields.
The RM is given by the
change in observed polarization angle, $\Delta \chi_0$, over a change in
the observed wavelength square, $\Delta\lambda _0^{2}$.
For a  polarized radio source at cosmological redshift $z_{s}$
it is defined as

\begin{equation}
\label{eq:defRM}
RM(z_{s}) = \frac{{\Delta \chi_0 }}{{\Delta \lambda _0^{2} }} = 8.1
\cdot
10^{5} \int\limits_{z_{s}}^{0} \frac{n_e
(z)B_\parallel(z)}{(1+z)^{2}}\frac{dl}{dz}dz,
\end{equation}

where the RM is in units of rad m$^{-2}$, the free electron number
density, $n_{e}$, is in cm$^{-3}$, the magnetic field component
along the line of sight, $B_{\|}$, is in Gauss,
and the comoving path increment per unit redshift, $dl$/$dz$, is in pc.
Eq. \ref{eq:defRM} assumes a uniform
RM screen across the source and a spatial separation of the
linearly polarized source and the Faraday rotating plasma.

In \cite{Kronberg2008} (K08) we used a sample of 268 RM values of
extragalactic radio sources to assess the redshift evolution in the RM
dispersion. We found an increase in the RM dispersion with redshift,
which became statistically significant above $z \sim 1$. We postulated
that the increase in the RM dispersion is produced by magnetic fields
in intervening galaxies. To test this hypothesis spectra of 71 QSOs at
UVES/VLT were taken. In \cite{Bernet2008} (B08) we showed that indeed
sightlines with intervening strong MgII absorption systems have
significantly higher RM values than those without. The findings in
that work implies that $\sim 10 \; \mu\rm{G}$ magnetic fields exist in
galaxies out to $z \sim 1.3$.

Recently \cite{Taylor2009} (TSS09) determined RM values of 37'543
sources, based on polarization observation of the NRAO VLA Sky Survey
(NVSS). After the release of the RM catalogue we compared our RM
values with those of TSS09 and found major differences between the two
datasets. As we show in section \ref{discrepancies} using the RM
values of TSS09 the results of K08 and B08 can not be reproduced. In
this work we present an analysis of the differences found between the
two datasets. We then develop a toy model to show that such
differences can be accounted for by inhomogeneities in the RM screens
of the QSOs host galaxies and intervening galaxies. In view of this
model, due to the strong depolarization effects, RM data based on low
frequencies observations and interpreted according to
Eq.~(\ref{eq:defRM}) are inadequate to probe inhomogeneous RM screens
produced by intervening galaxies.

Recently there has been an increased attention to the effects of
inhomogeneous RM screens on the observed degree of polarization and
polarization angle as function of
wavelength. \cite{Rossetti2008,Mantovani2009} used multiwavelength
radio observations to model depolarization of their sources. They
showed that the depolarization as a function of wavelength can be
better described including a covering factor for the inhomogeneous
screens. \cite{Farnsworth2011} used Westerbork Synthesis Radio
Telescope (WSRT) observation at $\sim 1 \rm{m}$ combined with NVSS
observation at 21 cm to test different depolarization models and RM
determination methods. They considered the traditional Faraday
dispersion screen \citep{Burn1966}, a two component model for Faraday
Rotation which produces oscillation in the degree of polarization, and
the RM Synthesis method. The comparison of the different RM values
obtained from these methods revealed that if Faraday structure is
present, the different methods may lead to different RMs. They further
stress the importance of considering both the polarization angle and
amplitude for the correct determination of the RMs.

While several effects may be at work, as briefly discussed in section
\ref{effects:sec}, in this paper we keep the level of sophistication
of the model to a minimum and focus on the role of Faraday screen
particularly on simple ideas associated with inhomogeneity which can
account for important observational effects and test these ideas for
consistency with available data.  The rest of this paper is organized
as follows.  In section \ref{RM_data} the RM datasets of B08 and K08
are compared and the differences are presented. Previous work on
depolarization of extragalactic sources is shortly presented in
section \ref{sec:Depmodel}. In section \ref{modelling} a
depolarization toy model is presented which can account for the
differences in the RM values of the two datasets.  A discussion of the
nature of the partial inhomogeneous RM screens and computed Faraday
spectra as comparison for RM surveys is presented in section
\ref{sec:discussion}. In section \ref{sec:summary} we give a summary of our findings.

\section{Rotation Measure Data}
\label{RM_data}
\subsection{Datasets}
\label{datasets}

The RM values used in K08, B08 and \cite{Bernet2010} were collected by P. Kronberg
and collaborators over the past decades using polarization observations at various telescopes, including VLA and Effelsberg. The sample consists of 901 sources with determined RM and redshifts, partly taken by Kronberg and collaborators, partly taken from the literature
\citep{SimardNormandin1981}.
Until the work of TSS09 it has been the only existing large RM catalogue.
Generally at least three wavelengths were used  for the RM determination (Phil Kronberg, private communication) using polarization data between 37 to 0.9 GHz, with the bulk of the data between $\sim$ 10.5 to 1.6 GHz \citep{SimardNormandin1981}.

In the following sections we will assume that the determinations of the RM values of K08 were typically done at 6 cm and designate the RM values as $\rm{RM_{6}}$. Of course due to the heterogeneity of the sample the wavelength range and typical value over which the RMs are determined might vary.
While this is undesirable, its main effect should be the introduction of noise in the relations
predicted by our model between measured quantities.
There might be additional issues associated with the heterogenous character of the polarization
data used for the RM determinations, which, however, are not addressed here.

The sample of K08 consists of 268 sources at Galactic latitudes $|b| > 45^{\circ}$  (exact definition given in K08).  In B08 we obtained high resolution spectra of 71 relatively bright QSOs and
relaxed the selection to $|b| > 30^{\circ}$.
Here we use the subset that was employed in the study of B08 and \cite{Bernet2010}
(the RM data are still proprietary and will be published elsewhere by P. Kronberg),
except when we look for differences in the redshift evolution and use all sources at $|b| > 30^{\circ}$ which were also in the \cite{Taylor2009} catalogue.

The RM values of TSS09 are based on the NRAO VLA Sky Survey (NVSS)
from \cite{Condon1998} which covers the sky at declinations $|\delta|
> 40^{\circ}$ in Stokes I, Q and U. The survey imaged the sky at 21 cm
with a resolution of $\sim 45$ arcsecs and produced a catalogue of
$2\times10^{6}$ discrete sources. TSS09 choose a subsample of this
catalogue and derived RM values of these sources based on
determination of the polarization angles at 1364.9 MHz and 1435.1
MHz. The subsample was selected by requesting a source intensity
$\rm{I} > 5\: \rm{mJy}$ and a 8$\sigma$ detection in polarized
intensity. To ensure that the polarized intensity is not dominated by
instrumental effects they only considered sources with a fractional
polarization greater than 0.5 $\%$, which yielded a RM catalogue of
37'543 objects. In the following sections we will designate the RM
values of TSS09 as $\rm{RM_{21}}$.

\subsection{Discrepancies}
\label{discrepancies}
After the release of the TSS09's RM catalogue we checked if it contained any of the sources in B08, and found this to be the case for 54 out of 71 of them.
Somewhat surprisingly we found striking differences in the RM values which are briefly
presented here:

i) A comparison of the RM values from K08 and TSS09 reveals that the biggest differences in the RM datasets correspond to large RM values of K08 and sources having a low degree of polarization $p_{21}$. Here $p_{21}$ is the degree of polarization at ~ 21 cm from TSS09 (average degree of polarization at the two wavelengths 20.89 cm $\&$ 21.96 cm). The situation is illustrated in Figure \ref{fig:CompPPK_T}.
Sources with $p_{21} > 3.2\%$ (black cross, 25 QSOs) have quite similar RM values in both datasets and mostly crowd around the diagonal line. On the other hand sources with $p_{21} < 3.2\%$ show a big scatter around the diagonal line. Furthermore there are sources which have large RM values ( $|\rm{RM}| > 50$ rad m$^{-2}$) in the dataset of K08 but very low $|\rm{RM}|$ values in the sample of TSS09. The value of $p_{21} = 3.2\%$ maximizes these effects in Figure \ref{fig:CompPPK_T}.

ii) Using a sample of 371 RM values from TSS09
at latitudes $|b| > 30^{\circ}$ and for which the QSO's redshifts, $z$, were available,
we found no increase in the RM dispersion with $z$, contrary to the main finding of K08. The situation is illustrated in Figure \ref{fig:cumRMz}, where the cumulative RM distributions at 6 cm
(left panel) and 21 cm (right panel) are shown, split at the median fractional polarization of the total sample, $p_{21}=2.5\%$ (blue and black lines), and according to whether the source redshift is below or above $z=1.0$ (solid and dash line, respectively). The cumulative distribution of $|\rm{RM_{21}}|$
shows no evolution with $z$ in both low and high $p_{21}$ samples, whereas
there is a significant broadening of the low $p_{21}$ ($0.5\% < p_{21} < 2.5\%$)
$|\rm{RM_{6}}|$ distribution with $z$. A Kolmogorov-Smirnov test (KS test) reveals that the RM distributions above and below $z=1.0$ are different at a significance level of 99.75\%. We also show  (red distributions) sources with determined $\rm{RM_{6}}$ values which are not in the \cite{Taylor2009} catalogue, but
have declination $|\delta| > 40^{\circ}$ and are thus in the NVSS. Most likely these sources are below the inclusion limits of the \cite{Taylor2009} catalogue, which are a $8\sigma$ detection in polarized intensity and $p_{21}>0.5\%$. A redshift evolution can be seen also for these sources with a similar significance level of 99.64\%. Most likely the broadening of the RM distribution towards lower polarization $p_{21}$ is due to Galactic depolarization and possibly partly due to an increased error in RM, $\delta_{RM}$, towards lower polarized flux levels. This is supported by the fact that $\delta_{RM} \propto \delta_{P}/P$, where P is the polarized flux and $\delta_{P}$ its error \citep{Brentjens2005}, and the high correlation between $p_{21}$ and polarized flux, as attested by a Kendall's $\tau$ test, which yields $\tau=0.40$ and a chance probability of only $4.4\times10^{-30}$ using all 371 RM values.
However the broadening with z seen in the $|\rm{RM_{6}}|$ distributions is hard to explain by an observational bias. The interpretation of a $p_{21}$ dependent redshift evolution of the $|\rm{\rm{RM_{6}}}|$ distribution is however not straightforward either. In section \ref{modelling} we show that it is crucial to distinguish between sight lines with/without intervening galaxies.

iii) The result of B08 that the RM distribution for QSOs with strong MgII systems along their sight lines  is broader (at $\sim 95\%$ significance level) than for QSOs free of absorbers, completely disappears using the RM values of TSS09. Figure \ref{fig:CumRMdist} shows the cumulative distribution
(dash histograms) of $|\rm{RM_{21}}|$ values from TSS09 for sight lines with
($N_{\rm{MgII}}>0$, black)) and without MgII ($N_{\rm{MgII}} =0$, red)
absorption systems.
Clearly there is no difference between the two RM distributions. For comparison the
solid histograms show the distributions of the $|\rm{RM_{6}}|$ values of B08.

\subsection{Caveats}\label{effects:sec}

In the following sections we present a simple model to describe the impact of
inhomogeneous, redshift dependent Faraday screens, on the polarization
and RM of distant QSOs, as a function of wavelength.

However, additional effects may be at work when comparing quantities
measured at different frequencies.  In particular besides potential
large uncertainties measured with both datasets, the low and high
frequency emissions may originate from separate components in the
source (e.g. the radio lobes and the compact core in a radio galaxy),
inducing all sorts of frequency dependent effects, e.g., location,
angular size, spectral indices and fractional polarization.  For
example, in some radio sources the fractional polarization appear to
increase and then decrease with wavelength~\citep{Conway1974}.

Also, while our model could be validated (or ruled out) by comparison
of its predictions with observational data, this would require a
high quality dataset, where the effects discussed above (and possibly
others) are kept under strict control. Unfortunately such a dataset is
not available to us at the moment, which forces us to refrain from
such comparison. The latter, however, might be possible in the near
future, with the delivery of new radio data from polarization surveys,
either planned or just under way (see Sec.~\ref{rms:sec}).

\begin{figure}
\begin{center}
\includegraphics[width=0.450\textwidth]{F1.ps}
\caption[Comparison of the RM values]{Comparison of the RM values of K08 and TSS09, $\rm{RM_{6}}$ and $\rm{RM_{21}}$ respectively, splitted according to whether the degree of polarization is above (black crosses) or below (red filled circles) $p_{21}=3.2\%$. The two datasets differ especially for low $p_{21}$ values. Errors on $\rm{RM}_{6}$ are available for 24 of 54 RM measurments. \label{fig:CompPPK_T}}
\end{center}
\end{figure}

\begin{figure*}
\begin{center}
\includegraphics[width=1.0\textwidth]{F2.ps}
\caption[  ]{Comparison of the cumulative distributions of RM values measured typically at 6cm (left panel) and at 21 cm (right panel). The samples are split according to the polarized fraction $p_{21}$ and the redshifts of the sources. Significant redshift evolution is seen in the $|\rm{RM_{6}}|$ values but not for the $|\rm{RM_{21}}|$ values. For sources with $0.5\% < p_{21} < 2.5\%$ the RM distributions
for sources above z=1 is broader than for sources below z=1, at a significance level of 99.75\%. Red histograms are for NVSS sources not included in~\cite{Taylor2009} catalogue. This is because they are below the inclusion limits of the catalogue, which are a 8$\sigma$ detection in polarized intensity and $p_{21} > 0.5\%$. For these sources also a significant redshift evolution can be seen with a significance level of 99.64\%. \label{fig:cumRMz}}
\end{center}
\end{figure*}

\begin{figure}
\begin{center}
\includegraphics[width=0.450\textwidth]{F3.ps}
\caption[Comparison of the RM distribution]{Comparison of the cumulative RM distributions of B08 (solid) and TSS09 (dash) for QSO sight lines with no MgII absorption systems (black lines) or with one or two, respectively (red lines). RM data in TSS09 were available for 54 out of the 71 QSOs in B08.  \label{fig:CumRMdist}}
\end{center}
\end{figure}

\section{Depolarization by inhomogeneous Faraday screens}

\label{sec:Depmodel}

\subsection{Previous work}
In this section we develop a simple model to understand the effects arising from inhomogeneous Faraday screens and show that these can produce important
depolarization effects that reproduce the differences of the RM datasets of
K08 and TSS09.

The observed polarization $\mathbf{p}$ can be written as a complex number as:
\begin{equation}
\label{eq:ComplexP}
\mathbf{p}=pe^{2i\chi},
\end{equation}
where $p=P/I$ is the fractional degree of polarization given by the
ratio of the polarized and total intensity, P and I, respectively and $\chi$ is the polarization angle determined by the other Stokes parameters, U and Q, as $\chi=1/2\arctan(U/Q)$.

The linear dependence between the polarization angle, $\chi$ and $\lambda^{2}$ stated in Eq. \ref{eq:defRM} is only valid for the case of a uniform foreground screen. Both the presence of unresolved inhomogeneities in the Faraday screen
and/or sources of polarized radiation embedded within the Faraday active region produce increasing depolarization of the source at longer wavelength \citep{Burn1966,Tribble1991,Sokoloff1998}.
This leads to nonlinear dependencies of the polarization angles and $\lambda^{2}$. In such cases detailed modeling is necessary for the correct interpretation of the RMs and for their use in measurements of magnetic fields.

There are several mechanisms that can reduce the fractional degree of polarization either in the radio source itself or in its foreground:
\begin{itemize}
\item[i)] \cite{Burn1966,Sokoloff1998} showed that random fluctuations in the magnetic field within the source lead to a wavelength independent reduction of the degree of polarization. The latter is given by the ratio of the regular-to-total magnetic field energy, $p_{0}=p_{t}(\gamma)B_{r}^{2}/B^{2}$, where $p_{t}(\gamma)=\frac{3\gamma+3}{3\gamma+7}$ is the theoretical value of the degree of polarization which depends on the spectral index $\gamma$ of the emitting relativistic electrons ($\sim 0.74$ for $\gamma \sim 2.8$), and $p_{0}$ is the degree of polarization as
$\lambda \to 0$.

\item[ii)] A further effect which reduces the degree of polarization is {\it differential Faraday Rotation} \citep{Sokoloff1998}. This effect happens if the synchrotron emission and the medium producing the Faraday rotation are not spatially separated. In such a case polarization angles from different depths within the source are rotated differently. The line of sight integrated emission suffers increasing depolarization with increasing wavelength. For extragalactic sources this effect seems not to be important \citep{Tribble1991}.

\item[iii)] Inhomogeneous Faraday Rotation screens within the radio beam lead to depolarization of the sources. If the RM screen is modelled by many independent RM cells, this effect is called depolarization by {\it external Faraday dispersion} \citep{Burn1966,Sokoloff1998}. If the RM screen varies systematically within the radio beam this effect is called {\it beam depolarization}.

\end{itemize}

\cite{Burn1966} gives the formula
\begin{equation}
\label{eq:BurnDep}
p=p_{0}\exp(-2\sigma_{RM}^{2}\lambda^{4})
\end{equation}
to describe the depolarization induced by an inhomogeneous Faraday
screen with a RM dispersion $\sigma_{RM}$.
Assuming for simplicity that each RM cell is a cube of linear size $l_{0}$,
then each cell contributes a dispersion $\sigma_{c}=0.81Bn_{e}l_{0}$
and $\sigma_{RM}=\sigma_{c}\sqrt{\eta}$,
where $\eta=L/l_{0}$ is the number of cells along the
path-length L traversed by the radio waves.

The size of the cell is determined by the scale above which the RM
contributions are uncorrelated and can be
determined by computing the structure function in high resolution RM
maps.\footnote{The structure function D at scale s is
  defined as $D(s)=\langle(RM(x+s)-RM(x))^{2}\rangle$ and
  $\langle\rangle$ means ensemble averaging.}

\cite{Rossetti2008} and \cite{Mantovani2009} modelled polarisation
observations of $\sim 65$ compact steep spectrum sources between 2.8
to 21 cm done with the WSRT, VLA and Effelsberg telescope. They
observed that the fractional degree of polarisation at large
wavelengths is too large to be explained by Burn's depolarization law
(Eq.\ref{eq:BurnDep}). They observed that for a large fraction of
sources p remains approximately constant above 6 - 13 cm. To account
for these observation they suggested that just a fraction of the
polarised source is covered by a depolarising inhomogeneous RM screen
and modified Eq.~\ref{eq:BurnDep} to

\begin{equation}
\label{eq:fracDep}
p=p_{0}(f_{c}\exp(-2\sigma_{RM}^{2}\lambda^{4}) +(1-f_{c})),
\end{equation}
where $f_{c}$ is the covering factor of the source.

Here we emphasize that \textit{partial} coverage of the polarized
source by inhomogeneous RM screens is the key for explaining the
differences in the RM values of K08 and TSS09.

\section{Modelling}
\label{modelling}
\subsection{Extension to cosmological screens}

In Eq. \ref{eq:fracDep} the ($1+z)^{-2}$ correction for cosmological distances is not included.
Assuming that the RM dispersion causing the depolarization, $\sigma_{RM}$, is constant with z,
we modify Eq. \ref{eq:fracDep} for cosmological sources as:
\begin{equation}
\label{eq:fracDep_z}
p=p_{0}(f_{c}\exp(-2\sigma_{RM}^{2}(1+z)^{-4}\lambda^{4}) +(1-f_{c})).
\end{equation}
Thus the width of $p(\lambda)$ changes as a function of z as

 \begin{equation}
\label{eq:widthp}
\sigma_{p}=\frac{(1+z)^{2}}{2\sigma_{RM}}.
\end{equation}
This shows that depolarization by a non-evolving rest frame Faraday
dispersion screen is expected to decrease for screens at higher
redshift. Below, we explicitly compute the depolarization by typical
RM screens as a function of redshift of the sources.

\subsection{A simple model}

In our model the Faraday screens consist of three components:
(i) an inhomogeneous foreground screen local to the source with covering
factor $f_{c,QSO}$, (ii) an inhomogeneous foreground
screen in intervening galaxies with covering factors $f_{c,MgII}$ and
(iii) a homogeneous screen due to the Milky Way, which is assumed
uniform across the extension on the sky of the polarized source.

The uniform Faraday screen in the Milky Way is set to a constant
value, $RM_{MW}= -10\: \rm{rad\: m^{2}}$. This value is consistent with \cite{Schnitzeler2010} who determined the
Milky Way contribution of Rotation Measures at $|b| > 20^{\circ}$ using the \cite{Taylor2009} data.

On the other hand, each inhomogeneous foreground Faraday screen is
characterized by an ensemble of cells of size $l_{0}$ with
uncorrelated RM values.  The RM values have a Gaussian distribution
with dispersion $\sigma_{RM_x}/(1+z_x)^{2}$ and zero mean, where
$\sigma_x$ is the rest-frame RM dispersion, $z_x$ the screen's redshift
and, $x=QSO,MgII,$ labels different screens types, for which the
above parameters may differ.

 If the RM screen is at the source redshift and the source has linear
 size  $s$, then it is covered by $N=s^{2}/l_{0}^{2}$ cells.  Of these, only
 a fraction $f_{c,x}$ will be Faraday active for each screen. If the RM screen
is at the redshift of the MgII systems, $s$ is the projected linear size of the source
viewed from the Earth at the distance to the MgII system.

Each screen is then fully described by a realization of $N$ RM values,
a fraction $f_{c,x}$ of which are extracted from the associated
Gaussian distribution to characterize the active cells, while the
reminder are set to zero to represent the inactive cells. Assuming a
uniform flux of normalized intensity (I=1) and uniform (zero)
intrinsic polarization angle across the source surface, we can write
the following relations for the remaining non-zero Stokes parameter U,
Q, the angle and degree of polarization, respectively,
\begin{align}
U(\lambda^{2}) &= \frac{1}{N}\sum_{i=1}^{N}\sin\left(2RM_{i}\lambda^{2}\right) \\
Q(\lambda^{2}) &= \frac{1}{N}\sum_{i=1}^{N}\cos\left(2RM_{i}\lambda^{2}\right) \\
\label{eq:polangle}
\chi(\lambda^{2}) & = \frac{1}{2}\arctan\left(\frac{U}{Q}\right)  \\
\label{eq:degreepol}
p(\lambda^{2})&= \sqrt{U^{2}+Q^{2}},
\end{align}
where
\begin{equation}
\label{eq:RMi}
RM_{i}=RM_{QSO,i}+RM_{MgII,i}+RM_{MW},
\end{equation}
are random variables determined by a Monte-Carlo realization.

In Figure \ref{fig:sketch_dep} we present generic results for three
representative cases, namely a low ($z_{QSO}<1$) and high
($z_{QSO}>1$) redshift QSO with no intervening absorber in the top and
mid panel, respectively, and a high redshift QSO with intervening
absorber in the bottom panel. More detailes are specified below.  In
all cases, the inhomogeneous screen comprise eight cells,
$N\,f_{c,x}=8$.

In each panel we plot the polarization angle, $\chi$ (black solid line
-- left y-axis), and the polarization fraction, p (red solid line --
right y-axis) as a function of $\lambda^{2}$.
To emphasize the importance of the effects of depolarization, we also
show the rotation in polarization angle produced by (a) the average RM
within the beam (dash line),
$$\chi=RM_{avg}\lambda^{2},$$
where
\begin{align} \label{avgrm:eq}
RM_{avg}=&\frac{1}{N}\sum_{i=1}^{N}RM_{i}\\  \label{avgrm2:eq}
=&RM_{MW}+\frac{1}{N}\sum_{i=1}^{N}RM_{QSO,i}+RM_{MgII,i},
\end{align}
and (b) by the Milky Way (dash-dot line),
$$\chi=RM_{MW}\lambda^{2}.$$
Note that $RM_{avg}$ is in general non-zero and different
from $RM_{MW}$. This is because for fixed fraction of active cells
the second term in Eq.~\ref{avgrm2:eq}
is a random number of aplitude $1/\sqrt{N}$, with null
probability of being either zero or $-RM_{MW}$.
Finally, from left to right, the vertical blue dash lines indicate the typical
observational wavelength of 20 GHz for \citep{Jackson2010,Murphy2010}, of 5 GHz for K08 and of 1.435 GHz and 1.365 GHz
for the NVSS survey \citep{Condon1998}) and~\cite{Taylor2009}.

The top panel illustrates the case of a low redshift sources ($z < 1.0$),
with observed RM dispersion of $\sigma_{RM,QSO}/(1+z)^{2}= 28\;
\rm{rad\: m^{-2}}$, $f_{c,QSO}=0.5$ and no intervening MgII absorber ($f_{c,MgII}=0$).
It can be seen that at
short wavelengths, $\lambda^{2} < 0.014$, application of the simple
$\lambda^2$ relation in Eq. \ref{eq:defRM}, yields the average RM within the beam
from which the RM distributions in the foreground screens can be inferred \citep{Bernet2008}.
However, at longer wavelengths the flux through the inhomogeneous screen is depolarized so that the
change in polarization angle is dominated by the
contribution of the Milky Way. Correspondingly,
the degree of polarization is given by $p \sim 1-f_{c,QSO}$.

The mid panel illustrates the case for a high redshift source, $z > 1.0$
with observed RM dispersion of $\sigma_{RM,QSO}/(1+z)^{2}= 8\;
\rm{rad\: m^{-2}}$ and $f_{c,QSO}=0.5$. In this case, depolarization is
negligible up to $\lambda^{2}=0.05$ or at 1.4 GHz. This means across
most of the considered wavelength range application of the
$\lambda^2$ relation in Eq. \ref{eq:defRM} would yield
the average RM contributed by both the QSO screen and the Milky Way.

Finally, the bottom panel illustrates the same case as the mid panel but
with an additional Faraday screen due to an absorber, with
$\sigma_{RM,MgII}/(1+z)^{2}\sim\: 230\: \rm{rad\: m^{-2}}$ and $f_{c,MgII}=0.5$.

This case has direct connection to the study of B08,
who showed that intervening galaxies traced by MgII absorption
lines contribute an additional Faraday screen with an observed rest
frame RM dispersion $\sigma_{MgII}= 140\;\rm{rad\; m^{-2}}$.
In the context of our simple model,
this implies a RM dispersion of the individual cells of the screen,
responsible for the depolarization,
$\sigma_{RM,MgII}=\sigma_{MgII}\sqrt{N/f_{c,MgII}}$.
The value for $\sigma_{RM,MgII}/(1+z)^{2}$ assumed above is
is based on this relation and the choice of $N\,f_{c,MgII}=8$.
The bottom panel of Fig.~\ref{fig:sketch_dep}
shows that with this choice of parameters the intervening screen causes
significant depolarization above $\lambda^2 \sim 0.003 \rm{m^{2}}$.
In this case the application of the $\lambda^2$ relation at longer wavelengths
yields the Milky Way RM value.

The approach taken here, is valid in the limit of large number of random cells.
Using the total flux - angular diameter relation given by
\cite{Windhorst1984} we can estimate the extension of the region of the polarized emission.
The median flux of our sources which are in the \cite{Taylor2009} catalogue (371 sources)
is 1.2 Jy. This translates to a median source size in total flux of $\sim$ 10 arcsecs. Since the
polarized emission is likely to be dominated by some hotspots the effective size in
polarized emission is expected to be smaller than that.
Given that the extension of the polarized emission is a few arcsecs
and what we know about the scale of fluctuations of the RM (see next section) we
expect a significant number of cells within the beam.
In addition, using Eq. \ref{eq:fracDep_z} and future multi-wavelength radio polarization
observations one can determine $\sigma_{RM,MgII}$ and $f_{c,MgII}$ directly
and thus calculate N.

Finally, we have assumed a homogeneous RM screen in the Milky Way.
\cite{Gaensler2005}, however, shows that arcsec scale fluctuation
exist in the RM screen of the Large Magellanic Cloud
and~\cite{Haverkorn2008} shows that there are RM fluctuation in the
local interstellar medium.  Inhomogeneous Galactic RM contribution,
which might vary for different sight lines, would lead to additional
depolarization and add scatter to the predicted trends (see section
\ref{Dep_model}) of our simple model, but cannot mimic them.

\subsection{Model predictions} \label{Dep_model}

Based on this toy model with the free parameters $f_{c,x}$,
$\sigma_{RM,x}$, we can predict simple trends in the observed angle
and degree of polarization measured at fixed frequency as a function
of radio source's redshift.  For simplicity we shall assume there is
no redshift evolution in the model parameters.  We must also
distinguish between the two cases with and without the Faraday screen
provided by intervening galaxies.

For the case without intervening galaxies the model predicts
\begin{itemize}

\item[i)] that towards low redshifts $p_{21}/p_{\lambda \rightarrow 0}
  \sim 1-f_{c,QSO}$, because the flux through the inhomogeneous Faraday
  screen is depolarized.

\item[ii)] that towards high redshift $p_{21}/p_{\lambda \rightarrow 0} \approx  1 $
because the depolarization effects are suppressed. However,
$p_{21}/p_{\lambda \rightarrow 0}$ anti-correlates with $\sigma_{RM,QSO}$ due to residual
depolarization effects associated with the local screen.

\item[iii)] that towards low redshifts the discrepancy $|\rm{RM_{\lambda \rightarrow 0}-RM_{21}}|$ increases
because due to depolarization effects
$\rm{RM_{\lambda \rightarrow 0}}$ measures $\rm{RM_{avg}}$ while $\rm{RM_{21}}$ is dominated
by the Milky Way contribution.

\item[iv)] that the discrepancy $|\rm{RM_{\lambda \rightarrow
      0}-RM_{21}}|$ decreases towards high redshifts because both
  $\rm{RM_{\lambda \rightarrow 0}}$ and $\rm{RM_{21}}$ tend to measure
  the average $\rm{RM_{avg}}$ (Eq.~\ref{avgrm:eq}).

\end{itemize}
For the case with intervening galaxies the model predicts
\begin{itemize}

\item[i)] that at all redshift the discrepancy $|\rm{RM_{\lambda \rightarrow 0}-RM_{21}}|$ is large,
because due to depolarization effects
$\rm{RM_{\lambda \rightarrow 0}}$ measures $\rm{RM_{avg}}$ and $\rm{RM_{21}}$ is dominated
by the Milky Way contribution.

\item[ii)] that at all redshift $p_{21}/p_{\lambda \rightarrow
    0}\lesssim 1-f_{c,MgII}$ because the sources will be significantly
  depolarized.

\end{itemize}

 \begin{figure}
\begin{center}
\includegraphics[width=1\hsize]{F4.eps}
\caption[Summary of effects of intrinsic RM screen]{
Angle of polarization, $\chi$ (black solid line -- left y-axis),
and theoretical polarization fraction, p (red solid line -- right y-axis), as a function of $\lambda^{2}$,
for three models of inhomogeneous Faraday screens:
a low (top) and high (mid) redshift QSO with no intervening absorbing system,
and a high redshift QSO with intervening absorber (bottom).
   The dash line indicates the rotation of
   polarization angles due to the average RM within the beam,
  $\chi=RM_{avg}\lambda^{2}$, and the dash-dot line
  that due to the Milky Way, $\chi=RM_{MW}\lambda^{2}$.
  The vertical blue dash lines from left to
  right, indicate typical wavelength of observations at 1.5 cm, at 6 cm (K08),
  and at 20.89 cm and 21.96 cm (NVSS survey, \cite{Condon1998})
  for \cite{Taylor2009} calculated RM values.
  In the top and mid panel the Faraday screens include an inhomogeneous
  screen local to the source with a covering factor $f_{c}=0.5$
  and a screen in the Milky Way that is uniform across the source extension.  In the top
  panel the source QSOs is at $z < 1.0$ and has
  $\sigma_{RM,QSO}/(1+z)^{2}= 28\; \rm{rad\: m^{-2}}$; in the mid panel the
  QSO is at $z > 1.0$ and has $\sigma_{RM,QSO}/(1+z)^{2} =
  8\; \rm{rad\: m^{-2}}$. The bottom panel is the same as the mid panel with an additional
  Faraday screen due to an intervening system, with $\sigma_{RM,MgII}/(1+z)^{2}\sim\: 230\:
  \rm{rad\: m^{-2}}$ and $f_{c}=0.5$. \label{fig:sketch_dep}}
\end{center}
\end{figure}

\section{Discussion}
 \label{sec:discussion}

\subsection{Nature of the partial inhomogeneous RM screen}

It is instructive to look at high resolution Very Long Baseline Array
(VLBA) radio polarization observations of some of our objects in
K08. Examples of sources where VLBA polarization observations exist
are 3C43 \citep{Cotton2003}, 3C118 \citep{Mantovani2009} and B1524-026
\citep{Mantovani2002}. Typical resolutions of these observations are
$\sim 8 \times 8\: \rm{mas^{2}}$, which corresponds to a resolution of
$64\:\rm{pc}\times 64\:\rm{pc}$ at $z \sim 1$. At such a high
resolution complex structures in polarization angles and RM maps are
revealed.  Often it can be seen, e.g B1524-026 \citep{Mantovani2002}
that there is a dominant compact component in polarised flux and a
more extended diffuse polarised component. Further it can be seen that
the diffuse component consist of many independent RM cells. That means
that for unresolved observations at large wavelengths the diffuse
component will cancel and the more compact component dominates the
observations.

For some sources it possible that the number of cells
$f_{c}N$ in the RM screen is very low. In this case no depolarization
is observed but p and $\chi$ oscillate. This situation was observed
for the source 3C 27 by \cite{Goldstein1984}.  \cite{Rossetti2008} fitted a
two component model to the data to describe p and $\chi$ for the
source B3 0110+401. \cite{Farnsworth2011} also used a two component
model to describe radio polarization observation at large wavelengths
$\lambda \sim 1$ m.

For the sightlines with intervening galaxies it is very natural to
assume that the magnetic fields within them will lead to
depolarization, an effect studied in the LMC by \cite{Gaensler2005}.
 Using the Milky Way as typical galaxy we would expect
depolarization of the background QSOs. For NGC 1310 this effect was observed by
\cite{Fomalont1989} and~\cite{Schulman1992}.
One possibility is that the
source covers both the spiral arms and interarm regions. For the
spiral arms the coherence lengths of the magnetic fields are much
shorter as suggested by observations of \cite{Haverkorn2008}. These
authors gives an outer scale of turbulence of 0.1 kpc for interarm
regions and 10 pc for the spiral arms in the Milky Way\footnote{The
  small coherence lengths of the magnetic fields has probably to do
  with our point of view in the disc of the Milky Way. We know of
  course from observations of nearby spiral galaxies that there is a
  magnetic field component which is coherent over several kpc.}. In
this way the area covered by the spiral arms would be depolarized and
the interarms would produce a coherent screen. Other interpretations
are again as for the QSO itself that the polarized emission is
dominated by one compact component which competes with a more extended
diffuse emission. If the size of the compact component is small
enough, this component could get a coherent screen whereas the
extended source gets different RM screens which will lead to
depolarization of this component.

\subsection{Rotation Measure Synthesis} \label{rms:sec}

At the moment there are several polarization surveys under way or
planned, e.g. GALFACTS \citep{Taylor2010}, LOFAR \citep{Anderson2012},
or POSSUM \citep{Gaensler2010} within ASKAP. These
polarization surveys should pave the way for the planned polarization
survey for SKA \citep{Gaensler2004,Gaensler2009,Beck2004b}. In
particular one wishes to study the evolution of magnetic fields in
galaxies and in the intergalactic medium as a function of cosmic time
using large RM datasets.

\begin{figure}
\begin{center}
\includegraphics[width=0.48\textwidth]{F5.eps}
\caption[FD_spectrum_lowzQSO]{Original Faraday spectrum for a low
  redshift QSO and its associated observed polarization angle and
  degree, together with the recovered Faraday spectrum for a finite
  wavelength coverage. The Monte Carlo realization is identical to the
  top panel in Figure \ref{fig:sketch_dep}. Upper left panel: Original
  Faraday spectrum for a low redshift QSO with a homogeneous Milky Way
  RM screen of $\rm{RM}=-10\: \rm{rad\: m^{2}}$ and an inhomogeneous
  intrinsic RM screen with $\sigma_{RM,QSO}/(1+z)^{2}= 28\: \rm{rad\:
    m^{-2}}$ and a covering factor $f_{c}=0.5$. Upper middle panel:
  Corresponding U and Q Stokes parameters (thin solid line, thin
  dashed line) and degree of polarization p (thick solid line) as a
  function of $\lambda^{2}$. An observational error
  $\sigma_{U,Q}\approx 0.017\%$ is added to every channel. Upper right
  panel: Corresponding polarization angle $\chi$
  vs. $\lambda^{2}$. The dashed line indicates the expected
  polarization angle from the homogeneous Milky Way RM
  contribution. Lower left panel: Recovered Faraday spectrum for the
  wavelength range $\lambda_{min}=0.03 \rm{m}$ to $\lambda_{max}=0.27
  \rm{m}$. The thin solid/dashed line indicates the real/imaginary
  part of the spectrum and the thick solid line shows the
  amplitude. Lower middle panel: Faraday spectrum after applying the
  CS-RM-Thin method of \cite{Li2011} to correct for the limited
  wavelength coverage.  \label{fig:FD_spec_lowzQSO}}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[width=0.50\textwidth]{F6.eps}
\caption[FD_spectrum_highzQSO_MgII]{Identical to Figure \ref{fig:FD_spec_lowzQSO} but for the case of a high redshift QSO with an intervening MgII system. The Monte Carlo realization is identical to the bottom panel in Figure \ref{fig:sketch_dep}\label{fig:FD_spec_highzQSO_MgII}}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[width=0.49\textwidth]{F7.eps}
\caption[FD_spectrum_highzQSO_MgII_largew]{Identical to Figure \ref{fig:FD_spec_highzQSO_MgII} with same $\Delta \lambda^{2}$ coverage and thus identical Faraday depth resolution $\delta \phi$ but with observations done at longer wavelengths. \label{fig:FD_spec_highzQSO_MgII_largew}}
\end{center}
\end{figure}

With the large number of available spectral channels in these surveys,
e.g. a few thousands, Faraday Rotation Measure Synthesis
\citep{Brentjens2005} can be performed. Using this technique one
performs a Fourier transformation of the observed complex polarization
$p(\lambda^{2})$ to obtain a Faraday depth spectrum $F(\phi)$. Here
the case of a single uniform Faraday screen corresponds to a delta
function in Faraday depth space and in this case the Faraday depth is
equal to the traditional RM (Eq.~\ref{eq:defRM}).

Basic parameters for a Faraday survey are the maximum observable
Faraday depth, $\phi_{max} \approx \sqrt{3}/ \delta\lambda^{2}$, the
Faraday depth resolution, $\delta \phi \approx 2\sqrt{3}/ \Delta
\lambda^{2}$ and the largest scale in Faraday depth that one is
sensitive to, max-scale $\approx \pi/\lambda_{min}^{2}$. Here
$\delta\lambda^{2}$ is the channel width, $\Delta \lambda^{2}$ is the
total bandwidth and $\lambda_{min}^{2}$ is the smallest wavelength
(squared) of the observations. Regions which produce only Faraday
rotation but do not emit polarized radiation can be described by Dirac
$\delta$ functions in $\phi$ space and are Faraday-thin sources
\citep{Brentjens2005}. Below we discuss our model of the
depolarization of QSOs in terms of Faraday Rotation Measure
Synthesis. This is to provide some basic comparisons for ongoing or
future RM surveys. See e.g. \cite{OSullivan2012} for current observations
of Faraday depth spectra.

In the next, with the auxilium of
Fig.~(\ref{fig:FD_spec_lowzQSO})--(\ref{fig:FD_spec_highzQSO_MgII_largew}) we
give a simple example of the application of RM-synthesis to the same
cases studied in Figure~\ref{fig:sketch_dep}, which illustrates the
advantages of this emerging technique.  In Figure
\ref{fig:FD_spec_lowzQSO} the original Faraday spectrum for a low
redshift QSO without intervening galaxies is shown. Here the Monte
Carlo realization is the same as in Figure \ref{fig:sketch_dep} (upper
panel) with adopted parameters $\sigma_{RM,QSO}/(1+z)^{-2}= 28\:
\rm{rad\: m^{-2}}$ and $f_{c,QSO}=0.5$. In particular, all of the  16 cells have the
contribution from the MW and eight cells have an additional
intrinsic low-z QSO contribution. The Faraday spectrum is only
real valued which means that the intrinsic polarization angles are
zero. The adopted minimum and maximum wavelengths are
$\lambda_{min}=0.03\: \rm{m}$ and $\lambda_{max}=0.27\; \rm{m}$ and
correspond to a Faraday depth resolution of $\delta \phi \approx\: 48.1\:
\rm{rad\: m^{-2}}$. The choosen wavelength range corresponds to the
offered wavelength range at the Australia Telescope Compact Array
which is similar to the EVLA \citep{Beck2012}.  The recovered Faraday
spectrum with this resolution is shown in the lower left panel.

There are several methods to recover the information lost due to the
incomplete wavelength coverage \citep{Heald2009,Li2011}. We use here
the compressive sampling (CS) method of \cite{Li2011}. Best results
are obtained if prior information about the Faraday spectrum is
present, e.g. if the sources are Faraday thin or thick. The obtained
Faraday spectrum after applying the CS RM thin method of \cite{Li2011}
to the Q and U vectors (upper middle panel) is shown in the lower
right panel. It can be seen that the homogeneous RM component at -10
$\rm{rad\: m}^{-2}$ can be approximately recovered, but not all of the
inhomogeneous RM components.

In Figure \ref{fig:FD_spec_highzQSO_MgII} the Faraday spectrum for a
high redshift QSO with an intervening galaxy is shown. Here the
Faraday spectrum is identical to the one used in Figure
\ref{fig:FD_spec_lowzQSO} in the lower panel with the parameters
$\sigma_{RM,MgII}/(1+z)^{2}\sim\: 230\: \rm{rad\: m^{-2}}$ and
$f_{c,MgII}=0.5$, $\sigma_{RM,QSO}/(1+z)^{2}\sim\: 8\: \rm{rad\:
  m^{-2}}$ and $f_{c,QSO}=0.5$, and $\rm{RM}=-10\: \rm{rad}\: m^{-2}$.
In the Monte Carlo realization
shown in Figure \ref{fig:FD_spec_highzQSO_MgII} all of the 16 cells have the
contribution from the MW, eight (random) cells have an additional
intrinsic high-z QSO contribution and eight (random) cells have an
additional contribution from the intervening galaxy.
With the observational parameters $\lambda_{min}=0.03\: \rm{m}$ and
$\lambda_{max}=0.27\: \rm{m}$ and $\delta \phi \approx 48.1 \; \rm{rad\: m^{-2}}$
the MW+QSO components can not be resolved but lead to a
distinct peak at $\phi \approx -10\; \rm{rad}\; \rm{m}^{-2}$ with an
amplitude $\sim 0.45$ $\rm{m}^{2}\: \rm{rad^{-1}}$ in the recovered
Faraday spectrum. On the other hand, the eight RM components with
contributions from intervening galaxies can be well resolved with the
assumed covered wavelength range.

For comparison in Figure \ref{fig:FD_spec_highzQSO_MgII_largew}
we show the recovered Faraday spectrum for observations using longer
wavelengths, $\lambda_{min}=0.27\: \rm{m}$ and $\lambda_{max}=0.38\:
\rm{m}$ but with the same covered wavelength range $\Delta
\lambda^{2}$. This shows that the qualitative features of the
Faraday spectrum are also recovered, although with a lower quality
than in Fig.~\ref{fig:FD_spec_highzQSO_MgII}.

In summary, from section \ref{Dep_model} using polarization angle
$\chi$ vs. $\lambda^{2}$ observations one might conclude that it is
best to do observations at short wavelengths (below the exponential
fall off) in order to measure the average RM. However as we have
illustrated above using RM Synthesis this is not necessary. In order
to be able to resolve the individual RM components a large $\Delta
\lambda^{2}$ is required. (See \cite{Beck2012} for a summary of the
Faraday depth resolution $\delta \phi$ of current and future radio
telescopes.) The proposed wavelength range for SKA with $\lambda \sim
0.03 - 4.3\: \rm{m}$ and $\Delta \lambda \sim 18\: \rm{m^{2}}$ and
$\delta \phi \sim\: 0.2\: \rm{rad}\: \rm{m}^{-2}$ will offer a superb
Faraday resolution to resolve individual RM components in intervening
galaxies.

\section{Summary and conclusions}
\label{sec:summary}

In previous work we have used RM values from K08, typically determined
at 6 cm, to study magnetic fields in normal galaxies at high
redshift. When the analysis was repeated using the recently released
RM data of TSS09, determined at 21 cm, we could find neither a
correlation between $|$RM$|$ and absorbing systems as in B08, nor an
increase in the RM dispersion with z as found in K08.  Motivated by
the above results, we have attempted to understand those differences
in terms of a simple model based on inhomogeneous Faraday screens
associated both with the QSO and the MgII host galaxies, and for both
low and high redshift.

We find that the presence of inhomogeneous screens leads to important
departures from the classical $\lambda^2$ dependence of the rotation
of the polarization angle.  Related to this are depolarization effects
which become stronger towards higher wavelengths.  As a result, due to
cosmological redshift, observations at fixed wavelength are affected
differently by depolarization and are sensitive to different Faraday
active components.  In particular depolarization effects become
stronger for lower redshift QSOs.  We find that the depolarization
saturates to a value given by the intrinsic polarization times the
complement of the covering factor of the inhomogeneous screen,
$(1-f_c)$.

Actual predictions depend on the assumed values for the model
parameters. The following results apply for the choices made in
section.~\ref{modelling}, which are relevant for the current
investigation.  When the line of sight to the QSO is free of
absorption systems, application of the $\lambda^2$ analysis to extract
RM values from radio observations then has the following consequences:
\begin{itemize}
\item for low redshift QSOs, $\rm{RM_{21}}$ is dominated by the Milky
  Way contribution, while $\rm{RM_{\lambda \rightarrow 0}}$ measures
  $\rm{RM_{avg}}$ (see Eq. \ref{avgrm:eq}).
\item for high redshift QSOs, in general the RM value reflect $\rm{RM_{avg}}$
\end{itemize}

The presence of absorption systems contributes an additional Faraday
screen which further depolarizes the low frequency radiation.
Therefore,
\begin{itemize}
\item while $\rm{RM_{\lambda \rightarrow 0}}$ is given by
  $\rm{RM_{avg}}$, $\rm{RM_{21}}$ is dominated by the Milky Way
  contribution and the discrepancy $|\rm{RM_{\lambda \rightarrow
      0}-RM_{21}}|$ is large at all redshifts.
\end{itemize}

In conclusion, while the model is admittedly simple, it seems
plausible to consider that the discrepancy between results based on
K08 and TSS08 RM are due to the severe depolarization induced by
inhomogeneous Faraday screen on high wavelength radiation.  This,
however, does not exclude the importance of other effects.

Finally, the study of magnetic fields in galaxies as a function of
cosmic time will benefit considerably from the application of
RM-synthesis, which has the power to disintangle the contribution from
inhomogeneous magneto-active components. For this purpose,
instrumental bandwidth is most important, although higher frequency
channels appear to deliver higher quality. This conclusions may be
refined with future investigations.

\acknowledgements We are very grateful to an anonymous referee for
several valuable comments which helped improve the manuscript
considerably.  This work was supported by the Swiss National Science
Foundation and has made use of NASA's Astrophysics Data System.
During the refereeing process a related work by \cite{Arshakian2011}
appeared. It makes general predictions for future radio polarization
surveys in qualitative agreement with ours, though it does not study
the case of intervening galaxies. Further the RM catalogue of \cite{Hammond2012} appeared
with determined redshifts of 4003 sources of the \cite{Taylor2009} sample. Similar to our
findings they do not see any redshift evolution of the RM distribution in their large sample.

\vskip 0.5truecm