ในสาขาวิชาคณิตศาสตร์ทฤษฎีกราฟทฤษฎีบทการสุ่มตัวอย่างแบบเดินขยาย (expander walk sampling theorem)กล่าวไว้โดยสัญชาตญาณว่าการสุ่มตัวอย่างจุดยอดในกราฟขยายโดยการเดินสุ่มระยะ สั้นๆ สามารถจำลองการสุ่มตัวอย่างจุดยอดโดยอิสระจากการกระจายแบบเอกรูป ได้ ทฤษฎีบทเวอร์ชันแรกสุดเป็นผลงานของAjtai, Komlós & Szemerédi (1987)และเวอร์ชันทั่วไปมักถูกยกให้เป็นผลงานของGillman (1998 )

อนุญาต ${\displaystyle G=(V,E)}$เป็นกราฟขยายที่ มี n จุดยอดและ มีขอบที่มีน้ำหนักเป็นบวก และให้${\displaystyle A\subset V}$. อนุญาต${\displaystyle P}$ให้ แทนเมทริกซ์สุ่มของกราฟ และให้${\displaystyle \lambda _{2}}$เป็นค่าลักษณะเฉพาะ ที่ใหญ่เป็นอันดับสอง ของ${\textstyle P}$. อนุญาต${\displaystyle y_{0},y_{1},\ldots ,y_{k-1}}$ระบุจุดยอดที่พบใน${\displaystyle (k-1)}$- การเดินแบบสุ่มทีละขั้นตอนบน${\displaystyle G}$เริ่มต้นที่จุดยอด${\displaystyle y_{0}}$และปล่อยให้${\textstyle \pi (A):=}$${\displaystyle \lim _{k\rightarrow \infty }{\frac {1}{k}}\sum _{i=0}^{k-1}\mathbf {1} _{A}(y_{i})}$. ที่ไหน${\textstyle \mathbf {1} _{A}(y){\begin{cases}1,&{\text{ถ้า }}y\in A\\0,&{\text{มิฉะนั้น }}\end{cases}}}$

(เป็นที่ทราบกันดี^{[ 1 ]}ว่าวิถีเกือบทั้งหมด${\displaystyle y_{0},y_{1},\ldots ,y_{k-1}}$ลู่เข้าสู่จุดจำกัดบางจุด${\textstyle \pi (A)}$, เช่น${\textstyle k\rightarrow }$${\textstyle \infty }$.)

ทฤษฎีบทกล่าวว่าสำหรับกราฟที่มีน้ำหนัก${\displaystyle G=(V,E)}$และการเดินแบบสุ่ม${\displaystyle y_{0},y_{1},\ldots ,y_{k-1}}$ที่ไหน${\displaystyle y_{0}}$ถูกเลือกโดยการแจกแจงเริ่มต้น${\textstyle \mathbf {q} }$สำหรับทุกคน${\displaystyle \gamma >0}$เรามีขอบเขตดังต่อไปนี้:

${\displaystyle \Pr \left[{\bigg |}{\frac {1}{k}}\sum _{i=0}^{k-1}\mathbf {1} _{A}(y_{i})-\pi (A){\bigg |}\geq \gamma \right]\leq Ce^{-{\frac {1}{20}}(\gamma ^{2}(1-\lambda _{2})k)}.}$

ที่ไหน${\displaystyle C}$ขึ้นอยู่กับ${\displaystyle \mathbf {q} ,G}$และ${\displaystyle A}$.

ทฤษฎีบทนี้ให้ขอบเขตสำหรับอัตราการลู่เข้าสู่${\displaystyle \pi (A)}$เมื่อพิจารณาจากความยาวของการเดินแบบสุ่ม จึงทำให้ได้วิธีการประมาณค่าที่มีประสิทธิภาพมากขึ้น${\displaystyle \pi (A)}$เมื่อเปรียบเทียบกับการสุ่มตัวอย่างจุดยอดแบบอิสระของ${\displaystyle G}$.

เพื่อพิสูจน์ทฤษฎีบท เราจะให้คำจำกัดความบางส่วน ตามด้วยบทพิสูจน์ย่อยสามข้อ

อนุญาต${\displaystyle {\it {{w}_{xy}}}}$เป็นน้ำหนักของขอบ${\displaystyle xy\in E(G)}$และปล่อยให้${\textstyle {\it {{w}_{x}=\sum _{y:xy\in E(G)}{\it {{w}_{xy}.}}}}}$กำหนดให้โดย${\textstyle \pi (x):={\it {{w}_{x}/\sum _{y\in V}{\it {{w}_{y}}}}}}$. อนุญาต${\textstyle {\frac {\mathbf {q} }{\sqrt {\pi }}}}$เป็นเมทริกซ์ที่มีรายการต่างๆ${\textstyle {\frac {\mathbf {q} (x)}{\sqrt {\pi (x)}}}}$และปล่อยให้${\textstyle N_{\pi ,\mathbf {q} }=||{\frac {\mathbf {q} }{\sqrt {\pi }}}||_{2}}$.

อนุญาต${\displaystyle D={\text{diag}}(1/{\it {{w}_{i})}}}$และ${\displaystyle M=({\it {{w__{ij})}}}$. อนุญาต$P(r) = PE_{r}}$ที่ไหน${\textstyle P}$คือเมทริกซ์สุ่ม${\textstyle E_{r}={\text{diag}}(e^{r\mathbf {1} _{A}})}$และ${\textstyle r\geq 0}$. แล้ว:

${\displaystyle P={\sqrt {D}}S{\sqrt {D^{-1}}}\qquad {\text{และ}}\qquad P(r)={\sqrt {DE_{r}^{-1}}}S(r){\sqrt {E_{r}D^{-1}}}}$

ที่ไหน${\displaystyle S:={\sqrt {D}}M{\sqrt {D}}{\text{ และ }}S(r):={\sqrt {DE_{r}}}M{\sqrt {DE_{r}}}}$. เช่น${\displaystyle S}$และ${\displaystyle S(r)}$เนื่องจากสมมาตร จึงมีค่าไอเกนเป็นจำนวนจริง ดังนั้น เมื่อค่าไอเกนของ${\displaystyle S(r)}$และ${\displaystyle P(r)}$เท่ากัน ค่าลักษณะเฉพาะของ${\textstyle P(r)}$เป็นเรื่องจริง ให้${\textstyle \lambda (r)}$และ${\textstyle \lambda _{2}(r)}$เป็นค่าไอเกนที่ใหญ่ที่สุดอันดับแรกและอันดับสองของ${\textstyle P(r)}$ตามลำดับ

เพื่อความสะดวกในการเขียน ให้กำหนดดังนี้${\textstyle t_{k}={\frac {1}{k}}\sum _{i=0}^{k-1}\mathbf {1} _{A}(y_{i})}$,${\textstyle \epsilon =\lambda -\lambda _{2}}$,${\textstyle \epsilon _{r}=\lambda (r)-\lambda _{2}(r)}$และปล่อยให้${\displaystyle \mathbf {1} }$เป็นเวกเตอร์ที่มีค่าเป็น 1 ทั้งหมด

บทตั้งที่ 1

${\displaystyle \Pr \left[t_{k}-\pi (A)\geq \gamma \right]\leq e^{-rk(\pi (A)+\gamma )+k\log \lambda (r)}(\mathbf {q} P(r)^{k}\mathbf {1} )/\lambda (r)^{k}}$

การพิสูจน์:

โดยอสมการของมาร์คอฟ

${\displaystyle {\begin{alignedat}{2}\Pr \left[t_{k}\geq \pi (A)+\gamma \right]=\Pr[e^{rt_{k}}\geq e^{rk(\pi (A)+\gamma )}]\leq e^{-rk(\pi (A)+\gamma )}E_{\mathbf {q} }e^{rt_{k}}\end{alignedat}}}$

ที่ไหน${\displaystyle E_{\mathbf {q} }}$คือความคาดหวังของ${\displaystyle x_{0}}$เลือกตามการกระจายความน่าจะเป็น${\displaystyle \mathbf {q} }$เนื่องจากสามารถตีความได้โดยการรวมผลลัพธ์จากวิถีการเคลื่อนที่ที่เป็นไปได้ทั้งหมด${\displaystyle x_{0},x_{1},...,x_{k}}$, เพราะฉะนั้น:

${\displaystyle E_{\mathbf {q} }e^{rt}=\sum _{x_{1},x_{2},...,x_{k}}e^{rt}\mathbb {q} (x_{0})\Pi _{i=1}^{k}p_{x_{i-1}x_{i}}=\mathbf {q} P(r)^{k}\mathbf {1} }$

การนำผลลัพธ์ทั้งสองมารวมกันเป็นการพิสูจน์บทพิสูจน์ย่อย

บทตั้งที่ 2

สำหรับ${\displaystyle 0\leq r\leq 1}$,

${\displaystyle (\mathbf {q} P(r)^{k}\mathbf {1} )/\lambda (r)^{k}\leq (1+r)N_{\pi ,\mathbf {q} }}$

การพิสูจน์:

ในฐานะค่าลักษณะเฉพาะของ${\displaystyle P(r)}$และ${\displaystyle S(r)}$เท่าเทียมกัน

${\displaystyle {\begin{aligned}(\mathbf {q} P(r)^{k}\mathbf {1} )/\lambda (r)^{k}&=(\mathbf {q} P{\sqrt {DE_{r}^{-1}}}S(r)^{k}{\sqrt {D^{-1}E_{r}}}\mathbf {1} )/\lambda (r)^{k}\\&\leq e^{r/2}||{\frac {\mathbf {q} }{\sqrt {\pi }}}||_{2}||S(r)^{k}||_{2}||{\sqrt {\pi }}||_{2}/\lambda (r)^{k}\\&\leq e^{r/2}N_{\pi ,\mathbf {q} }\\&\leq (1+r)N_{\pi ,\mathbf {q} }\qquad \square \end{aligned}}}$

บทตั้งที่ 3

ถ้า${\displaystyle r}$เป็นจำนวนจริงซึ่ง${\displaystyle 0\leq e^{r}-1\leq \epsilon /4}$,

${\displaystyle \log \lambda (r)\leq r\pi (A)+5r^{2}/\epsilon }$

สรุปหลักฐาน:

เราเทย์เลอร์ขยายธุรกิจ${\textstyle \log \lambda (y)}$เกี่ยวกับประเด็น${\textstyle r=z}$เพื่อให้ได้มา:

${\displaystyle \log \lambda (r)=\log \lambda (z)+m_{z}(r-z)+(r-z)^{2}\int _{0}^{1}(1-t)V_{z+(r-z)t}dt}$

ที่ไหน${\displaystyle m_{x}{\text{ and }}V_{x}}$คืออนุพันธ์อันดับที่หนึ่งและอันดับที่สองของ${\displaystyle \log \lambda (r)}$ที่${\displaystyle r=x}$เราแสดงให้เห็นว่า${\displaystyle m_{0}=\lim _{k\to \infty }t_{k}=\pi (A).}$จากนั้นเราจะพิสูจน์ว่า (i)${\textstyle \epsilon _{r}\geq 3\epsilon /4}$โดยการจัดการเมทริกซ์ แล้วพิสูจน์ (ii)${\displaystyle V_{r}\leq 10/\epsilon }$โดยใช้ (i) และการประมาณค่าของ Cauchyจากการวิเคราะห์เชิงซ้อน

ผลลัพธ์ทั้งหมดแสดงให้เห็นว่า

${\displaystyle {\begin{aligned}\log \lambda (r)=\log \lambda (0)+m_{0}r+r^{2}\int _{0}^{1}(1-t)V_{rt}dt\leq r\pi (A)+5r^{2}/\epsilon \end{aligned}}}$

สามารถดูการพิสูจน์แบบบรรทัดต่อบรรทัดได้ใน Gilman (1998)

การพิสูจน์ทฤษฎีบท

เมื่อรวมบทพิสูจน์ย่อยที่ 2 และบทพิสูจน์ย่อยที่ 3 เข้าด้วยกัน เราจะได้ว่า

${\displaystyle \Pr[t_{k}-\pi (A)\geq \gamma ]\leq (1+r)N_{\pi ,\mathbf {q} }e^{-k(r\gamma -5r^{2}/\epsilon )}}$

การตีความเลขชี้กำลังทางด้านขวามือของอสมการว่าเป็นกำลังสองใน${\displaystyle r}$และเมื่อลดรูปนิพจน์ เราจะเห็นว่า

${\displaystyle \Pr[t_{k}-\pi (A)\geq \gamma ]\leq (1+\gamma \epsilon /10)N_{\pi ,\mathbf {q} }e^{-k\gamma ^{2}\epsilon /20}}$

ขอบเขตที่คล้ายกัน

${\displaystyle \Pr[t_{k}-\pi (A)\leq -\gamma ]\leq (1+\gamma \epsilon /10)N_{\pi ,\mathbf {q} }e^{-k\gamma ^{2}\epsilon /20}}$

ถือไว้ ดังนั้นจึงตั้งค่า${\displaystyle C=2(1+\gamma \epsilon /10)N_{\pi ,\mathbf {q} }}$ให้ผลลัพธ์ที่ต้องการ

ทฤษฎีบทนี้มีประโยชน์ในการลดความสุ่มในการศึกษาการลดความสุ่ม [ ^{2 ] แสดงให้เห็นว่าการเดินสุ่มแบบขยายเป็นตัวสร้างสุ่มเทียมที่ดีเมื่อเทียบ กับ}ฟังก์ชันทดสอบหลายประเภท การสุ่มตัวอย่างจากการเดินแบบขยายเป็นตัวอย่างของตัวสุ่ม ที่มีประสิทธิภาพด้านความสุ่ม โปรดทราบว่าจำนวนบิตที่ใช้ในการสุ่มตัวอย่าง${\displaystyle k}$ตัวอย่างอิสระจาก${\displaystyle f}$เป็น${\displaystyle k\log n}$ในขณะที่หากเราสุ่มตัวอย่างจากตระกูลอนันต์ของตัวขยายที่มีดีกรีคงที่ ค่าใช้จ่ายจะเพียงเท่านั้น${\displaystyle \log n+O(k)}$ตระกูลดังกล่าวมีอยู่จริงและสามารถสร้างได้อย่างมีประสิทธิภาพ เช่นกราฟรามานุจันของลูบอตสกี -ฟิลลิปส์- ซาร์นัค