發送到隨機預言機的查詢的答案的獨立性
假設我們有一個算法詢問隨機預言機 $ \mathcal{O} $ $ Q $ 查詢 $ u_1, \ldots, u_Q $ . 所有查詢都是唯一的， $ u_i \neq u_j $ 為了 $ i \neq j $ . 查詢 $ u_i $ 也是隨機變數。
看到隨機變數的最簡單（數學上正確）的方法是什麼 $ (\mathcal{O}(u_1),\ldots,\mathcal{O}(u_Q)) $ 具有均勻分佈 - 或 - $ \mathcal{O}(u_i) $ 是獨立的隨機變數嗎？
似乎教科書中涵蓋的標准定理（例如Stinson 中的這一定理）無法直接應用。
編輯：
這是我的問題的更正式和簡化的版本： $ A $ 是所有隨機磁帶（或私鑰或其他東西）的集合， $ B $ is 是所有函式的集合，比如說， $ \mathbb{Z}_q $ 至 $ \mathbb{Z}_q $ . $ \mathcal{A} $ 是一些有參數的算法 $ \omega \in A $ 和隨機預言機 $ \mathcal{O} $ 從 $ B $ . 我們從中挑選元素 $ A $ 和 $ B $ 具有均勻分佈。
例如，假設我想計算機率 $ P((\omega, \mathcal{O}) \in A\times B| \mathcal{A}(\omega, \mathcal{O}) \text{ succeeds}) $
這可以重寫為
$ P((\omega, \mathcal{O}) \in A\times B| \mathcal{A}(\omega, \mathcal{O}(u_1), \ldots, \mathcal{O}(u_Q)) \text{ succeeds}) $
然後我有一個斯廷森定理，可以用其他一些“教科書”或可引用的定理代替。
主要目標是證明 $ (\omega, \mathcal{O}(u_1), \ldots, \mathcal{O}(u_Q)) $ 通過引用某事具有均勻分佈。
首先，請注意說查詢 $ u_1,\ldots,u_Q $ are distinct 意味著它們不是獨立的，例如，如果 $ u_i=a $ 然後 $ u_j\neq a $ 對所有人 $ j>i $ .
其次，您的論點確實來自斯廷森書中對隨機預言機的定義。讓 $ \mathcal{O}:\mathcal{X}\rightarrow \mathcal{Y} $ 成為一個隨機的神諭。這意味著對於每個查詢 $ u $ 之前沒有被質疑過，它認為 $ Pr[\mathcal{O}(u)=y]=1/|\mathcal{Y}| $ 對於每個 $ y\in \mathcal{Y} $ . 現在，自從 $ u_1,\ldots,u_Q $ 都是不同的，因此
對所有人 $ y\in\mathcal{Y} $ 和 $ i\in[Q]: Pr[\mathcal{O}(u_i)=y]=\frac{1}{|\mathcal{Y}|} $
$ \Rightarrow $ 對所有人 $ (y_1,\ldots,y_Q)\in\mathcal{Y^Q} $ : $ Pr[\mathcal{O}(u_1)=y_1,\ldots, \mathcal{O}(u_Q)=y_Q]= \prod_{i=1}^Q Pr[\mathcal{O}(u_i)=y_i]=\frac{1}{|\mathcal{Y}|^Q} $